代码随想录算法训练营第51期第28天 | 122. 交易股票的最佳机会 II、55. 跳跃游戏、45. 跳跃游戏 II、1005.K次取反后最大化的数组和

122. 交易股票的最佳机会 II

122. 交易股票的最佳机会 II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/1.我刚刚看了一下之前用C++写题的时间，自己说了句【我好像记得这道题是怎么写的，也不知道是福是祸】会心一笑，好像不是坏事，过了这么久了，我照旧记得，阐明我会呀
2.很简朴哈，就是搜集区间为正数的逐日收入，加起来就行了，有一说一，这个是不是画个坐标系，然后统计每个上升区间的差值就可以了

1. int maxProfit(int* prices, int pricesSize) {
2.     int res = 0;
3.     for (int i = 1; i < pricesSize; i++) {
4.         // int money = *(prices + i) - *(prices + i - 1);
5.         int money = prices[i] - prices[i-1];
6.         if (money > 0) {
7.             res += money;
8.         }
9.     }
10.     return res;
11. }

复制代码

55. 跳跃游戏

55. 跳跃游戏

https://leetcode.cn/problems/jump-game/1.有点尴尬，看之前的blog的时间，不鉴戒看到范围两个字，好吧，我知道怎么写了
2.这题的关键在于覆盖范围，当覆盖范围到达数组长度的时间，就是返回true的时间了，一旦没有到达覆盖范围，则return false
3.我把卡哥的代码也放进来，我以为更轻便一些
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），团体最优解：末了得到团体最大覆盖范围，看是否能到止境。

1. bool canJump(int* nums, int numsSize) {
2.     int range = *nums;
3.     int tmp = 0;
4.     for (int i = 1; i < numsSize; i++) {
5.         if (i <= range) {
6.             tmp = nums[i] + i;
7.             if (tmp > range) {
8.                 range = tmp;
9.                 if (range > numsSize -1){
10.                     return true;
11.                 }
12.             }
13.         }else{
14.             return false;
15.         }
16.     }
17.     return true;
18. }
20. #define max(a, b) (((a) > (b)) ? (a) : (b))
22. bool canJump(int* nums, int numsSize){
23.     int cover = 0;
25.     int i;
26.     // 只可能获取cover范围中的步数，所以i<=cover
27.     for(i = 0; i <= cover; ++i) {
28.         // 更新cover为从i出发能到达的最大值/cover的值中较大值
29.         cover = max(i + nums[i], cover);
31.         // 若更新后cover可以到达最后的元素，返回true
32.         if(cover >= numsSize - 1)
33.             return true;
34.     }
36.     return false;
37. }

复制代码

45. 跳跃游戏 II

1.打眼一看，这道题应该用动态规划会更好做一点，但是tm的我现在记不得动态规划的写法了；
2.参考文心一言的写法，懂的很惬意
3.看了一言的写法，dp也可以，无非是没有贪心高效罢了
  

1. int jump(int* nums, int numsSize) {
2.     int jumps = 0;  // 跳跃次数
3.     int currentEnd = 0;  // 当前跳跃范围的结束位置
4.     int farthest = 0;  // 在当前跳跃范围内能够到达的最远点
6.     for (int i = 0; i < numsSize - 1; i++) {  // 遍历到倒数第二个元素
7.         farthest = (farthest > i + nums[i]) ? farthest : i + nums[i];  // 更新最远点
8.         if (i == currentEnd) {  // 到达当前跳跃范围的边界
9.             jumps++;  // 进行一次新的跳跃
10.             currentEnd = farthest;  // 更新跳跃范围的结束位置为当前能够到达的最远点
11.             if (currentEnd >= numsSize - 1) {  // 如果已经能够跳到最后一个元素或更远
12.                 break;  // 提前终止循环
13.             }
14.         }
15.     }
17.     return jumps;
18. }

复制代码

       1005.K次取反后最大化的数组和

   1.以为这道题很简朴，但是怎么想都没有想出来，就是在k还没遍历完，但是全部数都是正数了，怎么处置处罚?
   2.看了一下教学，两次贪心，两次排序，茅塞顿开 !!!第一次贪心：让绝对值大的负数变正数；第二次贪心：排序之后，找数值最小的正整数举行反转
  

1. int cmp(const void* a, const void* b) {
2.     int inta = *(int *)a;
3.     int intb = *(int *)b;
4.     return inta - intb;
5. }
6. int largestSumAfterKNegations(int* nums, int numsSize, int k) {
7.     qsort(nums, numsSize, sizeof(int), cmp);
8.     int res = 0;
9.     for (int i = 0; i < numsSize; i++) {
10.         if (nums[i] < 0 && k > 0){
11.             nums[i] = -nums[i];
12.             k--;
13.         }
14.         res += nums[i];
15.     }
16.     qsort(nums, numsSize, sizeof(int), cmp);
17.     if (k % 2 == 1) {
18.         res = res - nums[0] * 2;
19.     }
20.     return res;
21. }

复制代码

  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。