LC611. Valid Triangle Number Med
找到能组成三角形的边的组合数，N范围1000
考虑朴素：直接N^3 枚举
其实只要枚举两个边，第三个边的范围就确定了，(a-b, a+b)，只需要有个手段统计这个区间内数字数量即可
权值线段树？好像用不着，排个序然后二分查找应该就行
不过我估计双指针也行，但是确实不是很擅长
impl Solution {
pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
if nums.len() < 3 {
return 0;
}
nums.sort_unstable();
let mut ans = 0;
for i in 0..nums.len() - 2 {
for j in i+1..nums.len() - 1 {
let s = nums[i] + nums[j];
ans += nums[j+1..].partition_point(|&n| n < s) as i32;
}
}
ans
}
}LC1. Two Sum Ez
基础解法枚举N^2 没啥可说的，考虑能不能更快
丢hashmap，理论O(N), 好像也没啥可说的。。
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::new();
for (i, num) in nums.iter().enumerate() {
let x = target - num;
if let Some(&j) = map.get(&x) {
return vec![j as i32, i as i32];
}
map.insert(num, i);
}
vec![0, 0]
}
}LC4. Median of Two Sorted Arrays Hard
感觉是什么经典题，给俩有序数组，要求 log 求出中位数
首先是我估计先合并了再求也能过，因为 OJ 卡不了那么精确估计。
考虑怎么 log 做，我猜肯定是在两个数组上分别二分，然后逐渐逼近答案，这个是时间复杂度限制的，基本不会用别的算法了
考虑第一次二分会有什么性质
假设数组 a 的中位数是 x, b 的是 y，以 y > x 为例
有 >= len/2 的数 > x, 有 >= len/2的数 < y，所以答案一定在[x, y] 范围内。
我们好像一下就缩小了很大的范围，两个数组都只剩一半的数了（其实应该更少，但是我们在数组 A 中截取后一半，数组 B 中截取前一半）（x > y 同理）但是问题是这么缩，剩下的数组的中位数好像就偏移了。想解决这个问题其实蛮简单，我不删那么多就好了，我按少的删。比如 A 的一半是 10，B 的一半是 8，我也只删 A 的前八个、B 的后八个（不是真的删，只是范围指针变化了）在这种情况下，一定是中位数的两边各删了 8 个
在最后，一定会有较小的数组剩 1 或 2，这时候直接插进去求中位数即可，这种方法目测是 O(log(min(m+n)))的，比题目要求更优秀，不过实现起来比较麻烦。
还有一个小细节，插入的复杂度是 O(N)的，但是我们这里只会插1-2 个数，插到大数组里不会让大数组的中位数偏移超过 1（极端情况，数组 1 [1, 2, 3, 4, 5, 6, 7, 8]，数组 2[9, 10]），所以只留大数组中间四个数即可
看了下官方题解，还不如我这个好理解，写一下验证一下。
use std::mem::swap;
impl Solution {
fn mid_segment<'a>(nums: &'a[i32]) -> &'a[i32] {
match nums.len() {
0..=4 => nums,
_ => {
let lower = ((nums.len() - 1) as f64 / 2.0).floor() as usize - 1;
let upper = ((nums.len() - 1) as f64 / 2.0).ceil() as usize + 2;
&nums[lower..upper]
}
}
}
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let (mut n1, mut n2) = (&nums1[..], &nums2[..]);
let med = |arr: &[i32]| {
let mid = (arr.len() - 1) as f64 / 2.0;
let (left, right) = (mid.floor() as usize, mid.ceil() as usize);
((arr[left] + arr[right]) as f64 / 2.0, mid)
};
while n1.len() > 2 && n2.len() > 2 {
let (mut m1, mut m2) = (med(n1), med(n2));
if m1.0 > m2.0 {
swap(&mut n1, &mut n2);
swap(&mut m1, &mut m2);
}
let remove = std::cmp::min(m1.1.floor() as usize, n2.len() - m2.1.ceil() as usize - 1);
n1 = &n1[remove..];
n2 = &n2[..(n2.len()-remove)];
}
let mut res = Self::mid_segment(n1).to_vec();
res.extend(Self::mid_segment(n2));
res.sort();
med(&res).0
}
}LC2971. Find Polygon With the Largest Perimeter Med
感觉像排序+前缀和，然后从后往前扫到第一个 sum[i] > num[i+1] 的
impl Solution {
pub fn largest_perimeter(mut nums: Vec<i32>) -> i64 {
nums.sort_unstable();
let sum: Vec<_> = nums
.iter()
.scan(0, |acc, &num| {
*acc += num as i64;
Some(*acc)
})
.collect();
sum.iter()
.enumerate()
.rev()
.skip(1)
.find(|&(i, &v)| v > nums[i + 1] as i64)
.map_or(-1, |(i, _)| sum[i] + nums[i + 1] as i64)
}
}LC1363. Largest Multiple of Three Hard
给定一些数码，拼一个最大的能被三整除的数
首先明显有俩性质，不知道老外知不知道，但是中国学生肯定都知道
- 数字越长肯定越大
- 数字加和能被 3 整除，不管咋排列都能被 3 整除
所以这个问题就变成了找到最多的数使其加和能被 3 整除，在此基础上对数码们排个序
先 DP 再贪心，简单的 dp 方案很显然，dpi 表示选了 i 及 i 之前的数，且余数为 k(0, 1, 2)的前提下，最多能选几个数
初始 dpi % 3] = 1，其他为 -1（不可达）
问题是这么 dp 不好找方案，还得维护个数组记录当前这个数从哪来的
遇到了几个坑
- 前导零，这个预判到了，但是方案错了，一开始先 parse 再转回来，但是稍微大点的数这个方案就不能用了
多方案，比如会出现用 2 替换 8 的情况（因为%3 都相等），要在 dp 的时候特判。因为是完全等价的，所以这块可以贪心的看当前的数码就行。
- 这个死活调不出来，不知道哪里出问题了，最后选择对数码排个序
N^2卡的很紧，因为数据范围是10^4 我本来以为常数小，但是被卡 T 了一个点，在这个时候我去看正解是 nlog的，非常伤心。但是我相信我能卡进去！
- 第一步是做一点优化，发现 0、3、6、9只要有解就要加进去， 所以我们先把 0、3、6 抽出来，最后统一加，加了这个优化的结果是被一个没有0369的卡了
- 第二步是初始化 vec 的大小
- 第三步是大无语事件发生了，我把算法丢给gpt，想让它帮我卡常，结果他直接丢了个正解给我，显得我很呆
- 算了，最后也没卡过去，但是过了绝大多数的点, 没过去的点直接run都卡到400多ms了，不知道为什么submit就过不去
impl Solution {
pub fn largest_multiple_of_three(digits: Vec<i32>) -> String {
let threes: Vec<i32> = digits.iter().cloned().filter(|&x| x % 3 == 0).collect();
let mut digits: Vec<i32> = digits.into_iter().filter(|&x| x % 3 != 0).collect();
digits.sort_unstable_by_key(|a| -a);
let n = digits.len();
let mut dp = vec![vec![-1; 3]; n+1];
let mut from = vec![vec![(n, 0); 3]; n+1];
for i in 0..n {
dp[i][digits[i] as usize % 3] = 1;
for j in 0..i {
for k in 0..3 {
let to = (digits[i] as usize + k) % 3;
if dp[j][k] == -1 {
continue;
}
if dp[i][to] < dp[j][k] + 1 {
dp[i][to] = dp[j][k] + 1;
from[i][to] = (j, k);
}
}
}
}
let mut maxn = (0..n).max_by_key(|&i| (dp[i][0], digits[i])).unwrap_or(0);
if dp[maxn][0] == -1 {
if threes.len() == 0 {
return "".to_string();
}
maxn = n;
}
let mut res = Vec::with_capacity((dp[maxn][0] + threes.len() as i32) as usize);
let mut cur = 0;
while maxn < n {
let last = from[maxn][cur];
res.push(digits[maxn]);
maxn = last.0;
cur = last.1;
}
res.extend(threes);
res.sort_unstable_by(|a, b| b.cmp(a));
println!("{:?}", res);
if res[0] == 0 {
return "0".to_string();
}
res
.into_iter()
.map(|i| i.to_string())
.collect()
}
}
评论 (0)