讨论/题目交流/🐱 第 12 场夜喵双周赛/
🐱 第 12 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组变换
4 分 - 力扣排行榜
5 分 - 树的直径
7 分 - 删除回文子数组

第一题 Design A Leaderboard

这道题如果光从比赛的角度说,暴力就行了。但是更进一步,我们可以找到更好的办法。利用hashMap<play_id, score>保存用户分数,剩下的需要一个数据结构,它要既能够方便地插入数据,同时又能够有序地遍历内部的元素。最简单的就是BST,key是score,value保存有几个这样的score,比如tree[100]=3,表示得分为100的人3人。然后topK就可以以O(k)的时间复杂度算得。进而,我想到了SBT,size-balanced-tree。可以logN的时间查询出第K大,每个节点除了维护size还可以多维护一个所有子树的和,这样可以做到插入和查询都是O(logN)。但是,由于不想写,还是只用了标准库的BTree,思路是一样的,实际上比BST还快一点点。

use std::collections::{HashMap, BTreeMap};
use std::cmp::Reverse;

struct Leaderboard {
    user_score: HashMap<i32, i32>,
    rank: BTreeMap<Reverse<i32>, i32>,
}

impl Leaderboard {

    fn new() -> Self {
        Self{
            user_score: HashMap::new(),
            rank: BTreeMap::new(),
        }
    }

    fn add_score(&mut self, player_id: i32, score: i32) {
        if score == 0 {
            return;
        }
        let mut before = None;
        if let Some(&v) = self.user_score.get(&player_id) {
            before = Some(v);
        }
        let p = self.user_score.entry(player_id).or_insert(0);
        *p += score;
        if let Some(v) = before {
            if let Some(t) = self.rank.get_mut(&Reverse(v)) {
                *t -= 1;
            }
        }
        *self.rank.entry(Reverse(*p)).or_insert(0) += 1;
    }

    fn top(&self, k: i32) -> i32 {
        let mut count = 0;
        let mut n = k;
        for (k,&v) in self.rank.iter() {
           if n >= v {
               count += k.0 * v;
               n -= v;
           } else {
               count += k.0 * n;
               n = 0;
           }
            if n == 0 {
                break;
            }
        }
        count
    }

    fn reset(&mut self, player_id: i32) {
        if let Some(v) = self.user_score.get_mut(&player_id) {
            let t = *v;
            *v = 0;
            if t > 0 {
                *self.rank.get_mut(&Reverse(t)).unwrap() -= 1;
            }
        }
    }
}

第二题 Array Transformation

这道题是个easy,其实就是模拟这个过程就行了。为了节约空间可以用01滚动。

impl Solution {
    pub fn transform_array(arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();
        if n <= 2 {
            return arr;
        }
        let mut darr = [arr, vec![0; n]];
        darr[1][0] = darr[0][0];
        darr[1][n-1] = darr[0][n-1];
        let mut pos = 0;
        loop {
            let mut change = false;
            let np = pos ^ 1;
            for i in 1..n-1 {
                if darr[pos][i] > darr[pos][i-1] && darr[pos][i] > darr[pos][i+1] {
                    change = true;
                    darr[np][i] = darr[pos][i]-1;
                } else if darr[pos][i] < darr[pos][i-1] && darr[pos][i] < darr[pos][i+1] {
                    change = true;
                    darr[np][i] = darr[pos][i]+1;
                } else {
                    darr[np][i] = darr[pos][i];
                }
            }
            if !change {
                break;
            }
            pos = np;
        }
        darr[pos].clone()
    }
}

第三题 Tree Diameter

两次BFS,第一次任选一个点作为起点(比如0点),进行一次BFS,找到离0最远的点T。然后从T开始再进行一次BFS,找到离T最远的点,这个点到T的距离就是树的直径。
那么问题来了,为什么呢?下面给出证明:

设树的直径的左端点为S,右端点为T。随机选择一点P作为起点,分两种情况讨论:

假设P恰好在直径上

SP+PT=ST。那么离P最远的点必然是T(或者S)。为什么?
可以利用反证法,假设离P最远的点是W,不是T。此时可以推出:
SP+PW > SP+PT => SP+PW > ST。而由于SP是直径,树中没有任何路径能大于它,因此不存在这样的W点。
由此可得,当P点恰好在直径上,离他最远的点必然是直径的两个端点之一。

