不做大哥好多年
xiaonaiqiang
2021-06-19
目录

02.数组

# 31.寻找峰值

  • 162.寻找峰值 (opens new window)

  • 给你一个整数数组 nums，找到峰值元素并返回其索引

  • 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可

  • 你可以假设 nums[-1] = nums[n] = -∞

  • 你必须实现时间复杂度为 O(log n) 的算法来解决此问题

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：
	你的函数可以返回索引 1，其峰值元素为 2
 	或者返回索引 5， 其峰值元素为 6
1
2
3
4
5
6
7
8
9
  • 要解决这个问题，我们可以使用二分查找来达到 O(log n) 的时间复杂度
  • 由于题目中提到我们可以假设 nums[-1] = -∞ 和 nums[n] = -∞
  • 这意味着数组两端的元素比其外部的元素都要大，因此至少存在一个峰值

# 1、python

  • 我们用二分查找不断缩小搜索区间，每次都根据 nums[mid] 和 nums[mid + 1] 的大小关系决定是缩小到左侧还是右侧

  • 当 left == right 时，我们找到了一个峰值所在的位置

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        # 如果中间元素大于其右侧的元素，则峰值在左侧
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            # 如果中间元素小于等于其右侧的元素，则峰值在右侧
            left = mid + 1
    
    return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 32.柱状图中最大的矩形

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10  #（5,6两个组成）
1
2
3

# 1、python

  • 栈用于存放柱子的索引，以确保这些索引对应的柱子高度是递增的
  • 这样，当遇到一个比栈顶高度更低的柱子时，可以确定当前栈顶柱子的左右边界，从而计算该柱子形成的矩形面积
  • 第一部分：遍历柱子：
    • 对于每个柱子 nums[i]，如果它比栈顶柱子低，说明当前柱子将是栈顶柱子形成矩形的右边界
    • 弹出栈顶元素，并计算该矩形的面积
  • 第二部分：处理剩余柱子：
    • 如果所有柱子遍历完了，但栈中仍有元素，说明这些柱子延伸到整个直方图的最右边
    • 再次弹出栈顶元素，计算剩余部分的矩形面积
class Solution:
    def largestRectangleArea(self, nums):
        stack = []                  # 用来存放柱子的索引，保持栈中对应的柱子高度是递增的
        max_ = 0                    # 初始化 最大面积=0

        for i in range(len(nums)):
            while stack and nums[i] < nums[stack[-1]]:       # 如果栈不为空且当前柱子的高度小于栈顶柱子的高度
                h = nums[stack.pop()]                        # 弹出栈顶元素
                w = i if not stack else i - stack[-1] - 1    # 计算矩形的宽度
                max_ = max(max_, h * w)                      # 更新最大面积
            stack.append(i)                                  # 将当前柱子的索引压入栈中

        while stack:                                         # 处理栈中剩余的柱子
            h = nums[stack.pop()]
            # 栈为空宽度为 len(nums)，栈不为空 右边界为 len(nums) 左边界为栈中新的栈顶元素的下一个索引
            w = len(nums) if not stack else len(nums) - stack[-1] - 1
            max_ = max(max_, h * w)

        return max_
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 33.电话号码的字母组合

  • 17.电话号码的字母组合 (opens new window)
  • 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合，答案可以按 任意顺序 返回
  • 给出数字到字母的映射如下（与电话按键相同）注意 1 不对应任何字母

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = "2"
输出：["a","b","c"]
1
2
3
4
5

# 1、python

class Solution:
    def letterCombinations(self, digits):
        if not digits:
            return []

        dic = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }

        def dfs(start, path):
            if start == len(digits):              # 如果索引到达数字字符串的末尾，表示组合已完成
                res.append(path)                  # 将当前的字母组合添加到结果列表
                return

            chars = dic[digits[start]]            # 获取当前数字对应的字母
            for i in range(len(chars)):           # 遍历当前数字对应的所有字母
                char = chars[i]
                dfs(start + 1, path + char)       # 递归生成下一个位置的字母组合

        res = []
        dfs(0, "")
        return res

