資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中拼寫單詞的貼紙
假設我們有N種不同的貼紙。每種貼紙上都印有一個小寫英文字母的單詞。我們希望透過從我們的貼紙集合中剪下單個字母並重新排列它們來拼出給定的目標字串。如果需要，我們可以多次使用每張貼紙，並且我們擁有每張貼紙無限的數量。
我們必須找到拼出目標所需的最小貼紙數量？如果任務不可能，則返回 -1。
因此，如果輸入類似於 [“dog”, “sentence”, ”antenna”]，而目標是“dance”，則答案將是 3
為了解決這個問題，我們將遵循以下步驟 -
- n := 目標的大小
- N := 將n左移1位
- 定義一個大小為N的陣列dp，並將其初始化為inf
- dp[0] := 0
- 用於初始化 i := 0，當 i <N 時，更新（i 增加 1），執行 -
- 如果 dp[i] 與 inf 相同，則 -
- 忽略以下部分，跳到下一次迭代
- 用於初始化 j := 0，當 j <貼紙的大小，更新（j 增加 1），執行 -
- s := stickers[j]
- x := i
- 用於初始化 k := 0，當 k <s 的大小，更新（k 增加 1），執行 -
- z := s[k]
- 用於初始化 l := 0，當 l <目標的大小，更新（l 增加 1），執行 -
- 如果 target[l] 與 z 相同，並且（將 x 右移 l 位）AND 1）與 0 相同，則 -
- x := x OR（將 1 左移 l 位）
- 退出迴圈
- 如果 target[l] 與 z 相同，並且（將 x 右移 l 位）AND 1）與 0 相同，則 -
- dp[x] := dp[x] 和 dp[i] + 1 的最小值
- 如果 dp[i] 與 inf 相同，則 -
- 返回 dp[N - 1] 為 inf 則設定為 - 1，否則設定為 dp[N - 1]
讓我們檢視以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
int n = target.size();
int N = 1 << n;
vector <int> dp(N, INT_MAX);
dp[0] = 0;
for(int i = 0; i < N; i++){
if(dp[i] == INT_MAX) continue;
for(int j = 0; j < stickers.size(); j++){
string s = stickers[j];
int x = i;
for(int k = 0; k < s.size(); k++){
char z = s[k];
for(int l = 0; l < target.size(); l++){
if(target[l] == z && ((x >> l) & 1) == 0){
x |= (1 << l);
break;
}
}
}
dp[x] = min(dp[x], dp[i] + 1);
}
}
return dp[N - 1] == INT_MAX? -1 : dp[N - 1];
}
};
main(){
Solution ob;
vector<string> v = {"dog", "sentence","antenna"};
cout << (ob.minStickers(v, "dance"));
}輸入
["dog", "sentence","antenna"] "dance"
輸出
3
更新於: 2020年6月2日
335 次檢視
廣告