不做大哥好多年
目录

01.数组

# 01.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标
你可以假设每种输入只会对应一个答案但是，数组中同一个元素不能使用两遍
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
1
2
3
4
5
6

# 1、python

class Solution:
    def twoSum(self, nums, target):
        dic = {}
        for k, v in enumerate(nums):
            if target - v in dic:  # 证明字典中存在一个value与当前value和等于target
                return [dic[target - v], k]
            dic[v] = k

nums = [2,11,15,3,6,7]
target = 9
Solution().twoSum(nums, target) # 3 4
1
2
3
4
5
6
7
8
9
10
11

# 2、golang

package main

import "fmt"

func twoSum(nums []int, target int) []int {
	tmpMap := map[int]int{}
	for index, num := range nums {
		_,ok := tmpMap[target-num]
		if ok {  // 证明字典中存在一个value与当前value和等于target
			return []int{tmpMap[target-num], index}  // 返回这两个值的索引
		}
		tmpMap[num] = index
	}
	return []int{}
}

func main()  {
	nums := []int{2,7,11,15}
	target := 9
	li := twoSum(nums, target)
	fmt.Println(li)  // [0,1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 02.最大子数组和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6
1
2
3

# 1、python

  • 基本思路就是遍历一遍，用两个变量，一个记录最大的和，一个记录当前的和
  • 如果当前和小于0，当前最长序列到此为止以该元素为起点继续找最大子序列
  • 时空复杂度貌似还不错......（时间复杂度 O(n)，空间复杂度 O(l)
def maxSub(nums):
	max_ = nums[0]  # 假设第一个为最大和
	for i in range(1, len(nums)):
		if nums[i - 1] > 0:  # 如果当前和大于0就将当前和加上当新数据，否则重新开始当前和
			nums[i] += nums[i - 1]
		max_ = max(max_, nums[i])  # 当前和 于 记录最大和比较，大的为新的最大和
	return max_

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSub(nums))  #  6 ==》[4,-1,2,1]
1
2
3
4
5
6
7
8
9
10

# 2、golang

  • 基本思路就是遍历一遍，一个记录最大的和，一个记录当前的和
  • 如果当前的和大于0，就继续加下一个元素，然后比较max，如果更大就更新max
  • 时空复杂度貌似还不错......（时间复杂度 O(n)，空间复杂度 O(l)
package main

import "fmt"

func maxSubArray(nums []int) int {
	max := nums[0]  // 假设第一个为最大和
	for i := 1; i < len(nums); i++ {
		if nums[i] + nums[i-1] > nums[i] {   // 如果nums[i-1]当前和大于0，将当前和加上当新数据，否则重新开始当前和
			nums[i] += nums[i-1]
		}
		if nums[i] > max {  // 当前和与记录最大的和比较，如果当前和更大就更新
			max = nums[i]
		}
	}
	return max
}

func main() {
	nums := []int{-2,1,-3,4,-1,2,1,-5,4}
	fmt.Println( maxSubArray(nums) )  // 6
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 03.买卖股票的最佳时机

  • 121.买卖股票的最佳时机 (opens new window)

  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格

  • 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润

  • 注意你不能在买入股票前卖出股票

输入: [7,4,6,3,1]
输出: 2
1
2

# 1、python

  • 有 买入（buy） 和 卖出（sell） 这两种状态

  • 当天买的话意味着损失 -prices[i]，当天卖的话意味着增加 prices[i]，当天卖出总的收益就是 buy+prices[i]

  • 所以我们只要考虑当天买和之前买哪个收益更高，当天卖和之前卖哪个收益更高

    • buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）
    • sell = max(sell, prices[i] + buy)
s = [7,4,6,3,1]

def maxProfit(prices):
    if len(prices) <= 1:
        return 0
    buy = prices[0]  # 当天买的话意味着损失 -prices[i]
    sell = 0
    for i in prices:
        buy = min(buy, i)  # 当前买的价格 比 以前买入的大,就在当前节点买入
        sell = max(sell, i-buy)  # 卖的价钱 = 现在成交价格i - 购买价格buy
    return sell

print(maxProfit(s))    # 2
1
2
3
4
5
6
7
8
9
10
11
12
13

# 2、golang

package main

import (
	"fmt"
)

func maxProfit(prices []int) int {
	if len(prices) <= 1{
		return 0
	}
	buy := prices[0]  // 当天买的话意味着损失 -prices[i]
	sell := 0       // 初始化利润为0
	for _, price := range prices{
		if price < buy {  // 当前买的价格 比 以前买入的大,就在当前节点买入
			buy = price   // 卖的价钱 = 现在成交价格i - 购买价格buy
		}
		if price-buy > sell{  // 如果当前价格减卖的价格 大于记录的最大利润，就更新最大利润
			sell = price-buy
		}
	}
	return sell
}

func main() {
	prices := []int{7,4,6,3,1}
	ret := maxProfit(prices)
	fmt.Println(ret)  // 2
}
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

# 04.买卖股票的最佳时机II

  • 122.买卖股票的最佳时机II (opens new window)

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

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

  • 你也可以先购买，然后在 同一天 出售，返回 *你能获得的 最大 利润

输入：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
1
2
3
4
5

# 1、python

  • max_profit 初始化为 0，用于存储最大利润

  • 我们从数组的第二天开始遍历 (i 从 1 开始)，检查当前价格是否高于前一天的价格

  • 如果价格上涨 (prices[i] > prices[i - 1])，则将上涨的差值加入 max_profit 中

  • 这样做相当于每天都买入并卖出股票，只要有利润就加上

  • 最后返回 max_profit，即最大总利润

def maxProfit(prices):
    max_profit = 0
    for i in range(1, len(prices)):
        # 如果今天的价格高于昨天的价格，就在今天卖出，赚取差价
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]
    return max_profit

# 测试用例
prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))  # 输出：7
1
2
3
4
5
6
7
8
9
10
11

# 05.合并两个有序数组

  • 88.合并两个有序数组 (opens new window)

  • 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中*，*使 nums1 成为一个有序数组

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n

  • 你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
1
2

# 1、python

  • 将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中
  • 我们为两个数组分别设置一个指针p1 与 p2 来作为队列的头部指针