print(Solution().letterCombinations("23"))       # ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
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

# 34.长度最小的子数组

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组
1
2
3

# 1、python

  • 左右指针初始都指向0，列表开头位置
  • 右指针逐步向右移动，将新元素加到总和中
  • 当总和达到或超过目标时，尝试移动左指针来缩小窗口，并更新最小长度
class Solution:
    def minSubArrayLen(self, target, nums):
        min_ = float("inf")                         # 初始化最小数组长度为无穷大
        sum = 0
        l = 0
        for r in range(len(nums)):
            sum += nums[r]                             # 扩展窗口，增加当前元素到总和
            while sum >= target:                       # 当总和达到或超过目标时，尝试收缩窗口
                min_ = min(min_, r - l + 1)      # 更新最小长度
                sum -= nums[l]                         # 从总和中减去左侧元素
                l += 1

        return min_ if min_ != float("inf") else 0

print( Solution().minSubArrayLen(7, [2, 3, 1, 2, 4, 3]) )  # 输出 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 35.滑动窗口最大值

# 1、python

  • 使用list模仿队列，存储元素值倒序排列（存的是索引）

    • eg: q = [1,2,3]       # 实际值是 [3, -1, -3]
      1

  • r 指针不断滑动，加入新元素与队尾最小元素比对

  • 如果r指针新元素比队尾元素大，就一直pop()出队，直到队列为空或者遇到比当前元素大的值

  • 然后将当前元素加入队列，移除不在当前窗口范围内的元素，记录窗口最大值

class Solution:
    def maxSlidingWindow(self, nums, k):
        res = []
        q = []                                    # 保持q中元素值倒序排列（存的是索引）用队列其实更好
        l = 0
        for r in range(len(nums)):
            while q and nums[q[-1]] < nums[r]:    # 如果当前值大于栈顶元素就出栈
                q.pop()
            q.append(r)                           # 当前值 小于等于 栈顶值时 入栈（索引）

            if q[0] < l:                          # 移除不在当前窗口范围内的元素
                q.pop(0)

            if r >= k - 1:                        # 当窗口达到大小 k 时，记录最大值
                res.append(nums[q[0]])
                l += 1                            # 窗口左边界右移

        return res

print(Solution().maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3, 3, 5, 5, 6, 7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 36.前 K 个高频元素

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

# 1、python

  • 使用快排 查找前k大数，然后只对这些数排序
from collections import Counter

class Solution:
    def topKFrequent(self, nums, k):
        dic_cnt = Counter(nums)                      # 统计每个元素的频率 {1: 3, 2: 2, 3: 1}
        arrs = list(dic_cnt.items())                 # 将频率转换为 [(1, 3), (2, 2), (3, 1)]

        def quick_select(low, high, k):
            p = arrs[low][1]                         # 选择最左边的数作为基准
            l, r = low, high

            while l < r:
                while l < r and arrs[r][1] <= p:
                    r -= 1
                if l < r:
                    arrs[l] = arrs[r]

                while l < r and arrs[l][1] > p:
                    l += 1
                if l < r:
                    arrs[r] = arrs[l]

            arrs[l] = (arrs[l][0], p)            # l == r, p 的最终位置确定

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

        quick_select(0, len(arrs) - 1, k)                   # 快速选择前 k 个高频元素
        return [arrs[i][0] for i in range(k)]               # 打印前k个 [(1, 3), (2, 2), (3, 1)]

print(Solution().topKFrequent( [1, 1, 1, 2, 2, 3], 2))  # 输出: [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
26
27
28
29
30
31
32
33
34
35

# 37.乘积最大子数组

  • 152.乘积最大子数组 (opens new window)

  • 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组

  • （该子数组中至少包含一个数字），并返回该子数组所对应的乘积

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6
1
2
3

# 1、python

  • 这是一个经典的动态规划问题，要求在数组中找出乘积最大的连续子数组
  • 由于负数的存在，最大乘积可能会通过将最小的负数翻转为正数而获得，因此在计算过程中需要同时维护最大值和最小值
  • 以 数组 nums = [2, 3, -2, 4]为例
class Solution:
    def maxProduct(self, nums):
        max_ = min_ = res = nums[0]              # 最大乘积 最小乘积、最终的最大乘积 都是第一个元素
        for i in range(1, len(nums)):
            if nums[i] < 0:                      # 如果当前小于0 最大最小交互位置
                max_, min_ = min_, max_
            max_ = max(nums[i], nums[i] * max_)
            min_ = min(nums[i], nums[i] * min_)
            res = max(res, max_)
        return res

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

# 38.最长连续序列

  • 128.最长连续序列 (opens new window)
  • 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
  • 请你设计并实现时间复杂度为 O(n) 的算法解决此问题
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]它的长度为 4
1
2
3

