lc3266_K次乘运算后的最终数组II 千万不要放弃对自己财务的控制【TED演讲】 绕过cursor单机免费次数限制 md笔记图片位置思考
Algorithm
lc3266_K次乘运算后的最终数组II
思路:
这题暴力解法 O(n*k) 必定超时。
肯定是需要维护原来的数组和数组下标的绑定结构体里面，然后结构体根据值动态排序。
这样就可以 O(k*logn) 的复杂度进行计算，计算取模10^9 + 7完之后按照下标填入原来的下标位置即可。
但是 k 本身就有 1e9, 所以 O(k*logn) 的复杂度还是太大了。
可能还需要更多优化。–可能这里涉及什么数学规律。
注意还得使用 long long 防止溢出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
impl Solution {
pub fn get_final_state(nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
let n = nums.len();
let mut pairs: Vec<(i64, usize)> = nums.into_iter()
.enumerate()
.map(|(i, x)| (x as i64, i))
.collect();
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
for pair in pairs.iter() {
// 使用元组比较规则: 先比较第一个元素,相等时比较第二个元素
// 这里用负数实现最小堆,所以第二个元素也要取负来实现最小index优先
heap.push((-pair.0, -(pair.1 as i64)));
}
for _ in 0..k {
if let Some((val, idx)) = heap.pop() {
let new_val = (-val * multiplier as i64) % 1000000007;
heap.push((-new_val, idx));
}
}
// Convert heap back to pairs
let mut result = vec![0; n];
while let Some((val, idx)) = heap.pop() {
result[-idx as usize] = (-val) as i32;
}
result
}
}
|
确实超出时间限制了:
503 / 694 个通过的测试用例
最后执行的输入
nums = [66307295,441787703,589039035,322281864]
k = 900900704
multiplier = 641725
确实有数学论证的循环，具体的见题解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
fn quick_mul(x: i64, y: i64, m: i64) -> i64 {
let mut res = 1;
let mut x = x;
let mut y = y;
while y > 0 {
if y % 2 == 1 {
res = (res * x) % m;
}
x = (x * x) % m;
y /= 2;
}
res
}
pub fn get_final_state(nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
if multiplier == 1 {
return nums;
}
let n = nums.len();
let m = 1_000_000_007;
let mx = *nums.iter().max().unwrap() as i64;
let mut v: BinaryHeap<Reverse<(i64, usize)>> = nums.into_iter()
.enumerate()
.map(|(i, num)| Reverse((num as i64, i)))
.collect();
let mut k = k as i64;
while let Some(Reverse((val, _))) = v.peek() {
if *val >= mx || k == 0 {
break;
}
let Reverse((mut min_val, idx)) = v.pop().unwrap();
min_val *= multiplier as i64;
v.push(Reverse((min_val, idx)));
k -= 1;
}
let mut result = vec![0; n];
let mut vec_v = v.into_vec();
vec_v.sort_unstable_by_key(|Reverse((val, idx))| (*val, *idx));
for (i, Reverse((val, idx))) in vec_v.iter().enumerate() {
let t = k / n as i64 + if (i as i64) < k % n as i64 { 1 } else { 0 };
result[*idx] = ((val % m) * Solution::quick_mul(multiplier as i64, t, m) % m) as i32;
}
result
}
}
|
Review
千万不要放弃对自己财务的控制【TED演讲】
经济自由决定人生自由，永远不要放弃经济管理权。
Tips
绕过cursor单机免费次数限制
Share_md笔记图片位置思考
以前自己写markdown笔记是把图片放在文档的那个层级的目录上面，方便简洁。
后面因为自己做静态网站，把网站图片搞成图床，于是就习惯上了用 assets 目录归集所有图片。
这样对博文来说是ok的，但是对于频繁写入和更改的笔记来说，图片每次都要选择位置，很麻烦。
因此笔记的图片可以直接放在文档那个层级的目录里。
其实就算后面还要做图床，也可以直接利用以下方法导出所有的图片:
遍历全路径的 .jpg 和 .png, 然后 mkdir -p 来恢复目录层级。
(可选): 最后再扫一遍 assets 目录，把图移动到父目录，然后删除一些多余的 assets 目录就行了。