Leetcode_20 天编程能力基础_day11

Posted on | In ,
| 11k | 1:32

继续，继续。

1376. Time Needed to Inform All Employees

Analysis

题目真长，不过意思还算简单，实质上就是在求树的最长路径，而通知时间就是结点与结点之间的边权，这与图很类似。

Code

bfs

从 bfs 的角度来思考可能会容易一些。

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
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int root = headID;
        if(n == 1) return 0;
        vector<int> totaltime(n);
        queue<int> q;
        q.push(root);
        while(!q.empty()) {
            int node = q.front(); q.pop();
            int tmptime = informTime[node];
            for(int i = 0; i < n; i++) {
                if(manager[i] == node) {
                    q.push(i);
                    totaltime[i] = tmptime + totaltime[node];
                }
            }
        }
        int maxtime = INT_MIN;
        for(int i = 0; i < n; i++) {
            if(maxtime < totaltime[i]) maxtime = totaltime[i];
        }
        return maxtime;
    }
};

可惜，这段代码提交上去超时了，原因是找子结点的时候是又重复遍历了一次数组。既然这样，那就按照根结点来统计一下子结点的下标：

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
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int root = headID;
        if(n == 1) return 0;
        vector<int> totaltime(n);
        unordered_map<int, vector<int>> indices;
        for(int i = 0; i < n; i++) {
            if(manager[i] != -1) indices[manager[i]].push_back(i);
        }
        queue<int> q;
        q.push(root);
        while(!q.empty()) {
            int node = q.front(); q.pop();
            int tmptime = informTime[node];
            for(int &i: indices[node]) {
                q.push(i);
                totaltime[i] = tmptime + totaltime[node];
            }
        }
        int maxtime = INT_MIN;
        for(int i = 0; i < n; i++) {
            if(maxtime < totaltime[i]) maxtime = totaltime[i];
        }
        return maxtime;
    }
};

这种思路虽然可以通过，但是时间、空间消耗都比较大。
仔细一看，这种思路实际上是利用邻接表遍历图，并求出最长路径，那干脆直接按照图的方式来写：

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
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int root = headID;
        if(n == 1) return 0;
        vector<int> totaltime(n);
        vector<vector<int>> adj(n);
        for(int i = 0; i < n; i++) {
            if(manager[i] != -1) adj[manager[i]].push_back(i);
        }
        queue<int> q;
        q.push(root);
        int maxtime = INT_MIN;
        while(!q.empty()) {
            int node = q.front(); q.pop();
            int tmptime = informTime[node];
            for(int &i: adj[node]) {
                q.push(i);
                totaltime[i] = tmptime + totaltime[node];
                if(totaltime[i] > maxtime) maxtime = totaltime[i];
            }
        }
        return maxtime;
    }
};

把 unordered_map 换成 vector 时间、空间消耗都减少很多😂。另外，因为不存在环（题目给的都是树），所以 visit 数组就可以省去了。

dfs

再回头想想 dfs 怎么写，按照前面的思路，当作图来写 dfs：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> totaltime = vector<int>(1e5);
    int maxtime = INT_MIN;
    void dfs(int u, vector<vector<int>>& adj, vector<int>& informTime) {
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            totaltime[v] = informTime[u] + totaltime[u];
            if(maxtime < totaltime[v]) maxtime = totaltime[v];
            dfs(v, adj, informTime);
        }
    }
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        int root = headID;
        if(n == 1) return 0;
        vector<vector<int>> adj(n);
        for(int i = 0; i < n; i++) {
            if(manager[i] != -1) adj[manager[i]].push_back(i);
        }
        dfs(headID, adj, informTime);
        return maxtime;
    }
};

同样，因为没有环，所以也不需要 visit 数组。

49. Group Anagrams

Analysis

这个题第一眼看过去，没读懂，仔细又读了一下，原来是个分类的题目，只需要将字母异位词组合在一起就可以了。
话说，求字母异位词好像就是求字母的全排列，不得不又联想到昨天做的那个题😂。
不过这个题，感觉用 hash 会好一点。

Code

一开始总数想让 hash 直接映射成不同类型字母异位词的下标，倒腾半天 map<vector<int>, int>，没倒腾出来，只能用暴力一点的解法了。

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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        vector<bool> ht(size);
        vector<vector<string>> ret;
        int amount = 0;
        while(amount < size) {
            vector<int> cnt1(26);
            int index = 0;
            while(index < size && ht[index] == true) index++;
            int len = strs[index].length();
            for(int i = 0; i < len; i++) {
                cnt1[strs[index][i] - 'a']++;
            }
            vector<string> tmp;
            for(int i = 0; i < size; i++) {
                len = strs[i].length();
                vector<int> cnt2(26);
                for(int j = 0; j < len; j++) {
                    cnt2[strs[i][j] - 'a']++;
                }
                if(cnt2 == cnt1) {
                    tmp.push_back(strs[i]);
                    ht[i] = true;
                }
            }
            amount += tmp.size();
            ret.push_back(tmp);
        }
        return ret;
    }
};

