1.合并两个有序数组

题目描述

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

1
2
3
4
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

1
2
3
4
5
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

题解

思路不多说，尾插法即可，较为简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func merge(nums1 []int, m int, nums2 []int, n int) {
	//不额外占用空间，所以就是在num1上原地修改
	ptr1, ptr2, ptr := m-1, n-1, m+n-1
	for ;ptr1 >=0 && ptr2 >= 0;{
        if nums1[ptr1]>nums2[ptr2]{
            nums1[ptr] = nums1[ptr1]
            ptr--
            ptr1--
        }else{
            nums1[ptr] = nums2[ptr2]
            ptr--
            ptr2--
        }
	}
    for ;ptr2>=0;{
        nums1[ptr] = nums2[ptr2]
        ptr--
        ptr2--
    }
}

2.移动元素

题目描述

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

1
2
3
4
5
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

题解

原地移除且允许顺序变换，那就是简单的元素位置交换，思路不多说，主要看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func removeElement(nums []int, val int) int {
    lst := len(nums)-1
    for i := 0; i<=lst; i++{
        if nums[i] != val {
            continue
        }
        for {
            if lst>=0&&nums[lst]==val{
                lst--
            }else{
                break
            }
        }
        if i<lst{
            tmp := nums[i]
            nums[i] = nums[lst]
            nums[lst] = tmp
        }
    }
    return lst+1;
}

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

题目描述

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

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

1
2
3
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeDuplicates(nums []int) int {
    //特例，额外处理
    if len(nums)<=1{
        return len(nums)
    }
    //有效数字
    start := 0
    for ptr := 1; ptr<len(nums); ptr++{
        if nums[ptr]!=nums[start]{
            start++
            nums[start] = nums[ptr]
        }
    }
    return start+1
}

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

题目描述

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

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

1
2
3
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

1
2
3
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

题解

这题其实本质上和上一题相同，不过多解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeDuplicates(nums []int) int {
    if len(nums)<=2{
        return len(nums)
    }
    start := 1
    for ptr := 2; ptr<len(nums); ptr++{
        //这个对比的是start-1,不可以是ptr-2
        if nums[ptr] != nums[start-1]{
            start++
            nums[start] = nums[ptr]
        }
    }
    return start+1

}

5.多数元素

题目描述

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：nums = [3,2,3]
输出：3

示例 2：

1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题解

典型的思维题，解决方式也比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func majorityElement(nums []int) int {
    res := -1
    count := 0
    for _,val := range nums{
        if val==res{
            count++;
        }else{
            if count==0{
                res = val
                count++
            }else{
                count--
            }
        }
    }
    return res
}

6.轮转数组

题目描述

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

题解

其实这也是个思维题，我们可以尝试用呆板的方式解决，或者也可以用trick，这里两种题解都放一下

Trick解法：翻转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
func reverse(nums []int, start int, end int){
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}
func rotate(nums []int, k int)  {
    k = k%len(nums)
    reverse(nums,0,len(nums)-1)
    reverse(nums,0,k-1)
    reverse(nums,k,len(nums)-1)
}

写到这里其实已经很感觉出来go是个很简洁的语言了，主要感觉还是有一些库啥的不太熟练，比如我就不知道go有没有优先级队列

传统解法，看似呆瓜实际全是技巧

听我说，这种方法真的写起来很累，真的很累

同时写到这里的时候，我发现一个问题

在 Go 中，:= 是短变量声明操作符，用于在同一作用域内声明并初始化变量。Go 的设计允许在嵌套作用域（如循环块、条件块等）中重复使用 := 声明同名变量，但需要注意：

  • 在 Go 中，变量的作用域由其声明的位置决定。
  • 如果在一个嵌套作用域（如循环体或条件块）中使用 := 声明一个与外部作用域同名的变量，则会屏蔽（shadow） 外部作用域中的变量。
  • 当嵌套作用域结束时，屏蔽效果消失，外部作用域的变量重新可见。
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
func rotate(nums []int, k int)  {
    n := len(nums)
    if n<=1{
        return
    }
    k = k%n
    start := 0
  	//记录安置好的元素个数
    count := 0
  	//从第一个开始安置
    ptr := start
    for count<len(nums){
        ptr = (ptr+k)%n
        if ptr == start{
          	//第start圈循环的最后一个，安置到start位置
          	//记得安置完数目+1
            count++
            start++
            ptr = start
            continue
        }
        tmp := nums[start]
        nums[start] = nums[ptr]
        nums[ptr] = tmp
        count++
    }
}

