On the shoulders of giants.

weekly-contest-178

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

给你一个数组 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
题解

直接遍历统计。

时间复杂度:\(O(n^2)\)

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

通过投票对团队排名

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

排名规则如下:

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

给你一个字符串数组 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
  • votes[i][j] 是英文 大写 字母
  • votes[i] 中的所有字母都是唯一的
  • votes[0] 中出现的所有字母 同样也 出现在 votes[j] 中,其中 1 <= j < votes.length
题解

我们记录每个字符的每一排名的个数,存入可比较的列表中。

列表比较是以排名为一为第一关键字,排名为二为第二关键字,……。

最后,为了处理字典序问题,我们可以把字符从小到大映射为数字从大到小(字符小的优先)。

然后排序即可。

时间复杂度:\(O(nm+n\log n)\) ,n 为字符个数,m 为裁判个数。

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes.size(), l = votes[0].size();
        if(n == 1) return votes[0];
        vector<vector<int>> inform(27, vector<int> (27, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < l; j++) {
                inform[votes[i][j] - 'A'][j]++;
            }
        }
        for(int i = 0; i < 26; i++) {
            inform[i].back() = 26 - i;
        }
        sort(inform.begin(), inform.end(), greater<vector<int>>());
        string result;
        for(int i = 0; i < l; i++) {
            result += 'A' + 26 - inform[i].back();
        }
        return result;
    }
};

二叉树中的列表

给你一棵以 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 之间。
题解

枚举每一个节点,判断该节点往下走能否构成 head 链表。

时间复杂度:\(O(nm)\)

/**
 * 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 check(ListNode* head, TreeNode* root) {
        if(head == NULL) return true;
        if(root == NULL) return false;
        if(head->val != root->val) return false;
        if(check(head->next, root->left)) return true;
        if(check(head->next, root->right)) return true;
        return false;
    }
    bool search(ListNode* head, TreeNode* root) {
        if(root == NULL) return false;
        if(head->val == root->val) {
            if(check(head, root)) return true;
        }
        if(search(head, root->left)) return true;
        if(search(head, root->right)) return true;
        return false;
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        return search(head, root);
    }
};

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

给你一个 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 的代价修改一个格子中的数字,但每个格子中的数字 只能修改一次 。

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

示例 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
题解

最短路变性,(1,1) 到 (n,m) 的最小代价。

我们可以从已知 最小 代价的点开始走,它到达下一个点,只有两种可能,

该点的最小代价 或 该点最小代价+1 ,根据情况考虑。

现在,我们要找到下一个点开始转移,我们应该找最小的代价,所以双端队列可以解决。

下一个点是 该点的代价 时,把下一个点加入队头;

下一个点是 该点的代价-1 时,把下一个点加入队尾。

这样可以保证我们枚举的每个点都是最小代价的点。

时间复杂度:\(O(nm)\)

const int dt[2][4] = {{0, 0, 1, -1}, {1, -1, 0, 0}};
class Solution {
public:
    deque<pair<int, int>> dq;
    map<int, bool> vis;
    int n, m;
    bool check(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    int minCost(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        dq.push_front(make_pair(0, 0));
        while(!dq.empty()) {
            auto u = dq.front(); dq.pop_front();
            if(vis[u.first]) continue;
            vis[u.first] = true;
            int x = u.first / m, y = u.first % m;
            if(x == n - 1 && y == m - 1) return u.second;
            for(int i = 0; i < 4; i++) {
                int dx = x + dt[0][i];
                int dy = y + dt[1][i];
                int v = dx * m + dy;
                if(!check(dx, dy) || vis[v]) continue;
                if(grid[x][y] - 1 != i) {
                    dq.push_back(make_pair(v, u.second + 1));
                } else {
                    dq.push_front(make_pair(v, u.second));
                }
            }
        }
        return -1;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注