Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (28) 盛最多水的容器 跳跃游戏 扑克牌中的顺子 两个数组的交集

发表于 更新于 分类于

盛最多水的容器

盛最多水的容器

解题思路

  1. 暴力解法，双层for循环

  2. 双指针法，设立两个指针left和right分别指向左右边界，水槽板高度分别为height[left]和height[right]。那么可容纳水的高度由两个板中的短板决定。在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度-1：

    • 若向内移动短板，水槽的短板可能变大，因此下个水槽的面积可能增大
    • 若向内移动长，水槽的短板不变或者变小，因此下个水槽的面积一定减小

    因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

解题算法

双指针法：

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
func maxArea(height []int) int {
    res := 0    // 容纳水的最大值
    left, right := 0, len(height)-1     // right和left为两条线的左右边界
    
    for left < right {
        if height[left] < height[right] {
            res = max(res, height[left]*(right-left))
            left++
        } else {
            res = max(res, height[right]*(right-left))
            right--
        }
    }

    return res

}

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

跳跃游戏

跳跃游戏

解题思路

  1. 用一个数组accessible[i]来记录第i个下标的可达性，从前向后遍历数组，同时更新accessible，判断是否可以到达最后一个位置。
  2. 如果一个位置能够到达，那么这个位置左侧所有位置都能到达。所以记录前n-1个元素能够到达的最远下标为k，那么就考察这个最远下标是否可以达到最后一个元素即可。

解题代码

  1. 用数组记录下标的可达性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func canJump(nums []int) bool {
    accessible := make([]bool, len(nums))
    accessible[0] = true

    for i := 0; i < len(nums); i++ {
        if accessible[i] {
            // 如果第i个位置是可达的
            for j := 1; i+j < len(nums) && j <= nums[i]; j++ {
                // 从当前位置开始可以到达的每一个下标都设置为可达的
                accessible[i+j] = true
            }
            if accessible[len(nums)-1] {
                // 如果最后一个位置可达
                return true
            }
        }
    }

    return false
}
  1. 如果一个位置能够到达，那么这个位置左侧所有位置都能到达：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func canJump(nums []int) bool {
    k := 0  // 记录前n-1个元素可以到达的最远下标
    for i := 0; i <= k; i++ {
        k = max(k, i+nums[i])   // i+nums[i]为当前位置可以到达的最远下标
        if k >= len(nums)-1 {
            // 可以走到最后一个位置
            return true
        }
    }

    return false
}

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

扑克牌中的顺子

扑克牌中的顺子

解题思路

  • 首先进行排序

  • 计算大小王的个数

  • 从最后一张大小王的下下张牌开始，逐张判断：

    • 与上一张牌相同：一定不是顺子
    • 与比上一张牌大，但是不构成顺子，有足够的大小王可以代替：减去用掉的大小王数量，跳过判断下一张牌
    • 没有足够的大小王：一定不是顺子
    • 比上一张牌大1点：与上一张牌构成顺子，对下一张牌进行判断

  • 可以完整跳出循环，说明是顺子

解题代码

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 isStraight(nums []int) bool {
    // 首先进行排序
    sort.Ints(nums)
    // 计算0(大小王)的个数
    zeroNum := 0
    for i := 0; i < len(nums) && nums[i] == 0; i++ {
        zeroNum++
    }
    // 从最后一张0的下下张牌开始，计算是否为顺子
    for i := zeroNum+1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            // 与上一张牌相等，一定不是顺子
            return false
        } else if nums[i] > nums[i-1]+1 && zeroNum >= nums[i]-nums[i-1]-1 {
            // 与比上一张牌大，但是不构成顺子，有足够的0可以代替
            zeroNum -= nums[i]-nums[i-1]-1
        } else if nums[i] > nums[i-1]+1 {
            // 没有足够的0代替
            return false
        }
    }

    return true
}

两个数组的交集

两个数组的交集

解题思路

利用哈希表记录nums中元素的情况，false代表还没有加入到结果集中，true代表已经加入到结果集中。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func intersection(nums1 []int, nums2 []int) []int {
    hashMap := map[int]bool{}      // 记录nums中元素的情况，false代表还没有加入到结果集中，true代表已经加入到结果集中
    res := make([]int, 0)       // 结果集
    // 记录nums1的元素情况
    for _, num := range nums1 {
        hashMap[num] = false
    }
    for _, num := range nums2 {
        if isRecord, ok := hashMap[num]; ok && !isRecord {
            // 找到交集，并且还未记录到结果中
            res = append(res, num)
            hashMap[num] = true
        }
    }

    return res
}