Rust算法练习-LC600/268/316/201/1111

yyi
yyi
2024-02-22 / 0 评论 / 59 阅读 / 正在检测是否收录...

LC1111. Maximum Nesting Depth of Two Valid Parentheses Strings Med

给定一个括号序列,让你拆成两份,使得最深的那一个深度最小。

感觉是个二分答案,考虑当假设答案为 k 的时候,怎么验证

开两个栈,往栈里塞左括号,正常匹配,直到:当这个栈达到 K 的时候,换个栈,继续塞。

不过这好像和一个栈也没啥区别啊。。就是判断栈的深度会不会超过 2K 呗

那好像不用二分答案了,找到最深的点,/2上取整就是 K,然后栈深 =< k 的是 0,>k的是 1

写的有点啰嗦,但比较好理解

impl Solution {
    pub fn max_depth_after_split(seq: String) -> Vec<i32> {
        let mut stack = vec![];
        let mut dep = 0;
        for i in seq.chars() {
            if i == '(' {
                stack.push(1);
                dep = dep.max(stack.len());
            } else {
                stack.pop();
            }
        }
        let mut res = vec![0; seq.len()];
        dep = (dep >> 1) + (dep & 1);
        for (i, ch) in seq.chars().enumerate() {
            if ch == '(' {
                stack.push(1);
                if stack.len() > dep {
                    res[i] = 1;
                }
            } else {
                if stack.len() > dep {
                    res[i] = 1;
                }
                stack.pop();
            }
        }
        res
    }
}

LC201. Bitwise AND of Numbers Range Med

数据范围INTMAX,很显然是要按位做了

第i位为1要求[l, r]中的每一个数第i位都为1

因此问题转换为了如何判定这件事

假设说l的这一位为1,如果l-r这一位都没有发生进位的话,那它仍是1,只要发生了一次进位,那就肯定变0了

应该就是这样了,至于怎么判断进没进位呢,对于l的第7位 l(7) = 1000111,应该只要看 (r-l) + l(6) 是否大于 1<<6就行了

一遍过,看了俩题解,好像人家写的比我简单多了,惊觉我说的东西就是最长公共前缀,只要求最长公共前缀就行了。

代码是原来的思路,不改了、。

impl Solution {
    pub fn range_bitwise_and(left: i32, right: i32) -> i32 {
        (0..32)
        .filter(|&i| (left & (1 << i) != 0) && ((right - left) + (left & ((1 << i) - 1)) < 1 << i))
        .fold(0, |acc, i| acc | (1 << i))
    }
}

LC316. Remove Duplicate Letters & 1081 Med

删掉重复的字母,使得字典序最小,算法应该是比较明显的贪心,考虑下咋贪。这个数据范围才1000,感觉最差情况都可以每次确定一位。

考虑一个字母在什么情况下有用。

我们肯定是想让最小的在最前,如果前面的都能删那自然不用说,假设说前面有一个不能删呢(假设是字母 k,所有k都在a前面)在这种情况下我肯定希望选择最后一个k前面最小的字母作为首字母。

考虑按字母扫数组,从a开始

首先考虑a能不能是最小的,充要条件是第一个a前面的每个字母都在a后面出现过。

如果能,则选择a,否则看b,条件一致。一直到选出第一个字母为止,删掉所有该字母前面的,和后面所有的该字母。

结果最长26,对于每个26,都有26*1000,复杂度应该是够的。但是写起来比较麻烦。

看了下Topic,有个单调栈,考虑单调栈咋做吧。

应该是个单调递增的栈,当遍历到一个新字母,且新字母没出现过,若栈顶字母大于当前字母:

  • 栈顶字母在后面还有,弹出
  • 栈顶字母后面没有了,不能弹

压入新字母

impl Solution {
    pub fn remove_duplicate_letters(s: String) -> String {
        let mut stack = vec![];
        let mut vis = vec![0; 26];
        let mut last = vec![0; 26];
        for (i, ch) in s.bytes().enumerate() {
            last[(ch - b'a') as usize] = i;
        }
        
        for (i, ch) in s.bytes().enumerate() {
            // println!("{:?}", stack);
            if vis[(ch - b'a') as usize] != 0 {
                continue;
            }
            while let Some(&top) = stack.last() {
                if top > ch && last[(top - b'a') as usize] > i {
                    stack.pop();
                    vis[(top - b'a') as usize] = 0;
                } else {
                    break;
                }
            }
            stack.push(ch);
            vis[(ch - b'a') as usize] = 1;
        }
        String::from_utf8(stack).unwrap()
    }
}

LC268. Missing Number Easy

这题方法太多了。

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        (n+1) * (n) / 2 - nums.iter().sum::<i32>()
    }
}

LC600. Non-negative Integers without Consecutive Ones Hard

是不是一个32位的dp啊...

dpi 表示由i位组成的数字,最后一位是0/1共有多少个符合题意

dpi+1 = dpi, dpi+1 = dpi + dpi;

这个DP还能压,

dp[i] = dp[i-1] + dp[i-2]

(dpi + dpi)

​ = (dpi-1 + dpi-1 + dpi-1)

​ =(dp[i-1] + dpi-1)

​ = (dp[i-1] + dp[i-2])

Ans = dp[i]

但是这样处理不了正好到n,考虑是不是能暴力或者做一个类似康拓展开的那种处理。

感觉还是要做一个康拓展开那种东西

随便来个n,考虑怎么加:

N = 10011101 (base 2)

首先包括 dp[7] : (0000000-01111111),全都比N小

之后固定第一位,包括dp[5]: (10000000-10001111),全都比N小,且和上面的不重

大概就这个思路, 但是有一类情况可能得特殊考虑,比如说这个dp[4] 可能就不能包括全进来,因为第五位是1

发现对于这种情况,后面要考虑的:(10001000-10001011)再下一个就是 (10001100-...)了,这些后面的肯定都不满足,都不用带了

impl Solution {
    pub fn find_integers(mut n: i32) -> i32 {
        let mut f = vec![0; 31];
        f[0] = 1;
        f[1] = 1;
        for i in 2..31 {
            f[i] = f[i-1] + f[i-2];
        }
        let mut res = 0;
        let mut last = 0;
        for i in (0..=29).rev() {
            let val = 1 << i;
            if (n & val) != 0 {
                n -= val;
                res += f[i + 1];
                if last == 1 {
                    break;
                }
                last = 1;
            } else {
                last = 0;
            }
            if i == 0 {
                res += 1;
            }
        }
        res
    }
}
0

评论 (0)

取消