class Solution:
    def merge(self, nums1, m, nums2, n):
        sorted = []
        p1, p2 = 0, 0
        while p1 < m or p2 < n:
            if p1 == m:
                sorted.append(nums2[p2])
                p2 += 1
            elif p2 == n:
                sorted.append(nums1[p1])
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                sorted.append(nums1[p1])
                p1 += 1
            else:
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted  # 将合并后的结果复制回nums1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 2、golang
func merge(nums1 []int, m int, nums2 []int, n int) {
    // 初始化两个指针，分别指向 nums1 和 nums2 的末尾
    p1, p2 := m-1, n-1
    // 指针 p 合并后的 nums1 的末尾
    p := m + n - 1

    // 从后往前逐步比较和插入
    for p1 >= 0 && p2 >= 0 {
        if nums1[p1] > nums2[p2] {
            nums1[p] = nums1[p1]
            p1--
        } else {
            nums1[p] = nums2[p2]
            p2--
        }
        p--
    }

    // 如果 nums2 还有剩余元素，直接插入 nums1 开头
    for p2 >= 0 {
        nums1[p] = nums2[p2]
        p--
        p2--
    }
}

func main() {
    nums1 := []int{1, 2, 3, 0, 0, 0}
    m := 3
    nums2 := []int{2, 5, 6}
    n := 3
    merge(nums1, m, nums2, n)
    fmt.Println(nums1) // 输出: [1, 2, 2, 3, 5, 6]
}
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

# 06.最长重复子数组

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]
1
2
3

# 1、python dp

  • 定义一个二维数组 dp，其中 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度

  • 初始化：当 i=0 或 j=0 时，dp[i][j] 应为 0，因为空数组不可能有公共子数组

  • 状态转移：如果 nums1[i-1] == nums2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1，否则，dp[i][j] = 0

  • 最终结果：遍历整个 dp 数组，找到其中的最大值即为所求的最长公共子数组的长度

class Solution(object):
    def findLength(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_len = 0

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 如果 nums1[i-1] == nums2[j-1]，长度值先更新为 斜对角值+1
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    
                    max_len = max(max_len, dp[i][j]) # 更新最大长度
                else:
                    dp[i][j] = 0 # 否则，dp[i][j] = 0

        # 最终结果：遍历整个 dp 数组，找到其中的最大值即为所求的最长公共子数组的长度
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 以 nums1 = [1, 2, 3, 2, 1] 和 nums2 = [3, 2, 1, 4, 7] 为例，构建 dp 数组如下：
i\j 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 1 0 0
2 0 0 1 0 0 0
3 0 1 0 0 0 0
4 0 0 2 0 0 0
5 0 0 0 3 0 0

# 07.删除有序数组中重复项

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

# 1、python

  • 使用 count指针记录当前列表中无重复数字的长度

  • 使用 i 指针遍历列表，如果 相邻两个元素不相等，什么都不处理

  • 如果相邻两个元素不相等，就将 不重复的值放到 count指针位置

  • 遍历完结果：

  •    nums = [0, 0, 1, 1, 1, 2, 2 ,3, 3, 4]   # 原始列表
   nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]   # 遍历后结果，count=5，遍历后取出 nums[5]，就是目标结果
    1
    2
def removeDulp(nums):
    count = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[count] = nums[i]  # 如果相邻两个元素不相等，就将 不重复的值放到 count指针位置
            count += 1
    return count

nums = [0,0,1,1,1,2,2,3,3,4]
print( removeDulp(nums) )  # 5, [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
1
2
3
4
5
6
7
8
9
10

# 07.2 删除有序数组中的重复项 II

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

# 1、python

class Solution:
    def removeDuplicates(self, nums):
        if not nums:
            return 0
        slow = 2   # `slow` 用于记录结果数组的位置，允许元素最多出现两次

        for i in range(2, len(nums)):
            # 如果当前元素与 `slow - 2` 位置的元素不同，说明当前元素可以加入结果数组
            if nums[i] != nums[slow - 2]:
                nums[slow] = nums[i]  # 将当前元素放到 `slow` 位置
                slow += 1  # 移动 `slow` 指针，准备放置下一个元素
        return slow
1
2
3
4
5
6
7
8
9
10
11
12

# 08.两数之和 II - 输入有序数组

输入：numbers = [2,3,4], target = 6
输出：[1,3]
输入：numbers = [-1,0], target = -1
输出：[1,2]
1
2
3
4

# 1、python

  • 初始时两个指针分别指向第一个元素位置和最后一个元素的位置
  • 每次计算两个指针指向的两个元素之和，并和目标值比较
  • 如果两个元素之和等于目标值，则发现了唯一解
  • 如果两个元素之和小于目标值，则将左侧指针右移一位
  • 如果两个元素之和大于目标值，则将右侧指针左移一位
def twoSum(numbers, target):
    low, high = 0, len(numbers) - 1  # 初始时两个指针分别指向第一个元素位置和最后一个元素的位置
    while low < high:  # 只要左右指针没有相遇就循环
        total = numbers[low] + numbers[high]
        if total == target:   # 判断两个元素之和等于目标值，则发现了唯一解
            return [low + 1, high + 1]
        elif total < target:
            low += 1
        else:
            high -= 1
    return [-1, -1]

