代码随想录算法训练营第二十七天 | 122、55、45、1005

算法
, , ,

122. 买卖股票的最佳时机 II

1
2
3
4
5
6
7
8
9
10
11
12
package main

func maxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}

55. 跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

func canJump(nums []int) bool {
    maxReach := 0
    n := len(nums)
    for i := 0; i < n; i++ {
        if i > maxReach {
            return false
        }
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
        if maxReach >= n-1 {
            return true
        }
    }
    return maxReach >= n-1
}

45. 跳跃游戏 II

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
package main

func jump(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }
    jumps := 0
    currentEnd := 0
    maxFar := 0
    for i := 0; i < n-1; i++ {
        if i+nums[i] > maxFar {
            maxFar = i + nums[i]
        }
        if i == currentEnd {
            jumps++
            currentEnd = maxFar
            if currentEnd >= n-1 {
                break
            }
        }
    }
    return jumps
}

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

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
package main

import (
    "math"
    "sort"
)

func largestSumAfterKNegations(nums []int, K int) int {
    sort.Ints(nums)
    sum := 0
    minVal := math.MaxInt32
    for i := 0; i < len(nums); i++ {
        if K > 0 && nums[i] < 0 {
            nums[i] = -nums[i]
            K--
        }
        sum += nums[i]
        if nums[i] < minVal {
            minVal = nums[i]
        }
    }
    if K%2 == 1 {
        sum -= 2 * minVal
    }
    return sum
}