面试 top 150 - 数组和字符串
#LeetCode#算法#面试经典 150 题#数组和字符串 2023-12-31

数组/字符串

88. 合并两个有序数组

思路

倒序双指针。正序双指针比较会被覆盖，我们可以使用倒序。

遍历一遍数组，即可原地合并成功。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func merge(nums1 []int, m int, nums2 []int, n int)  {
    var low1, low2 = m - 1, n - 1 // 指向数组尾部的指针
    for i := m + n - 1; i >= 0; i--{
        // 将 nums2 的元素填充进 nums1 即可
        if low1 < 0{
            nums1[low2] = nums2[low2]
            low2--
            continue
        }
        // 如果 nums2 的元素已经填充完了，前面的就不用动了
        if low2 < 0{
            break
        }
        if nums1[low1] < nums2[low2]{
            nums1[i] = nums2[low2]
            low2--
        }else{
            nums1[i] = nums1[low1]
            low1--
        }
    }
}

27. 移除元素

思路

双指针，当遍历时遇到与 val 不等的值，交换元素。最后返回 low 的值即可。

代码实现

1
2
3
4
5
6
7
8
9
10
func removeElement(nums []int, val int) int {
    var low int
    for i, v := range nums{
        if v != val{
            nums[low], nums[i] = nums[i], nums[low]
            low++
        }
    }
    return low
}

26. 删除有序数组中的重复项

思路

同向双指针遍历，当我们遇到与当前元素不一致的元素时，与 low 指针指向的下一个元素调换。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
func removeDuplicates(nums []int) int {
    if len(nums) == 1{
        return len(nums)
    }
    var low int
    for i, v := range nums{
        if v != nums[low]{
           low++
           nums[low], nums[i] = nums[i], nums[low]
        }
    }
    return low + 1
}

80. 删除有序数组中的重复项 II

思路

双指针。

因为需要保留的是出现一次和两次的。我们可以从 2 开始遍历。当快指针遍历的元素，与慢指针的上两个元素不一样时，将其元素交换即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
func removeDuplicates(nums []int) int {
    if len(nums) < 3{
        return len(nums)
    }
    var low = 2
    for i := 2; i < len(nums); i++{
        if nums[i] != nums[low - 2]{
            nums[low] = nums[i]
            low++
        }
    }
    return low
}

169. 多数元素

思路

没啥好说的，哈希表

代码实现

1
2
3
4
5
6
7
8
9
10
11
func majorityElement(nums []int) int {
    var m = make(map[int]int)
    var k = len(nums) / 2
    for _, v := range nums{
        m[v]++
        if m[v] > k{
            return v
        }
    }
    return 0
}

189. 轮转数组

思路

创建一个新数组，然后根据 k 计算出当前位置元素应该是哪个下标。

为了不出现负数下标，需要将 k 与原数组长度 n 进行取模运算。

代码实现

1
2
3
4
5
6
7
8
9
func rotate(nums []int, k int)  {
    n := len(nums)
    k %= n
    var ans = make([]int, n)
    for i := range nums{
        ans[i] = nums[(n - k + i) % n]
    }
    copy(nums, ans)
}

121. 买卖股票的最佳时机

思路

可以维护一个双端队列，队头大队尾小。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxProfit(prices []int) int {
    // 维护一个双端队列
    var s []int
    var ans int
    for i := len(prices) - 1; i >= 0; i--{
        for len(s) > 0 && s[len(s) - 1] < prices[i]{
            s = s[:len(s) - 1]
        }
        if len(s) > 0{
            // 队内有元素，与对头最大的那个进行比较
            ans = max(ans, s[0] - prices[i])
        }
        s = append(s, prices[i])
    }
    return ans
}

func max(x, y int) int {
    if x < y{
        return y
    }
    return x
}

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

思路

使用动态规划。定义一个二维数组，第二维 0 -> 未买入，1 -> 买入。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxProfit(prices []int) int {
    var n = len(prices)
    var ans = make([][2]int, n)

    ans[0][1] = -prices[0] // 1 为持有

    for i := 1; i < n; i++{
        // 什么都不做，或者卖出
        ans[i][0] = max(ans[i - 1][0], ans[i - 1][1] + prices[i])
        ans[i][1] = max(ans[i - 1][1], ans[i - 1][0] - prices[i])
    }
    return ans[n - 1][0]
}