if __name__ == '__main__':
    numbers = [2,3,4]
    target = 6
    print( twoSum(numbers, target) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 2、golang

package main

import "fmt"

func twoSum(numbers []int, target int) []int {
	low, high := 0, len(numbers) - 1  // 初始时两个指针分别指向第一个元素位置和最后一个元素的位置
	for low < high {  // 只要左右指针没有相遇就循环
		total := numbers[low] + numbers[high]
		if total == target{  // 判断两个元素之和等于目标值，则发现了唯一解
			return []int{low+1, high+1}
		}else if total < target {
			low += 1
		}else {
			high -= 1
		}
	}
	return nil
}

func main() {
	nums := []int{2,7,11,15}
	target := 9
	v := twoSum(nums, target)
	fmt.Println(v)  // [1 2]
}
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

# 09.多数元素

  • 169.多数元素 (opens new window)

  • 给定一个大小为 n 的数组，找到其中的多数元素

  • 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素

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

输入：[3,2,3]
输出：3
输入：[2,2,1,1,1,2,2]
输出：2
1
2
3
4

# 1、python

  • 我们先将 nums 数组排序，然后返回上文所说的下标对应的元素
  • 应为肯定出现多数元素，那么排序后，中位数一定是这个多数
def manyNums(nums):
    nums.sort()
    return nums[len(nums) // 2]

nums = [3,2,3]
print( manyNums(nums) )  # 3
1
2
3
4
5
6

# 10.旋转数组的最小数字

  • 154.寻找旋转排序数组中的最小值 II (opens new window)

  • 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组

  • 例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

    • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
    • 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

  • 数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

# 1、python

  • 左边界为low，右边界为high，区间的中点为 m,被分为下面三情况
    • 如果 m的值小于 R的值，最小值一定在左半部分
    • 如果m的值大于R的值，最小值一定在右半部分
    • 如果中间值m等于 R的值，那么右指针就向左移动一位
class Solution:
    def findMin(self, nums):
        # 左边界为L，右边界为R，区间的中点为 m
        L, R = 0, len(nums) - 1
        while L < R:
            m = L + (R - L) // 2
            if nums[m] < nums[R]:  # 如果 m的值小于 R的值，最小值一定在左半部分
                R = m
            elif nums[m] > nums[R]:  # 如果m的值大于R的值，最小值一定在右半部分
                L = m + 1
            else:  # 如果中间值m等于 R的值，那么右指针就向左移动一位
                R -= 1  # R右指针向左移动，值是会变小的
        return nums[L]
1
2
3
4
5
6
7
8
9
10
11
12
13

# 2、golang

package main

import "fmt"

func minArray(numbers []int) int {
  // 左边界为L，右边界为R，区间的中点为 m
	L, R := 0, len(numbers) - 1
	for L < R {
		m := L + (R-L) / 2
		if numbers[m] < numbers[R] {  // 如果 m的值小于 R的值，最小值一定在左半部分
			R = m
		} else if numbers[m] > numbers[R] {  // 如果m的值大于R的值，最小值一定在右半部分
			L = m + 1
		} else {  // 如果中间值m等于 R的值，那么右指针就向左移动一位
			R -= 1  // R右指针向左移动，值是会变小的
		}
	}
	return numbers[L]
}

func main() {
	nums := []int{3,4,5,1,2}
	v := minArray(nums)
	fmt.Println(v)  // 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

# 11.两个数组的交集

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
1
2

# 1、python

def disNum(nums1, nums2):
    _set = set(nums1)  # 将nums1转换成集合
    result = []

    for num in nums2:
        if num in _set:    # 如果nums2中元素在集合中
            result.append(num)
            _set.discard(num)   # 集合中去除刚刚已经添加的元素，避免重复解
    return result

if __name__ == '__main__':
    nums1 = [4,9,5]
    nums2 = [9,4,9,8,4]
    print( disNum(nums1, nums2) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2、golang

package main

import "fmt"

func intersection(nums1 []int, nums2 []int) []int {
	set1 := map[int]bool{}
	for _, v := range nums1 {  // 将nums1转换成集合
		set1[v] = true
	}
	tmp := []int{}
	for _,v2 := range nums2 {
		_,ok := set1[v2]
		if ok {           // 如果nums2中元素在集合中
			tmp = append(tmp,v2)
			delete(set1, v2)  // 集合中去除刚刚已经添加的元素，避免重复解
		}
	}
	return tmp
}

func main() {
	nums1 := []int{4,9,5}
	nums2 := []int{9,4,9,8,4}
	v := intersection(nums1, nums2)
	fmt.Println(v)  // [9 4]
}
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

# 12.加一

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

# 1、python

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1  # 进位
        p = len(digits) - 1  # p指针从右侧开始
        while p >= 0:
            sum = digits[p] + carry
            digit = sum % 10  # 当前数字
            carry = sum // 10  # 进位
            digits[p] = digit
            p -= 1
        if carry == 1:
            digits = [1] + digits
        return digits
1
2
3
4
5
6
7
8
9
10
11
12
13

# 2、golang

package main

import "fmt"

func plusOne(digits []int) []int {
	tmp := 1              // 设置临时变量 1
	n := len(digits) - 1  // 列表最右侧元素下标为 n
	for n >= 0 {          // 从列表右侧向左遍历
		sum := digits[n] + tmp  // 当前值加上井位为当前位置 总值
		digit := sum % 10       // 取余获得当前位置值
		digits[n] = digit
		tmp = sum / 10       // 井位
		n -= 1               // 下标向左移动一位
	}
	if tmp > 0 {           // 如果是 999这种情况，循环结束列表还存在井位
		digits = append([]int{tmp}, digits...)  // 直接将井位添加到列表头部即可
	}
	return digits
}

func main() {
	nums := []int{9,9,9}
	v := plusOne(nums)
	fmt.Println(v)  // [1 0 0 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

# 13.和为s的连续正数序列

  • 和为s的连续正数序 (opens new window) 被移除了
  • 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）
  • 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列
输入：target = 9
输出：[[2,3,4],[4,5]]
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
1
2
3
4

# 1、python滑动窗口

  • 双指针滑动窗口: 使用两个指针 left 和 right，分别表示序列的起点和终点

  • 移动指针: 通过调整 left 和 right 来改变当前序列的和，如果序列和小于 target，则右

def findNum(target):
    # 初始化两个指针，分别指向序列的起始位置和结束位置
    left, right = 1, 2
    # 初始化当前窗口的和
    sum_seq = left + right
    # 用于存储符合条件的结果序列
    res = []

    # 当左指针小于右指针时继续循环
    while left < right:
        if sum_seq == target:
            # 如果当前序列的和等于目标值，将序列加入结果集
            res.append(list(range(left, right + 1)))
            # 移动左指针，同时更新序列的和
            sum_seq -= left
            left += 1
        elif sum_seq < target:
            # 如果当前序列的和小于目标值，移动右指针增加序列和
            right += 1
            sum_seq += right
        else:
            # 如果当前序列的和大于目标值，移动左指针减少序列和
            sum_seq -= left
            left += 1

    return res

# 测试用例
print(findNum(9))   # 输出: [[2, 3, 4], [4, 5]]
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

# 2、golang滑动窗口

package main

import (
	"fmt"
)

func findContinuousSequence(target int) [][]int {
	left, right := 1, 2
	sumSeq := left + right
	var res [][]int

	for left < right {
		if sumSeq == target {
			// 如果当前序列的和等于目标值，将序列加入结果集
			sequence := make([]int, right-left+1)
			for i := left; i <= right; i++ {
				sequence[i-left] = i
			}
			res = append(res, sequence)
			// 移动左指针，同时更新序列的和
			sumSeq -= left
			left++
		} else if sumSeq < target {
			// 如果当前序列的和小于目标值，移动右指针增加序列和
			right++
			sumSeq += right
		} else {
			// 如果当前序列的和大于目标值，移动左指针减少序列和
			sumSeq -= left
			left++
		}
	}

	return res
}

func main() {
	fmt.Println(findContinuousSequence(9))  // 输出: [[2, 3, 4], [4, 5]]
}
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

# 14.两个数组的交集 II

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
1
2
3
4

# 1、python字典方法

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 使用字典记录 nums1 中每个元素的出现次数
        d = {}
        for i in nums1:
            d[i] = d.get(i, 0) + 1

        tmp = []
        for i in nums2:
            if i in d:
                tmp.append(i)
                d[i] -= 1
                if d[i] == 0:
                    d.pop(i)
        return tmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2、golang字典方法

package main

import (
	"fmt"
)

func findCom(nums1, nums2 []int) []int {
	// 使用map记录nums1中每个元素的出现次数
	d := make(map[int]int)
	for _, num := range nums1 {
		d[num]++
	}

	tmp := []int{}
	for _, num := range nums2 {
		if count, exists := d[num]; exists {
			tmp = append(tmp, num)
			d[num]--
			if count == 1 {
				delete(d, num)
			}
		}
	}
	return tmp
}

func main() {
	// 测试用例
	nums1 := []int{4, 9, 4, 5}
	nums2 := []int{9, 4, 9, 8, 4}
	fmt.Println(findCom(nums1, nums2))  // 输出: [4, 9]
}
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

# 15.找到所有数组中消失的数字

  • 448.找到所有数组中消失的数字 (opens new window)

  • 给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次

  • 找到所有在 [1, n] 范围之间没有出现在数组中的数字

  • 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
1
2
3
4

# 1、python

利用索引标记：

  • 我们遍历数组中的每个数字，并利用该数字（减 1 后）的索引位置将数组中对应的值标记为负数
  • 例如，若当前数字为 4，则将 nums[3]（即索引 3 对应的元素）标记为负数这样，我们就可以知道数字 4 出现在数组中

找到未标记的索引：

  • 遍历完成后，数组中那些正数位置的索引 + 1 就是缺失的数字，因为这些位置没有被标记为负数，说明对应的数字从未出现过

时间复杂度：

  • 这个算法的时间复杂度为 O(n)，因为我们只需要遍历数组两次
  • 空间复杂度为 O(1)，因为我们没有使用额外的空间（不计算返回结果的空间
def findNums(nums):
    n = len(nums)
    
    # 遍历数组中的每个数字
    for num in nums:
        # 计算对应的索引位置（需要使用模运算避免数组越界）
        x = (num - 1) % n
        # 在该索引位置的值上增加n，以标记该数字出现过
        nums[x] += n
    
    # 找出数组中值未超过n的位置，这些位置对应的数字即为缺失的数字
    ret = [i + 1 for i, num in enumerate(nums) if num <= n]
    
    return ret

# 测试用例
nums = [4, 3, 2, 7, 8, 2, 3, 1]
print(findNums(nums))  # 输出: [5, 6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

  • # 2、go

package main

import "fmt"

// findMissingNumbers 识别数组中缺失的数字
func findNums(nums []int) []int {
	n := len(nums)

	// 遍历数组中的每个数字，并在相应的索引位置上增加n，表示这个数字出现过
	for _, num := range nums {
		// 计算出对应的索引位置，注意这里需要使用模运算以避免数组越界
		x := (num - 1) % n
		nums[x] += n
	}

	// 遍历数组，找出未被标记过的位置，它们就是缺失的数字
	var ret []int
	for i, num := range nums {
		if num <= n { // 如果该位置的值不大于n，说明该位置对应的数字缺失
			ret = append(ret, i+1)
		}
	}

	return ret
}

func main() {
	// 测试用例
	nums := []int{4, 3, 2, 7, 8, 2, 3, 1}
	fmt.Println(findMissingNumbers(nums)) // 输出: [5, 6]
}
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

# 16.三数之和

  • 15.三数之和 (opens new window)

  • 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？

  • 请你找出所有和为 0 且不重复的三元组

  • 注意：答案中不可以包含重复的三元组

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
1
2

# 1、python

  • 对数组进行排序
  • 遍历排序后数组：
    • 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果
    • 对于重复元素：跳过，避免出现重复解
    • 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
      • 当 nums[i]+nums[L]+nums[R]==0，执行循环
      • 判断左界和右界是否和下一位置重复，去除重复解
      • 并同时将 L,R移到下一位置，寻找新的解
        • 若和大于 0，说明 nums[R] 太大，R左移
        • 若和小于 0，说明 nums[L] 太小，L右移
class Solution:
    def threeSum(self, nums):
        n = len(nums)
        res = []
        if not nums or n < 3:  # 数组为 null 或者数组长度小于 3，返回 []
            return []
        nums.sort()  # 对数组进行排序
        if nums[0] > 0:  # 若 nums[0]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回[]
            return []

        for i in range(0, n):  # 遍历排序后数组
            if i > 0 and nums[i] == nums[i - 1]:  # 对于重复元素：跳过，避免出现重复解
                continue

            L = i + 1
            R = n - 1
            while L < R:  # 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环
                if nums[i] + nums[L] + nums[R] == 0:
                    res.append([nums[i], nums[L], nums[R]])
                    # 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解
                    while L < R and nums[L] == nums[L + 1]:
                        L = L + 1
                    while L < R and nums[R] == nums[R - 1]:
                        R = R - 1
                    # 并同时将 L,R 移到下一位置，寻找新的解
                    L = L + 1
                    R = R - 1
                elif nums[i] + nums[L] + nums[R] > 0:  # 若和大于 0，说明 nums[R] 太大，R 左移
                    R = R - 1
                else:  # 若和小于 0，说明 nums[L] 太小，L 右移
                    L = L + 1
        return res


nums = [-1, 0, 1, 2, -1, -4]
print(Solution().threeSum(nums))  # [[-1, -1, 2], [-1, 0, 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

# 17.列表连续相同数据放一起

  • 力扣删除了
将列表：# [1,2,2,3,4,4,5,6,6,6,7,8,2,2,2]
转换成：# [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]
1
2

# 1、python

初始化 result 和 current_group：用于存储结果列表和当前正在处理的连续相同元素的分组

遍历原列表：逐个检查元素是否与当前分组的最后一个元素相同，相同则加入当前分组，不同则结束当前分组并开始新的分组

添加最后一个分组：在遍历结束后，将最后一个分组添加到结果列表中，确保所有元素都被处理

def group_eles(lst):
    if not lst:
        return []

    result = []  # 用于存储最终的结果
    current_group = [lst[0]]  # 初始化第一个分组，包含列表的第一个元素

    for i in range(1, len(lst)):
        if lst[i] == current_group[-1]:
            # 如果当前元素和当前分组的最后一个元素相同，则将其加入当前分组
            current_group.append(lst[i])
        else:
            # 如果当前元素和当前分组的最后一个元素不同，则将当前分组加入结果中
            result.append(current_group)
            # 开始一个新的分组
            current_group = [lst[i]]

    result.append(current_group)  # 添加最后一个分组到结果中
    return result

# 测试用例
lst = [1, 2, 2, 3, 4, 4, 5, 6, 6, 6, 7, 8, 2, 2, 2]
print(group_consecutive_elements(lst))  # 输出: [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  • # 2、go

package main

import (
	"fmt"
)

func groupEles(lst []int) [][]int {
	if len(lst) == 0 {
		return [][]int{}
	}

	var result [][]int  // 用于存储最终的结果
	currentGroup := []int{lst[0]}  // 初始化第一个分组，包含列表的第一个元素

	for i := 1; i < len(lst); i++ {
		if lst[i] == currentGroup[len(currentGroup)-1] {
			// 如果当前元素和当前分组的最后一个元素相同，则将其加入当前分组
			currentGroup = append(currentGroup, lst[i])
		} else {
			// 如果当前元素和当前分组的最后一个元素不同，则将当前分组加入结果中
			result = append(result, currentGroup)
			// 开始一个新的分组
			currentGroup = []int{lst[i]}
		}
	}

	result = append(result, currentGroup)  // 添加最后一个分组到结果中
	return result
}

func main() {
	// 测试用例
	lst := []int{1, 2, 2, 3, 4, 4, 5, 6, 6, 6, 7, 8, 2, 2, 2}
	fmt.Println(groupEles(lst))  // 输出: [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]
}
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

# 18.盛最多水的容器

  • 11.盛最多水的容器 (opens new window)

  • 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai)

  • 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)

  • 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49

示例 2：
输入：height = [1,1]
输出：1
1
2
3
4
5
6
7
8

# 1、python

  • 算法流程：

    • 设置双指针 i,j 分别位于容器壁两端，根据规则移动指针（后续说明）
    • 并且更新面积最大值 res，直到 i == j 时返回 res

  • 指针移动规则与证明：

    • 每次选定围成水槽两板高度 h[i],h[j] 中的短板，向中间收窄 1格
    • 由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i, j) = min(h[i], h[j]) × (j - i)
    • 在每一个状态下，无论长板或短板收窄 1格，都会导致水槽 底边宽度 -1
    • 左右长度，那个小，就移动哪一个，才有可能让面积增大
def maxArea(nums):
    # L左指针，J右指针, 面积S(i, j) = min(h[i], h[j]) × (j - i)
    L, R, S = 0, len(nums) - 1, 0
    while L < R:  # 只要左右指针不重合就一直循环
        if nums[L] < nums[R]:  # 如果做指针小，那么移动左指针才有可能使面积增大
            S = max(S, nums[L] * (R - L))
            L += 1
        else:  # 否则若果有指针小，只有移动右指针才有可能使面积增大
            S = max(S, nums[R] * (R - L))
            R -= 1
    return S

nums = [1,8,6,2,5,4,8,3,7]
print( maxArea(nums) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2、golang

package main

import (
	"fmt"
)

func maxArea(height []int) int {
  // L左指针，J右指针, 面积S(i, j) = min(h[i], h[j]) × (j - i)
	L, R, S := 0, len(height)-1, 0
	for L < R {                         // 只要左右指针不重合就一直循环
		  if height[L] < height[R] {
			  if height[L] * (R - L) > S {  // 如果做指针小，那么移动左指针才有可能使面积增大
				  S = height[L] * (R - L)
			  }
			  L += 1
		  } else {         // 否则若果有指针小，只有移动右指针才有可能使面积增大 
			  if height[R] * (R - L) > S {
				  S = height[R] * (R - L)
			  }
			  R -= 1
		  }
	}
	return S
}

func main() {
	nums := []int{1,8,6,2,5,4,8,3,7}
	v := maxArea(nums)
	fmt.Println(v)  // 49
}
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

# 19.合并区间

  • 56.合并区间 (opens new window)

  • 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]

  • 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
1
2
3

# 1、python

  • 首先，我们将列表中的区间按照左端点升序排序
  • 相邻两个列表如果前一个列表最大值小于下一个列表最小值，肯定无需合并，直接添加到空列表
  • 否则找到这两个列表中的最大值，拓展区间
def merge(intervals):
    intervals.sort(key=lambda x: x[0])  # 首先，我们将列表中的区间按照左端点升序排序
    merged = []
    for interval in intervals:
        # 如果列表为空，或者 一个列表右边的值 < 下一个列表左边的元素
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)  # 直接添加，无需合并
        else:
            # 否则的话，我们就可以与上一区间进行合并, 右边值为两个列表右侧较大的值
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

intervals = [[2,3],[1,6],[8,10],[15,18]]
print(merge(intervals))  # [[1, 6], [8, 10], [15, 18]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 20.搜索旋转排序数组

  • 33.搜索旋转排序数组 (opens new window)

  • 整数数组 nums 按升序排列，数组中的值 互不相同

  • nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转

  • 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1

原始数组：[0,1,2,4,5,6,7]  
旋 转 后：[4,5,6,7,0,1,2]
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
1
2
3
4

# 1、python

  • 可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的

def search(nums, target):
    if not nums:
        return -1
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid

        # 如果 第一个元素 < 中间值 证明前半部分有序
        if nums[0] <= nums[mid]:
            # 如果目标元素 在前半部分，就移动右指针为 mid-1
            if nums[0] <= target < nums[mid]:
                r = mid - 1
            else:  # 否则移动左指针 为 mid+1
                l = mid + 1
        # 否则 后半部分有序
        else:
            # 如果目标元素 在后半部分，就移动左指针为 mid+1
            # 在判断后半部分是否有序时，我们需要比较的其实是目标值 target 与数组的最后一个元素之间的关系
            if nums[mid] < target <= nums[len(nums) - 1]:
                l = mid + 1
            else: # 否则右指针为 mid - 1
                r = mid - 1
    return -1

target = 0
nums = [4,5,6,7,0,1,2]
print( search(nums, target) )  # 4
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

# 21.数组中的第K个最大元素

例：寻找第二大元素
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
1
2
3

# 22.1 python

quick_select 函数：实现类似快速排序的分区过程，但只继续处理可能包含第 k 大元素的那部分数组

分区过程：每次选择数组的第一个元素作为基准点，将数组分为两部分，左边部分大于基准，右边部分小于基准

递归处理：通过递归，缩小查找范围，直到找到第 k 大的元素

注：这里是倒序排列，所以第k大的数就是left == k - 1时

class Solution:
    def findKthLargest(self, nums, k):
        def quick_select(low, high):
            # 不需要像快排一样显式的终止条件 low >= high 因为  l==k-1 时直接返回结果，而不是继续递归
            l, r = low, high
            p = nums[l]          # 选择最左边的数作为基准
            while l < r:
                while l < r and nums[r] <= p:
                    r -= 1
                nums[l] = nums[r]              # 将右边小于p值的数放到左边空位置

                while l < r and nums[l] > p:
                    l += 1
                nums[r] = nums[l]              # 将右边大于p值的数放到右边空位置

            nums[l] = p            # l == r, p 的最终位置确定

            if l == k - 1:         # 如果基准的最终位置是第 k 大的位置，找到，直接返回
                return nums[l]     
            elif l > k - 1:        # 如果基准位置大于第 k 大的位置，证明k一定在左边
                return quick_select(low, l - 1)
            else:                  # 如果基准位置小于第 k 大的位置，继续从右边找 加入到左边
                return quick_select(l + 1, high)

        return quick_select(0, len(nums) - 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

# 22.接雨水

  • 42.接雨水 (opens new window)

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

# 1、python

class Solution:
    def trap(self, height):
        nums = height
        if not nums:
            return 0
        
        l, r = 0, len(nums) - 1
        l_max, r_max = 0, 0         # 初始化左和右最大高度
        s = 0                       # 总共接到的雨水量

        while l <= r:
            if nums[l] <= nums[r]:       # 左侧柱子 小于等于 右侧柱子高度
                if nums[l] >= l_max:       # 左侧柱子 大于等于 左边的最大高度（无雨水）
                    l_max = nums[l]        # 更新左边的最大高度
                else:
                    s += l_max - nums[l]   # 计算当前柱子能够接到的雨水量，并累加
                l += 1
            else:
                if nums[r] >= r_max:        # 右侧柱子 大于等于 右边的最大高度（无雨水）
                    r_max = nums[r]         # 更新右边的最大高度
                else:
                    s += r_max - nums[r]     # 计算当前柱子能够接到的雨水量，并累加
                r -= 1
        return s                               # 返回计算出的总雨水量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 23.全排列

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
1
2
3
4
5
6
7
8

# 1、python

  • 时间复杂度为 O(n * n!)
    • 生成一个排列需要遍历列表中的每个元素，并且有 n!（1*2*3*n!） 种不同的排列
    • 对于每一个排列，生成的过程涉及递归深度为 n，并且每层递归都需要遍历所有 n 个元素
  • 空间复杂度为 O(n) 加上结果存储的空间 O(n * n!)
    • 递归栈空间: 由于递归调用的深度为 n，因此递归栈空间的复杂度为 O(n)
    • 附加存储空间: 需要一个数组来跟踪哪些元素已经被使用 (used 数组)，以及保存当前排列 (path 数组)，这些也都是 O(n) 的空间
    • 结果存储空间: 生成的所有排列需要存储，占用 O(n * n!) 的空间

  • 对于一个给定的数组，DFS会从头到尾依次选择一个元素作为排列的一部分

  • 然后对剩余元素继续递归，直到生成一个完整的排列当所有排列都生成后，递归结束

  • 递归函数 dfs:
    • path 保存当前排列路径
    • used 是一个布尔数组，标记哪些元素已经被使用过
    • res 是存放所有排列结果的列表
  • 递归逻辑:
    • 在递归函数中，我们遍历 nums 的每一个元素，通过检查 used[i] 是否为 False，判断该元素是否已经被使用过
    • 如果未被使用，则将其加入 path 并标记为已使用，继续递归处理剩下的元素
    • 在递归返回后，通过 pop() 和 used[i] = False 撤销选择，进行回溯

class Solution:
    # path（排列路径）user（哪些使用过） res(排列结果列表)
    def permute(self, nums):
        def dfs(path, used, res):
            if len(path) == len(nums):  # 找到一个完整的排列
                res.append(path[:])  # path[:] 创建了一个浅拷贝
                return

            # 遍历每个数字，尝试将其加入当前排列路径中
            for i in range(len(nums)):
                if used[i]:  # 如果当前数字被使用过 跳过
                    continue

                path.append(nums[i])  # 选择当前数字
                used[i] = True

                dfs(path, used, res)  # 递归处理剩余的数字

                path.pop()  # 回溯：撤销选择
                used[i] = False

        res = []
        used = [False] * len(nums)
        dfs([], used, res)
        return res

# 示例输入
nums = [1, 2, 3]
print(Solution().permute(nums))
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

# 24.下一个排列

  • 31.下一个排列 (opens new window)
  • 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列
  • 从右往左找到第一个小于其右侧元素的数字，交换位置就是下一个排列
  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3]

# 1、python

假设我们有一个数字序列 [1, 3, 5, 4, 2]，我们需要找到这个序列的下一个排列 –> [1, 4, 2, 3, 5]

  • 1）步骤 1: 从右往左找到第一个小于其右侧元素的数字

    • 2<4, 4<5, 5>3，左侧3小于右侧5，3 就是我们需要调整的元素，位置是 i = 1

  • 2）步骤 2: 从右往左找到第一个比3大的元素并交换

    • 2<3, 4>3, 4就是是第一个比 3 大的数字， 3 和 4 交换，序列变为 [1, 4, 5, 3, 2]

  • 3）步骤 3: 反转交换位置后的右侧部分

    • 交换位置4(i=1)，右侧部分为5, 3, 2 ，反转后的序列是 [1, 4, 2, 3, 5]（这个就是下一个排列）

class Solution:
    def nextPermutation(self, nums):
        # 第一步：从右往左找到第一个小于其右侧元素的数字
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:  # 如果找到这样的元素
            # 第二步：从右往左找到第一个大于 nums[i] 的数字
            j = len(nums) - 1
            while nums[j] <= nums[i]:               # 第一步中 i+1 肯定是，所以至少存在一个
                j -= 1

            nums[i], nums[j] = nums[j], nums[i]     # 交换 nums[i] 和 nums[j]

        # 第三步：反转 i 索引后的所有元素
        l, r = i + 1, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
        print(nums)  # [1, 3, 2]


Solution().nextPermutation([1, 2, 3])
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

# 25.分割等和子集

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]
1
2
3

