第 178 场周赛

Posted on | In , | |
Words count in article: 505 | Reading time ≈ 3

5344. 有多少小于当前数字的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> ret;
        vector<int> tmp = nums;
        sort(tmp.begin(), tmp.end());
        int count = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<tmp.size(); i++){
            if(i > 0 && tmp[i] == tmp[i-1]){
                count++; continue;
            }
            mp[tmp[i]] = count;
            count++;
        }
        for(int i=0; i<nums.size(); i++){
            ret.push_back(mp[nums[i]]);
        }
        return ret;
    }
};

5345. 通过投票对团队排名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
  string rankTeams(vector<string>& votes) {
    string S;
    int n = votes[0].size();
    vector<vector<int>> cnt(26, vector<int>(n, 0));
    for (auto &c: votes[0]) S.push_back(c);
    for (auto &v: votes) {
      for (int i = 0; i < v.size(); i++)  cnt[v[i] - 'A'][i]++;
    }
    sort(S.begin(), S.end());
    sort(S.begin(), S.end(), [&cnt](char l, char r) {
      return cnt[l-'A'] > cnt[r-'A'];
    });
    return S;
  }
};

5346. 二叉树中的列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  vector<int> L;
  bool dfs(TreeNode* root, vector<int> &cur) {
    if (L.size() <= cur.size() && equal(L.begin(), L.end(), cur.end() - L.size())) return true;
    if (root == NULL) return false;
    cur.push_back(root->val);
    if (dfs(root->left, cur)) return true;
    if (dfs(root->right, cur)) return true;
    cur.pop_back();
    return false;
  }
  
  bool isSubPath(ListNode* head, TreeNode* root) {
    L.clear();
    while (head) L.push_back(head->val), head = head->next;
    vector<int> cur;
    return dfs(root, cur);
  }
};

5347. 使网格图至少有一条有效路径的最小代价

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
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int inf = 0x3f3f3f3f;
        vector<vector<int> > cost(n, vector(m, inf));
        cost[0][0] = 0;
        queue<pair<int, int>> Q;
        Q.push({0, 0});
        while (!Q.empty()) {
            auto cur = Q.front(); Q.pop();
            int x = cur.first, y = cur.second, tx, ty;
            for (int i = 1; i <= 4; ++i) {
                tx = x, ty = y;
                if (i == 1) ty++;
                else if (i == 2) ty--;
                else if (i == 3) tx++;
                else tx--;
                
                if (tx >= 0 && ty >= 0 && tx < n && ty < m) {
                    int extra = i != grid[x][y];
                    if (cost[tx][ty] > extra + cost[x][y]) {
                        cost[tx][ty] = extra + cost[x][y];
                        Q.push({tx, ty});
                    }
                }
            }
        }
        return cost[n-1][m-1];
    }
};
Donate? comment?