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

给你一个数组?nums,对于其中每个元素?nums[i],请你统计数组中比它小的所有数字的数目。
换而言之,对于每个?nums[i]?你必须计算出有效的?j?的数量,其中 j 满足?j != i nums[j] < nums[i]?。
以数组形式返回答案。

样例

示例 1:

输入:nums = [8,1,2,2,3]
输出:[4,0,1,1,3]
解释:
对于 nums[0]=8 存在四个比它小的数字:(1,2,2 和 3)。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字:(1)。
对于 nums[3]=2 存在一个比它小的数字:(1)。
对于 nums[4]=3 存在三个比它小的数字:(1,2 和 2)。

示例 2:

输入:nums = [6,5,4,8]
输出:[2,1,0,3]

示例 3:

输入:nums = [7,7,7,7]
输出:[0,0,0,0]

提示

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

代码

viv丑陋版

太简单啦!两层循环,暴力找每个数字的比它小的数字个数。

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

zz美丽版

一模一样,嘿嘿嘿。

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

2. 通过投票对团队排名

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

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

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

样例

示例 1:

输入:votes = ["ABC","ACB","ABC","ACB","ACB"]
输出:"ACB"
解释:A 队获得五票「排位第一」,没有其他队获得「排位第一」,所以 A 队排名第一。
B 队获得两票「排位第二」,三票「排位第三」。
C 队获得三票「排位第二」,两票「排位第三」。
由于 C 队「排位第二」的票数较多,所以 C 队排第二,B 队排第三。

示例 2:

输入:votes = ["WXYZ","XYZW"]
输出:"XWYZ"
解释:X 队在并列僵局打破后成为排名第一的团队。X 队和 W 队的「排位第一」票数一样,但是 X 队有一票「排位第二」,而 W 没有获得「排位第二」。

示例 3:

输入:votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
输出:"ZMNAGUEDSJYLBOPHRQICWFXTVK"
解释:只有一个投票者,所以排名完全按照他的意愿。

示例 4:

输入:votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
输出:"ABC"
解释:
A 队获得两票「排位第一」,两票「排位第二」,两票「排位第三」。
B 队获得两票「排位第一」,两票「排位第二」,两票「排位第三」。
C 队获得两票「排位第一」,两票「排位第二」,两票「排位第三」。
完全并列,所以我们需要按照字母升序排名。

示例 5:

输入:votes = ["M","M","M","M"]
输出:"M"
解释:只有 M 队参赛,所以它排名第一。

提示

  • 1 <= votes.length <= 1000
  • 1 <= votes[i].length <= 26
  • votes[i].length ==?votes[j].length for?0 <= i, j < votes.length
  • votesi?是英文 大写 字母
  • votes[i]?中的所有字母都是唯一的
  • votes[0]?中出现的所有字母 同样也 出现在?votes[j]?中,其中?1 <= j < votes.length

代码

viv丑陋版

这个也好简单哦,看数据范围暴力就可以啦。
统计每个字母在每个位置出现的次数,然后按照题目要求排序就好。

struct CH {
    int cnt[1005];
    bool vis;
    char c;
} ch[26];

bool cmp(const CH & c1, const CH & c2) {
    for(int i=0; i<1000; i++) {
        if(c1.cnt[i] != c2.cnt[i]) return c1.cnt[i] > c2.cnt[i];
    }    
    return c1.c < c2.c;
}

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        for(int i=0; i<26; i++) {
            memset(ch[i].cnt, 0, sizeof(ch[i].cnt));
            ch[i].vis = false;
            ch[i].c = 'A' + i;
        }
        
        int n = votes.size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<votes[i].size(); j++) {
                ch[votes[i][j]-'A'].cnt[j]++;
                ch[votes[i][j]-'A'].vis = true;
            }
        }
        sort(ch, ch+26, cmp);
        
        string ans = "";
        for(int i=0; i<26; i++) {
            if(!ch[i].vis) continue;
            ans += ch[i].c;
        }
        return ans;
    }
};

zz美丽版

zz比我机智许多qwq。
首先是我脑子瓦特了,结构体里的cnt根本不需要开那么大,就26个字母,位置也就最大26,不是votes的长度1000。
然后就是也根本不需要vis这个变量,像zz这样直接取votes[0]所涉及到的字母排序就很ok。

int cnt[30][30];

bool cmp(char a, char b){
    a -= 'A'; b -= 'A';
    for (int i = 0; i < 26; i++){
        if (cnt[a][i] > cnt[b][i]) return true;
        if (cnt[a][i] < cnt[b][i]) return false;
    }
    return a < b;
}

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        memset(cnt, 0, sizeof(cnt));
        int n = votes[0].length();
        
        for (auto s: votes)
            for (int i = 0; i < n; i++) 
                ++cnt[s[i] - 'A'][i];
        
        string ans = votes[0];
        sort(ans.begin(), ans.end(), cmp);
        
        return ans;
    }
};