# 1、python dp

  • 状态定义：dp[i] 表示是否可以找到一个子集，其元素之和为 i
  • 状态转移方程：dp[i] = dp[i] or dp[i - num]
    • 如果 dp[i - num] 为 True，说明之前的某些数字可以组成和为 i - num 的子集
    • 加上当前的 num，就可以组成和为 i 的子集，因此 dp[i] 也应该被设置为 True
  • 初始状态：dp 数组初始为 [True, False, False ...]，表示暂时还不知道是否可以找到对应和的子集
class Solution:
    def canPartition(self, nums):
        total_sum = sum(nums)
        if total_sum % 2 != 0:           # 如果总和是奇数，不可能分成两个相等的子集
            return False

        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True                     # 和为0的子集是存在的，而这个子集就是空集

        for num in nums:
            # list(range(11, 0, -1)) = [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
            for i in range(target, num - 1, -1):            # 需要从后往前更新dp数组，避免重复使用当前数字
                dp[i] = dp[i] or dp[i - num]

        return dp[target]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  • 推演[1,5,11,5]
# num=1  range(11, 0, -1) = [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[True, True, False, False, False, False, False, False, False, False, False, False]

# num=5  range(11, 4, -1) = [11, 10, 9, 8, 7, 6, 5]
[True, True, False, False, False, True, True, False, False, False, False, False]

