今日刷題匯總 - day007

1、字符串中找出連續最長的數字串

1.1、題目

1.2、思路

讀完題知道，需要求一段字符串中最長且是連續的數字字符串。既然涉及到找最長，意味著具有比較關系，所以立馬想到利用一個變量字符串temp進行統計各個連續的數字字符串的長度，最后留取最長retstr的返回即可。另外，還可以利用雙指針，標記每一次出現數字字符的起始位置，然后紀錄其連續的長度，然后返回最長處的其實位置的字串也行。那么。接下來兩個思路都寫一寫吧。

1.3、程序實現 – 比較

首先，我們根據思路和題目定義三個字符串，一個str作為原字符串輸入，一個retstr最后最后的返回字符串，一個temp作為比較retstr更新字符串，接著，開始遍歷str的各個字符，當遇見數字字符，則尾插進temp中，否則，遇見其它字符則比較retstr和temp的長度，如果temp的長度大于retstr時，則保留最長的數字字符串到retstr，否則清空短的字符串temp繼續遇見遍歷到下一個數字字符再次依次尾插連續數字字符統計長度，依次類推，得到最后的最長數字連續字符串retstr輸出即可。

#include <iostream>
#include <string>
using namespace std;bool isNum(char c)
{return c <= '9' && c >= '0';
}int main() {string str;string retstr;string temp;cin >> str;size_t len = str.size();for (int i = 0; i <= len; i++){if (isNum(str[i])){temp += str[i];} else{if (retstr.size() < temp.size())retstr = temp;elsetemp.clear();}}cout << retstr << endl;return 0;
}

1.4、程序實現 – 雙指針

接下來，雙指針需要利用begin標記遍歷出現數字字符的位置，且定義一個j從begin處開始遍歷連續數字字符串的長度，遇見非數字字符停止，求得 j - i 的長度保存到maxlen中，然后，將 i 置到 j 處繼續遍歷，且每一次標記begin和maxlen保持更新為最長的數字字符串的起始地址和長度即可。最后利用substr輸出指定位置的字串即可。

#include <iostream>
#include <string>
using namespace std;bool isNum(char ch)
{return ('0' <= ch && ch <= '9');
}int main()
{string str;cin >> str;int begin = -1;int maxlen = -1;for(int i = 0;i< str.size();i++){if(isNum(str[i])){int j = i;while(j < str.size() && isNum(str[j]))j++;if(j -i > maxlen){begin = i;maxlen = j-i;}i = j;}     }cout << str.substr(begin, maxlen) << endl;return 0;
}

2、島嶼數量

2.1、題目

2.2、思路

讀完題知道，又是屬于在一個二維數組里進行搜索/擴散/累計啊等問題。那么立馬就想到了深度優先搜索dfs和廣度優先搜索bfs，然后讓我們實現統計，屬于聯通的島嶼(即具有上下左右連通的‘1’)的個數。那么這里就采用dfs解決即可。比之前的腐爛的蘋果和單詞搜索更簡單一些，因為只需要計數即可。接下來，就是程序實現。

2.3、程序實現 - dfs

首先，既然采用dfs把固定的套路和模板先寫上即可。定義m,n計算二維數組的大小，方便稍后遍歷，再定義兩個方向數組dx和dy，接著定義bool類型的vis數組，表示是否已連通。模板寫好，接著就是遍歷二維數組判斷是否是島嶼，是則計數count且dfs搜索上下左右是否連通。連通就規劃為一塊島嶼，否則就繼續遍歷，直到規劃出所有連通的島嶼，規劃出多少那么coun就恰好統計出結果，最后返回count即可。

class Solution {
public:int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[201][201] = { false };int solve(vector<vector<char> >& grid){m = grid.size();n = grid[0].size();int count = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == '1' && !vis[i][j]){count++;dfs(grid,i,j);}}}return count;}
};

那么，繼續完善dfs函數，其實方法都類似，先進入dfs后標記當前屬于島嶼，再此島嶼基礎上，就是在4個方向上判斷是否是島嶼‘1’且沒有越界且沒有被標記已連通，是則與當前島嶼執行遞歸標記連通，否則周圍就沒有需要連通的島嶼了。

class Solution {
public:int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[201][201] = { false };int solve(vector<vector<char> >& grid){m = grid.size();n = grid[0].size();int count = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == '1' && !vis[i][j]){count++;dfs(grid,i,j);}}}return count;}void dfs(vector<vector<char> >& grid, int i,int j){vis[i][j] = true;for(int k = 0;k < 4;k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])dfs(grid,x,y);}}
};

3、拼三角

3.1、題目

3.2、思路

