前言

思路及算法思维，指路 代码随想录。
题目来自 LeetCode。

day 32，一个不上班的周六，坚持一了一点~

题目详情

[122] 买卖股票的最佳时机II

题目描述

122 买卖股票的最佳时机II

解题思路

前提：求最大利润
思路：把利润分解为每天为单位的维度，取每天正利润之和。
重点：贪心算法 整体拆分部分。

代码实现

C语言

拆分为每天利润

int maxProfit(int* prices, int pricesSize) {
    int max = 0;
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] > prices[i - 1]) {
            max += (prices[i] - prices[i - 1]);
        }
    }
    return max;
}

[55] 跳跃游戏

题目描述

55 跳跃游戏

解题思路

前提：最远距离
思路：每次跳跃最远距离，判断是否可以到数组结尾
重点：贪心算法。

代码实现

C语言

for循环数组，判断最远距离

bool canJump(int* nums, int numsSize) {
    int max = 0;
    for (int i = 0; i < numsSize; i++) {
        if (max < i) {
            break;
        }
        if ((nums[i] + i) > max) {
            max = nums[i] + i;
        }
    }
    if (max < (numsSize - 1)) {
        return false;
    }
    return true;
}

for循环当前最远距离，判断是否包含数组结尾

bool canJump(int* nums, int numsSize) {
    int max = 0;
    // 注意for循环退出条件为 >=
    for (int i = 0; i <= max; i++) {
        if ((nums[i] + i) > max) {
            max = nums[i] + i;
        }
        if (max >= (numsSize - 1)) {
            return true;
        }
    }
    return false;
}

[45] 跳跃游戏II

题目描述

45 跳跃游戏II

解题思路

前提：题目保证可以到达 nums[n-1]
思路：保存前一步最远范围与当前一步的最远范围，如果当前已为前一步的最远范围，步数加一。
重点：判断是否为前一步的最远位置，步数加一的理解。

代码实现

C语言

判断当前步数范围是否到到达数组结尾

需要单独处理一个元素的情况

int jump(int* nums, int numsSize) {
    int count = 0;
    int curMax = 0;
    int preMax = 0;
    // 单独处理一个元素情况
    if (numsSize == 1) {
        return count;
    }
    // 多个元素
    for (int i = 0; i < numsSize; i++) {
        if (curMax < (nums[i] + i)) {
            curMax = nums[i] + i;
        }
        if (i >= preMax) {
            count++;
            preMax = curMax;
            if (curMax >= (numsSize - 1)) {
                break;
            }
        }
        
    }
    return count;
}

处理前numsSize – 1个元素，最后判断是否需要最后多加一步

将问题转化为前numsSize – 1个元素 和

int jump(int* nums, int numsSize) {
    int count = 0;
    int curMax = 0;
    int preMax = 0;
    // 处理前 numsSize - 1 个元素, 判断是否需要最后一步
    for (int i = 0; i < numsSize - 1; i++) {
        if (curMax < (nums[i] + i)) {
            curMax = nums[i] + i;
        }
        if (i == preMax) {
            // 跳到当前最远处需要步数+1
            count++;
            // 更新最远下标
            preMax = curMax;
        }
    }
    return count;
}

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

题目描述

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

解题思路

前提：数组
思路：优先负数取反，未取到k次, 两两抵消后，将绝对值最小的正值取反。
重点：两次贪心。

代码实现

C语言

数组大小排序

注意临界导致数组溢出

int cmp(void *p1, void *p2)
{
return (*(int *)p1 > *(int *)p2);
}
int sum(int *nums, int numsSize)
{
int sum = 0;
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
}
return sum;
}
int largestSumAfterKNegations(int* nums, int numsSize, int k) {
// 排序
qsort(nums, numsSize, sizeof(int), cmp);
// 取反, 优先负数取整
int zeroIdx = 0;
int curIdx = 0;
while ((k > 0) && (curIdx < numsSize) && (nums[curIdx] < 0)) {
nums[curIdx] = 0 - nums[curIdx];
curIdx++;
k--;
}
// 判断是否未取到k次, 两两抵消后，将绝对值最小的正值取反
if (k % 2 != 0) {
if ((curIdx == 0) || (numsSize == 1)) {
nums[0] = 0 - nums[0];
}
else if (curIdx == numsSize) {
nums[curIdx - 1] = 0 - nums[curIdx - 1];
}
else
{
if (nums[curIdx] <= nums[curIdx - 1]) {
nums[curIdx] = 0 - nums[curIdx];
}
else
{
nums[curIdx - 1] = 0 - nums[curIdx - 1];
}
}
}
return sum(nums, numsSize);
}

数组绝对值大小排序

int cmp(void *p1, void *p2)
{
return abs(*(int *)p1) < abs(*(int *)p2);
}
int sum(int *nums, int numsSize)
{
int sum = 0;
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
}
return sum;
}
int largestSumAfterKNegations(int* nums, int numsSize, int k) {
// 按绝对值从大到小排序
qsort(nums, numsSize, sizeof(int), cmp);
// 将前k个负数取正
for (int j = 0; j < numsSize; j++) {
if (k == 0) {
break;
}
if (nums[j] < 0) {
nums[j] = 0 - nums[j];
k--;
}
}
// k未消耗完，将绝对值最小的元素取反，即数组最后一位
if (k % 2 == 1) {
nums[numsSize - 1] = 0 - nums[numsSize - 1];
}
// 求和
return sum(nums, numsSize);
}

今日收获

1. 贪心算法：不太容易想到的解决方式。