Algorithm
lc1703_得到连续K个1的最少相邻交换次数
一开始以为很简单…写了如下代码，然后发现根本想不出来，然后看题解，发现是个数学公式，看了一会，有点难证明，所以暂时先放过这个公式先，投入产出比比较小
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
|
// 双指针，k个1的滑动窗口中的0的最小个数就是答案---感觉不应该是hard吧.2分钟想出来了
/*
写完WA了...21 / 116 个通过的测试用例
解答错误
输入
nums = [1,0,0,1,0,1,1,1,0,1,1]
k = 7
发现自己想得太简单了，这个案例确实没想到...
*/
func minMoves(nums []int, k int) int {
sz := len(nums)
one_cnt := 0
ans := sz
one2nums_id := make(map[int]int)
for l, r := 0, 0; r < sz; r++ {
if nums[r] == 1 {
// one_cnt从0开始，one2nums_id[0]代表第一个1的位置
one2nums_id[one_cnt] = r
one_cnt++
if one_cnt < k {
if r == sz-1 {
panic("can't find k 1's")
}
continue
}
l = one2nums_id[one_cnt-k]
if ans > r-(l-1)-k {
ans = r - (l - 1) - k
}
}
}
return ans
}
|
官方题解如下: https://leetcode.cn/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/2024008/de-dao-lian-xu-k-ge-1-de-zui-shao-xiang-mk5ws/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
static inline int min(int a, int b) {
return a < b ? a : b;
}
int minMoves(int* nums, int numsSize, int k) {
int g[numsSize], preSum[numsSize + 1];
int gSize = 0, preSumSize = 0;
preSum[preSumSize++] = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 1) {
g[gSize++] = i - gSize;
preSum[preSumSize++] = preSum[preSumSize - 1] + g[gSize - 1];
}
}
int m = gSize, res = INT_MAX;
for (int i = 0; i <= m - k; i++) {
int mid = i + k / 2;
res = min(res, (1 - k % 2) * g[mid] + \
(preSum[i + k] - preSum[mid + 1]) - \
(preSum[mid] - preSum[i]));
}
return res;
}
|
Review
【TED演讲】我生命中最艰苦的105天
面对一个艰难的目标，我们的激情，雄心很重要，但是更重要的是，我们需要真正地接受当下的每一个时刻，接受自己当前的混乱与不足，接受自己出现的放弃的念头，然后继续地努力前行，才能完成自己觉得可能完成不了的事情。
Tips
Golang三色标记混合写屏障GC模式全分析
Share-推荐书籍《财务自由之路》
感觉整体上带着读者去分析自己的财务状况，并且推心置腹地给出了很多的有见解的观点，主要让我印象深刻的有如下几点:
- 钱是很美好的东西，赚钱是对自己创造价值的一种认可，花钱是对自己的生活的一种重要的满足手段
- 一定要把有钱和很美好的事情联系起来，把没有钱和自己遇到的糟糕的事情联系起来，这样自己才会想要赚钱
- 对自己的财务状况负责，不要找外部原因，而是不断努力提升自己，去好好搞好自己的财务状况
- 花90%的时间思考自己为什么做这个事情，花10%的时间想怎么做，而不是反过来
- 因为自己是动机目的论者，不是因果论者，所以作者这个90%的思考应该怎么做，其实就是让我们想清楚自己到底想要什么，这样才能真正有动力地去实现自己目标
- 投资赚钱，投机赢钱，投资应该在你买入的时候就产生收益，投机才是卖出的时候产生收益，投资+时间=未来财务自由
- 不要杀了你下金蛋的鹅，而是先储蓄投资赚出自己的第一个下金蛋的鹅(替你赚钱的机器)
- 每个人的鹅不一样，具体看每月的固定花费是多少，然后用书中的公式去计算
- 流入金钱的资产才是投资，流出金钱的资产是负债(包括房子车子)
- 不是说不让买房车，而是要合理控制自己的资产，在有鹅之后，自住房分期在自己的多个金蛋里面分期买自住房