今日刷題匯總 - day005

1、游游的you

1.1、題目

1.2、思路

讀完題知道，屬于是貪心加模擬類的題型，那么肯定要滿足you次數最多，再拼接oo滿足最大分數的思想。其次，蠻力法我也寫了，不過超出題目限制的空間范圍了，思路就是按照題目模擬即可直接貼出來就不多說了。接下來，結合預處理方式，實現貪心的思路，既然我們需要you最大化，那么貪心的思想就是求you的最大次數，觀察示例可知，you的次數是同時消耗a,b,c的次數，所以you的最大次數等于a,b,c中的最小值，其次，值得注意的是oo是1分,而ooo是2分,oooo是3分，可以推出oo的最大分數為b-1次數。然后，我們會先拼接you，會同時消耗b，那么oo最大分數就變成了b減去拼接you用掉o的次數，再-1即可。所以，最后的最大分數就等于you + oo的分數。接下來，具體看程序實現。

1.3、程序實現 - 蠻力法

就是模擬實現，過程略。

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <stack>
using namespace std;int main() {stack<int> y;stack<int> o;stack<int> u;int q = 0;int a = 0;int b = 0;int c = 0;cin >> q;while (q--) {cin >> a >> b >> c;while (a) {y.push(a--);}while (b) {o.push(b--);}while (c) {u.push(c--);}int you = 0;while (!y.empty() && !o.empty() && !u.empty()) {y.pop();o.pop();u.pop();you += 2;}while (!y.empty()) {y.pop();}int oo = 0;int m = 0;int flag = 0;while (!o.empty()) {flag = 1;o.pop();m++;}if (flag) oo = m - 1;else oo = m;while (!u.empty()) {u.pop();}cout << (you + oo) << endl;}return 0;
}

1.4、程序實現 - 貪心(優化)

首先，按照題目要求，編寫輸入q表示訪問次數，也就是a,b,c的輸入次數，那么采用預處理方法，輸入一次處理一次。

#include <iostream>
using namespace std;int main()
{int q = 0;cin >> q;int a,b,c;while(q--){}return 0;
}

接著，處理a,b,c和you與oo的次數與分數的關系。定義變量you統計當前預處理的a,b,c中you的分數，通過上述思路分析思考得知，you的最大分數就等于a,b,c的最小次數乘以2(2表示的是它的分之)，即：you最大分數 = 次數 X 分值即可。同理，思路中分析得知，oo具有b-1的性質，且you會消耗o的次數即b的次數，即：oo的最大分數，定義變量ooo = b - 1 - (you/2)即可。最后，輸出每一次預處理的結果you + ooo即可。

#include <iostream>
using namespace std;int main()
{int q = 0;cin >> q;int a,b,c;while(q--){cin >> a >> b >> c;int you = min(a,min(b,c)) * 2;int ooo = max(b-(you/2)-1,0);cout << (you + ooo) << endl;}return 0;
}

2、腐爛的蘋果

2.1、題目

2.2、思路

讀完題，第一反應就是之前寫過的dfs算法思路，再次理解題目要求，0，1，2分別表示空格、好蘋果、壞蘋果且是隨機的(多個2，多個0，多個1)，然后一樣四個方向每分鐘(理解為一次操作)進行傳播(可以理解為搜索)，然后求多少次傳播操作后沒有好蘋果，或遍歷完后傳播不到的好蘋果的情況返回-1即可。然后，再根據示例分析，這里適用dfs是不適用的，屬于是一圈一圈的傳播，而不是一個一個的，那么這里需要用到多源bfs思路。也就是需要滿足同時一次操作對于多個壞蘋果2進行它周圍傳播的情況，那么我們可以把同一次操作中所有的2壞蘋果放進一個隊列里，就可以實現每一次出隊列就可同時操作多個2壞蘋果，其次，每一次操作就是一次傳播所以用一個變量count記錄壞蘋果傳播的次數，但是注意的是外層傳播時注意邊界控制。然后，傳播到空格0，不管，傳播到1好蘋果則，將1置為2或者標記為已傳播(我這里才用標記)，然后繼續把這個被傳播的好蘋果標記后，進入壞蘋果隊列，繼續排序傳播即可。遍歷傳播結束后，最后再遍歷二維數組判斷是否還有1好蘋果，則返回-1即可，否則輸出count傳播次數。
由于不好理解，我簡單畫個圖，便于理解：