假设P是直径外一点

设,存在一个点W,使得PW > PT
设PW和直径ST相交于点X(必然相交,这个太简单就不证了),由此可得:
PX+XW > PX+XT(因为我们假设W离P最远),同理可得
PX+XW > PX+XS
两式相加可得:
2PX+2XW > 2PX+ST即:

XW > ST/2

我们继续分情况讨论:

  • 假如X恰好是ST的中点,则有: ST/2=SX=ST,而XW>ST/2=SX,因此:

SX+XW > ST,由于ST是直径,所以不存在这样的点W。

  • 假如X离S更近离T更远,即SX<XT, XT>ST/2

因此,XT+XW > SX+XT = ST。而ST是直径,所以不存在这样的点W。

综上可得,离树上任意点最远的点,必然是树的直径的两个端点之一。

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn tree_diameter(edges: Vec<Vec<i32>>) -> i32 {
        if edges.is_empty() {
            return 0;
        }
        if edges.len() == 1 {
            return 1;
        }
        let mut graph = HashMap::new();
        for edge in edges {
            let (a,b) = (edge[0], edge[1]);
            graph.entry(a).or_insert(HashSet::new()).insert(b);
            graph.entry(b).or_insert(HashSet::new()).insert(a);
        }
        let (t, _) = Self::bfs(&graph, 0);
        let (_, ans) = Self::bfs(&graph, t);
        ans
    }
    fn bfs(graph: &HashMap<i32, HashSet<i32>>, start: i32) -> (i32, i32) {
        let mut visited = HashSet::new();
        let mut q = vec![];
        let mut s = 0;
        let mut ans = 0;
        q.push((start, 0));
        visited.insert(start);
        while !q.is_empty() {
            let (cur, dist) = q.pop().unwrap();
            if ans < dist {
                ans = dist;
                s = cur;
            }
            if let Some(nodes) = graph.get(&cur) {
                for &node in nodes.iter() {
                    if !visited.contains(&node) {
                        visited.insert(node);
                        q.push((node, dist+1));
                    }
                }
            }
        }
        (s, ans)
    }
}

第四题 Palindrome Removal

这道题是一道比较经典的区间DP。一般来说这种题都是一个套路,对大区间操作有一定规则,且需要把内部小区间先操作了。

这道题同样。我们用f[i][j]表示把区间i..j全部删除的最少次数。由于这道题要求删除的必须是回文串,因此分情况讨论:
删除整个区间有两种可能,第一是先删i..k,再删k+1..j,第二是把i+1..j-1先删,最后和i&j一起删。

  • s[i] == s[j],那么把它俩放到任何一个回文串两边,都能组成一个新的回文串。也就意味着i+1..j-1这个区间不论怎么删,最后一次删除的时候,都可以把s[i]s[j]带上一起删。因此:
    f[i][j] = max(f[i+1][j-1], 1)。和1取max是因为整个区间删除至少需要一次,如果i..j本来就是回文串,这样递归下去我们会得到0

当然,我们也可以把si和sj分成两个部分删,先删si..sk,再删sk+1..sj

use std::cmp::{min, max};

impl Solution {
    pub fn minimum_moves(arr: Vec<i32>) -> i32 {
        if arr.is_empty() {
            return 0;
        }
        let n = arr.len();
        if n == 1 {
            return 1;
        }
        let mut f = vec![vec![0; n]; n];
        Self::dfs(0, n-1, &arr, &mut f)
    }
    fn dfs(l: usize, r: usize, arr: &Vec<i32>, f: &mut Vec<Vec<i32>>) -> i32 {
        if l > r {
            return 0;
        }
        if l == r {
            return 1;
        }
        if f[l][r] > 0 {
            return f[l][r];
        }
        let mut ans = (r-l+1) as i32;
        for i in l..=r {
            if l == i {
                ans = min(ans, 1+Self::dfs(i+1, r, arr, f));
            } else {
                if arr[l] == arr[i] {
                    ans = min(ans, max(Self::dfs(l+1, i-1, arr, f), 1)+Self::dfs(i+1, r, arr, f));
                } else {
                    ans = min(ans, Self::dfs(l+1, i-1, arr, f)+2+Self::dfs(i+1, r, arr, f));
                }
            }
        }
        f[l][r] = ans;
        ans
    }
}
1
展开全部 12 讨论