LeetCode-0

Algorithm Comments

简单题

two-sum

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

例如：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

遍历

空间复杂度O(n)
时间复杂度O(n)

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i, n in enumerate(nums):
            x = target - n
            if x in dict:
                return [dict[x], i]
            else:
                dict[n] = i

暴力

两层循环，时间复杂度O(n^2)
注意：不能考虑重复元素

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l = len(nums)
        for i in range(l):
            for j in range(i+1, l, 1):
                if nums[i] + nums[j] == target:
                    return [i, j]

删除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

反向遍历POP

注意索引

1
2
3
4
5
6
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in range(len(nums)-1, -1, -1):
            if(nums[i] == val):
                nums.pop(i)
        return len(nums)

2

记录val值个数，一次循环，元素前移

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0
        l = len(nums)
        for i, n in enumerate(nums):
            nums[i-k] = nums[i]
            if(n==val):
                k = k+1
        return l-k

双指针

l为新数组索引，r为原数组索引。

1
2
3
4
5
6
7
8
9
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l = 0
        r = 0
        for r in range(len(nums)):
            if(nums[r]!=val):
                nums[l]=nums[r]
                l = l+1
        return l

count & remove

1
2
3
4
5
6
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        a = nums.count(val)  # 计算数组nums中val值的个数
        for i in range(a):
            nums.remove(val)
        return len(nums)

index & del

1
2
3
4
5
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            del nums[nums.index(val)]
        return len(nums)

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

set()

1
2
3
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums)!=len(set(nums))

删除有序数组中的重复项

删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

倒序POP

注意索引

1
2
3
4
5
6
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for i in range(len(nums)-1, 0, -1):
            if (nums[i] == nums[i-1]):
                nums.pop(i)
        return len(nums)

快慢指针

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        fast = 1
        slow = 0
        while(fast < len(nums)):
            if(nums[fast] != nums[slow]):
                slow = slow + 1
                nums[slow] = nums[fast]
            fast = fast + 1
        return slow+1

数组中的重复数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

哈希字典

1
2
3
4
5
6
7
8
9
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dic = set() 
        for i in range(0, len(nums), 1):
            if nums[i] in dic:
                return nums[i]
            else:
                dic.add(nums[i])
        return -1

原地交换

数组长度为n，数字范围在[0, n-1]，且有数字重复。所以可以调整索引数值一一对应，当发生冲突则返回。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] != i:
                if nums[nums[i]] == nums[i]:
                    return nums[i]
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
            else:
                i += 1
        return -1

独苗

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

异或

  1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
  2. 任何数和其自身做异或运算，结果是 0，即a⊕a=0。
  3. 异或运算满足交换律。

因此，把所有数值做异或运算即可得到结果。

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            ans = ans ^ nums[i]
        return ans

查找目标值

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

二分

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            m = (l+r)//2
            if target == nums[m]:
                return m
            elif target>nums[m]:
                l = m + 1
            else:
                r = m - 1
        return -1

List.index()

这个耗时还少，赢麻了

1
2
3
4
5
6
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except ValueError:
            return -1

下一个更大

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

暴力

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        for n in nums1:
            i = nums2.index(n)
            for j in range(i, len(nums2)):
                if nums2[j] > n:
                    ans.append(nums2[j])
                    break
                if j == len(nums2)-1:
                    ans.append(-1)
        return ans

单调栈

从后往前遍历nums2，当栈顶元素比当前值小则出栈，保证栈顶为最近的大元素。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = {}
        st = []
        for num in reversed(nums2):
            while st and num >= st[-1]:
                st.pop()
            res[num] = st[-1] if st else -1
            st.append(num)
        return [res[num] for num in nums1]

消失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

暴力

1
2
3
4
5
6
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if i != nums[i]:
                return i
        return i + 1

计算

1
2
3
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return sum(range(len(nums) + 1)) - sum(nums)

插入的位置

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

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

顺序查找

时间复杂度O(n)

1
2
3
4
5
6
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i, n in enumerate(nums):
            if(target <= n):
                return i
        return i+1

二分查找

时间复杂度为 O(log n) 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while(l <= r):
            mid = (l+r)//2
            if(nums[mid]>target):
                r = mid - 1
            elif (nums[mid]<target):
                l = mid + 1
            else:
                return mid
        return l

