学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
循环渐进Forward-CSDN博客
目录
循环渐进Forward-CSDN博客
字符串中找出连续最长的数字串
思路：
岛屿数量
思路：
深度优先遍历DFS
广度优先遍历 BFS
并查集
拼三角
思路：
字符串中找出连续最长的数字串
牛客网做题链接：字符串中找出连续最长的数字串_牛客题霸_牛客网 (nowcoder.com)
思路：
模拟+双指针。
当j指针和i指针之间长度len大于之前的值时更新len
#include <iostream>
using namespace std;
#include<string>
int main() {
string str;
cin>>str;
int begin=-1,len=0;
for(int i=0;i<str.size();i++)
{
int j=i;
while(j<str.size() && str[j]>='0' && str[j]<='9')j++;
if(j-i>len)
{
begin=i;
len=j-i;
}
i=j;
}
cout<<str.substr(begin,len)<<endl;
}岛屿数量
leetcode网做题链接：200. 岛屿数量 - 力扣（LeetCode）
思路：
深度优先遍历DFS
目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。
dfs方法： 设目前指针指向一个岛屿中的某一点 (i, j)，寻找包括此点的岛屿边界。
- 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
- 终止条件：
- (i, j) 越过矩阵边界;
- grid[i][j] == 0，代表此分支已越过岛屿边界。
- 搜索岛屿的同时，执行 grid[i][j] = ‘0’，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。
- 主循环：
- 遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。
- 复杂度：所有的数遍历一遍，所以复杂度是O(N*M)
class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j)
{
// 当前部分走过了，因此把当前部分置为0
grid[i][j] = '0';
// 依次看看上下左右是不是还有同属岛屿的其他部分
// 若有，则依次遍历并置为0
if (i > 0 && grid[i-1][j] == '1')
dfs(grid, i-1, j);
if (i < grid.size()-1 && grid[i+1][j] == '1')
dfs(grid, i+1, j);
if (j > 0 && grid[i][j-1] == '1')
dfs(grid, i, j-1);
if (j < grid[0].size()-1 && grid[i][j+1] == '1')
dfs(grid, i, j+1);
}
int numIslands(vector<vector<char>>& grid) {
// 分别记录行、列以及岛屿总数
int row = grid.size();
int col = grid[0].size();
int cnt = 0;
// 从第一行第一列开始，寻找有没有是'1'的位置，若有，则登岛遍历，岛屿数加1
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
if (grid[i][j] == '1')
{
dfs(grid, i, j);
++cnt;
}
}
}
// 返回岛屿的总数
return cnt;
}
};广度优先遍历 BFS
- 主循环和思路一类似，不同点是在于搜索某岛屿边界的方法不同。
- bfs 方法：
- 借助一个队列queue，判断队列首部节点(i, j)是否未越界而且为1
- 如果是则置（删除此岛屿），并将此节点上下左右节点(i+1,j),(i-1,j),(i,j+1),(i,j-1)加入队列
- 如果不是则跳过此节点
- 循环
pop队列首节点，直到整个队列为空，此时已经遍历完此岛屿
- 借助一个队列queue，判断队列首部节点(i, j)是否未越界而且为1
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int row = grid.size();
int col = grid[0].size();
int cnt = 0;
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
// 只要找到了一个为'1'的，那么登岛
if (grid[i][j] == '1')
{
// 当前找到的新岛屿，数量加1
++cnt;
// 广度优先，那么需要借助队列来实现
queue<pair<int, int>> bfs_q;
// 把当前走过的地方置0
grid[i][j] = 0;
bfs_q.push({i, j});
// 只要队不空就循环
while (!bfs_q.empty())
{
// 取出队头元素，出队
auto cur = bfs_q.front();
bfs_q.pop();
// 判断队头元素的上下左右是否有岛屿的其他部分，有的话则入队并置0
if (cur.first > 0 && grid[cur.first-1][cur.second] == '1')
{
bfs_q.push({cur.first-1, cur.second});
grid[cur.first-1][cur.second] = 0;
}
if (cur.first < row-1 && grid[cur.first+1][cur.second] == '1')
{
bfs_q.push({cur.first+1, cur.second});
grid[cur.first+1][cur.second] = 0;
}
if (cur.second > 0 && grid[cur.first][cur.second-1] == '1')
{
bfs_q.push({cur.first, cur.second-1});
grid[cur.first][cur.second-1] = 0;
}
if (cur.second < col-1 && grid[cur.first][cur.second+1] == '1')
{
bfs_q.push({cur.first, cur.second+1});
grid[cur.first][cur.second+1] = 0;
}
}
}
}
}
return cnt;
}
};并查集
是一种树型的数据结构，用于处理一些不相交的合并以及查询问题。
步骤：
- 遍历这个二维数组，将所有的1都认为是一个单独的集合
- 遍历这个二维数组，对于每一个1，只看它的左边和上边，如果发现有1，就做union操作（为甚只看左边和上边，因为右边和下边是对称的，而我们从左到右，从上到下遍历，所以不会重复和遗落）
class Solution {
public:
int find(int idx)
{
// 若当前节点的父节点就是自己，那么只需要返回自己
if (parent[idx] == idx)
return idx;
// 路径压缩，只要idx节点的父节点不是整个集合的头节点，那么就把路径上每个节点都向集合的头结点
parent[idx] = find(parent[idx]);
// 返回idx的父节点（也是整个集合的头节点）
return parent[idx];
}
void union_n (int idx_1, int idx_2)
{
int par_1 = find(idx_1);
int par_2 = find(idx_2);
// 若idx_1和idx_2的父节点是同一个，那就不做任何操作
if (par_1 == par_2)
return;
// 原本par_1和par_2分别是idx_1和idx_2的父节点，因此都指向自己
// 这个赋值将par_1的父节点指向了par_2，完成了合并操作
parent[par_1] = par_2;
// 每当一块陆地拼进了岛屿，那么陆地数量自减
--land_num;
}
int numIslands(vector<vector<char>>& grid) {
// 输入的行与列
int row = grid.size();
int col = grid[0].size();
// 初始化陆地数量以及数组
land_num = 0;
parent = vector<int> (row*col, -1);
// 构建并查集
for (int i = 0; i < row; ++i)
for (int j = 0; j < col; ++j)
{
if (grid[i][j] == '1')
++land_num;
// 初始化父亲节点都为自己
parent[i*col + j] = i*col + j;
}
// 进行并查的过程
for (int i = 0; i < row; ++i)
for (int j = 0; j <col; ++j)
{
if (grid[i][j] == '1')
{
// 从左往右逐行遍历，若下方或者右方的节点也是陆地，那么就拼在一起
if (i + 1 < row && grid[i+1][j] == '1')
union_n(i*col+j, (i+1)*col+j);
if (j + 1 < col && grid[i][j+1] == '1')
union_n(i*col+j, i*col+j+1);
}
}
// 返回剩下的陆地数量（岛屿数量）
return land_num;
}
private:
// 记录父节点以及陆地的数量
vector<int> parent;
int land_num;
};拼三角
牛客网做题链接：A-拼三角_牛客小白月赛32 (nowcoder.com)
思路：
这道题所需要的，其实就是利用贪心算法，找出这条规律：能组成三角形的三条边中，两条最短边之和一定大于第三边。注意，是最短边，如果是任意两条边，那样会加大我们的工作量的。
但贪心的点就在于，要是连两条最短边相加，都大于第三边了，那其他任意两边之和，一定也会大于第三边的。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> arr(6);
for(int i = 0; i < n; ++i)
{
cin >> arr[0] >> arr[1] >> arr[2] >> arr[3] >> arr[4] >> arr[5];
sort(arr.begin(), arr.end());
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;
}
else
{
cout << "No" << endl;
}
}
return 0;
}学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