# 11 range(11, 10, -1) = [11]
[True, True, False, False, False, True, True, False, False, False, False, True]

# num=5  range(11, 4, -1) = [11, 10, 9, 8, 7, 6, 5]
[True, True, False, False, False, True, True, False, False, False, True, True]
1
2
3
4
5
6
7
8
9
10
11

# 26.缺失的第一个正数

  • 41.缺失的第一个正数 (opens new window)

  • 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数

  • 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有
1
2
3

# 1、python

  • 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中
  • 将 nums 数组本身当作哈希表来使用
  • 遍历数组 nums，对于每个元素 nums[i]，尝试将它放到对应的位置，即 nums[nums[i] - 1]
  • 在放置过程中，需要考虑以下条件：
    • 忽略非正数和超过数组长度的数
    • 如果目标位置已经放置了正确的数，则跳过，以避免无限循环
  • 最终数组中第一个不符合条件的位置的索引加 1 就是缺失的最小正整数

推演

  • 初始 nums = [3, 4, -1, 1]

  • i = 0 时，nums[0] = 3，它应该放在索引2处（3-1=2），交换后得到[1, 4, -1, 3]

  • 此时，nums[0] = 1，它已经在正确的位置，所以不需要进一步交换

  • i = 1时，nums[1] = 4，它应该放在索引3处（4-1=3），交换后得到[1, 3, -1, 4]

  • 此时，nums[1] = 3，它应该放在索引 2 处（3-1=2），再次交换后得到 [1, -1, 3, 4]

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        for i in range(n):
            # 尝试将 nums[i] 放到 nums[nums[i] - 1] 的位置上（eg: nums[i] = 3 应该放到 nums[2]位置上）
            while 1 <= nums[i] <= n and  nums[i] !=  nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):                 # 寻找第一个 nums[i] != i + 1 的位置
            if nums[i] != i + 1:
                return i + 1
        return n + 1                       # 如果所有位置都正确，则返回 n + 1

