LeetCode 1365 - 1368

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

枚举一下每个数，对于每一个数再去遍历一下数组当中的所有其他数，求有多少个数比它小

class Solution {
public:
    vector smallerNumbersThanCurrent(vector& nums) {
        //用变量存储数组长度
        int n =nums.size();
        //定义答案数组长度为n
        vector res(n);
        //依序遍历数组中的每一个数
        for(int i = 0;i < n;i++)
            //对于当前这个数再遍历数组当中所有的数
            for(int x : nums)
                if(x < nums[i])
                    res[i] ++;
        return res;
    }
};

通过投票对团队排名

 

 

 

按照题目要求把过程模拟出来即可，评委要给每个选手一个排名，把每一个评委给每个选手的排名的顺序给出，接下来对所有选手排序，如果存在并列就看下一个评委的排名顺序

所有选手是按大写英文字母来表示，所以最多有 26 个选手

输入每一个评委给出的排名

统计样例1 中，选手排名第 1 的次数排名第 2 的次数排名第 3 的次数

          1        2        3

A        5        0        0

B        0        2        3

C        0        3        2

排名第 1 的次数最多是 A

B、C 排名第一的次数是一样的，比较排名第 2 的次数，C 选手排名第 2 的次数比 B 选手多，因此排名第 2 的是 C 选手

最多 1k 个评委，每个评委给出的排名长度最大是 26，由于只有 26 个字母，保证所有评委给出的数据是一样长，数据合法

需要排序，用二维数组保存每一个选手在每一个排名下的次数，在做排序时，只需要依据次数去排序即可，根据字典序来比较次数，先比较排名第一的次

数，如果排名不同，第一次比较多的更靠前，如果相同，再看第二个数. . . 如果最后两个选手所有的次数都是一样，根据字典序来排序，除了 n 个排名外，

需要加上一维，加上字母本身的序号

STL 中的容器如果可以做比较的话，一般是按照字典序来比较的

快速地给数组按照字典序排序

sort 排序默认从小到大进行排序。

如果我们想从大到小排序可以将第 3 个参数写为 greater()

26 个字母没有按顺序给，可能直接给其中的某一个-> 为了防止越界开 26 个空间

第 n + 1 个是按字典序排序，如果选手的次序完全相同要按照字母的字典序来排序

class Solution {
public:
    string rankTeams(vector& votes) {
        //求有多少个选手
        int n = votes[0].size();
        //出现完全相同的情况 要根据字母的字典序进行排名-> 让'A'>'B'
        vector> ranks(26,vector(n + 1));
        //最后一维的初始化 -1 > -2
        for(int i = 0;i < 26;i++ ){
            ranks[i][n] = -i;
        }
        //把每一个评委的信息放到ranks中
        for(auto &vote : votes)
            for(int i = 0;i < n;i++ )
                //做偏移 vote[i]选手的i排名++
                ranks[vote[i]-'A'][i] ++;
        //把所有选手从大到小排序    
        sort(ranks.begin(),ranks.end(),greater>());
        //最后的排名 排名前n的选手一定是前n个出现过的选手 剩下的选手没有出现过 次数都是0
        string res;
        for(int i = 0;i < n;i++ ) res += -ranks[i][n] + 'A';
        return res;
    }
};

二叉树中的列表

 

 

 

给出一个二叉树和链表，问：二叉树中有没有一条从上到下的路径，使得路径上的值与链表上的值 一 一 对应

枚举链表匹配的起点，按顺序往下走，看能不能把链表走出来

需要匹配 4，2，8，先判断根节点和第一个点 4 是否匹配，接着往后枚举即可 . . .

①枚举起点  数量取决于二叉树点的数量 2500次

②匹配         数量取决于链表的个数 100次

时间复杂度：2.5 × 10^5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        //从根节点开始匹配 匹配成功
        if (dfs(head,root)) return true;
        //如果为空直接返回
        if(!root) return false;
        //否则继续枚举整个子树的每一个点作为起点先枚举左子树再枚举右子树-> 枚举起点
        return isSubPath(head,root->left) || isSubPath(head,root->right);    
    }
    //从当前点开始匹配能不能匹配成功-> 起点已经固定 匹配的过程
    bool dfs(ListNode* cur,TreeNode* root) {
        //判断每个点对应的是不是相同即可
        //链表为空 已经把整个列表匹配出来了
        if(!cur) return true;
        //树为空 匹配不了
        if(!root) return false;
        //树和链表都不是空
        //判断两者值是不是相同的
        if(cur->val != root->val) return false;
        //依次判断左右两边行不行-> 先判断左边再判断右边
        return dfs(cur->next,root->left) || dfs(cur->next,root->right);
    }
};

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

 

 

网格图中的数字如果是 1，表示下一步要往右走，是 2，表示下一步要往左走，是 3 表示下一步要往下走，是 4 表示下一步要往上走

案例 1：按照所给的路径不一定能到达最后一个格子，但是可以改变格子的方向

最少改变几个格子的方向，使得可以从左上角走到右下角

把矩阵当中的每一个格子当做是图论中的一个点

从一号点走到十六号点的最短路径的长度是多少

每个格子中的方向只能改变一次

在最优解中的每个格子最多只能变一次

10000个点、40000条边

bfs + 双端队列

 

class Solution {
public:
    int minCost(vector>& grid) {
        typedef pair PII;
        const int INF = 0x3f3f3f3f;
        
        #define x first
        #define y second
    
        int n = grid.size(),m = grid[0].size();
        
        vector> dist(n,vector(m,INF));
  
        vector> st(n,vector(m));

        int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};

        deque q;
        q.push_back({0,0});
        dist[0][0] = 0;
        
        while (q.size()) {
            
            auto t = q.front();
            q.pop_front();
    
            if(st[t.x][t.y]) continue;
            st[t.x][t.y] = true;

        for(int i = 0;i < 4；i++) {
            int x = t.x + dx[i],y = t.y + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            
            int w = grid[t.x][t.y] -1 != i;
            if(dist[x][y] > dist[t.x][t.y] + w) { 
                dist[x][y] = dist[t.x][t.y] + w;
                    if(w == 0) q.push_front({x,y});
                    else q.push_back({x,y});
                }
            }
        }

        return dist[n-1][m-1];
    }
    
};