Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (21) 最长重复子数组 用队列实现栈 乘积最大子数组 买卖股票的最佳时机II

发表于 更新于 分类于

最长重复子数组

最长重复子数组

解题思路

利用动态规划的思想，dp[i][j]表示以nums1[i]和nums2[j]为结尾的最长公共后缀的长度。

  • 初始化为：
    • 若nums1[i] == nums2[0]，则dp[i][0] = 1，否则为0
    • 若nums1[0] == nums2[j]，则dp[0][j] = 1，否则为0
  • 状态转移方程：若nums1[i] == nums2[j]，dp[i][j] = dp[i-1][j-1]+1，否则为0

解题代码

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
36
37
func findLength(nums1 []int, nums2 []int) int {
    m := len(nums1)
    n := len(nums2)
    dp := make([][]int, m)      // dp[i][j]表示A的前i项与B的前j项的最长重复子数组长度
    maxLen := 0     // 最长公共子数组长度
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    // 初始化dp数组
    for i := 0; i < m; i++ {
        if nums1[i] == nums2[0] {
            dp[i][0] = 1
            maxLen = 1
        }
    }
    for j := 0; j < n; j++ {
        if nums1[0] == nums2[j] {
            dp[0][j] = 1
            maxLen = 1
        }
    }
    
    // 计算dp数组
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if nums1[i] == nums2[j] {
                dp[i][j] = dp[i-1][j-1]+1
            }
            if dp[i][j] > maxLen {
                // 更新最大长度
                maxLen = dp[i][j]
            }
        }
    }

    return maxLen
}

用队列实现栈

用队列实现栈

解题思路

一个队列为主队列，一个为辅助队列，当入栈操作时，我们先将主队列内容导入辅助队列，然后将入栈元素放入主队列队头位置，再将辅助队列内容，依次添加进主队列即可。

解题代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
type MyStack struct {
    queue1, queue2 []int
}


func Constructor() MyStack {
    return MyStack{
        queue1: make([]int, 0),
        queue2: make([]int, 0),
    }
}


func (this *MyStack) Push(x int)  {
    // 将队列1的元素依次出队，放入到队列2中
    this.moveTo2()
    // 元素入队1
    this.queue1 = append(this.queue1, x) 
    // 将队列2的元素依次出队，放入到队列1中
    this.moveTo1()
}

func (this *MyStack) moveTo2() {    // 将队列1的元素依次出队，放入到队列2中
    this.queue1, this.queue2 = this.queue2, this.queue1
}

func (this *MyStack) moveTo1() {    // 将队列2的元素依次出队，放入到队列1中
    this.queue1 = append(this.queue1, this.queue2...)
    this.queue2 = make([]int, 0)
}

func (this *MyStack) Pop() int {
    x := this.queue1[0]     // 取出队列1的队头元素
    this.queue1 = this.queue1[1:]   // 出队
    return x
}


func (this *MyStack) Top() int {
    return this.queue1[0]
}


func (this *MyStack) Empty() bool {
    if len(this.queue1) > 0 {
        return false
    } else {
        return true
    }
}

乘积最大子数组

乘积最大子数组

解题思路

  • 令curMax为当前最大值，则当前最大值为curMax = max(num, num*curMax)
  • 由于负数的存在，会导致最大的变最小的，最小的变最大的。所以还要维护当前最小值curMin，则当前最小值为curMin = min(num, num*curMin)
  • 当负数出现时则curMax与curMin交换

解题代码

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
func maxProduct(nums []int) int {
    res := math.MinInt64    // 记录最大乘积
    curMax := 1     // 当前最大乘积
    curMin := 1     // 当前最小乘积

    for _, num := range nums {
        if num < 0 {
            // 如果当前值为负数，交换当前最大、最小乘积
            curMax, curMin = curMin, curMax
        }
        curMax = max(num, num*curMax)
        curMin = min(num, num*curMin)
        if curMax > res {
            res = curMax
        }
    }

    return res
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    } else {
        return n2
    }
}

func min(n1, n2 int) int {
    if n1 < n2 {
        return n1
    } else {
        return n2
    }
}

买卖股票的最佳时机 II

买卖股票的最佳时机 II

解题思路

动态规划，定义dp[i][j]表示下标为i的的这一天，持股状态为j时（j表示下标为i的那一天是持有股票，还是持有现金，0表示持有现金，1表示持有股票），手上的最大现金数。

  • 初始值：
    • dp[0][0] = 0
    • dp[0][1] = -prices[0]
  • 状态转移方程：
    • dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxProfit(prices []int) int {
    dp := make([][]int, len(prices))
    for i :=0; i < len(dp); i++ {
        dp[i] = make([]int, 2)
    }
    // dp初始化
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    // 计算dp数组
    for i := 1; i < len(dp); i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
    }

    return dp[len(dp)-1][0]
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    } else {
        return n2
    }
}