資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢有多少個兵卒可以到達第一行
假設我們有兩個大小為n的二進位制字串S和T。考慮一個n乘n的棋盤。
目前，第n行有一些兵卒。第一行也有一些敵方兵卒。一步之內，我們可以移動一個自己的兵卒。如果目標方格中沒有兵卒，則兵卒可以向上移動一格（從(i,j)到(i−1,j)）。當且僅當目標方格中有敵方兵卒時，兵卒可以向上移動一格對角線（從(i,j)到(i−1,j−1)或(i−1,j+1)）。該敵方兵卒也被移除。我們必須找到可以到達第1行的自己兵卒的最大數量？只有我們可以移動兵卒，敵方兵卒永遠不會移動。此外，當自己的兵卒到達第1行時，它將卡住並且無法再移動。S和T分別表示敵方兵卒序列和自己的兵卒序列。如果S[i]或T[i]為1，則存在兵卒，如果為0，則該單元格為空。
問題類別
上述問題可以透過應用貪心問題解決技術來解決。貪心演算法技術是一種演算法，其中選擇當前最佳解決方案而不是遍歷所有可能的解決方案。貪心演算法技術也用於解決最佳化問題，例如其更大的兄弟動態規劃。在動態規劃中，有必要遍歷所有可能的子問題以找出最優解，但它有一個缺點；它需要更多的時間和空間。因此，在各種情況下，使用貪心技術來找出問題的最優解。雖然它並非在所有情況下都能提供最優解，但如果設計得當，它可以比動態規劃問題更快地產生解。貪心技術為最佳化問題提供區域性最優解。此技術的示例包括克魯斯卡爾和普里姆的最小生成樹 (MST) 演算法、霍夫曼樹編碼、迪傑斯特拉的單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入類似於 S = "000"；T = "111"，則輸出將為 3，因為我們可以簡單地將所有 3 個兵卒向前推進。因此，答案是 3。
步驟
為了解決這個問題，我們將遵循以下步驟 -
ans := 0 n := size of S for initialize i := 0, when i < n, update (increase i by 1), do: if T[i] is same as '1', then: if S[i] is same as '0', then: (increase ans by 1) otherwise when S[i - 1] is same as '1', then: S[i - 1] = '0', increase ans by 1 otherwise when S[i + 1] is same as '1', then: S[i + 1] = '0', increase ans by 1 return ans
示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(string S, string T){
int ans = 0;
int n = S.size();
for (int i = 0; i < n; i++){
if (T[i] == '1'){
if (S[i] == '0')
ans++;
else if (S[i - 1] == '1')
S[i - 1] = '0', ans++;
else if (S[i + 1] == '1')
S[i + 1] = '0', ans++;
}
}
return ans;
}
int main(){
string S = "000";
string T = "111";
cout << solve(S, T) << endl;
}輸入
"000", "111"
輸出
3
216 次瀏覽