# 1、python

  • 将nums转换为 set集合

  • 循环遍历集合中元素，判断当前元素是否是 序列起点（i-1不在集合中）

  • 不断查找连续序列，直到i的下一个数不存在于数组中

class Solution:
    def longestConsecutive(self, nums):
        res = 0                              # 记录最长连续序列的长度
        set_ = set(nums)                     # 记录is中的所有数值
        for i in set_:
            if (i - 1) not in set_:          # 如果当前的数是一个连续序列的起点，统计这个连续序列的长度
                len_ = 1                     # 连续序列的长度，初始为1
                while (i + 1) in set_:
                    len_ += 1
                    i += 1                   # 不断查找连续序列，直到i的下一个数不存在于数组中
                res = max(res, len_)         # 更新最长连续序列长度
        return res
1
2
3
4
5
6
7
8
9
10
11
12

# 39.最大数

  • 179.最大数 (opens new window)
  • 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
  • **注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数
输入：nums = [3,30,34,5,9]
输出："9534330"
1
2

# 1、python

  • 通过自定义冒泡排序，两两相加比较，如果交换位置结果更大就交换位置
class Solution:
    def largestNumber(self, nums):
        def bubble_sort(nums):
            for i in range(len(nums)):
                for j in range(0, len(nums) - i - 1):
                    if nums[j] + nums[j + 1] < nums[j + 1] + nums[j]:    # nums[j]=3  nums[j + 1]=30   330 > 303 条件不成立，不交换
                        nums[j], nums[j + 1] = nums[j + 1], nums[j]      # 如果 nums[j] + nums[j+1] 小于 nums[j+1] + nums[j]，交换位置
        nums_str = list(map(str, nums))       # ['3', '30', '34', '5', '9']
        bubble_sort(nums_str)                 # ['9', '5', '34', '3', '30']
        result = ''.join(nums_str)            # 拼接排序后的数字
        if result[0] == '0':                  # 特殊情况处理：如果结果的第一个字符是 '0'，则说明所有数字都是 0
            return '0'
        return result

print( Solution().largestNumber([3, 30, 34, 5, 9]) )  # 输出: "9534330"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • ['3', '30', '34', '5', '9'] 推演
# 初始值 ['3', '30', '34', '5', '9']
330 > 303     =>  ['3', '30', '34', '5', '9']    #不变
3034 < 3430   =>  ['3', '34', '30', '5', '9']    #交换
305 < 530     =>  ['3', '34', '5', '30', '9']    #交换
309 < 930     =>  ['3', '34', '5', '9', '30']    #交换
# 第二次循环 ['3', '34', '5', '9',    '30']   30已经放到最后了，只需要比较前面4个数据
1
2
3
4
5
6

# 40.分发糖果

  • 135.分发糖果 (opens new window)
  • n 个孩子站成一排给你一个整数数组 ratings 表示每个孩子的评分
  • 你需要按照以下要求，给这些孩子分发糖果：
    • 每个孩子至少分配到 1 个糖果
    • 相邻两个孩子评分更高的孩子会获得更多的糖果
  • 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果
1
2
3

# 1、python

  • 初始化糖果数组，每个孩子至少得到1颗糖果
  • 从左到右遍历，确保右侧评分更高的孩子得到更多糖果
  • 然后 从右到左遍历，确保左侧评分更高的孩子得到更多糖果