7.买卖股票的最佳时机

121. 买卖股票的最佳时机

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

题解

经典题，go不提供Max的比较方式，同时，MaxInt、MinInt是在math包下

1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int) int {
    preMin := math.MaxInt
    res := math.MinInt
    for _,value := range prices{
        if value<preMin{
            preMin = value
        }
        if res<value-preMin{
            res = value-preMin
        }
    }
    return res
}

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

题目描述

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

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

题解

我不喜欢用贪心的思路去做，所以还是用dp做了

注意go初始化二维切片的时候，第一次make其实只初始化了第一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func max(num1, num2 int) int{
    if num1>num2 {
        return num1
    }else{
        return num2
    }
}

func maxProfit(prices []int) int {
    //只初始化了第一维，每个子数组其实还是nil，第一次使用的时候要手动初始化
    dp := make([][]int,len(prices))
    dp[0] = make([]int,2)
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    res := 0
    for i := 1; i<len(prices); i++{
        dp[i] = make([]int,2)
        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])
        res = max(dp[i][0],res)
    }
    return res
}

9.跳跃游戏

题目描述

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

题解

1
2
3
4
5
6
7
8
9
func canJump(nums []int) bool {
    max := 0
    for pre :=0; pre<=max&&pre<len(nums); pre++{
        if pre + nums[pre] > max {
            max = pre + nums[pre]
        }
    }
    return max>=len(nums)-1
}

10.跳跃游戏II

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

题解

典型的dp问题了，不多说了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func jump(nums []int) int {
    end := 0
    maxPos := 0
    res := 0
    for index, value := range nums{
        if index + value > maxPos {
            maxPos = index + value
        }
        if index == end && index<len(nums)-1 {
            end = maxPos
            res++
        }
    }
    return res
}

看官解的思路很怪，这是我原本的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int jump(int[] nums) {
        int res[] =new int[nums.length];
        res[0]=0;
        int j=0;
        for(int i=1;i<nums.length;i++){
            while(nums[j]+j<i){
                j++;
            }
            res[i]=res[j]+1;
        }
        return res[nums.length-1];
    }
}

再用go写一遍

1
2
3
4
5
6
7
8
9
10
11
12
func jump(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = 0
    start := 0
    for i:=1;i<len(nums);i++{
        for start+nums[start]<i{
            start++;
        }
        dp[i] = dp[start]+1
    }
    return dp[len(nums)-1]
}

11.H指数

题目描述

274. H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

1
2
输入：citations = [1,3,1]
输出：1

提示：

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

题解

这题稍微要转个弯，有两种解法，首先是排序的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func hIndex(citations []int) int {
    sort.Slice(citations,func(i, j int) bool{
        return citations[i] < citations[j]
    });
  	//当然也可以这么写
  	//sort.Ints(citations)
  	//假设全部论文都满足引用大于n，然后从头开始删除
    pre := len(citations)
    for _, value := range citations{
        if value < pre{
            pre--
        }
    }
    return pre
}

第二种思路，就是计数排序，但是需要创建额外的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func min(num1, num2 int) int{
    if num1>num2 {
        return num2
    }
    return num1
}
func hIndex(citations []int) int {
    index := make([]int, len(citations)+1)
    n := len(citations)
    for _,value := range citations{
        index[min(value,n)]+=1
    }
    sum := 0
    for i:=n; i>=0; i--{
        sum += index[i]
        if sum>= i{
            return i
        }
    }
    return 0;
}

12.O(1) 时间插入、删除和获取随机元素