最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

sorted()

1
2
3
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return sorted(arr)[:k]

heap

1
2
3
4
5
6
7
8
9
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        heapq.heapify(arr)
        ans = []
        while k:
            ans.append(arr[0])
            heapq.heappop(arr)
            k -= 1
        return ans
1
2
3
4
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return heapq.nsmallest(k,arr)

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

min()

1
2
3
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        return min(numbers)

倒序遍历查找

1
2
3
4
5
6
7
8
9
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        ans = numbers[-1]
        for i in range(len(numbers)-1, -1, -1):
            if ans >= numbers[i]:
                ans = numbers[i]
            else:
                return ans
        return ans

二分

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l, r = 0, len(numbers) - 1
        while l < r:
            m = (l + r) // 2
            if numbers[m] < numbers[r] or numbers[m] < numbers[l]:
                r = m
            elif numbers[m] > numbers[r]:
                l = m + 1
            else:
                return min(numbers[l:r])
        return numbers[l]

和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

暴力

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        for i in range(1, target//2 + 1):
            s = 0
            for j in range(i, target):
                if s == target and j - i > 1:
                    res.append(list(range(i, j)))
                elif s > target:
                    break  
                s += j    
        return res

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        l, r, s = 1, 2, 3
        res = []
        while l < r:
            if s == target:
                res.append(list(range(l, r + 1)))
            if s >= target:
                s -= l
                l += 1
            else:
                r += 1
                s += r
        return res

连续子数组和的最大值

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

dp

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        f = len(nums) * [0]
        ms = f[0] = nums[0]
        for i in range(1, len(nums)):
            f[i] = f[i-1] + nums[i] if f[i-1]>0 else nums[i]
            ms = ms if ms >= f[i] else f[i]
        return ms

区域和检索-数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray:

    def __init__(self, nums: List[int]):
        self.pre = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.pre[i+1] = self.pre[i] + nums[i]


    def sumRange(self, left: int, right: int) -> int:
        return self.pre[right+1] - self.pre[left]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

暴力解法

逐次遍历，两两找最长前缀。

注意每次拿前缀和新的字符串比较时，用切片保证前缀长度比新字符串小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""
        if not strs:
            return prefix
        else:
            prefix = strs[0]
        for str0 in strs:
            # 前缀长度一定是最小的
            if len(str0) < len(prefix):
                prefix = prefix[0: len(str0)]
            for i in range(min(len(str0), len(prefix))):
                if prefix[i]!= str0[i]:
                    prefix = prefix[0:i]
                    break
        return prefix

字典排序

用min和max获得字典排序的最小串和最大串，直接找两者最大前缀

1
2
3
4
5
6
7
8
9
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        str0, str1 = min(strs), max(strs)
        for i in range(len(str0)):
            if str0[i]!=str1[i]:
                return str0[:i]
        return str0

压缩

set函数生成集合，集合中不能有相同元素，可以用集合长度确定strs相同位置的元素是否相同。

1
2
3
4
5
6
7
8
9
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""
        for i in list(zip(*strs)):
            if len(set(i))==1:
                prefix += i[0]
            else:
                break
        return prefix

合并有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

sort

哈哈哈哈哈

1
2
3
4
5
6
7
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2
        nums1.sort()

倒序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2, p3 = m-1, n-1, n+m-1
        while p1>=0 and p2>=0:
            if(nums1[p1] > nums2[p2]):
                nums1[p3] = nums1[p1]
                p1 -= 1
            else:
                nums1[p3] = nums2[p2]
                p2 -= 1
            p3 -= 1
        while p2>=0 and p3>=0:
            nums1[p3] = nums2[p2]
            p2 -= 1
            p3 -= 1

加1

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

反向遍历

从后往前找，9则置0，找到第一个不为9的+1返回。若全为9则在0位插入一个1。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        l = len(digits)
        for i in range(l-1, -1, -1):
            if digits[i] is 9:
                digits[i] = 0
                if not i:
                    digits.insert(0, 1)
            else:
                digits[i] += 1
                break
        return digits

移0

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = fast = 0
        for num in nums:
            if num != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        # 尾部置零
        while(slow < fast):
            nums[slow] = 0
            slow += 1

move & append

这个相对来说慢很多

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        cnt = 0
        while 0 in nums:
            nums.remove(0)
            cnt += 1
        while (cnt):
            nums.append(0)
            cnt -= 1

两个数组交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

set.intersection()

求两个集合的交集。

1
2
3
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set.intersection(set(nums1), set(nums2)))
1
2
3
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1).intersection(set(nums2)))