class Solution:
    def candy(self, ratings):
        n = len(ratings)
        candies = [1] * n                            # 初始化糖果数组，每个孩子至少得到1颗糖果
        for i in range(1, n):                        # 从左到右遍历，确保右侧评分更高的孩子得到更多糖果
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1      # 如果当前孩子的评分高于前一个孩子，糖果数应比前一个孩子多1

        for i in range(n - 2, -1, -1):               # 从右到左遍历，确保左侧评分更高的孩子得到更多糖果
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)   # 如果当前孩子的评分高于后一个孩子，糖果数应比后一个孩子多1
        return sum(candies)
1
2
3
4
5
6
7
8
9
10
11
12

# 41.和为 K 的子数组

输入：nums = [1,2,3], k = 3
输出：2  # 1,2 和 3 两种
1
2

# 1、python

  • 前缀和是指从数组的开始位置到当前位置所有元素的累积和
  • 使用前缀和，可以将一个子数组的和转换为前缀和之间的差值，从而更高效地判断是否存在某个和为 kkk 的子数组
class Solution:
    def subarraySum(self, nums, k):
        dic = {0: 1}                   # 字典记录前缀和出现的次数，表示前缀和为0的子数组出现过1次
        sum, count = 0, 0              # 当前的前缀和, 和为k的子数组的数量
        for i in nums:
            sum += i                   # 更新当前的前缀和
            if sum - k in dic:         # 如果 (当前前缀和 - k) 在哈希表中，说明 存在 和为 k 的子数组
                count += dic[sum - k]
            dic[sum] = dic.get(sum, 0) + 1   # 将当前的前缀和记录到哈希表中

        print(dic)  # {0: 1, 1: 1, 3: 1, 6: 1, 4: 1, 9: 1}
        return count

print(Solution().subarraySum([1,2,3,-2,5], 5) )  # [2,3]   [5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 42.打家劫舍

  • 198.打家劫舍 (opens new window)
  • 你是一个专业的小偷，计划偷窃沿街的房屋
  • 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统
  • 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
  • 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)  偷窃到的最高金额 = 1 + 3 = 4
1
2
3

# 1、python dp

  • 核心思想是对于每个房子，我们有两个选择：偷或者不偷

  • dp[i] 表示偷到第 i 个房子时能偷到的最大金额

  • 不偷：那么最大金额就是前一个房子偷到的最大金额，即 dp[i-1]

  • 偷：那么最大金额是当前房子的钱加上前前一个房子偷到的最大金额，即 dp[i-2] + nums[i]

  • 边界条件：

    • dp[0] = nums[0]，只有一个房子时，偷该房子
    • dp[1] = max(nums[0], nums[1])，两个房子时，偷钱更多的那个
class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
    
        dp = [0] * n                       # 创建dp数组，dp[i]表示偷到第i间房子时能获得的最大金额
        dp[0] = nums[0]                    # 只有一间房子时，最大金额就是偷这间房子的金额
        dp[1] = max(nums[0], nums[1])      # 有两间房子时，选择金额较大的那一间
        for i in range(2, n):              # 从第3间房子开始遍历到最后一间，更新dp数组
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])         # 不偷（dp[i-1]）偷（dp[i-2] + nums[i]）
            
        return dp[-1]                      # 返回dp数组的最后一个值，即偷到最后一间房子时能获得的最大金额
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 43.零钱兑换 II

  • 518.零钱兑换 II (opens new window)

  • 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额

  • 请你计算并返回可以凑成总金额的硬币组合数如果任何硬币组合都无法凑出总金额，返回 0

  • 假设每一种面额的硬币有无限个

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：[1,1,1,1,1], [1,1,1,2], [1,2,2], [5]
1
2
3

# 1、python dp

  • 状态定义：我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 的方法数
  • 状态转移方程： dp[i] += dp[i - coin] 表示我们把之前 dp[i - coin] 的组合数加到 dp[i] 中
    • 如果我们已经知道了组合成金额 i - coin 的方法数
    • 那么，所有组合成金额 i - coin 的方法加上这个硬币 coin 都是组合成金额 i 的有效方法
  • 初始状态：[1, 0, 0, 0, 0, 0]
    • dp[0] 为 1，因为凑成金额 0 的唯一方法是使用 0 个硬币
  • 最终 dp = [1, 1, 2, 2, 3, 4]