接下來，就是程序實現。

2.3、程序實現 - bfs

首先，按照采用bfs思路的需求，編寫需要的方向數組dx和dy，定義m,n計算二維數組的大小方便執行遍歷(訪問)操作，其次，這里采用布爾類型數組vis標記法表示是否已傳播，然后定義壞蘋果隊列badapple，這里pair<int,int>因為需要的下標所以是用pair存放壞蘋果的行和列即可。然后，遍歷二維數組將壞蘋果進隊列。

class Solution
{int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[1001][1001] = {false};queue<pair<int,int>> badapple;public:int rotApple(vector<vector<int> >& grid){n = grid.size();m = grid[0].size();for(int i = 0;i < n;i++){for(int j = 0;j<m;j++){if(grid[i][j] == 2)badapple.push({i,j});}}
};

接著，創建count計數傳播次數，因為是相鄰之間的傳播所以可以利用傳播次數就是輸出結果。
然后，只要隊列中有壞蘋果則執行傳播，即出一層壞蘋果且用sz保存當前這一層有幾個壞蘋果，以便依次執行上下左右的傳播操作，即有多少個壞蘋果就執行多少次傳播，實現模擬同時一層壞蘋果的傳播。然后if(x >=0 && x < n && y >=0 && y < m && grid[x][y] == 1 && !vis[x][y])，進行邊界控制防止出界且為好蘋果且未被標記，則將它標記為已傳播，再將它進隊列，成為理解的下一層將要傳播得壞蘋果之一，等待sz次后，完成所有得第二層壞蘋果，依次類推，直到傳播結束。

class Solution
{int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[1001][1001] = {false};queue<pair<int,int>> badapple;public:int rotApple(vector<vector<int> >& grid){n = grid.size();m = grid[0].size();for(int i = 0;i < n;i++){for(int j = 0;j<m;j++){if(grid[i][j] == 2)badapple.push({i,j});}}int count = 0;while(badapple.size()){count++;int sz = badapple.size();while(sz--){auto [a,b] = badapple.front();badapple.pop();for(int k = 0; k < 4;k++){int x = a + dx[k];int y = b + dy[k];if(x >=0 && x < n && y >=0 && y < m && grid[x][y] == 1 && !vis[x][y]){vis[x][y] = true;badapple.push({x,y});}                  }}}}
};

傳播結束有兩種情況，要么當前層的所有壞蘋果的下一次傳播單元(數組下標)都是空格0，要么就是全部壞蘋果被傳播完畢(遍歷完)。最后，只需要再次遍歷這個二維數組判斷是都還有未被感染的好蘋果且為被標記，有則返回-1，否則就是輸出count-1即可。

class Solution
{int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[1001][1001] = {false};queue<pair<int,int>> badapple;public:int rotApple(vector<vector<int> >& grid){n = grid.size();m = grid[0].size();for(int i = 0;i < n;i++){for(int j = 0;j<m;j++){if(grid[i][j] == 2)badapple.push({i,j});}}int count = 0;while(badapple.size()){count++;int sz = badapple.size();while(sz--){auto [a,b] = badapple.front();badapple.pop();for(int k = 0; k < 4;k++){int x = a + dx[k];int y = b + dy[k];if(x >=0 && x < n && y >=0 && y < m && grid[x][y] == 1 && !vis[x][y]){vis[x][y] = true;badapple.push({x,y});}                  }}}for(int i = 0;i < n;i++){for(int j = 0;j<m;j++){if(grid[i][j] == 1 && !vis[i][j])return -1;}}return count - 1;}
};

3、孩子們的游戲(圓圈中最后剩下的數)

3.1、題目

3.2、思路

讀完題，立馬知道了屬于是之前寫過的楊輝三角問題同樣經典的約瑟夫環問題了。題目意思跟大家熟悉的數字炸彈游戲類似的規則，首先需要一個隨機數m，然后這里是按照從0開始報數，讓其后報數為m-3的小朋友退出，直到剩下最后一個小朋友即可。那么，對于約瑟夫問題可以采用蠻力法模擬實現，我這里就是使用環形鏈表來實現，其次還可以通過像利用楊輝三角的性質(狀態方程)一樣，結合約瑟夫環的規律遞推(動態規劃)求解。首先，鏈表方法，由于題目中已知小朋友的編號是有序的0~n-1，所以直接先讓其進鏈表即可，然后判斷m-1位置時，讓其該位置釋放掉即可，直到剩下最后一個小朋友的編號輸出即可。值得注意的是需要處理一些細節等，如需要讓被釋放的位置的下一個位置作為計數的開始，所以需要一個it變量記錄，變化的計數位置(可以巧妙的利用迭代器)。
然后，對于遞推(動態規劃法)，跟之前寫過的最小花費爬樓梯套路是一樣的需要確定動態規劃的狀態表示以及狀態轉移方程。那么就來推理dp[i]和dp[n]，為了方便理解畫個圖理解：

3.3、程序實現 – 環形鏈表

首先，我們建立鏈表，將編號插入鏈表。

class Solution {public:int LastRemaining_Solution(int n, int m){list<int> lt;for (int i = 0; i < n; i++){lt.push_back(i);}}
};

然后，我們利用迭代器變量it，記錄按照規則走的位置，走到m-1位置處，直接用it.erase刪除釋放即可，值得注意的是，當調用 lt.erase(it) 刪除元素后，返回的迭代器是指向被刪除元素之后的那個元素的迭代器。因此，在刪除元素后，不需要再手動將 it 設置為 lt.begin()，因為 it 已經自動更新為指向下一個元素的迭代器（如果存在的話）。所以，在刪除元素后直接進行下一次循環即可。
另外，如果實現的循環呢？判斷it遍歷到end處就使它置begin位置即可。所以鏈表模擬相對于數組模擬，迭代器相對更好用。依次類推，遇見m-1就刪除，直到鏈表中剩下一個編號，返回即可。

class Solution {public:int LastRemaining_Solution(int n, int m){list<int> lt;for (int i = 0; i < n; i++){lt.push_back(i);}auto it = lt.begin();while (lt.size() > 1){for (int count = 1; count < m; ++count){++it;if (it == lt.end()){it = lt.begin();}}it = lt.erase(it);if (it == lt.end())it = lt.begin();}return *it;}
};

3.4、程序實現 – 約瑟夫環(動態規劃法)

接著，動態規劃重要的在于分析和理解，狀態表示以及狀態轉移方程，程序就相對簡單了。


接著按照推導的方程寫好程序即可。只需要說一下為什么這里%上的 i，其實就是推導出的dp[n] = (dp[n-1] + m)%n;只是把n換成每一次循環求的 i 而已，表示求每一步的映射關系。

class Solution {
public:int dp[5001];int LastRemaining_Solution(int n, int m){dp[1] = 0;for(int i = 2;i <= n;i++)dp[i] = (dp[i-1] + m) % i;return dp[n];}
};

還可以進一步空間優化，直接控制變量即可。總結模擬就是老實的遍歷刪除，動態規劃就是找規律，推導方程求解。

class Solution {
public:int LastRemaining_Solution(int n, int m){int f = 0;for(int i = 2;i <= n;i++)f = (f + m) % i;return f;}
};

4、題目鏈接

游游的you
腐爛的蘋果
孩子們的游戲(圓圈中最后剩下的數)