77 组合
题目链接:组合
思路
做此题目之前建议大家先看一下回溯算法的理论基础,然后体会一下回溯三部曲以及回溯模板。在我理解看来for
循环就是选择不同的入口进行递归,总而言之还是一道递归题目。
自己实现了一个粗粒度的代码,多了一个数组的空间复杂度。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>&nums, int left, int k){
if(path.size()== k){
res.push_back(path);
return;
}
for(;left<nums.size(); left++){
path.push_back(nums[left]);
backtracking(nums, left+1, k);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<int> nums(n);
for(int i=0; i<n; i++){
nums[i] = i+1;
}
backtracking(nums, 0, k);
return res;
}
};
回溯算法的剪枝
剪枝说明白了就是给回溯算法的for
循环添加上限制条件。之前的回溯算法相当于就是暴力搜索,它会遍历每一条路,找满足条件的结果。剪枝就是对于那些根本不可能存在结果的路径,我们直接在for
循环里就删除掉,以此减少搜索的速度,减少程序运行的时间。
200 岛屿数量
题目链接:岛屿数量
思路
参考解析,思路大概如下:用一个矩阵来存储每个节点的访问状态,已经访问记为True
,没有访问记为false
。如果当前节点是岛屿且状态为false
,那么首先将状态修改为true
,然后岛屿数量加1,同时使用dfs
去搜索该节点的所有临界节点,同时将状态改为true
。
class Solution {
public:
int dir[4][2] = {
0,1,1,0,-1,0,0,-1};
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){
for(int i=0; i<4; i++){
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx<0 || nextx>= grid.size() || nexty<0 || nexty>= grid[0].size()){
continue;
}
if(!visited[nextx][nexty] && grid[nextx][nexty] == '1'){
visited[nextx][nexty] = true;
dfs(grid, visited, nextx, nexty);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
int result = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++){
if(!visited[i][j] && grid[i][j] == '1'){
visited[i][j] = true;
result++;
dfs(grid, visited, i, j);
}
}
}
return result;
}
};
参考链接
- https://programmercarl.com/0200.%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F.%E6%B7%B1%E6%90%9C%E7%89%88.html#%E6%80%9D%E8%B7%AF