func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

55. 跳跃游戏

思路

i + nums[i]，其中，i - i + nums[i] 是可到达的下标，然后在遍历的时候动态更新最远可到达的下标。当最远可到达的下标大于最后一个下标时，返回 true 即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func canJump(nums []int) bool {
    if len(nums) == 1{
        return true
    }
    var m, n = 0, len(nums)
    for i := 0; i < len(nums) - 1; i++{
        if m < i{
            break
        }
        m = max(m, i + nums[i])
        if m >= n - 1{
            return true
        }
    }
    return false
}

func max(x,y int) int{
    if x > y{
        return x
    }
    return y
}

45. 跳跃游戏 II

思路

贪心算法。维护动态的边界和最远可到达距离，当到达边界时，代表需要的步数加一。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func jump(nums []int) int {
    var maxB, broad, ans int // 可到达的最远区域
    for i := 0; i < len(nums) - 1; i++{
        maxB = max(maxB, i + nums[i])
        if i == broad{
            broad = maxB
            ans++
        }
    }
    return ans
}

func max(x, y int) int{
    if x > y{
        return x
    }
    return y
}

274. H 指数

思路

排序法：将数组排序后，从后面开始遍历，当前元素大于 h 时，则 h 指数++，直到找到 len(c) + 1。

代码实现

1
2
3
4
5
6
7
8
func hIndex(citations []int) int {
    sort.Ints(citations)
    var h int
    for i := len(citations) - 1; i >= 0 && citations[i] > h; i--{
        h++
    }
    return h
}

380. O(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
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
51
52
type RandomizedSet struct {
    nums    []int
    indices map[int]int
}


func Constructor() RandomizedSet {
    return RandomizedSet{[]int{}, map[int]int{}}
}


func (this *RandomizedSet) Insert(val int) bool {
    _, exist := this.indices[val]
    if exist {
        return false
    }
    last := len(this.nums)
    this.indices[val] = last
    this.nums = append(this.nums, val)
    return true
}


func (this *RandomizedSet) Remove(val int) bool {
    idx, exist := this.indices[val]
    if !exist {
        // 没有该元素
        return false
    }
    last := len(this.nums) - 1
    this.indices[this.nums[last]] = idx
    delete(this.indices, idx)
    
    this.nums[idx], this.nums[last] = this.nums[last], this.nums[idx]
    this.nums = this.nums[:last]

    return true
}


func (this *RandomizedSet) GetRandom() int {
    return this.nums[rand.Intn(len(this.nums))]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

238. 除自身以外数组的乘积

思路

自身以外数组的乘积，就是当前下标左边和右边的乘积。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func productExceptSelf(nums []int) []int {
    var n = len(nums)

    var L = make([]int, n)
    L[0] = 1
    for i := 1; i < n; i++{
        L[i] = L[i - 1] * nums[i - 1]
    }

    var R = make([]int, n)
    R[n - 1] = 1
    for i := n - 2; i >= 0; i--{
        R[i] = R[i + 1] * nums[i + 1]
    }

    var ans = make([]int, n)
    for i := range nums{
        ans[i] = L[i] * R[i]
    }
    return ans
}

134. 加油站

思路

在遍历时，计算当前的开销是否支持到达下一个加油站。如果不支持，从下一个加油站开始遍历。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func canCompleteCircuit(gas []int, cost []int) int {
    for i, n := 0, len(gas); i < n; {
        var sumOfGas, sumOfCost, cnt int
        for cnt < n{
            var j = (i + cnt) % n
            sumOfGas += gas[j]
            sumOfCost += cost[j]

            if sumOfCost > sumOfGas{
                break
            }
            cnt++
        }

        if cnt == n{
            // 循环了
            return i
        }
        // 下一个不能到达的加油站
        i += cnt + 1
    }
    return -1
}