LeetCode 第 178 场周赛

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

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

2. 通过投票对团队排名

class Solution {
public:
    struct node{
        string ch;
        int rank[26];
        bool operator < (node b)const{
            for(int i = 0; i < 26; i++) {
                if(rank[i] > b.rank[i]) return true;
                if(rank[i] < b.rank[i]) return false;
            }
            return ch < b.ch;
        }
        node(){}
    };
    string rankTeams(vector<string>& votes) {
        string allchar = votes[0];
        int len = allchar.length();
        node all[26];
        for(int i = 0; i < len; i++) { // init
            all[(allchar[i] - 'A')].ch = allchar[i];
            for(int j = 0; j < 26; j++) for(int k = 0; k < 26; k++) all[j].rank[k] = 0;
        }
        for(int i = 0; i < votes.size(); i++) {
            for(int j = 0; j < len; j++) {
                all[(votes[i][j]) - 'A'].rank[j]++;
            }
        }
        
        sort(all, all + 26);
        // for(int i = 0; i < len ; i++) {
        //     cout << all[i].ch << " : ";
        //     for(int j = 0; j < len; j++) cout << all[i].rank[j] << " "; cout << "\n";
        // } cout << endl;
        string ans = "";
        for(int i = 0; i < len; i++) {
            ans += all[i].ch;
            //cout << all[i].rank[0] << " " << all[i].rank[1] << " " << all[i].rank[2] << endl;
        }
        return ans;
    }
};

3. 二叉树中的列表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool solve(ListNode* head, TreeNode* root) {
        if(head == NULL) return true;
        if(root == NULL || root -> val != head -> val) return false;
        return solve(head -> next, root -> left) || solve(head -> next, root -> right); 
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        if(root == NULL) return false;
        return solve(head, root) || isSubPath(head, root -> left) || isSubPath(head, root -> right);
        
    }
};

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

class Solution {
public:
    int n, m;
    struct point{
        int x, y, c;
        point(){}
        point(int x, int y, int c):x(x), y(y), c(c){}
        friend bool operator < (point a, point b) {
            return a.c > b.c;
        }
    };
    bool is_ok(point p) {
        return (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m);
    }
    int minCost(vector<vector<int>>& grid) {
        priority_queue<point> pq;
        int vis[100][100];
        memset(vis, -1, sizeof vis);
        int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //按照右左下上的顺序
        n = grid.size(), m = grid[0].size();
        point cur = point(0, 0, 0);
        pq.push(cur);
        vis[0][0] = 0;
        while(!pq.empty()) {
            cur = pq.top();
            pq.pop();
            for(int i = 0; i < 4; i++) {
                point nxt = cur;
                nxt.x += nx[i]; nxt.y += ny[i];
                if(!is_ok(nxt)) continue;
                if(grid[cur.x][cur.y] != i + 1) nxt.c++;
                if(vis[nxt.x][nxt.y] == -1 || nxt.c < vis[nxt.x][nxt.y]) {
                    vis[nxt.x][nxt.y] = nxt.c;
                    pq.push(nxt);
                }
            }
        }
        return vis[n-1][m-1];
    }
};