讀完題，理解到讓我們實現在6根木棍中，任選3根木棍來拼接三角形，其次，還得判斷在剩下的3根木棍中是否還能拼接成三角形。如果同時能，則輸出“Yes”，否則輸出"No"即可。由于，只有6根數量級不大，直接嘗試一波蠻力法試試，蠻力法思路就是遍歷每3根都去判斷一下，能夠組成三角形，能則繼續判斷剩下3根是否也能組成三角形，能則輸出“Yes”，如果不能組成三角形那么輸出“No”即可。另外，在寫蠻力法時發現，會有很多的冗余操作和判斷，會發現具有一些特定，即具備判斷的單調性(稍后畫圖理解)，所以利用這個特點且只針對這道題，就有了更優解法。其次，看其它大佬也有用dfs的，但是我沒想出來，而且這里用起來很麻煩且邊界不好控制，就不寫dfs了。
那么接下來，就是程序實現。

3.3、程序實現 – 蠻力法

首先，根據蠻力法的思路，具體分為以下幾個步驟：
(1)、首先，先對木棍長度進行排序，目的是簡化，便于邏輯思考下標處理等；
(2)、套三層for循環，遍歷判斷check三角形的性質是否滿足(任意兩邊之和大于第三邊)；
(3)、再(2)滿足條件下，繼續判斷剩下check the other three的三根木棍是否滿足三角形性質；
那么，先根據題目要求和思路寫好基本框架，再把數組sort排序，再為了增加代碼閱讀性，我這里采用封裝了CheckTriangles函數單獨處理是否滿足三角形邏輯。

#include <iostream>
#include <algorithm>
using namespace std;bool CheckTriangles(int* arr)
{
}int main()
{int n;cin >> n;while (n--){int arr[6];for (int i = 0; i < 6; i++)cin >> arr[i];sort(arr, arr + 6);//步驟1：排序if (CheckTriangles(arr))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

接著，實現蠻力法遍歷邏輯，先根據三邊需要求和比較的的關系，寫三層for循環，其次，額外封裝了一個isTriangle函數，判斷是否滿足三角形性質，注意哈，這里需要任意兩邊之和大于第三邊為真才滿足哈。

#include <iostream>
#include <algorithm>
using namespace std;bool isTriangle(int a, int b, int c)
{return (a + b > c && a + c > b && b + c > a);
}bool CheckTriangles(int* arr)
{//步驟2：for循環嵌套for (int i = 0; i < 3; i++){for (int j = i + 1; j < 4; j++){for (int k = j + 1; k < 5; k++){//步驟3： Check -- isTriangleif (isTriangle(arr[i], arr[j], arr[k])){//步驟4： Check the other three -- isTriangle}}}}return false;
}int main()
{int n;cin >> n;while (n--){int arr[6];for (int i = 0; i < 6; i++)cin >> arr[i];sort(arr, arr + 6);//步驟1：排序if (CheckTriangles(arr))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

最后一步就是檢查，若步驟3滿足，則剩下的三根木棍是否仍然滿足三角形性質。所以，這里定義Residue[3]表示存放剩余木棍的數組，定義index表示它的下標，方便操作，然后遍歷原數組，把剩下的數組元素，存放進Residue數組，這樣就可以方便把Residue數組每一根木棍一起放進isTriangle進行拼接驗證是否滿足三角形性質，若滿足，則返回ture，否則繼續回到步驟2，繼續遍歷結束為止，直到最后都沒有滿足，則返回false，則main輸出“No”，否則輸出"Yes"即可。

#include <iostream>
#include <algorithm>
using namespace std;bool isTriangle(int a, int b, int c)
{return (a + b > c && a + c > b && b + c > a);
}bool CheckTriangles(int* arr)
{//步驟2：for循環嵌套for (int i = 0; i < 3; i++){for (int j = i + 1; j < 4; j++){for (int k = j + 1; k < 5; k++){//步驟3： Check -- isTriangleif (isTriangle(arr[i], arr[j], arr[k])){//步驟4： Check the other three -- isTriangleint Residue[3];int idx = 0;for (int m = 0; m < 6; m++){if (m != i && m != j && m != k){Residue[idx++] = arr[m];}}if (isTriangle(Residue[0], Residue[1], Residue[2])){return true;}}}}}return false;
}int main()
{int n;cin >> n;while (n--){int arr[6];for (int i = 0; i < 6; i++)cin >> arr[i];sort(arr, arr + 6);//步驟1：排序if (CheckTriangles(arr))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

3.4、程序實現 – 巧解(單調性)

解法二，基于解法一的情況下，發現此題具有單調性的特點，所以利用這一特點，能夠更快的方便判斷求解。為了更好的理解，畫個圖演示：

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int n;cin >> n;while(n--){int arr[6];for(int i = 0;i < 6;i++)cin >> arr[i];sort(arr,arr+6);if(arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5] ||arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5] ||arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5] ||arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3]){cout << "Yes" << endl;}elsecout << "No" << endl;}return 0;
}

4、題目鏈接

字符串中找出連續最長的數字串
島嶼數量
拼三角