LeetCode 算法入门

感觉自己的算法和编程太弱了😭，故每天在 LeetCode 上刷一两道算法题，希望慢慢提高自己的算法能力和编程能力，从简单的题目开始慢慢刷吧，看看自己能坚持多久，fighting是💪！！！

二分查找

704. 二分查找

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

解答

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。
如果目标值较小，继续在左侧搜索。
如果目标值较大，则继续在右侧搜索。

class Solution:
    """二分查找"""
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + ((right -left) >> 1)
            if nums[mid] == target:
                return mid
            elif target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return -1

• 1、循环条件： left <= right
  • 循环条件包含了 left == right的情况，则我们必须在每次循环中改变 left 和 right的指向，以防止进入死循环。
• 2、循环终止条件包括：
  • 找到了目标值
  • left > right （这种情况发生于当left, mid, right指向同一个数时，这个数还不是目标值，则整个查找结束。）
• 3、中间位置计算： mid = left + ((right -left) >> 1)
  • left + ((right -left) >> 1) 其实和 (left + right) / 2是等价的，这样写的目的一个是为了防止 (left + right)出现溢出，用右移操作(>>)替代除法提升了性能。
• 4、左边界更新：left = mid + 1
• 5、右边界更新： right = mid - 1
• 6、返回值： mid / -1

复杂度

时间复杂度：$\mathcal{O}(\log n)$​

空间复杂度：$\mathcal{O}(1)$

278. 第一个错误的版本

题目

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 231 - 1

解答

将左右边界分别初始化为 1 和 n，其中 n 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。直到 left=right，只剩下一个数了，这个数就是第一个错误的。

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right =1, n
        while left < right: 
            mid = left + ((right -left) >> 1)
            if isBadVersion(mid):
                right = mid     # 答案在区间 [left, mid] 中
            else:
                left = mid + 1  # 答案在区间 [mid+1, right] 中
        return left             # 此时有 left == right，区间缩为一个点，即为答案

复杂度

• 时间复杂度：$\mathcal{O}(\log n)$​，其中 n 是给定版本的数量。
• 空间复杂度：$\mathcal{O}(1)$。我们只需要常数的空间保存若干变量。

35. 搜索插入位置

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为无重复元素的升序排列数组
• -104 <= target <= 104

解答

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)- 1
        while left <= right:
            mid = left + ((right - left) >> 1)
            if nums[mid] == target:
                return mid
            elif target < nums[mid]:
                right = mid -1
            else:
                left = mid + 1
        return  left

双指针

977.有序数组的平方

题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

解答

方法一：直接排序

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(pow(num,2) for num in nu

方法二：双指针

方法一没有利用「数组 nums 已经按照升序排序」这个条件。

如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i 指向起始位置，j 指向终止位置。

定义一个新列表 res，和 nums 列表一样的大小，让 k 指向 res 终止位置。

如果nums[i] * nums[i] < nums[j] * nums[j] 那么 result[k--] = A[j] * A[j]

如果 nums[i] * nums[i] >= nums[j] * nums[j] 那么result[k--] = A[i] * A[i]

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        i, j, k = 0, len(nums)-1, len(nums)-1
        res = [-1] * len(nums)
        while i <= j:
            if nums[i] * nums[i] > nums[j] * nums[j]:
                res[k] = nums[i] * nums[i]
                i += 1
            else:
                res[k] = nums[j] * nums[j]
                j -= 1
            k -= 1
        return res

189. 旋转数组

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

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

示例 1:

输入: 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:

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

提示：

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

解答

我们可以新建一个列表将每个元素放至正确的位置。首先遍历原列表，将原列表下标为 i 的元素放至新数组下标为 (i+k) mod n 的位置，因为没有返回值，所以题目验证的还是原列表，因此最后将新数组拷贝至原数组即可。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        res = [-1] * len(nums)
        for i in range(len(nums)):
            res[(i+k)%len(nums)] = nums[i]
        for i in range(len(nums)):
            nums[i] = res[i]

283. 移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

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

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

解答

方法一：

给定一个数组，我们需要做的就是将非零的数字移到数组的前面，将0移到数组的末尾，同时不能使用额外的空间。首先使用两个指针，第一个指针 j 从前往后遍历所有的数字，第二个指针 i 指在数组中 0 所在的位置，当 j 遇到非 0 的数字时，我们就交换 num[i] 和 nums[j] 的值。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = -1
        for j in range(len(nums)):
            if nums[j]!=0:
                i+=1
                nums[i],nums[j]= nums[j], nums[i]      
                

方法二：

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。最终左指针左边均为非零数；右指针左边直到左指针处均为零。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

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

题目

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2：

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

示例 3：

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

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 递增顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

解答

初始状态下，令 left 指向第一个元素，right 指向最后一个元素，进入循环，控制循环的退出条件为 left >= right ,在每一次循环中如果 left 与 right 数字之和等于 target ,则返回当前的 left,right；若 left 与 right 数字之和小于 target ，left += 1，继续循环；若 left 与 right 数字之和大于 target ，right -= 1，继续循环；

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:   
        left, right = 0, len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left+1,right+1]
            elif numbers[left] + numbers[right] < target:
                left += 1
            else:
                right -= 1
        return [-1,-1]

