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

200. 岛屿数量

借助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复习）

98. 所有可达路径

#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;
    }
}

118. 杨辉三角

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;
    }
};

287. 寻找重复数

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

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;
    }
};

84. 柱状图中最大的矩形

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;
    }
};