作者： zhiyi

方法一、暴力方法

使用Python3内置index()或find()函数进行逻辑判断

str.index(), str.find()函数两者区别：

str.find(sub[, start[, end]])
返回子字符串 sub 在 s[start:end] 切片内被找到的最小索引。 可选参数 start 与 end 会被解读为切片表示法。 如果 sub 未被找到则返回 -1。

str.index(sub[, start[, end]])
类似于 find()，但在找不到子字符串时会引发 ValueError

Python3 代码题解

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not haystack and not needle:
            return 0
        if needle in haystack:
            return haystack.index(needle)
        else:
            return -1

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

方法一、双指针

题目要求删除数组中等于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）

方法一：

横向扫描
用LCP(S1…Sn)表示字符串S1…Sn的最长公共前缀。

LCP(S_1......S_n) = LCP(LCP(LCP(S_1,S_2),S_3),...S_n)

依次遍历字符串数组中的每个字符串，如果尚未遍历完所以的字符串时，最长公共前缀已经是空字符串，则最长公共前缀一定是空字符串。直接返回空字符串。

Python3 代码解法

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        prefix, cont = strs[0], len(strs)
        for i in range(1, cont):
            prefix = self.lcp(prefix, strs[i])
            if not prefix:
                break

        return prefix

    def lcp(self, str1, str2):
        length, index = min(len(str1), len(str2)), 0
        while index < length and str1[index] == str2[index]:
            index += 1
        return str1[:index]

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