Algorithm
lc2106_摘水果
思路:
贪心摘水果，就算左右两边都要走，也只会回头一次，否则走了多余的步数。
而且最远左右k步，带折返那边不能超过k/2步。
所以可以遍历所有步行情况，贪心选择最大值。
发现和题解一思路一致，顺便学习一下题解二的滑动区间法。
题解
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
|
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int n = fruits.size();
vector<int> sum(n + 1);
vector<int> indices(n);
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + fruits[i][1];
indices[i] = fruits[i][0];
}
int ans = 0;
for (int x = 0; x <= k / 2; x++) {
/* 向左走 x 步，再向右走 k - x 步 */
int y = k - 2 * x;
int left = startPos - x;
int right = startPos + y;
int start = lower_bound(indices.begin(), indices.end(), left) - indices.begin();
int end = upper_bound(indices.begin(), indices.end(), right) - indices.begin();
ans = max(ans, sum[end] - sum[start]);
/* 向右走 x 步，再向左走 k - x 步 */
y = k - 2 * x;
left = startPos - y;
right = startPos + x;
start = lower_bound(indices.begin(), indices.end(), left) - indices.begin();
end = upper_bound(indices.begin(), indices.end(), right) - indices.begin();
ans = max(ans, sum[end] - sum[start]);
}
return ans;
}
};
|
滑动区间法:
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
|
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int left = 0;
int right = 0;
int n = fruits.size();
int sum = 0;
int ans = 0;
auto step = [&](int left, int right) -> int {
if (fruits[right][0] <= startPos) {
return startPos - fruits[left][0];
} else if (fruits[left][0] >= startPos) {
return fruits[right][0] - startPos;
} else {
return min(abs(startPos - fruits[right][0]), abs(startPos - fruits[left][0])) + \
fruits[right][0] - fruits[left][0];
}
};
// 每次固定住窗口右边界
while (right < n) {
sum += fruits[right][1];
// 移动左边界
while (left <= right && step(left, right) > k) {
sum -= fruits[left][1];
left++;
}
ans = max(ans, sum);
right++;
}
return ans;
}
};
|
Review
How to get rich?
- 对赚钱有接近病态地痴迷 –> 你愿意牺牲多少生活时间
- 把90%的时间放在赚钱和如何变富上 –> 无法大富的 full time job 和 电视剧 都会减少你的时间投入！
花多少时间致富，你就会变成多富有的样子。
要么降低预期，要么增加投入。
Tip
Crypto Technology Will Eventually Dominate Finance_Interview with Backpack Founder Armani Ferrante
阿玛尼·费兰特：我希望加密货币能被每个人掌握，让世界上尽可能多的人都能参与其中。
我认为这是必然的。我认为这只是时间的推移，是人类解决难题、技术进步和产品改进的过程。
坦率地说，世代更替，年轻人接触加密货币对他们来说很自然。这很合理。
你知道，无论是千禧一代的 Z 世代还是 Alpha 世代，我们这一代人，随着年龄的增长，在世界上的占比越来越大。
加密货币会越来越普及，最终所有金融领域都会以有意义的方式使用加密货币。
在那样的世界里，我们可以参与其中，成为这种增长的一部分，成为这些产品的一部分，
成为传播加密货币、解决问题并希望改变世界的人的一部分。
我认为金融世界看起来非常不同，开创这个时代的团队将有助于重塑所有基础设施的结构。
所以，我认为成为你的主要金融服务提供商是最终目标。
Share
Neutral Trade 深度解析_Solana 生态的机构级 DeFi 投资平台