&

1
2
3
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

两个数组交集ii

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

Counter &

1
2
3
4
5
6
7
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        dic = (Counter(nums1) & Counter(nums2))
        res = []
        for i in dic.keys():
            res += dic[i]*[i]
        return res

最后的单词

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

反向遍历查找

反向找第一个字母，找到则记录tail word的长度

1
2
3
4
5
6
7
8
9
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        tail = 0
        for i in range(len(s)-1, -1, -1):
            if s[i]!=' ':
                while i > -1 and s[i] != ' ':
                    tail += 1
                    i -= 1
                return tail

str.split()

1
2
3
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.split()[-1])

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

str.replace()

1
2
3
class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(' ', '%20')

str.split() and str.join()

1
2
3
class Solution:
    def replaceSpace(self, s: str) -> str:
        return '%20'.join(s.split(' '))

替换解析

请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 “G”、”()” 和/或 “(al)” 按某种顺序组成。Goal 解析器会将 “G” 解释为字符串 “G”、”()” 解释为字符串 “o” ，”(al)” 解释为字符串 “al” 。然后，按原顺序将经解释得到的字符串连接成一个字符串。

给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。

str.replace()

1
2
3
class Solution:
    def interpret(self, command: str) -> str:
        return command.replace('()', 'o').replace('(al)', 'al')

反转字符串

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

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

str.reverse()

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

切片

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

双指针

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l = 0
        r = len(s)-1
        while l<r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

Counter

1
2
3
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s)==Counter(t)

左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

切片

1
2
3
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

list

字符串不能直接用下标赋值，通过list实现转换。

1
2
3
4
5
6
7
8
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        st = []
        for i in range(n, len(s)):
            st.append(s[i])
        for i in range(0, n):
            st.append(s[i])
        return ''.join(st)

用求余运算简化代码

1
2
3
4
5
6
7
class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        st = []
        l = len(s)
        for i in range(n, l + n):
            st.append(s[i % l])
        return ''.join(st)

二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

bin()

1
2
3
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

最大重复子字符串

给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。

给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。

str.find()

1
2
3
4
5
6
7
8
class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        res = len(sequence)//len(word)
        while res:
            if sequence.find(word * res) >= 0:
                return res
            res -= 1
        return res

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        lw = len(word)
        ls = len(sequence)
        maxk = 0
        for i in range(ls):
            k = 0
            while i+lw <= ls and sequence[i:i+lw] == word:
                k += 1
                i += lw
            if k > maxk:
                maxk = k
        return maxk
1
2
3
4
5
6
7
8
class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        res = 0
        tmp = word
        while tmp in sequence:
            tmp += word
            res += 1
        return res

字符重排判定

给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

哈希字典

1
2
3
class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        return Counter(s1)==Counter(s2)

判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

注意看清：s是目标串，t是原串。

双指针

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True 
        p = 0
        for w in t:
            if w == s[p]:
                p += 1
                if p == len(s):
                    return True
        return False

str.find()

1
2
3
4
5
6
7
8
9
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        for w in s:
            i = t.find(w, i)
            if i == -1:
                return False
            i += 1
        return True

合并有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

递归

1
2
3
4
5
6
7
8
9
10
11
12
# 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 and list2:
            if list1.val > list2.val:
                list1, list2 = list2, list1
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1 or list2

迭代

用带头节点的单链表统一操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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]:
        tmp = cur = ListNode(-1)  # Head Node
        while list1 and list2:
            if list1.val > list2.val:
                cur.next, list2 = list2, list2.next
            else:
                cur.next, list1 = list1, list1.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return tmp.next

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ans = None
        while head is not None:
            p = head.next
            head.next = ans
            ans = head
            head = p
        return ans

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return last

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

哈希表

用一个集合来存储已经访问过的结点（不是val），遍历访问时，判断当前结点是否已经访问过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head:
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    return True
        return False

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow = fast = head
        for i in range(k):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        return slow

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

