esc to dismiss
x
Home / week-87 / 876

信息

题解

解法1: 模拟

Warning
  1. 要求 连续 , 因此找到合适的开头后, 可以直接+1, 尝试找后一个
  2. 发现开头已经无效了, 就跳过 
pub fn is_n_straight_hand(hand: Vec<i32>, group_size: i32) -> bool {
    use std::cmp::Reverse;
    use std::collections::BinaryHeap;
    use std::collections::HashMap;
    if (hand.len() as i32) % group_size != 0 {
        // 张数不对
        return false;
    }
    let mut counter = HashMap::new();
    let mut pq = BinaryHeap::new();
    for card in hand {
        *counter.entry(card).or_insert(0) += 1;
        pq.push(Reverse(card));
    }

    while !pq.is_empty() {
        let start = pq.pop().unwrap().0;
        let entry = counter.entry(start).or_default();
        if *entry == 0 {
            // 起点已经被消耗了, 重新选一个
            continue;
        }
        *entry -= 1; //消耗一个
        for i in 1..group_size {
            // 因为连续, 所以可以枚举
            let e = counter.entry(start + i).or_default();
            if *e == 0 {
                // 凑不出连续
                return false;
            }
            *e -= 1;
        }
    }
    true
}

解法2: 贪心

上面用了优先队列, 其实可以不用, 直接排序就可以, 本意都是要一个有序的即可. 

pub fn is_n_straight_hand(hand: Vec<i32>, group_size: i32) -> bool {
    use std::collections::HashMap;
    if (hand.len() as i32) % group_size != 0 {
        // 张数不对
        return false;
    }
    let mut hand = hand;
    hand.sort();

    let mut counter = HashMap::new();
    for &card in hand.iter(){
        *counter.entry(card).or_insert(0) += 1;
    }

    for i in 0..hand.len(){
        let start = hand[i];
        let e= counter.entry(start).or_default();
        if *e ==0 {
            // 跳过, 下一个
            continue;
        }
        *e -= 1;
        for i in 1..group_size{
            // 开始假设枚举
            let e = counter.entry(start+i).or_default();
            if *e == 0{
                return false;
            }
            *e -= 1;
        }
    }
    true
}

Backlinks

Tags

x