Rust入门练习-Week9-LC1642/739/150/1074/2402

LC2402. Meeting Rooms III Hard

一开始还以为是经典的排序贪心，+魔改，细读之后发现应该不是。感觉就是个模拟，因为时间范围是可枚举的

最开始把所有会议按开始时间塞堆里，对于一个时间点： 遍历所有会议室，踢出已经开完会的

若所有会议室都满，跳过

若堆顶时间小于等于当前时间，且有空会议室，安排之，会议室k的结束时间设置为now + length

考虑了下题目条件，完全不必按时间枚举，按第一维排序之后按会议枚举应该就可以，每次要找到最早结束的会议室，还是要用个堆

小脑萎缩了，被倒数第二个点卡了十多分钟，最后发现爆int

use std::{cmp::Reverse, collections::BinaryHeap};
impl Solution {
    pub fn most_booked(n: i32, mut meetings: Vec<Vec<i32>>) -> i32 {
        let mut visits = vec![0; n as usize];
        let mut heap = BinaryHeap::new();
        let n = n as usize;
        meetings.sort_unstable();
        for i in 0..n {
            heap.push(Reverse((0 as i64, i)));
        }
        for i in meetings {
            while let Some(Reverse((time, idx))) = heap.peek() {
                let (time, idx) = (*time, *idx);
                if time < i[0] as i64{
                    heap.pop();
                    heap.push(Reverse((i[0] as i64, idx)));
                } else {
                    break;
                }
            }
            if let Some(Reverse((time, idx))) = heap.pop() {
                let end_time =   time + (i[1] - i[0]) as i64;
                visits[idx] += 1;
                heap.push(Reverse((end_time, idx)))
                // println!("meeting {:?} held in {}, to {}", i, idx, end_time);

            }
        }
        visits.iter().enumerate().max_by_key(|x| (x.1, -(x.0 as i32))).unwrap().0 as i32
    }
}

LC1074. Number of Submatrices That Sum to Target Hard

虽然是Hard，但是我感觉 N^4 + 矩阵前缀和就能做，常数应该不大的。

考虑sumx 是 (0, 0) 到 (x, y) 的前缀和，求 (a, b) 到 (x, y) 的前缀和是sumx + suma-1 - sumx - suma-1

怎么说呢。。这还打败96%

impl Solution {
    pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {
        let mut sum = vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1];

        for i in 1..=matrix.len() {
            for j in 1..=matrix[0].len() {
                sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        let mut res = 0;
        for i in 0..=matrix.len() {
            for j in 0..=matrix[0].len() {
                for k in 0..i {
                    for l in 0..j {
                        if sum[i][j] - sum[k][j] - sum[i][l] + sum[k][l] == target {
                            res += 1;
                        }
                    }
                }
            }
        }
        res
    }
}

LC150. Evaluate Reverse Polish Notation Med

给个后缀表达式，算值

impl Solution {
    pub fn eval_rpn(tokens: Vec<String>) -> i32 {
        let mut stack = vec![];
        for i in tokens {
            let val = i.parse().unwrap_or(-300);
            if val == -300 {
                let (rval, lval) = (stack.pop().unwrap(), stack.pop().unwrap());
                let res = match i.as_str() {
                    "+" => lval + rval,
                    "-" => lval - rval,
                    "*" => lval * rval,
                    "/" => lval / rval,
                    _ => panic!("Invalid operator"),
                };
                stack.push(res);
            } else {
                stack.push(val);
            }
        }
        stack.last().cloned().unwrap()
    }
}

LC739. Daily Temperatures Med

Find all j for i s.t. temp[j] > temp[i], 感觉是个单调数据结构

从右往左，如果有 temp[i] temp[j]， 如果 i < j && temp[i] > temp[j] ，那j就一定没用了，所有i之前的答案最长是i，不会到j

倒过来想比较不那么顺畅，有个基本的思路之后我们可以考虑正过来。维护一个单调递减的单调栈

对于当前扫到的i，如果栈顶低于i，pop栈顶，维护pop的结果，如果高于i，push进去

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        use std::collections::VecDeque;
        let mut res = vec![0; temperatures.len()];
        let mut stack = VecDeque::new();
        for i in 0..temperatures.len() {
            while !stack.is_empty() && temperatures[i] > temperatures[*stack.back().unwrap()] {
                let idx = stack.pop_back().unwrap();
                res[idx] = (i - idx) as i32;
            }
            stack.push_back(i);
        }
        res
    }
}

LC1642. Furthest Building You Can Reach Med

感觉挺明显是个贪心，我们肯定是要在高度差更大的楼上用梯子，少的地方用砖，只不过不能简单的排序，因为不一定能达到某个位置

我的策略是全用砖，并把用砖的数量扔堆里，当砖不够的时候，就从堆顶取出一些砖，然后放上一个梯子

死活被卡一个点，leetcode数据太水了，考虑我这个策略是不是有问题

假设说我们在之前把梯子都用光了，会不会出现应该把梯子拿到现在这块的情况呢？

应该是不会的，因为如果用了梯子，一定是砖不够了，就算把梯子放在新位置，原来也会断。

日，被脑瘫GPT3.5骗了，它骗我BinHeap是小根堆

这些个if-else不太优雅，合并下同类项

use std::collections::BinaryHeap;
impl Solution {
    pub fn furthest_building(heights: Vec<i32>, mut bricks: i32, mut ladders: i32) -> i32 {
        let mut heap = BinaryHeap::new();
        for i in 1..heights.len() {
            if heights[i] > heights[i-1] {
                let diff = heights[i] - heights[i-1];
                if diff <= bricks {
                    bricks -= diff;
                    heap.push(diff);
                    println!("{} use {} bricks, {} left", i, diff, bricks);
                } else if let Some(&val) = heap.peek() {
                    if val > diff && ladders > 0 {
                        bricks += heap.pop().unwrap();
                        bricks -= diff;
                        heap.push(diff);
                        ladders -= 1;
                        // println!("{} use {} bricks + 1 ladder, bring {} {} left", i, diff, val, bricks);
                    } else if ladders > 0 {
                        // println!("diff is {}, {} use 1 ladder, {} left", diff, i, ladders);
                        ladders -= 1;
                    } else {
                        return (i-1) as i32
                    }
                } else if ladders > 0 {
                        // println!("diff is {}, {} use 1 ladder, {} left", diff, i, ladders);
                        ladders -= 1;
                } else {
                    // println!("bricks : {}, ladder {} need {}", bricks, ladders, diff);
                    return (i-1) as i32;
                
                }
            }
        }
        (heights.len()-1) as i32
    }
}