日期: 2023 年 7 月 23 日

方法一、双指针

题目要求删除数组中等于val的所以元素，输出数组的长度小于或等于输入数组的长度，因此我们就可以把输出数组写在输入数组上。我们可以选择双指针：右指针i指向当前处理的数组元素，左指针cover_pointer指向下一个将要赋值的位置。

如果右指针指向的当前元素不等于val，nums[i]输出一个元素，我们就将当前元素不等于val值，则复制到覆盖指针指向的位置，并向后移动一位。

如果右指针指向的当前元素等于val，不能输出到数组中左指针不动，并将右指针向后移动一位。

Python3 代码题解

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 初始化覆盖指针和数组长度
        cover_pointer = 0
        length = len(nums)
        for i in range(length):
            if nums[i] != val:
                # 如果当前元素不等于初始值，则复制到覆盖指针指向的位置
                nums[cover_pointer] = nums[i]
                # 覆盖指针向后移动一位
                cover_pointer += 1
        return cover_pointer

Source: LeetCode（The title reproduced in this blog is for personal study use only）

方法一、双指针

判断nums的长度是否为0，为0则不包含任何元素，因此返回0。当数组nums的长度大于0时，数组中此时至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此nums[0]保持原状即可，从下标1开始删除重复元素。

定义两个指针fast和slow分别为快指针和慢指针，快指针则遍历数组到达下标的位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标sums[1]

Python3 代码题解

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        n = len(nums)
        fast = slow = 1
        while fast < n:
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1

        return slow

Source: LeetCode（The title reproduced in this blog is for personal study use only）

方法一、递归

List1或List2一开始就是空链表，那么不需要任何操作直接返回非空链表。否则我们就要判断List1或List2哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

Python3 代码题解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Source: LeetCode（The title reproduced in this blog is for personal study use only）

方法一、栈

一、利用栈先入后出的特点，如果遇到左括号入栈，遇到右口号时将对应栈顶左括号出栈，则遍历完所以的括号后stack仍为空。
二、建立哈希表pairs构建左右括号的对应关系。

Python3 代码解释

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        pairs = {
            "}": "{",
            "]": "[",
            ")": "(",
        }
        stack = list()
        for i in s:
            if i in pairs:
                if not stack or stack[-1] != pairs[i]:
                    return False
                stack.pop()
            else:
                stack.append(i)

        return not stack

Source: LeetCode（The title reproduced in this blog is for personal study use only）