LeetCode热题100刷题15：200. 岛屿数量、所有可达路径、118. 杨辉三角、287. 寻找重复数、84. 柱状图中最大的矩形

借助DFS寻找整个图的连通分量数，DFS将一个连通分量中的节点标记为visited，res记录连通分量数，最后返回res

class Solution {
public:const int dir[4][2] = {1,0,0,1,-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;else if(!visited[nextx][nexty] && grid[nextx][nexty]=='1') {visited[nextx][nexty]=true;dfs(grid,visited,nextx,nexty);} }}int numIslands(vector<vector<char>>& grid) {int res = 0;vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size(),0));for(int i=0;i<grid.size();i++) {for(int j=0;j<grid[0].size();j++) {if(!visited[i][j] && grid[i][j]=='1') {res++;visited[i][j]=true;dfs(grid,visited,i,j);}}}return res;}
};

（图论，深度优先搜索DFS复习）

#include <bits/stdc++.h>
using namespace std;vector<int> path;
vector<vector<int>> res;void dfs(const vector<vector<int>>& grid, int x, int n) {if(x==n) {res.push_back(path);return;}for(int i=1;i<=n;i++) {if(grid[x][i]==1) {path.push_back(i);dfs(grid,i,n);path.pop_back();}}
}
int main() {int n,m;cin>>n>>m;std::vector<vector<int>> grid(n+1,vector<int>(n+1,0));for(int i=1;i<=m;i++) {int a,b;cin>>a>>b;grid[a][b]=1;}path.push_back(1);dfs(grid,1,n);if(res.size()==0)cout<<-1<<endl;for(vector<int> pa : res) {for(int i=0;i<pa.size()-1;i++) {cout<<pa[i]<<" ";}cout<<pa[pa.size()-1]<<endl;}
}

res就当作是dp数组，找res[i][j]的更新规则，
样例中给出每一层的数组长度等于元素的个数，下标i从0开始，各层的长度需要resize为i+1

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res(numRows);for(int i=0;i<numRows;i++) {res[i].resize(i+1);res[i][0] = res[i][i] = 1;for(int j=1;j<i;j++) {res[i][j] = res[i-1][j]+res[i-1][j-1];}}return res;}
};

看作是一个数组找“环”的起点的题

class Solution {
public:int findDuplicate(vector<int>& nums) {if(nums.size()==1)return nums[0];int slow = nums[0],fast = nums[nums[0]];while(slow!=fast) {slow = nums[slow];fast = nums[nums[fast]];}slow = 0;while(slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
};

class Solution {
public:int largestRectangleArea(vector<int>& heights) {if(heights.size()==0)return 0;if(heights.size()==1)return heights[0];heights.insert(heights.begin(), 0);heights.push_back(0);stack<int> stk;int res=0;stk.push(0);for(int i=1;i<heights.size();i++) {if(heights[i] > heights[stk.top()]) {stk.push(i);}else if(heights[i] == heights[stk.top()]) {stk.pop();stk.push(i);}else {while(!stk.empty() && heights[i] < heights[stk.top()]) {int mid = stk.top();stk.pop();if(!stk.empty()) {int left = stk.top();int w = i-left-1;res = max(res,w*heights[mid]);}}stk.push(i);}}return res;}
};