print( Solution().firstMissingPositive([11,1,3,4,5,6,7,8,9,10]) )
# 最终 nums=[1, 11, 3, 4, 5, 6, 7, 8, 9, 10]   缺失的最小正整数就是 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 推演: 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中
# 初始数组 nums = [11, 1, 3, 4, 5, 6, 7, 8, 9, 10]
# i = 0 时
nums[0] = 11，因为 11 > 10（超出了数组的索引范围），我们不需要进行交换，直接进入下一个索引

# i = 1 时
nums[1] = 1，它应该放在索引 0 处（1-1=0），交换后得到 nums = [1, 11, 3, 4, 5, 6, 7, 8, 9, 10]
此时，nums[1] = 11，因为 11 > 10（超出了数组的索引范围），我们不需要进行交换，直接进入下一个索引

# i = 2 时
nums[2] = 3，它已经在正确的位置（索引 2，即 3-1=2），不需要进一步交换
# 最终的数组是 [1, 11, 3, 4, 5, 6, 7, 8, 9, 10]， 缺失的最小正整数就是 2
1
2
3
4
5
6
7
8
9
10
11

# 27.移动零

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2

# 1、python

  • 我们创建两个指针i和j，第一次遍历的时候指针j用来记录当前有多少 "非0元素"
  • 即遍历的时候每遇到一个非0元素就将其往数组左边挪
  • 第一次遍历完后，j指针的下标就指向了最后一个非0元素下标
  • 第二次遍历的时候，起始位置就从j开始到结束，将剩下的这段区域内的元素全部置为0