题目描述

380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

  • -231 <= val <= 231 - 1
  • 最多调用 insert、remove 和 getRandom 函数 2 * ``105 次
  • 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

题解

其实这题还挺难的，首先是插入、删除操作要是O1的就得需要一个方法快速判断当前val值是否存在，如果存在在哪个位置，这点就需要我们使用一个map来实现。其次的删除O1，注意的是，数组的删除是无法做到O1的，所以我们只能采用尾部节点位置替换的思路来做。

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
type RandomizedSet struct {
    nums []int
    hash map[int]int
}


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


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


func (this *RandomizedSet) Remove(val int) bool {
    if value, exist := this.hash[val]; exist{
        lst := len(this.nums)-1
        this.nums[value] = this.nums[lst]
        this.hash[this.nums[value]] = value
        delete(this.hash, val)
        this.nums = this.nums[:lst]
        return true
    }
    return false
}


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();
 */

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

题目描述

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 输入 保证 数组 answer[i] 在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

题解

笑了，这leetCode说的O(1)额外复杂度，意思是除了返回数组之外的，不让用除法就是两个list，分别是左边和右边的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func productExceptSelf(nums []int) []int {
    //返回数组，接下来我们用它来保存左边的乘积
    res := make([]int, len(nums))
    res[0] = 1
    pre := nums[0]
    for i := 1; i< len(nums); i++ {
        res[i] = pre
        pre = pre * nums[i]
    }
    //接下来修改原数组，用原数组保存右边的乘积
    lst := nums[len(nums)-1]
    nums[len(nums)-1] = 1
    for i := len(nums)-2; i>=0; i-- {
        tmp := lst
        lst = lst * nums[i]
      	//这里不能写lst/nums[i]的原因主要是可能/0
        nums[i] = tmp
    }
    for i := 0; i<len(nums); i++ {
        res[i] *= nums[i]
    }
    return res
}

14.加油站

题目描述

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

题解

这题其实问题在于如何剪枝，举个例子，如果从0出发醉多可以到达k，那么从0-k之内任何点出发，最多也只可以到达k，所以这时候下一个出发点就可以直接考虑k+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
func canCompleteCircuit(gas []int, cost []int) int {
    //假设我们的起点是0
    start := 0
    n := len(gas)
    for start<n {
        end := start
        rest := gas[start]
        //只要油还够，就能往前走了
        for rest>= cost[end]{
            rest = rest - cost[end] + gas[(end+1)%n]
            end = (end + 1) % n
            //如果到达起点，证明能环绕
            if end==start{
                return start
            }
        }
        //如果到达点在起点前，就一定无法抵达了，因为从0到起点-1出发都是不不能环绕的，起点到n也是不能环绕的
        if end < start{
            return -1
        } else {
            //更换剪枝后的新起点
            start = end + 1
        }
    }
    return -1
}

15.分发糖果

题目描述

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

1
2
3
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

1
2
3
4
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

题解

标准贪心，左边右边各贪一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func candy(ratings []int) int {
    //我个人喜欢定义一个数组走两遍，而不是定义俩数组
    res := make([]int, len(ratings))
    res[0] = 1
    for i := 1; i<len(ratings); i++{
        if ratings[i]>ratings[i-1]{
            res[i] = res[i-1]+1
        }else{
            res[i] = 1
        }
    }
    sum := res[len(ratings)-1]
    for i := len(ratings)-2; i>=0; i--{
        if ratings[i] > ratings[i+1] && res[i]<res[i+1]+1{
            res[i] = res[i+1]+1
        }
        sum += res[i]
    }
    return sum
}

16.接雨水

题目描述

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

题解

标准双指针问题

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 max(num1, num2 int) int{
    if num1<num2{
        return num2
    }
    return num1
}
func trap(height []int) int {
    left := 0
    right := len(height) - 1
    leftMax := 0
    rightMax := 0
    sum := 0
    for left<=right {
        if height[left]<=height[right]{
            leftMax = max(height[left],leftMax)
            sum += leftMax - height[left]
            left++
        }else{
            rightMax = max(height[right],rightMax)
            sum += rightMax - height[right]
            right--
        }
    }
    return sum
}

