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)