class Solution:
    def moveZeroes(self, nums):
        j = 0                          # j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        for i in range(len(nums)):
            if nums[i]:
                nums[j] = nums[i]
                j += 1
        for i in range(j,len(nums)):  # 二次遍历把末尾的元素都赋为0即可
            nums[i] = 0
        return nums

print( Solution().moveZeroes([0,1,0,3,12]) )  # [1, 3, 12, 0, 0]
1
2
3
4
5
6
7
8
9
10
11
12

# 28.寻找两个正序数组的中位数

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
1
2
3
4
5
6
7

# 1、python

  • 我们可以把问题转化为寻找两个数组中的第 k 小的元素

  • 对于两个数组 nums1 和 nums2，如果我们可以找到第 k 小的元素，那么中位数的计算就可以分为两种情况

    • 如果两个数组的总长度是奇数，那么中位数就是第 (m+n)//2 + 1 个元素

    • 如果两个数组的总长度是偶数，那么中位数就是第 (m+n)//2 和第 (m+n)//2 + 1 个元素的平均值

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        def findKth(arr1, arr2, k):           # 找到两个排序数组中第 k 小的元素
            if len(arr1) > len(arr2):         # 保证 arr1 是较短的数组
                return findKth(arr2, arr1, k)
            if not arr1:
                return arr2[k - 1]

            if k == 1:
                return min(arr1[0], arr2[0])

            # 二分查找：我们取两个数组的前 k//2 个元素 和 数组长度比较 取小值（避免越界）
            i = min(len(arr1), k // 2)
            j = min(len(arr2), k // 2)

            if arr1[i - 1] > arr2[j - 1]:       # arr2 的前 j 个元素不可能是第 k 小的元素,忽略掉 arr2 的前 j 个元素
                return findKth(arr1, arr2[j:], k - j)
            else:                               # arr1 的前 i 个元素不可能是第 k 小的元素忽略掉 arr1 的前 i 个元素
                return findKth(arr1[i:], arr2, k - i)

        total_len = len(nums1) + len(nums2)

        if total_len % 2 == 1:         # 如果总长度是奇数，中位数就是第 (total_length // 2 + 1) 小的元素
            return findKth(nums1, nums2, total_len // 2 + 1)
        else:                          # 如果总长度是偶数，中位数是第 total_length // 2 和 total_length // 2 + 1 小的元素的平均值
            return (
               findKth(nums1, nums2, total_len // 2) +
               findKth(nums1, nums2, total_len // 2 + 1)
            ) / 2.0


print(Solution().findMedianSortedArrays([1, 2], [3, 4]))  # 输出: 2.5
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

# 29.复原IP地址

  • 93.复原IP地址 (opens new window)
  • 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址
  • 这些地址可以通过在 s 中插入 '.' 来形成，你可以按任何顺序返回答案
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

输入：s = "0000"
输出：["0.0.0.0"]
1
2
3
4
5

# 1、python

  • 回溯法: 我们尝试在字符串的不同位置插入 .，并递归地检查剩余部分是否可以继续形成有效的 IP 地址

  • 有效性检查: 每一段 IP 地址都必须是有效的（即在 0 到 255 之间且没有前导零）

  • 终止条件: 当我们插入了 3 个 . 时，如果剩下的部分也是一个有效的 IP 段，那么我们可以构成一个完整的 IP 地址

class Solution:
    def restoreIpAddresses(self, s):
        def dfs(start, path):
            if len(path) == 4:
                # print(path)
                if start == len(s):                  # 已经分成了4段, 且已经用完所有字符
                    ret.append(".".join(path))       # 将路径转换为IP地址并存储
                return                               # 结束递归，防止路径超过4段

            for i in range(start, min(start + 3, len(s))):  # 每段最多3个字符, len(s) 保证不越界
                seg = s[start: i + 1]
                # 检查段是否合法：小于等于255，且不能有前导零（除非是"0"）
                if (seg[0] == "0" and len(seg) > 1) or (int(seg) > 255):
                    continue
                path.append(seg)
                dfs(i + 1, path)                        # 递归处理剩下的字符串
                path.pop()

        ret = []
        dfs(0, [])                 # 从第 0 个位置开始进行回溯
        return ret

print(Solution().restoreIpAddresses("25525511135"))  # 输出: ['255.255.11.135', '255.255.111.35']
# print(Solution().restoreIpAddresses("10111"))  # 输出: ['1.0.1.11', '1.0.11.1', '10.1.1.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
  • 推演：打印所有path=4的可能
class Solution:
    def restoreIpAddresses(self, s):
        def dfs(start, path):
            if len(path) == 4:
                print(path)
            for i in range(start, min(start + 3, len(s))):  # 每段最多3个字符, len(s) 保证不越界
                seg = s[start: i + 1]
                path.append(seg)
                dfs(i + 1, path)                        # 递归处理剩下的字符串
                path.pop()

        ret = []
        dfs(0, [])                 # 从第 0 个位置开始进行回溯
        return ret

print(Solution().restoreIpAddresses("25525511135"))  # 输出: ['255.255.11.135', '255.255.111.35']

"""
['2', '5', '5', '2']
['2', '5', '5', '25']
['2', '5', '5', '255']
['2', '5', '52', '5']
['2', '5', '52', '55']
['2', '5', '52', '551']
['2', '5', '525', '5']
['2', '5', '525', '51']
['2', '5', '525', '511']
['2', '55', '2', '5']
['2', '55', '2', '55']
['2', '55', '2', '551']
省略...
"""
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

# 30.最小覆盖子串

  • 76.最小覆盖子串 (opens new window)
  • 给你两个个字符串 s 、 t ，返回 s 中涵盖 t 所有字符的最小子串
  • 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
输入：s = "ADOBECODEBANC", t = "ABC"   输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'

输入: s = "a", t = "aa"    输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串
1
2
3
4
5

# 1、python

  • 字典初始化：dic_t 记录 t 中每个字符的数量，dic_s 记录当前窗口中字符的数量

  • 初始化：min_len 用于记录最小窗口的长度，ans_l 和 ans_r 用于记录最小窗口的左右边界

  • check 函数：检查当前窗口是否包含 t 中所有的字符

  • 滑动窗口：右指针 r 扩展窗口，左指针 l 收缩窗口，更新 dic_s 和检查窗口是否符合要求

class Solution:
    def minWindow(self, s, t):
        dic_s = {}       # 用于记录当前窗口中字符的数量
        dic_t = {}       # 记录t现次数：t = "ABC", dic_t = {'A': 1, 'B': 1, 'C': 1}
        min_len = float('inf')             # 最小窗口长度为正无穷
        ans_l, ans_r = -1, -1              # 答案 左、右指针

        for c in t:
            dic_t[c] = dic_t.get(c, 0) + 1

        def check():                         # 检查当前窗口是否包含 t 中的所有字符
            for k, v in dic_t.items():
                if dic_s.get(k, 0) < v:
                    return False
            return True

        l = 0
        for r in range(len(s)):
            if s[r] in dic_t:                    # 如果 s[r] 是 t 中的字符
                dic_s[s[r]] = dic_s.get(s[r], 0) + 1

            while check() and l <= r:            # 如果当前窗口包含 t 中的所有字符，尝试收缩窗口
                if r - l + 1 < min_len:          # 更新最小窗口的长度和位置
                    min_len = r - l + 1
                    ans_l, ans_r = l, r

                if s[l] in dic_t:                # 移动左指针，更新窗口中的字符数量
                    dic_s[s[l]] -= 1
                l += 1

        if ans_l == -1:        # 没有找到返回 ""
            return ""
        return s[ans_l:ans_r+1]

print(Solution().minWindow("ADOBECODEBANC", "ABC"))  # 输出 "BANC"
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
上次更新: 2024/10/15 16:27:13
06.动态规划
02.数组

← 02.数组→

最近更新
01
16.CAP
09-27
02
13.HTTP协议
09-25
03
12.TCP协议
09-25
更多文章>
Theme by Vdoing | Copyright © 2019-2024 逍遥子 技术博客 京ICP备2021005373号