• LeetCode Cookbook 数组习题（1）

    LeetCode Cookbook 数组习题（1）

      时间不多了 我要在这个月底把数据结构给完整的一遍，在阅读论文的同时认真地将算法好好的复习一遍，不多说了，开始！

    1. 两数之和

    题目链接：1. 两数之和
    题目大意：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

    • 两种解法（1）数组-双循环；（2）字典：单循环，比较快，空间换时间。
    class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        '''
        # 很耗时！
        # 使用数组双循环的方法并不好用 很慢
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j] == target:
                    return [i,j]
        '''

        # 使用字典的方法 要快不少
        # 把看过的数组的下标存起来 调用要比双循环 在时间上快不少
        vis = dict()
        for i,num in enumerate(nums):
            if target-num in vis:
                return [vis[target-num],i]
            vis[num] = i

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

    4. 寻找两个正序数组的中位数*

    题目链接：4. 寻找两个正序数组的中位数
    题目大意：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。

    • 需要灵活的使用 变形的二分法 非常不容易记忆 但有需要深刻记忆 学会背诵这里面的查询第k小元素的 getKthElement 子函数。
    class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        def getKthElement(k: int) -> float:
            id1,id2 =  0,0
            while 1:
                if id1 == n1:
                    return nums2[id2+k-1]
                if id2 == n2:
                    return nums1[id1+k-1]
                if k == 1:
                    return min(nums1[id1],nums2[id2])
                
                newId1 = min(id1+(k//2-1),n1-1)
                newId2 = min(id2+(k//2-1),n2-1)
                num1,num2 = nums1[newId1],nums2[newId2]

                if num1 <= num2:
                    k -= newId1-id1+1
                    id1 = newId1+1
                else:
                    k -= newId2-id2+1
                    id2 = newId2+1
            
        n1,n2 = len(nums1),len(nums2)
        n = n1+n2   
        if n%2 != 0:
            return getKthElement(n//2+1)
        else:
            return (getKthElement(n//2)+getKthElement(n//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

    11. 盛最多水的容器*

    题目链接：11. 盛最多水的容器
    题目大意：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

    解题思路： 双头指针

    1. 如何计算矩形面积 tmp = (R-L)*min(height[L],height[R])
    2. 指针R，L的移动判断 height[L]与height[R]的大小比较
    3. 不断比较 找出最大值
    class Solution:
    def maxArea(self, height: List[int]) -> int:
        L,R = 0,len(height)-1
        ans = 0
        while L<R:
            # 矩形的长为 R-L 高为 min(height[L],height[R])
            tmp = (R-L)*min(height[L],height[R])
            ans = max(ans,tmp)
            if height[L] < height[R]:
                L += 1
            else:
                R -= 1
        return ans

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

    15. 三数之和*

    题目链接：15. 三数之和
    题目大意：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

    解题思路： 双头指针

    1. 两个起始条件、四个细节难点
    2. 细节拉满，需要多琢磨
    class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        # 起始条件一
        if n<3: return []

        # 起始条件二
        nums.sort()
        ans = list()
        for i in range(n):
            # 这道题很让人无奈 另外 条件也很不容易记忆
            # 细节难点一
            # (1) 既然 Sum == 0 那么最小的数大于0 返回结果就Ok！
            # (2) 过滤重复元素
            if nums[i] > 0 : return ans
            if i>0 and nums[i] == nums[i-1]: continue

            L,R = i+1,n-1
            while L<R:
                if nums[i]+nums[L]+nums[R] == 0:
                    ans.append([nums[i],nums[L],nums[R]])
                    # 细节难点二
                    while L<R and nums[L] == nums[L+1] :
                        L += 1
                    while L<R and nums[R] == nums[R-1]:
                        R -= 1
                    # 细节难点三 注意了 双头指针要往里面 收一收
                    L,R = L+1,R-1
                # 细节难点四
                elif nums[i]+nums[L]+nums[R] < 0:
                    L += 1
                else:
                    R -= 1
        return ans

    • 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

    16. 最接近的三数之和

    题目链接：16. 最接近的三数之和
    题目大意：给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

    解题思路：

    1. 使用15. 三数之和 的去重思路和while循环
    2. 注意 update() 函数的编写
    class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        ans = 10**7

        def update(cur: int)->int:
            # 局部变量
            nonlocal ans
            if abs(cur-target) < abs(ans-target):
                ans = cur

        for i in range(n):
            # 结果子集去重
            if i>0 and nums[i]==nums[i-1]:
                continue
            L,R = i+1,n-1
            while L<R:
                s = nums[i]+nums[L]+nums[R]
                if s == target: return target
                update(s)
                if s < target:
                    L += 1
                    # 去重
                    while L<R and nums[L]==nums[L+1]: L += 1
                else:
                    R -= 1
                    while L<R and nums[R]==nums[R-1]: R -= 1
        return ans

    • 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

    18. 四数之和

    题目链接：18. 四数之和
    题目大意：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

    • 0 <= a, b, c, d < n；
    • a、b、c 和 d 互不相同；
    • nums[a] + nums[b] + nums[c] + nums[d] == target；
      你可以按 任意顺序 返回答案 。

    解题思路：

    1. 15. 三数之和 的进阶版本
    2. 两层 For 循环的编写 很重要！
    class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        if n<4: return ans
        
        for i in range(n-3):
            if i>0 and nums[i]==nums[i-1]: continue
            if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target:break
            if nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target:continue

            for j in range(i+1,n-2):
                if j>i+1 and nums[j]==nums[j-1]: continue
                if nums[i]+nums[j]+nums[j+1]+nums[j+2] > target:break
                if nums[i]+nums[j]+nums[n-2]+nums[n-1] < target:continue
                L,R = j+1,n-1
                while L<R:
                    s = nums[i]+nums[j]+nums[L]+nums[R]
                    if s == target:
                        ans.append([nums[i],nums[j],nums[L],nums[R]])
                        while L<R and nums[L]==nums[L+1]: L += 1
                        while L<R and nums[R]==nums[R-1]: R -= 1
                        L,R = L+1,R-1
                    elif s < target:
                        L += 1
                    else:
                        R -= 1
        return ans

    • 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

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

    题目链接：26. 删除有序数组中的重复项
    题目大意：给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。将最终结果插入 nums 的前 k 个位置后返回 k 。注意：不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    解题思路：

    • 这道题理解起来不难，主要抓住题意中的 原数组改动
    • 使用快慢指针 具体看代码 就是 low和fast这两个
    class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        low,fast = 1,1
        while fast<n:
            if nums[fast] != nums[fast-1]:
                nums[low]=nums[fast]
                low += 1
            fast += 1
        return low

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    27. 移除元素

    题目链接：27. 移除元素
    题目大意：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    解题思路：

    class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n=len(nums)
        low,fast = 0,0
        while fast<n:
            if nums[fast] != val:
                nums[low] = nums[fast]
                low += 1
            fast += 1
        return low

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    33. 搜索旋转排序数组*

    题目链接：33. 搜索旋转排序数组
    题目大意：整数数组 nums 按升序排列，数组中的值 互不相同 。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

    解题思路：

    • 经典二分模板 充分利用提议中所说的升序段
    class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        L,R = 0,n-1
        while L<=R:
            mid = L+(R-L)//2
            if nums[mid] == target: return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    R = mid-1
                else:
                    L = mid+1
            else:
                if nums[mid] < target <= nums[n-1]:
                    L = mid+1
                else:
                    R = mid-1
        return -1

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

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

    题目链接：34. 在排序数组中查找元素的第一个和最后一个位置
    题目大意：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

    解题思路：

    • 双头指针的方法最简单了！
    class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        # 双指针
        n = len(nums)
        if n == 0 or target not in nums: return [-1,-1]
        low,high = 0,n-1
        while low<=high:
            if nums[low] == target: low = low
            else: low += 1
            if nums[high] == target: high = high
            else: high -= 1
            if low >= 0 and high >= 0  and nums[low] == nums[high]:
                return [low,high]
                break

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    35. 搜索插入位置

    题目链接：33. 搜索旋转排序数组
    题目大意：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

    解题思路：

    • 经典二分模板 不多赘述
    class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        L,R = 0,len(nums)-1
        while L<=R:
            mid = L+(R-L)//2
            if nums[mid] == target:
                return mid
            if nums[mid]>target:
                R = mid-1
            else:
                L = mid+1
        return L

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    39. 组合总和*

    题目链接：39. 组合总和
    题目大意：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为 target 的不同组合数少于 150 个。

    解题思路：

    • 递归 - 回溯算法 经典题目 好好背一下吧！
    • 这里有一个 编程的知识点 [1]+[2] = [1,2]
    class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        def backTrack(start: int,tmp:List[int],target:int) -> None:
            for i in range(start,n):
                c = candidates[i]
                if c == target:
                    ans.append(tmp+[c])
                    return 
                if c < target:
                    backTrack(i,tmp+[c],target-c)
                else:
                    return

        candidates.sort()
        n = len(candidates)
        ans = []
        backTrack(0,[],target)
        return ans

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

    40. 组合总和 II

    题目链接：40. 组合总和 II
    题目大意：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。

    解题思路：

    1. 去重上 加入if i>start and candidates[i-1] == candidates[i]: continue
    2. 不重复 因此回溯需要往前走 backTrack(i+1,tmp+[c],target-c)
    class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backTrack(start: int,tmp:List[int],target:int) -> None:
            for i in range(start,n):
                if i>start and candidates[i-1] == candidates[i]:
                    continue
                c = candidates[i]
                if c == target:
                    ans.append(tmp+[c])
                    return 
                if c < target:
                    backTrack(i+1,tmp+[c],target-c)
                else:
                    return

        candidates.sort()
        n = len(candidates)
        ans = []
        backTrack(0,[],target)
        return ans

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

    总结

      今天，就先到这里，今天涨了几个粉丝，挺开心的！继续加油，明天，读论文，再写点总结。

  • 相关阅读:
    总结三：计算机网络面经
    05-HttpServlet类
    C# 如何使用windows服务做定时任务
    hdu 4841 “圆桌问题“
    前后端分离之Ajax入门
    IB中文A语言与文学：视觉文本分析
    还有半小时下班，用Python写个五子棋摸摸鱼~一天就过去啦~
    深入理解java并发编程之aqs框架
    Unity UGUI的RawImage（原始图片）组件的介绍及使用
    web基础学习
  • 原文地址：https://blog.csdn.net/weixin_42269028/article/details/126440804