ARST打卡第295周

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

impl Solution {
    pub fn rank_teams(votes: Vec<String>) -> String {
        // votes.len() 是投票人数,但我们需要的是每个位置的字符数,应该用 votes[0].len()
        let n = votes[0].len();
        // dp[i][j] 表示第i个位置字符j(A-Z)的得票数
        let mut dp = vec![vec![0; 26]; n];
        for vote in votes {
            for (i, c) in vote.chars().enumerate() {
                dp[i][c as usize - 'A' as usize] += 1;
            }
        }
        let mut ans = String::with_capacity(n);
        let mut used = vec![false; 26];
        for _ in 0..n {
            let mut max_char = 'A';
            let mut found = false;
            // 遍历所有未使用的字母
            for j in 0..26 {
                if used[j] {
                    continue;
                }
                if !found {
                    // 找到第一个未使用的字母，直接continue是为了有2个字母比较, 或者最后一个字母直接用
                    max_char = (j as u8 + b'A') as char;
                    found = true;
                    continue;
                }
                // 比较当前字母j和当前最大字母的所有位置得票
                let mut is_larger = false;
                let mut is_equal = true;
                for pos in 0..n {
                    let curr = dp[pos][j];
                    let max = dp[pos][max_char as usize - 'A' as usize];
                    if curr > max {
                        is_larger = true;
                        is_equal = false;
                        break;
                    }
                    if curr < max {
                        is_equal = false;
                        break;
                    }
                }
                if is_larger || (is_equal && j < (max_char as usize - 'A' as usize)) {
                    max_char = (j as u8 + b'A') as char;
                }
            }
            used[max_char as usize - 'A' as usize] = true;
            ans.push(max_char);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

use std::collections::HashMap;

impl Solution {
    pub fn rank_teams(votes: Vec<String>) -> String {
        let n = votes.len();
        // 初始化哈希映射
        let mut ranking: HashMap<char, Vec<i32>> = HashMap::new();
        for vid in votes[0].chars() {
            ranking.entry(vid).or_insert(vec![0; votes[0].len()]);
        }
        // 遍历统计
        for vote in votes {
            for (i, c) in vote.chars().enumerate() {
                if let Some(rank) = ranking.get_mut(&c) {
                    rank[i] += 1;
                }
            }
        }
        // 取出所有的键值对
        let mut result: Vec<(char, Vec<i32>)> = ranking.into_iter().collect();
        // 排序
        result.sort_by(|a, b| {
            for i in 0..a.1.len() {
                if a.1[i] != b.1[i] {
                    return b.1[i].cmp(&a.1[i]);
                }
            }
            a.0.cmp(&b.0)
        });

        // 构建结果字符串
        let mut ans = String::new();
        for (vid, _) in result {
            ans.push(vid);
        }
        ans
    }
}
// 链接：https://leetcode.cn/problems/rank-teams-by-votes/solutions/123922/tong-guo-tou-piao-dui-tuan-dui-pai-ming-by-leetcod/