LC2149. Rearrange Array Elements by Sign Med
好像双指针，但是它没要求常数空间，为什么不直接模拟呢。
use super::Solution;
impl Solution {
pub fn rearrange_array(nums: Vec<i32>) -> Vec<i32> {
let pos : Vec<_> = nums.iter().filter(|&&x| x > 0).collect();
let neg : Vec<_> = nums.iter().filter(|&&x| x < 0).collect();
pos.iter()
.zip(neg.iter())
.flat_map(|(&a, &b)| vec![a, b])
.cloned()
.collect();
}
}LC3034&3036. Number of Subarrays That Match a Pattern II Hard & Med
两道题区别是数据范围，3034可以n^2,3036要log
有一个很明显的性质，即nums相邻两项的关系是固定的，我们可以预处理一个nums2数组, nums2[i] 的 结果和 pattern的1, 0, -1 是一样的。
现在变成判断给定n个长度为m的数组，看看有多少个和给定pattern一样
这不直接比较哈希值就完事了吗，但是要均摊O(n)的获取这个哈希值
把字符串哈希的那种前缀哈希直接照搬过来，预处理一遍然后就可以O1的获取所有哈希了
设计hash函数：hash[i+1] = hash[i]*p + nums2[i]
已知 hash[r] - hash[l-1] * p^len = hash[l..r]
正解：
有俩地方要注意，一个是数字里有负数，要带上偏移，都偏到正
一个是rust不能溢出，要自己写个快速幂
最后看了最快的正解，应该是用KMP，哈希慢了点也能过
use super::Solution;
impl Solution {
fn mod_pow(base: i64, exp: u32, modulus: i64) -> i64 {
if modulus == 1 {
return 0;
}
let mut result = 1;
let mut base = base % modulus;
let mut exp = exp;
while exp > 0 {
if exp % 2 == 1 {
result = result * base % modulus;
}
exp >>= 1;
base = base * base % modulus;
}
result
}
pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 {
let mut ans = 0;
let (n, m) = (nums.len(), pattern.len());
let nums: Vec<i64>= nums.windows(2)
.map(|window| match window {
[a, b] if a < b => 1,
[a, b] if a == b => 0,
[a, b] if a > b => -1,
_ => unreachable!(),
})
.collect();
let base = 13131_i64;
let p = 1_000_000_007_i64;
let hash = nums.iter().fold(vec![0_i64], |mut hash, &num| {
hash.push((hash.last().unwrap() * base + num + 1) % p);
hash
});
let target_hash = pattern.iter().fold(0_i64, |hash, &num| (hash * base + num as i64 + 1) % p);
for i in 0..n {
if i + m >= n {
break;
}
let hash =( hash[i + m] - (hash[i] * Self::mod_pow(base, m as u32, p) % p ) + p) % p;
if hash == target_hash {
ans += 1;
}
}
ans
}
}暴力：
use super::Solution;
impl Solution {
pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 {
let mut ans = 0;
let (n, m) = (nums.len(), pattern.len());
for i in 0..(n-m) {
let sub_arr = &nums[i..=i+m];
println!("{:?}", sub_arr);
let mut res = true;
for j in 0..m {
if pattern[j] == 1 && sub_arr[j] >= sub_arr[j + 1]{
res = false;
break;
} else if pattern[j] == 0 && sub_arr[j] != sub_arr[j + 1] {
res = false;
break;
} else if pattern[j] == -1 && sub_arr[j] <= sub_arr[j + 1] {
res = false;
break;
}
}
if res {
ans += 1;
}
}
ans
}
}LC3033. Modify the Matrix Ez
2.11周赛T1
impl Solution {
pub fn modified_matrix(mut matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
for i in 0..matrix.len() {
for j in 0..matrix[i].len() {
if matrix[i][j] == -1 {
matrix[i][j] = matrix.iter()
.map(|f| f[j])
.max()
.unwrap();
}
}
}
matrix
}
}LC1658. Minimum Operations to Reduce X to Zero Med
在首尾各选一段区间，使得加和结果为x，且区间长度最小。
感觉可以二分答案，二分复杂度一个Log，每次验证是滑动窗口
数据范围10^5目测正解
写完发现，这东西并不单调，竟然这都让我过了二三十个点
感觉是双指针，但是这是面试题里我最不擅长的东西了。但是这道题好像还可以
两个指针从0开始，如果当前结果太大，r往右，如果当前结果太小，l往右
LC287. Find the Duplicate Number Med
好像是什么经典题，和之前做过的很像
impl Solution {
pub fn find_duplicate(mut nums: Vec<i32>) -> i32 {
for i in 0..nums.len() {
let index = nums[i].abs() as usize;
if nums[index] < 0 {
return index as i32;
}
nums[index] = -nums[index];
}
return 0;
}
}
评论 (0)