[leetcode] 1366. Rank Teams by Votes

[leetcode] 1366. Rank Teams by votes

Description

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]Output: "ACB"Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.Team B was ranked second by 2 voters and was ranked third by 3 voters.Team C was ranked second by 3 voters and was ranked third by 2 voters.As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]Output: "XWYZ"Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]Output: "ABC"Explanation: Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]Output: "M"Explanation: Only team M in the competition so it has the first rank.

Constraints:

1 <= votes.length <= 10001 <= votes[i].length <= 26votes[i].length == votes[j].length for 0 <= i, j < votes.length.votes[i][j] is an English upper-case letter.All characters of votes[i] are unique.All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

分析

题目的意思是：给定一个字符串数组，统计字符串数组字符每个位置的频率，然后按照频率从大到小进行排序，如果频率相同，则按照字母的顺序排序。这道题我还没怎么看懂，我这里把例1中间结果输出来：

('A', 'A', 'A', 'A', 'A')('B', 'C', 'B', 'C', 'C')('C', 'B', 'C', 'B', 'B')defaultdict(, {'A': [-5, 0, 0], 'B': [0, -2, -3], 'C': [0, -3, -2], 'D': [0, 0, 0], 'E': [0, 0, 0], 'F': [0, 0, 0], 'G': [0, 0, 0], 'H': [0, 0, 0], 'I': [0, 0, 0], 'J': [0, 0, 0], 'K': [0, 0, 0], 'L': [0, 0, 0], 'M': [0, 0, 0], 'N': [0, 0, 0], 'O': [0, 0, 0], 'P': [0, 0, 0], 'Q': [0, 0, 0], 'R': [0, 0, 0], 'S': [0, 0, 0], 'T': [0, 0, 0], 'U': [0, 0, 0], 'V': [0, 0, 0], 'W': [0, 0, 0], 'X': [0, 0, 0], 'Y': [0, 0, 0], 'Z': [0, 0, 0]})ACB

python真厉害，一下子就能取出所有字符串的同位置的字符，然后进行统计，统计完了以后进行排序，对votes[0]进行排序就行了，因为这里面包含了所有字符哈，然后从counts中取出相应字符的频率+字符，等于说sorted是数组+字母拼接出来的数组排序，python居然可以对这种数值的数据排序，也是厉害了哈，排序完了就能得出结果了哈。

代码

class Solution: def rankTeams(self, votes: List[str]) -> str: counts = collections.defaultdict(list) for vote in zip(*votes): cntr=collections.Counter(vote) for ch in "ABCDEFGHIJKLMNOPQRSTUVWXYZ": counts[ch]+=[-1*cntr[ch]] return "".join(sorted(votes[0],key=lambda x:counts[x]+[x]))

参考文献

​​[LeetCode]Straightforward​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。