class Solution:
    def change(self, amount, coins):
        dp = [0] * (amount + 1)    # 创建一个长度为 amount+1 的数组 dp，dp[i] 表示凑成金额 i 的方法数
        dp[0] = 1                  # 初始化 dp[0] 为 1，因为凑成金额 0 的唯一方法是使用 0 个硬币
        for coin in coins:
            for i in range(coin, amount + 1):    # 更新 dp 数组，从当前硬币面值开始到目标金额
                dp[i] += dp[i - coin]            # dp[i] 的新值为 dp[i] 加上 dp[i-coin]，即使用当前硬币前后的组合数
        return dp[amount]                        # 返回凑成金额 amount 的所有组合方法数

print(Solution().change(5, [1, 2, 5]))
""" dp变化
[1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1]  # coin = 1 (只使用 1 硬币时，最多只有1种方法 [1,1,1,1,1])
[1, 1, 2, 2, 3, 3]  # coin = 2 (使用 1 2硬币时，最多有3种方法 [1,1,1,1,1], [1,1,1,2], [1,2,2])
[1, 1, 2, 2, 3, 4]  # coin = 5 (使用 1 2 5硬币时，最多有四种方法 [1,1,1,1,1], [1,1,1,2], [1,2,2], [5])
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 44.每日温度

  • 739.每日温度 (opens new window)
  • 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
  • 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
  • 如果气温在这之后都不会升高，请在该位置用 0 来代替
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
1
2

# 1、python

  • 使用栈用于存储未找到更高温度的下标（栈顶温度是栈中最小的）
  • 当前温度高于栈顶温度, 计算天数的差更新到 res数组对应位置
  • 将当前天的下标入栈 (栈为空 或 当前温度小于等于栈顶温度)
class Solution:
    def dailyTemperatures(self, temperatures):
        nums = temperatures
        res = [0] * len(nums)        # 初始值为 0，表示如果没有找到更高的温度则保持为0
        stack = []                   # 栈用于存储未找到更高温度的下标（栈顶温度是栈中最小的）
        
        for i in range(len(nums)):
            while stack and nums[i] > nums[stack[-1]]:    # 当前温度高于栈顶温度, 计算天数的差更新到 res数组对应位置
                top_index = stack.pop()                   # 获取栈顶下标
                res[top_index] = i - top_index            # 计算天数差并存入结果数组
            stack.append(i)                               # 将当前天的下标入栈 (栈为空 或 当前温度小于等于栈顶温度)

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

# 45.跳跃游戏

  • 55.跳跃游戏 (opens new window)
  • 给你一个非负整数数组 nums ，你最初位于数组的第一个下标数组中的每个元素代表你在该位置可以跳跃的最大长度(可以比当前长度小)
  • 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false
输入：nums = [2,3,1,1,4]   输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标

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

# 1、python

  • 变量 max_ 用于记录当前能够到达的最远位置

  • i > max_成立，证明无法到达 当前 i位置直接返回 False

  • 否则更新max_为当前可到达的最远位置（当前i位置坐标+当前能跳的最大位置）

  • 如果max_已经能够到达或超过最后一个下标，返回True

class Solution:
    def canJump(self, nums):
        max_ = 0                       # 变量 max_ 用于记录当前能够到达的最远位置
        for i in range(len(nums)):
            if i > max_:               # i 超出了 max_ 无法达到当前 i 位置，直接返回 False
                return False
            else:
                max_ = max(max_, i + nums[i])     # 更新max_为当前可到达的最远位置（当前i位置坐标+当前能跳的最大位置）
                if max_ >= len(nums) - 1:         # 如果max_已经能够到达或超过最后一个下标，返回True
                    return True
        return False        # 如果遍历结束后，max_ 仍未到达最后一个下标，返回False

print( Solution().canJump([3,2,1,0,4]) )    # False
""" [3,2,1,0,4] 输出 False 推演 max(max_, i + nums[i]) 
i=0  max_=max(0, 0+3)=3
1=1  max_=max(3, 1+2)=3
i=2  max_=max(3, 2+1)=3
i=3  max_=max(3, 3+0)=3
i=4  max_=3 不符合 i <= max_ 所以最终返回 False
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 46.跳跃游戏 II

  • 45.跳跃游戏 II (opens new window)
  • 给定一个长度为 n 的整数数组 nums初始位置为 nums[0]
  • 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处
  • 返回到达 nums[n - 1] 的最小跳跃次数
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2，从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置
1
2
3