哈希字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        dic = set()
        p = headA
        while p:
            dic.add(p)
            p = p.next
            
        p = headB
        while p:
            if p in dic:
                return p
            p = p.next
        return p

双指针

$$
a+(b-c)=b+(a-c)=a+b-c
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p, q = headA, headB
        while q != p:
            p = p.next if p else headB
            q = q.next if q else headA
        return q

去尾

对两个链表，裁剪最大相同长度的尾部，同时遍历。

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p, q = headA, headB
        la, lb = 0, 0
        # 计算链表A长度
        while p:
            la += 1
            p = p.next
        # 计算链表B长度
        while q:
            lb +=1
            q = q.next
        # 裁剪去头
        while la > lb:
            headA = headA.next
            la -= 1
        while lb > la:
            headB = headB.next
            lb -= 1
        # 此时la==lb
        p, q = headA, headB
        while p and q:
            if p==q:
                return p
            p = p.next
            q = q.next
        return None

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        re = []
        def fun(p):
            if p:
                fun(p.next)
                re.append(p.val)
        fun(head)
        return re

正向遍历后翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-1]

删除链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

遍历一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = head
        while p and p.next:
            if p.val == p.next.val:
                p.next = p.next.next
            else:
                p = p.next
        return head

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        st = []
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        while slow:
            st.append(slow.val)
            slow = slow.next
        p = head
        while st:
            if st.pop()!=p.val:
                return False
            p = p.next
        return True

翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        st = []
        p = head
        while p:
            st.append(p.val)
            p = p.next
        return st[::1]==st[::-1]

二叉树最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

DFS

递归

1
2
3
4
5
6
7
8
9
10
11
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

BFS

模拟队列实现层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        depth = 0
        if root:
            q = collections.deque()
            q.append(root)
            while len(q):
                depth += 1
                for i in range(len(q)):
                    tmp = q.popleft()
                    if tmp.left:
                        q.append(tmp.left)
                    if tmp.right:
                        q.append(tmp.right)
        return depth

二叉树最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root:
            if root.right and root.left:
                return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
            if root.right:
                return self.minDepth(root.right) + 1
            if root.left:
                return self.minDepth(root.left) + 1
            # 遇到叶子结点则返回
            return 1
        return 0

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        depth = 0
        if root:
            q = [root]
            while q:
                depth += 1
                for i in range(len(q)):
                    tmp = q[0]
                    del q[0]
                    if tmp.left:
                        q.append(tmp.left)
                    if tmp.right:
                        q.append(tmp.right)
                    # 遇到叶子结点则返回深度
                    if not tmp.right and not tmp.left:
                        return depth
        return depth

二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        def dfs(r):
            if r:
                return max(dfs(r.right), dfs(r.left)) + 1
            return 0
        return dfs(root)

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            # 三条语句顺序无影响
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root

对称树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

递归

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        # 送入镜像结点
        def dfs(left, right):
            # 左右结点为空
            if not (left or right):
                return True
            # 单边结点为空
            if not (left and right):
                return False
            # 左右结点不为空
            # 当值不等，返回0
            if left.val != right.val:
                return False
            # 当值相等
            # 右结点的右子树和左结点的左子树比较
            # 右结点的左子树和左结点的右子树比较
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(root.left, root.right)

路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root:
            # 若无左右结点，则为叶子结点
            if not root.left and not root.right:
                return True if targetSum==root.val else False
            
            return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)
        
        # root为none则返回False
        return False

二叉树中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        trl = []
        def inorder(r):
            if r:
                inorder(r.left)
                trl.append(r.val)
                inorder(r.right)
        inorder(root)
        return trl

二叉搜索树第k大结点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

中序遍历

二叉搜索树的中序遍历（左中右）为递增序列， 右中左为递减序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        def dfs(r):
            if r and k > 0:
                dfs(r.right)
                self.k -= 1
                if self.k==0:
                    self.res = r.val
                    return 
                dfs(r.left)
        self.k = k    
        dfs(root)  
        return self.res

层次遍历

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

队列

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root:
            que = collections.deque()
            que.append(root)
            while que:
                lay = []
                for i in range(len(que)):
                    p = que.popleft()
                    lay.append(p.val)
                    if p.left:
                        que.append(p.left)
                    if p.right:
                        que.append(p.right)
                res.append(lay)
            return res
        return res

罗马数字

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

字典