3. 二叉树中的列表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True ,否则返回 False 。
一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。

样例

示例 1:

输入:head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:true
解释:树中蓝色的节点构成了与链表对应的子路径。
示例 2:

输入:head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:true
示例 3:
输入:head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:false
解释:二叉树中不存在一一对应链表的路径。

提示:

  • 二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
  • 链表包含的节点数目在 1 到 100 之间。
  • 二叉树包含的节点数目在 1 到 2500 之间。

代码

viv丑陋版

我被这道题卡自闭了qwq。我就不知道写个dfs怎么这么难,写到最后好不容易应该是对的还TLE。

zz美丽版

啊啊啊为什么zz的代码这么思路清晰简洁明了!
对于树上的每一个节点,都判断一下是否有从它开始的路径与链表相符合。
所以相当于做两遍dfs,第一遍在树上遍历节点作为起点,第二遍对于每一个起点dfs看是否有符合要求的路径。

class Solution {
public:
    bool check(TreeNode* rt, ListNode *head){
        if (head == NULL) return true;
        if (rt == NULL) return false;
        if (rt->val != head->val) return false;
        
        bool ret1 = check(rt->left, head->next);
        bool ret2 = check(rt->right, head->next);
        
        return ret1 || ret2;
    }
    
    bool dfs(TreeNode* rt, ListNode* head){
        if (rt == NULL) return false;

        bool ret1 = check(rt, head);
        bool ret2 = dfs(rt->left, head);
        bool ret3 = dfs(rt->right, head);
        
        return ret1 || ret2 || ret3;
    }
    
    bool isSubPath(ListNode* head, TreeNode* root) {
        return dfs(root, head);
    }
};

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

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

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

一开始,你会从最左上角的格子?(0,0)?出发。我们定义一条?有效路径?为从格子?(0,0)?出发,每一步都顺着数字对应方向走,最终在最右下角的格子?(m - 1, n - 1)?结束的路径。有效路径?不需要是最短路径?。
你可以花费?cost = 1?的代价修改一个格子中的数字,但每个格子中的数字?只能修改一次?。
请你返回让网格图至少有一条有效路径的最小代价。

样例

示例 1:

输入:grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出:3
解释:你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为: (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)
总花费为 cost = 3.

示例 2:

输入:grid = [[1,1,3],[3,2,2],[1,1,4]]
输出:0
解释:不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

示例 3:

输入:grid = [[1,2],[4,3]]
输出:1

示例 4:

输入:grid = [[2,2,2],[2,2,2]]
输出:3

示例 5:

输入:grid = [[4]]
输出:0

提示

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100

代码

viv丑陋版

无qwq。

zz美丽版

首先赞美一下zz的想法真是太妙了,虽然我现在很生气。
顺着箭头方向走需要的代价是0,改变箭头方向需要的代价是1。所以相当于求一条起点到终点的最短路,边权是0或1。
普通BFS是解决边权是1的最短路问题的,通过构造一个x x ... x ... x+1 ... x+1的队列,弹出时取队首,压入时将距离为x+1的元素时直接放在队尾。
0-1BFS可以解决边权是0或1的最短路问题,通过构造一个x x ... x ... x+1 ... x+1的队列,弹出时取队首,压入时将距离为x的元素放在队首,距离为x+1的元素时放在队尾。

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};

        int dist[105][105]; memset(dist, -1, sizeof(dist));
        deque<pair<int, int>> que; 

        dist[0][0] = 0;que.push_back(make_pair(0, 0));
        while(!que.empty()) {
            pair<int, int> cur = que.front(); que.pop_front();
            int x = cur.first, y = cur.second; 

            for(int i=0; i<4; i++) {
                int tx = x + dx[i], ty = y + dy[i];
                int cost = dist[x][y] + (grid[x][y] - 1 == i ? 0 : 1);
                if(tx < 0 || tx >=n || ty < 0 || ty >= m) continue;
                if(dist[tx][ty] == -1 || dist[tx][ty] > cost) {
                    dist[tx][ty] = cost;
                    if(dist[x][y] == dist[tx][ty]) que.push_front(make_pair(tx, ty));
                    else que.push_back(make_pair(tx, ty));
                } 
            }
        }
        return dist[n-1][m-1];
    }
};
最后修改:2020 年 03 月 18 日 11 : 16 AM
如果觉得我的文章对你有用,请随意赞赏