# 1、python

  • 对于每个位置，计算可以达到的最远位置 tmp_max
  • 如果当前位置是当前跳跃的最远位置 max_，则更新 max_ 为 tmp_max，并增加跳跃次数 steps
  • 如果当前位置 i 等于 max_，我们需要进行一次跳跃，以便扩展跳跃范围，继续前进（否则未到达最远位置 不增加跳跃次数）
class Solution:
    def jump(self, nums):
        steps = 0            # 跳跃次数
        max_ = 0             # 当前跳跃能到达的最远位置
        tmp_max = 0          # 遍历过程中能到达的最远位置

        for i in range(len(nums) - 1):
            # 更新当前跳跃范围内能到达的最远位置
            tmp_max = max(nums[i] + i, tmp_max)         # `nums[i] + i` 表示从当前位置 `i` 能跳到的最远位置
            if i == max_:                               # 当前位置 i 等于 max_，我们需要进行一次跳跃，以便扩展跳跃范围，继续前进
                max_ = tmp_max                          # 更新当前跳跃范围的结束位置
                steps += 1
                if max_ >= len(nums) - 1:               # 如果可以到达最后一个位置，提前结束
                    break
        return steps

print( Solution().jump([3,2,1,3,2,1]) )    # 输出 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 47.最接近的三数之和

  • 16.最接近的三数之和 (opens new window)
  • 给你一个长度为 n 的整数数组 nums 和 一个目标值 target请你从 nums 中选出三个整数，使它们的和与 target 最接近
  • 返回这三个数的和，假定每组输入只存在恰好一个解
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)
1
2
3

# 1、python

  • 使用一个循环遍历数组，选定一个基准数 nums[i]
  • l 和 r分别指向剩余部分的最左边和最右边的元素
  • 如果当前和更接近目标值，则更新最接近的和
  • 如果当前和小于目标值 l += 1,如果当前和大于目标值r -= 1 循环完成即可找到最接近
class Solution:
    def threeSumClosest(self, nums, target):
        nums.sort()
        sum = float('inf')                     # 初始化一个变量用于存储最接近的三数之和
        for i in range(len(nums) - 2):         # 保证i最大能到达倒数第三个位置
            l, r = i + 1, len(nums) - 1
            while l < r:                       # 移动左右指针来寻找最接近的三数之和
                tmp_sum = nums[i] + nums[l] + nums[r]               # 计算当前三数之和
                if abs(tmp_sum - target) < abs(sum - target):       # 如果当前和更接近目标值，则更新最接近的和
                    sum = tmp_sum

                if tmp_sum == target:          # 如果当前和正好等于目标值，直接返回
                    return tmp_sum
                elif tmp_sum < target:         # 如果当前和小于目标值，说明需要更大的数，将左指针右移
                    l += 1
                else:                          # 如果当前和大于目标值，说明需要更小的数，将右指针左移
                    r -= 1

        return sum        # 返回找到的最接近的三数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 48.组合总和 II

  • 40.组合总和 II (opens new window)
  • 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
  • candidates 中的每个数字在每个组合中只能使用一次
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
  [1,1,6],
  [1,2,5],
  [1,7],
  [2,6]
]
1
2
3
4
5
6
7
8

# 1、python

  • 使用深度优先搜索（DFS）来构建组合。递归函数 dfs 用于探索所有可能的组合路径
  • 在每一次递归调用中，k 是通过减去当前选中的数字 nums[i] 来更新的（即 k - nums[i]）