复杂度

• 时间复杂度：$\mathcal{O}(n)$​​​​
• 空间复杂度：$\mathcal{O}(1)$​。

344. 反转字符串

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

解答

方法一：双指针

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right =0, len(s)-1
        while left <= right:
            s[left],s[right] = s[right],s[left]
            left += 1
            right -= 1

方法二：库函数

• s[::-1] 表示反转 s 中的元素
• s[:] 表示数组中所有元素
• s[:]=s[::-1] 表示将原数组反转后赋值给 s 中每一个对应的位置
• s=s[::-1] 表示将 s 反转后赋值给新的对象 s（可以通过id函数查看内存地址），与题意原地修改不符。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:]=s[::-1]

557. 反转字符串中的单词 III

题目

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

提示：

• 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

解答

方法一：将字符串分割成单词列表，然后把每个单词反转再拼接

class Solution(object):
    def reverseWords(self, s):
        return " ".join(word[::-1] for word in s.split(" "))

• s.split(" ") 以空格为分隔符将字符串分割成单词列表

• [::-1] 将单词反转

• " ".join() 将单词列表转换为字符串，以空格分隔

方法二：利用两次切片，不需遍历

class Solution(object):
    def reverseWords(self, s):
        return " ".join(s.split(" ")[::-1])[::-1]

以字符串 “I love drag queen” 为例：

• s.split(“ “) 将字符串分割成单词列表:

['I', 'love', 'drag', 'queen']

• s.split(“ “)[::-1] 将单词列表反转:

['queen', 'drag', 'love', 'I']

• “ “.join(s.split(“ “)[::-1]) 将单词列表转换为字符串，以空格分隔:

"queen drag love I"

• “ “.join(s.split(“ “)[::-1])[::-1] 将字符串反转：

”I evol gard neeuq“

链表

876. 链表的中间结点

题目

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

• 给定链表的结点数介于 1 和 100 之间。

解答

用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。快指针可以前进的条件是当前快指针下一个节点和下下个节点都非空。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

19. 删除链表的倒数第 N 个结点

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

解答

方法一：循环迭代– 找到 length -n 个节点

先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L-n 个节点时，它就是我们需要删除的节点。

删除的方法是：找到被删除节点的前置节点，然后将前置节点的 next 指针指向该节点的后置节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head) #定义哑节点，放在头节点前面
        
        #step1: 获取链表长度
        cur, length = head, 0 
        while cur:
            length += 1
            cur = cur.next 
        
        #step2: 找到倒数第N个节点的前面一个节点
        cur = dummy
        for i in range(length - n):
            cur = cur.next
        
        #step3: 删除节点，并重新连接
        cur.next = cur.next.next
        return dummy.next 

方法二：快慢指针 – 找倒数第N个节点的前一个节点

设定双指针 slow 和 fast ，当 fast 指向末尾的 NULL，slow 与 fast 之间相隔的元素个数为 n 时，那么删除掉 slow 的下一个指针就完成了要求。

• 设置虚拟节点 dummy 指向 head
• 设定双指针 slow 和 fast，初始都指向虚拟节点 dummy
• 移动 fast，直到 slow 与 fast 之间相隔的元素个数为 n
• 再同时移动 slow 与 fast ，直到 fast 指向的为 NULL
• 将 slow 的下一个节点指向下下个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head) #定义哑节点，放在头节点前面
        
        #step1: 快指针先走n步
        slow, fast = dummy, dummy
        for i in range(n):
            fast = fast.next 

        #step2: 快慢指针同时走，直到fast指针到达尾部节点，此时slow到达倒数第N个节点的前一个节点
        while fast and fast.next:
            slow, fast = slow.next, fast.next 
        
        #step3: 删除节点，并重新连接
        slow.next = slow.next.next 
        return dummy.next 

Button

赞助💰

如果你觉得对你有帮助，你可以请我喝一杯冰可乐！嘻嘻🤭

支付宝支付	微信支付