英雄算法7月27号

1791

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int arr[100001] = {0}, len = edges.size();
        for(auto& x: edges) {
            if(++arr[x[0]]  == len) return x[0];
            if(++arr[x[1]] == len) return x[1];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

思路

不可多得的小水题

797

class Solution {
    vector<vector<int>> ans;
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> tmp(1,0);
        //dfs找到所有路径
        dfs(graph, tmp, 0, graph.size() - 1);
        return ans;
    }
    void dfs(vector<vector<int>>& graph, vector<int>& tmp, int idx, int tar) {
        //如果找到了，那么就将结果填充到ans中
        if(idx == tar) {ans.emplace_back(tmp); return;}
        //如果idx可以到达的元素个数为0，那么说明走到死胡同了，直接返回
        if(graph[idx].size() == 0) return;
        //idx可以到达其它元素，那么沿着不同的路径，dfs
        for(auto& x: graph[idx]) {
            //idx到达的下一个元素是x,因此在tmp中添加x
            tmp.emplace_back(x);
            dfs(graph, tmp, x, tar);
            //dfs完毕，删除x。归位
            tmp.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路

寻找所有路径，点名dfs

851

class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int len = quiet.size();
        unordered_map<int,vector<int>> hash;
        //建立答案数组，一共有len个人
        vector<int> ans(len, -1);
        //建立图结构，让穷人指向夫人
        for(auto& x: richer) {
            hash[x[1]].emplace_back(x[0]);
        }
        //从0~len-1，求解ans[i];
        for(int i = 0; i < len; ++i) {
            dfs(hash, quiet, i, ans);
        }
        return ans;
    }
    void dfs(unordered_map<int,vector<int>>& hash, vector<int>& quiet, int idx, vector<int>& ans) {
        //如果ans[idx]已经求结果，无需求解
        if(ans[idx] != -1) return;
        //ans[idx]先等于自己，如果有更优解，在替换
        ans[idx] = idx;
        //ans[idx]实际等于几，需要看比他富有的那几个人有多安静
        for(auto& x: hash[idx]) {
            dfs(hash, quiet, x, ans);
            if(quiet[ans[idx]] > quiet[ans[x]]) ans[idx] = ans[x];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

思路

翻译一下，本题需要返回的结果数组需要满足以下两个条件

• ans[x] = y；y起码和x一样富有（y可以等于x）
• y是所有 和x一样富有 甚至比x富有的 人中 最安静的那个

现在的问题是，如何找到比 x 富有的人？

为了解决这个问题，我们需要建立图结构，让穷的人指向富有的人。如果我们要寻找所有比x更富于的人，我们只需要在x的基础上，dfs整张图，寻找最安静的那个，即可得到ans[x]的答案。重复遍历所有人，即可得到ans数组

这里需要说以下：ans[x] = min( { quiet[ans[x]]，quiet[ans[比x富有的人1号]]， quiet[ans[比x富有的人2号]]，……} ])，所以这题可以用动态规划来求解，但我不会改。我们可以借助这个公式来理解dfs

959

class Solution {
    int dir[5] = {1, 0, -1, 0, 1};
public:
    int regionsBySlashes(vector<string>& grid) {
        //放大表格，为元素编号
        vector<vector<int>> g(3 * grid.size(), vector<int> (3 * grid[0].size(), 0));
        //转化
        for(int i = 0; i < grid.size(); ++i) {
            for(int j = 0; j < grid[0].size(); ++j) {
                if(grid[i][j] == '/') 
                    g[3*i][3*j+2] = g[3*i+1][3*j+1] = g[3*i+2][3*j] = 1;
                else if(grid[i][j] == '\\')
                    g[3*i][3*j] = g[3*i+1][3*j+1] = g[3*i+2][3*j+2] = 1;
            } 
        }
        int ans = 0;
        //染色
        for(int i = 0; i < g.size(); ++i) {
            for(int j = 0; j < g[0].size(); ++j) {
                //if(g[i][j] == 1) continue;
                if(g[i][j] == 0) {
                    dfs(g, i, j);
                    ++ans;
                }
            }
        }
        return ans;
    }
    void dfs(vector<vector<int>>& g, int row, int col) {
        //如果位置非法，或者已经染过色了，跳过
        if( isValid(g.size(), g[0].size(), row, col) || g[row][col] == 1) return;
		//染色  
        g[row][col] = 1; 
        //寻找四个方向
        for(int i = 0; i < 4; ++i) {
            int nextR = row + dir[i];
            int nextC = col + dir[i + 1];
            dfs(g, nextR, nextC);
        }
    }
    //判断R，C是否是非法位置
    bool isValid(int m, int n, int R, int C) {
        if(R < 0 || R >= m || C < 0 || C >= n) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

思路

放大矩阵+染色法

为什么要放大矩阵，因为不放大就染色不了！

比如说：

---

如果是一个1*1的矩阵，你知道区域被分为2个部分，你想要染色上面的三角形，和下面的三角形，但你染色不了。因为只矩阵是1*1的，没有多余的格子来染色。

既然没有多余的格子，那我们就创造多余的格子：放大法

---

如图所示，我们将1*1的矩阵放大，得到3*3的矩阵。我们就得到了多余的位置，用于染色了。

更进一步的，我们将/转化为数字1，如果小方块是数字0，则表示没有染色，1则是染色，我们可以得到以下图片

现在，我们可以对放大过后的矩阵进行dfs染色。如果遇到0，dfs可以把和他联通的区域全部染成1；如此循环，即可得到区域个数。

解法

• 放大grid到原来的3倍，得到新矩阵g
• 将grid中是/的元素，在g中转化为1
• 循环遍历g中的所有元素，如果遇到0，就调用dfs染色；每调用一次，就表示有1块区域
• 返回调用次数