数组记录，小数在大数前面，则小数取负，最后全部相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def romanToInt(self, s: str) -> int:
        dict = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        st = [0]
        top = ans = 0
        for i in s:
            st.append(dict[i])
            # 小数在大数前面，则小数取负
            if(dict[i]>st[top]):
                st[top] = - st[top]
            top += 1
        for i in st:
            ans += i
        return ans

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

类似斐波那契数列

递归

简单但超时

1
2
3
4
5
class Solution:
    def climbStairs(self, n: int) -> int:
        if n==0 or n==1:
            return 1
        return self.climbStairs(n-1)+self.climbStairs(n-2)

动态规划

自底向上求解，时间复杂度O(n)，空间复杂度O(n)

1
2
3
4
5
6
7
8
9
class Solution:
    def climbStairs(self, n: int) -> int:
        res = [1, 1]
        if(n<2):
            return res[n]
        # 注意这里上限是n+1-1=n
        for i in range(2, n+1):
            res.append(res[-1] + res[-2])
        return res[n]

动态规划-优化空间

每次只用到n-1规模和n-2规模的解，所以可以只存前两个解。

时间复杂度O(n)，空间复杂度O(1)

1
2
3
4
5
6
class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1 # f(0)=1, f(1)=1
        for i in range(2, n+1):
            a, b = b, a+b
        return b

记忆dfs

记忆性dfs自顶向下计算

1
2
3
4
5
6
7
8
9
10
class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(i, flag):
            if i==0 or i==1:
                return 1
            if flag[i]=='?':
                flag[i] = dfs(i-1, flag) + dfs(i-2, flag)
            return flag[i]
        
        return dfs(n, (n+1)*['?'])

炒股

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

实际上就是找到一个 i<j, max(prices[j] - prices[i])

暴力穷举

时间复杂度O(n^2)，超时

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(0, len(prices)-1):
            for j in range(i+1, len(prices)):
                res = max(prices[j]-prices[i], res)
        return res

一次遍历

思路：遍历一次，对于第i天记录此前价格最低点，假设在此前价格最低点买进，当天卖出，记录最大收益值。

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)==0 or len(prices)==1:
            return 0
        min_price = prices[0]
        max_income = 0
        for price in prices:
            # 若今天卖出，获得最大收益是多少？是否是当前最大收益？
            max_income = max(max_income, price-min_price)
            # 更新当前价格最低点
            min_price = min(min_price, price)
        return max_income

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

1
2
3
4
5
6
//实现 MyStack 类：

void push(int x) //将元素 x 压入栈顶。
int pop() //移除并返回栈顶元素。
int top() //返回栈顶元素。
boolean empty() //如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

List

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
class MyStack:

    def __init__(self):
        self.st = []

    def push(self, x: int) -> None:
        self.st.append(x)

    def pop(self) -> int:
        tmp = self.st[-1]
        del self.st[-1]
        return tmp

    def top(self) -> int:
        return self.st[-1]

    def empty(self) -> bool:
        return len(self.st)==0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

Dequeue-left

双端队列模拟，左边为栈顶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.appendleft(x)

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q)==0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

Dequeue-right

双端队列，右边为栈顶模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MyStack:

    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)

    def pop(self) -> int:
        return self.q.pop()

    def top(self) -> int:
        return self.q[len(self.q)-1]

    def empty(self) -> bool:
        return len(self.q)==0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

min栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

最小栈

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
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.st = []
        self.min_st = [math.inf]

    def push(self, x: int) -> None:
        self.st.append(x)
        self.min_st.append(min(x, self.min_st[-1]))

    def pop(self) -> None:
        self.st.pop()
        self.min_st.pop()

    def top(self) -> int:
        return self.st[-1]

    def min(self) -> int:
        return self.min_st[-1]
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

栈

利用字典构造匹配关系

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isValid(self, s: str) -> bool:
        dict = {'(':')', '{':'}', '[':']', '?':'?'}
        stack = ['?']
        for c in s:
            if c in dict:
                stack.append(c)
            elif dict[stack.pop()] != c:
                return False
        return len(stack)==1

回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

直接计算

如果x小于0则必不是回文数
如果x大于0则计算其倒序数值，比较和原x是否相等

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0:
            return False
        else:
            cur = 0
            num = x
            while(num>0):
                cur = cur*10 + num%10
                num = num//10
            return cur == x