class Solution:
    def combinationSum2(self, candidates, target):
        nums = candidates
        def dfs(start, path, k):
            if k == 0:
                res.append(list(path))
                return
            elif k < 0:                                      # 如果剩余目标值小于0，终止搜索
                return

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:     # 跳过重复元素，确保结果不重复
                    continue
                path.append(nums[i])
                dfs(i + 1, path, k - nums[i])                # 不允许重复使用数字，索引移动到下一个元素
                path.pop()

        nums.sort()                                          # 对数字进行排序，以便剪枝和去重
        res = []
        dfs( 0, [], target)
        return res

print(Solution().combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 49.在排序数组中查找元素的第一个和最后一个位置

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

# 1、python

class Solution:
    def searchRange(self, nums, target):
        def find_pos(nums, target, find_first):
            l, r = 0, len(nums) - 1
            pos = -1                          # position 位置
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    pos = mid
                    if find_first:
                        r = mid - 1           # 查找第一个位置，继续向左
                    else:
                        l = mid + 1           # 查找最后一个位置，继续向右
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return pos

        first_pos = find_pos(nums, target, True)
        last_pos = find_pos(nums, target, False)
        return [first_pos, last_pos]

print(Solution().searchRange([5, 7, 7, 8, 8, 10], 8))  # 输出: [3, 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

# 50.字母异位词分组

  • 49.字母异位词分组 (opens new window)
  • 给你一个字符串数组，请你将 字母异位词 组合在一起可以按任意顺序返回结果列表
  • 字母异位词 是由重新排列源单词的所有字母得到的一个新单词
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

输入: strs = [""]
输出: [[""]]
1
2
3
4
5

# 1、python

  • 使用一个字典来存储字母异位词组，字典key使用 字母异位词组排序
  • 只要是 字母异位词组，排序后结果肯定是一样的，存储即可
  • {'aet': ['eat', 'eat', 'tea'], 'ant': ['nat']}
class Solution:
    def groupdic(self, strs):
        dic = {}                            # 初始化一个空字典，用于存储字母异位词组
        for s in strs:
            key = ''.join(sorted(s))        # 将字符串排序，得到字母异位词的唯一标识
            if key not in dic:              # 如果key不在字典中，则创建一个新的列表
                dic[key] = []
            dic[key].append(s)              # 将原字符串加入对应的字母异位词组中
        return list(dic.values())           # 返回所有字母异位词组

print( Solution().groupdic(["eat", "eat", "tea", "nat"]) )  # [['eat', 'eat', 'tea'], ['nat']]
1
2
3
4
5
6
7
8
9
10
11

# 51.加油站

  • 134.加油站 (opens new window)
  • 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升
  • 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
  • 你从其中的一个加油站出发，开始时油箱为空
  • 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1
  • 如果存在解，则 保证 它是 唯一 的
输入: 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 可为起始索引
1
2
3
4
5
6
7
8
9
10

# 1、python

  • 只要所有的 总油量大于等于总消耗 就可以保证可以返回（因为起点可以自己选择）
  • 当油量不足以支持前进时，需要将起点移到下一个加油站，继续尝试
  • 题目中已说明如果存在解，则解是唯一的，这意味着我们只需找到那个起始点即可
class Solution:
    def canCompleteCircuit(self, gas, cost):
        record = 0                        # 总油量-总消耗（减去）
        cur = 0                          # 当前油量-当前消耗（减去）
        start_index = 0                  # 起始站点索引

        for i in range(len(gas)):
            record += gas[i] - cost[i]      # gas[i]（加油站汽油量）- cost[i]（下一个加油站消耗量）
            cur += gas[i] - cost[i]        # 更新当前油量与当前消耗的差值
            if cur < 0:                    # 如果当前油量不足以前进到下一个站点
                start_index = i + 1        # 将起点设置为下一个站点
                cur = 0                    # 重置当前油量，因为我们从新的站点重新开始

        return start_index if record >= 0 else -1      # 总油量大于等于总消耗，返回起始站点索引，否则返回 -1

print( Solution().canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2]) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
上次更新: 2024/9/27 11:33:57
01.数组
11.字符串

← 11.字符串→

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