17.罗马数字转整数

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

1
2
输入: s = "III"
输出: 3

示例 2:

1
2
输入: s = "IV"
输出: 4

示例 3:

1
2
输入: s = "IX"
输出: 9

示例 4:

1
2
3
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= s.length <= 15
  • s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
  • 关于罗马数字的详尽书写规则，可以参考 罗马数字 - 百度百科。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func romanToInt(s string) int {
    res := map[byte]int{'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
    sum := 0
    for i:= 0; i<len(s); i++{
        if i==len(s)-1 {
            sum+=res[s[i]]
            break
        }
        if res[s[i]]<res[s[i+1]]{
            sum -= res[s[i]]
        }else {
            sum += res[s[i]]
        }
    }
    return sum
}

18.整数转罗马数字

题目描述

12. 整数转罗马数字

七个不同的符号代表罗马数字，其值如下：

符号 值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

  • 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
  • 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
  • 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

**输入：**num = 3749

输出： “MMMDCCXLIX”

解释：

1
2
3
4
5
3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  40 = XL 由于 50 (L) 减 10 (X)
   9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

**输入：**num = 58

输出：“LVIII”

解释：

1
2
50 = L
 8 = VIII

示例 3：

**输入：**num = 1994

输出：“MCMXCIV”

解释：

1
2
3
4
1000 = M
 900 = CM
  90 = XC
   4 = IV

提示：

  • 1 <= num <= 3999

题解

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
func intToRoman(num int) string {
    //说实话，感觉这个题目纯是逆天题目
    //但是还有个细节要讲，这里不能定义map来存对应关系
    //因为go的map底层是真无序，也不能说无序，是按照hash序
    //严格来说，要么定义两个数组，要么定义一个结构体数组
    res := []struct{
        value int
        symbol string
    }{{1000,"M"},
        {900,"CM"},
        {500,"D"},
        {400,"CD"},
        {100,"C"},
        {90,"XC"},
        {50,"L"},
        {40,"XL"},
        {10,"X"},
        {9,"IX"},
        {5,"V"},
        {4,"IV"},
        {1,"I"}}
    str := ""
    for num>0 {
        for _,st := range res{
            for num>=st.value{
                num -= st.value
                str += st.symbol
            }
        }
    }
    return str
}

19.最后一个单词的长度

题目描述

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

1
2
3
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

1
2
3
输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

1
2
3
输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

提示：

  • 1 <= s.length <= 104
  • s 仅有英文字母和空格 ' ' 组成
  • s 中至少存在一个单词

题解

1
2
3
4
5
6
7
8
9
func lengthOfLastWord(s string) int {
    //这题其实是一个很简单的题，问题就是在于go有没有提供对string 的strip和slipt方法
    //strings包提供了一些操作，包括TrimSpace和Trim操作
    //同时strings也提供了Split方法
    s = strings.Trim(s, " ")
    sSplit := strings.Split(s," ")
    n := len(sSplit)-1
    return len(sSplit[n])
}

当然其实这题的本意肯定不是调库，搓一下吧

1
2
3
4
5
6
7
8
9
10
11
func lengthOfLastWord(s string) int {
    start := len(s)-1
    for s[start]==' '{
        start--
    }
    end := start
    for end>=0&&s[end]!=' '{
        end--
    }
    return start-end
}

20.最长公共前缀

题目描述

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 如果非空，则仅由小写英文字母组成

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func min(num1, num2 int) int{
    if num1 > num2 {
        return num2
    }
    return num1
}
func longestCommonPrefix(strs []string) string {
    res := ""
    n := math.MaxInt
    for _, str := range strs{
        n = min(n,len(str))
    }
    for i:=0;i<n;i++{
        b := strs[0][i]
        for _,str := range strs{
            if str[i] != b{
                return res
            }
        }
        res = res+string(b)
    }
    return res
}