第178场周赛总结

今天做了三题，对于stl的运用还不是很熟练：

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

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

我的做法：先用数组统计，然后想用类似前缀和的方法，结果因为数据量小还是用了暴力：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int cnt[103];
        memset(cnt,0,sizeof cnt);
        for(auto x:nums) cnt[x]++;
        vector<int> res;
        for(auto x:nums){
            int sum = 0;
            for(int i = 0; i < x; i++)
                sum += cnt[i];
            res.push_back(sum);
        }
        return res;
        
    }
};

前缀和做法：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int cnt[103];
        memset(cnt,0,sizeof cnt);
        for(auto x:nums) cnt[x]++;
        vector<int> res;
        for(int i = 1; i < 101; i++)
            cnt[i] += cnt[i-1];
        for(auto x:nums){
            if(x != 0)
            res.push_back(cnt[x-1]);
            else res.push_back(0);
        }
        return res;  
    }
};

直接暴力：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector <int> ret;
        for (int i = 0; i < nums.size(); i++) {
            int cur = nums[i];
            int s = 0;
            for (int j = 0; j < nums.size(); j++) {
                s += (nums[j] < nums[i]); //小技巧
            }
            ret.push_back(s);
        }
        return ret;
    }
};

5345. 通过投票对团队排名

现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。

排名规则如下：

参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。

请你返回能表示按排名系统排序后的所有团队排名的字符串。

考察自定义排序：

我的做法：用map统计字符的各个排名，然后把map复制到vector进行排序：

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        map<char,vector<int>> mp;
        for(auto v:votes){
            for(int i = 0; i < v.size();i++){
                mp[v[i]].resize(v.size());//map中的vector不懂怎么初始化
                mp[v[i]][i]++;
            }      
        }
        vector<pair<char,vector<int> >> s;
        for(auto m:mp){
            s.push_back(m);
        }
        sort(s.begin(),s.end(),[](pair<char,vector<int>>    a,pair<char,vector<int>> b){
            return a.second > b.second || a.second == b.second && a.first < b.first;
        });
        string res;
        for(auto x:s){
            res += x.first;
        }
         return res;  
    }
};

参考解答然后对代码进行了优化：

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        map<char,vector<int>> mp;
        for(auto v:votes){
            for(int i = 0; i < v.size();i++){
                mp[v[i]].resize(v.size());
                mp[v[i]][i]++;
            }      
        }
        string res = votes[0];
        sort(res.begin(),res.end(),[&](char a, char b){
            return mp[a]> mp[b] || mp[a] == mp[b] && a < b;
        });
         return res;  
    }
};

5346. 二叉树中的列表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

我的做法：递归，WA了两次，终于知道要区分是不是链表的首节点了；

然后用map进行优化也是不行的：

class Solution {
public:
    map<pair<TreeNode*,ListNode*>,bool> mp;
    ListNode* h;
    bool isSubPath(ListNode* head, TreeNode* root) {
        h = head;
        return issub(head,root);  
    }
    bool issub(ListNode* p, TreeNode* root){
        if(!p) return true;
        if(!root) return false;
        //if(mp.count({root,head})) return mp[{root,head}];
        bool res = false;
        if(root->val == p->val)
            res = issub(p->next,root->left) || issub(p->next,root->right);
        if( p == h)
            res = res || issub(p,root->left) || issub(p,root->right);
        //mp[{root,head}] = res;
        return res; 
    }
};

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

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
注意网格图中可能会有无效数字，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条有效路径为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径不需要是最短路径。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字只能修改一次。

请你返回让网格图至少有一条有效路径的最小代价。

当时没时间做，后面做成dfs了。