img

力扣第 394 场周赛

A

给你一个字符串 word。如果 word 中同时存在某个字母的小写形式和大写形式，则称这个字母为 特殊字母 。

返回 word 中 特殊字母 的数量。

示例 1:

输入：word = "aaAbcBC"

输出：3

解释：

word 中的特殊字母是 'a'、'b' 和 'c'。

示例 2:

输入：word = "abc"

输出：0

解释：

word 中不存在大小写形式同时出现的字母。

示例 3:

输入：word = "abBCab"

输出：1

解释：

word 中唯一的特殊字母是 'b'。

提示：

  • 1 <= word.length <= 50
  • word 仅由小写和大写英文字母组成。

题解的优雅位运算思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numberOfSpecialChars(string word) {
        int msk[26] = {0};
        for (char c : word) {
            // 记录大写字母
            if (c >= 'A' && c <= 'Z') msk[c - 'A'] |= 1;
            // 记录小写字母
            if (c >= 'a' && c <= 'z') msk[c - 'a'] |= 2;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) if (msk[i] == 3) ans++;
        return ans;
    }
};

B

依然是大佬的位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfSpecialChars(string word) {
        // lo[i]：小写字母 i 最后一次出现的下标
        // up[i]：大写字母 i 最后一次出现的下标
        int lo[26], up[26];
        memset(lo, -1, sizeof(lo)); memset(up, -1, sizeof(up));
        for (int i = 0; i < word.size(); i++) {
            char c = word[i];
            // 记录小写字母
            if (c >= 'a' && c <= 'z') lo[c - 'a'] = i;
            // 记录大写字母
            if (c >= 'A' && c <= 'Z' && up[c - 'A'] == -1) up[c - 'A'] = i;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) if (lo[i] >= 0 && up[i] >= 0 && lo[i] < up[i]) ans++;
        return ans;
    }
};

C

考虑使用dp，dp[i][j]代表如果第i列全部设置为j，那么从第一列开始到第i列最少需要修改几个数字。

因此转移方程为

1
dp[i][j] = min(dp[i][j], dp[i-1][k]+n-counter[i-1][j]);
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
class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<unordered_map<int, int>> counter(m);
        for (int i=0; i<m; i++)
        {
            unordered_map<int, int> tmp;
            for (int j=0; j<n; j++){
                tmp[grid[j][i]]++;
            }
            counter[i] = tmp;
        }
        vector<vector<int>> dp(m+1, vector<int>(10, INT_MAX));
        // 提前处理dp[0]
        for (int i=0; i<10; i++){
            dp[0][i] = 0;
        }
        // 提前处理dp[1]
        for (auto &kv : counter[0])
        {
            dp[1][kv.first] = n-kv.second;
        }
        for (int i=2; i<=m; i++){
            for (int j=0; j<10; j++){
                for (int k=0; k<10; k++){
                    if (k!=j && dp[i-1][k] != INT_MAX)
                    {
                        dp[i][j] = min(dp[i][j], dp[i-1][k]+n-counter[i-1][j]);
                    }
                }
            }
        }
        return *min_element(dp[m].begin(), dp[m].end());
    }
};

D

dijkstra记录最短路径和求解最短路径问题

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        vector<vector<int>> last(n);
        typedef long long LL;
        vector<LL> d(n,LLONG_MAX);
        vector<bool> ans(edges.size());
        vector<vector<tuple<int,int,int>>> g(n);
        for(int i=0;i<edges.size();i++){
            auto &e=edges[i];
            int x=e[0],y=e[1],w=e[2];
            g[x].emplace_back(y,w,i);
            g[y].emplace_back(x,w,i);
        }

        d[0]=0;

        priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<>> pq;
        pq.emplace(0,0);
        while(!pq.empty()){
            auto[dx,x]=pq.top();
            pq.pop();
            if(dx>d[x]){
                continue;
            }
            for(auto [y,w,_]:g[x]){
                int new_dis=dx+w;
                if(new_dis==d[y]){
                    last[y].emplace_back(x);
                }
                if(new_dis<d[y]){
                    last[y].clear();
                    last[y].emplace_back(x);
                    d[y]=new_dis;
                    pq.emplace(new_dis,y);
                }
            }
        }
        typedef pair<int,int > PII;
        set<PII> s;

        queue<int> q;
        q.emplace(n-1);
        while(q.size()){
            int t=q.front();
            q.pop();
            for(int x:last[t]){
                if(s.count({x,t})==0&&s.count({t,x})==0)
                {
                    s.insert({x,t});
                    s.insert({t,x});
                }
                q.emplace(x);
            }
        }

        for(int i=0;i<edges.size();i++){
            auto &e=edges[i];
            int x=e[0],y=e[1],w=e[2];
            if(s.count({x,y})){
                ans[i]=true;
            } 
        }

        return ans;
    }
};