这段代码姑且算是能出结果了，可惜提交上去超时了。突然发现，自己有点被题目绕晕了。而且，这个题的难点好像是在如何合理使用 STL 来表示 hash 上。
省去了一些重复的判断：

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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        vector<bool> ht(size);
        vector<vector<string>> ret;
        int amount = 0;
        while(amount < size) {
            vector<int> cnt1(26);
            int index = 0;
            vector<string> tmp;
            while(index < size && ht[index] == true) index++;
            int len = strs[index].length();
            for(int i = 0; i < len; i++) {
                cnt1[strs[index][i] - 'a']++;
            }
            ht[index] = true;
            tmp.push_back(strs[index++]);
            while(index < size) {
                vector<int> cnt2(26);
                int tmplen = strs[index].length();
                if(ht[index] == false && len == tmplen) {
                    for(int i = 0; i < tmplen; i++) {
                        cnt2[strs[index][i] - 'a']++;
                    }
                    if(cnt2 == cnt1) {
                        tmp.push_back(strs[index]);
                        ht[index] = true;
                    }
                }
                index++;
            }
            amount += tmp.size();
            ret.push_back(tmp);
        }
        return ret;
    }
};

还是超时的，是我把这个问题想的太复杂了吗？
分析一下上面的代码，判断两个词是字母异位词是基于两个词的字符个数相同，这就需要分别对两个词中的字符进行统计并判断是否相同。同时，设置了一个 hash 表来标记这个词是否被统计过，统计过了就说明是其他词的字母异位词，就不再统计了。strs 的长度范围是 $[1, 10^4]$，词的长度范围是 $[0, 100]$，极端情况下，就是 $10^6$，按理说这种思路，虽然很慢，应该是可以过的。不过，这种思路下，可能会产生很多无效统计。
既然事实已经证明，这种方法不行了，就得换个思路了。
瞅了两眼官方题解，突然发现官方题解不是用字符串的字母统计结果当作 map 的映射，而是将字符串先排序，如果字符串的排序结果一致就说明是字母异位词，真鸡贼啊😂~
等等，好像发现了什么东西，回到一开始的思路，重新写了一下：

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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        map<vector<int>, int> indices;
        vector<vector<string>> ret(size);
        int index = 0;
        for(int i = 0; i < size; i++) {
            vector<int> cnt(26);
            int len = strs[i].length();
            for(int j = 0; j < len; j++) {
                cnt[strs[i][j] - 'a']++;
            }
            if(indices.count(cnt)) {
                ret[indices[cnt]].push_back(strs[i]);
            } else {
                ret[index].push_back(strs[i]);
                indices[cnt] = index++;
            }
        }
        vector<vector<string>> ans;
        for(auto &v: ret) {
            if(v.size() != 0) ans.push_back(move(v));
        }
        return ans;
    }
};

干，一开始的思路是可以通过的，尽管时间和空间消耗不忍直视。突然发现好像一开始倒腾半天没出来的原因是语法写错了，感觉今天不在状态（我还傻傻的一个一个去判断🙃）。既然明确了这个思路，那不妨写的更简单一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        map<vector<int>, vector<string>> ht;
        vector<vector<string>> ret;
        for(int i = 0; i < size; i++) {
            vector<int> cnt(26);
            int len = strs[i].length();
            for(int j = 0; j < len; j++) {
                cnt[strs[i][j] - 'a']++;
            }
            ht[cnt].push_back(strs[i]);
        }
        for(auto &[v1, v2]: ht) {
            ret.push_back(v2);
        }
        return ret;
    }
};

...还真能这样写啊（C++ 的语法跟 STL 的知识还得补🙃）。另外，unordered_map 好像不能把 vector 当作 key。
现在回到官方题解的思路上来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int size = strs.size();
        unordered_map<string, vector<string>> mp;
        for(string &s: str) {
            string key = s;
            sort(key.begin(), key.end());
            mp[key].push_back(s);
        }
        vector<vector<string>> ret;
        for(auto &[s, v]: mp) {
            ret.push_back(v);
        }
        return ret;
    }
};

相比自己的思路，时间、空间消耗都少了一半。
官方题解的第二种思路与自己的思路是一样的，只是用了稍微复杂一点的语法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                return (acc << 1) ^ fn(num);
            });
        };
        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for(string &str: strs) {
            array<int, 26> counts{};
            int len = str.length();
            for(int i = 0; i < len; i++) {
                counts[str[i] - 'a']++;
            }
            mp[counts].push_back(str);
        }
        vector<vector<string>> ret;
        for(auto it = mp.begin(); it != mp.end(); it++) {
            ret.push_back(it->second);
        }
        return ret;
    }
};

有好多看不懂的语法...暂时放着吧。

Summary

感觉今天脑子有点迷迷糊糊的，不太清醒。
话说，老是做题，都没有具体的看看书，也没有好好的总结一下

Buy me a coffee ? :)
0%