反向切片

1
2
3
class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

牛顿迭代法

1
2
3
4
5
6
7
8
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        x0, x1 = float(x), float('inf')
        while x1-x0 > 1e-7:
            x0, x1 = (x0 + x / x0) / 2, x0
        return int(x0)

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l<=r:
            m = (l+r)//2
            if m**2 <= x:
                l = m + 1
                ans = m
            else:
                r = m - 1
        return ans

math

1
2
3
4
5
6
class Solution:
    def mySqrt(self, x: int) -> int:
        if x==0:
            return 0
        ans = int(math.exp(0.5 * math.log(x)))
        return ans+1 if (ans+1)**2<=x else ans
1
2
3
class Solution:
    def mySqrt(self, x: int) -> int:
        return int(math.pow(x, 0.5))

到达终点数字

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

每次你可以选择向左或向右移动。
第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。
给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

math

官方解答

1
2
3
4
5
6
7
8
class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        k = 0
        while target > 0:
            k += 1
            target -= k
        return k if target % 2 == 0 else k + 1 + k % 2  #多走两步必奇数

majority-element

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

排序

排序后取nums[n//2]

1
2
3
4
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

字典

1
2
3
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
       return Counter(nums).most_common(1)[0][0]
1
2
3
4
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
       counts = collections.Counter(nums)
       return max(counts.keys(), key=counts.get)
1
2
3
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
       return max(set(nums), key=nums.count)

摩尔投票

1
2
3
4
5
6
7
8
9
10
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        for num in nums:
            # 票数为0换候选人
            if count==0:
                candidate = num
            count += (1 if candidate == num else -1)
        return candidate

majority-element-ii

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

摩尔投票

选出2个有希望超过⌊ n/3 ⌋的候选人，统计他们的票数是否真的超过⌊ n/3 ⌋。

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
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        vote1 = 0
        vote2 = 0
        candidate1 = None
        candidate2 = None
        for num in nums:
            if num==candidate1:
                vote1 += 1
            elif num==candidate2:
                vote2 += 1
            elif vote1==0:
                vote1 = 1
                candidate1 = num
            elif vote2==0:
                vote2 = 1
                candidate2 = num
            else:
                vote1 -= 1
                vote2 -= 1
        res = []
        cnt1, cnt2 = 0, 0
        for num in nums:
            if vote1>0 and num==candidate1:
                cnt1 += 1
            elif vote2>0 and num==candidate2:
                cnt2 += 1
        if cnt1 > len(nums)//3:
            res.append(candidate1)
        if cnt2 > len(nums)//3:
            res.append(candidate2)
        return res

哈希字典

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        dic = {}
        res = []
        for num in nums:
            if num in dic:
                dic[num] += 1
            else:
                dic[num] = 1
        for i in dic.keys():
            if dic[i] > len(nums)//3 :
                res.append(i)
        return res

信号最好的坐标

给你一个数组 towers 和一个整数 radius 。

数组 towers 中包含一些网络信号塔，其中 towers[i] = [xi, yi, qi] 表示第 i 个网络信号塔的坐标是 (xi, yi) 且信号强度参数为 qi 。所有坐标都是在 X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。

整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。

如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊qi / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。

请你返回数组 [cx, cy] ，表示 信号强度 最大的 整数 坐标点 (cx, cy) 。如果有多个坐标网络信号一样大，请你返回字典序最小的 非负 坐标。

注意：

坐标 (x1, y1) 字典序比另一个坐标 (x2, y2) 小，需满足以下条件之一：
要么 x1 < x2 ，
要么 x1 == x2 且 y1 < y2 。
⌊val⌋ 表示小于等于 val 的最大整数（向下取整函数）。

枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def bestCoordinate(self, towers: List[List[int]], radius: int) -> List[int]:
        dis = lambda s1, s2 : ((s1[0] - s2[0]) ** 2 + (s1[1] - s2[1]) ** 2) ** 0.5
        maxq = 0
        res = [0, 0]
        for x in range(51):
            for y in range(51):
                q = 0
                for t in towers:
                    d = dis([x, y], t)
                    if d <= radius:
                        q += floor(t[2] / (1 + d))
                if q > maxq:
                    maxq, res = q, [x, y]
        return res

Cy