Leetcode练习册

Leetcode练习册。

Introduction

本练习册是AI小分队-算法刷题组的刷题记录~

Find All Numbers Disappeared in an Array (easy)

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Code $O(n)+O(1)$ 符号标记法

额外空间复杂度$O(1)​$。本方法受到豆豆酱的符号法的启发。

注意abs()不能省。

1
2
3
4
5
6
7
8
9
10
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
if(nums[abs(nums[i]) - 1] > 0):
nums[abs(nums[i]) - 1] *= -1
ans = []
for i in range(len(nums)):
if(nums[i] > 0):
ans.append(i + 1)
return ans

Code $O(n)+O(1)$ 归位法

Python为什么不需要swap(a, b) - 追寻真理之美- CSDN博客

以下为示例:

1553356859627

归位法将丢失原数组的信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
i = 0
while i < len(nums):
while nums[i] != i + 1: # 未归位
if nums[i] == nums[nums[i]-1]:
nums[i] = -1
if nums[i] < 0:
break
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] # swap
i += 1

i, ans = 0, []
while i < len(nums):
if nums[i] < 0:
ans.append(i + 1)
i += 1
return ans

Code MLE $O(n)+O(n)$ 集合运算

TimeComplexity - Python WikiDifference s-t

本方法来自暗涌大佬。

1
2
3
4
5
6
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
numbers_set = set(range(1, len(nums) + 1))
nums_set = set(nums)
missing_set = numbers_set - nums_set
return list(missing_set)

jump Game (medium)

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

1
2
3
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:(注意,有0。但有0只是必要条件)

1
2
3
4
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

Code $O(n)+O(1)$ 贪心

探查单向可达性。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def canJump(self, nums: List[int]) -> bool:
reach = 0
index = 0
while index <= reach and index < len(nums):
reach = max(reach, index + nums[index])
index += 1
if len(nums) - 1 <= reach:
return True
else:
return False

jump Game2 (hard)

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

1
2
3
4
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.(其实只要不含0就一定能抵达)

Code $O(n)$ 贪心

区间跳跃

每一步都有一个可行域(区间[lo,hi])。保存并逐步更新这样一个区间即可。当区间覆盖了终点,退出。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def jump(self, nums: List[int]) -> int:
steps = 0
lo = hi = 0
while hi < len(nums) - 1:
new_hi = 0
for i in range(lo, hi+1):
new_hi = max(new_hi, i + nums[i])
lo = hi + 1
hi = new_hi
steps += 1
return steps

Code TLE $O(kn)$ DP

k:平均跳跃距离。

1
2
3
4
5
6
7
8
9
10
class Solution:
def jump(self, nums: List[int]) -> int:
steps = [sys.maxsize] * len(nums)
steps[0] = 0
for i in range(len(nums)):
for j in range(1, nums[i] + 1):
if i + j >= len(nums):
break
steps[i + j] = min(steps[i + j], steps[i] + 1)
return steps[len(nums) - 1]

Longest Substring Without Repeating Characters (medium)

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Code $O(n)+O(dict)$ 减治+Hash

主要思路是贪心+hash。

从一端开始扫描,只要某一段出现了相同的字符,那么这一段就肯定不会被再次计算

hash集存储每个字符对应的最大出现位置。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxlen = 0
index = 0
diction = {}
for i in range(len(s)):
if diction.__contains__(s[i]):
index = max(index, diction[s[i]] + 1)
diction[s[i]] = i
maxlen = max(maxlen, i - index + 1)
return maxlen

Substring with Concatenation of All Words (hard)

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation(级联,一连串) of each word in words exactly once and without any intervening(介入的) characters.

Example 1:

1
2
3
4
5
6
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

1
2
3
4
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []

Code $O(n\times len_{word})+O(dict)$ 滑动窗口+multiset

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
35
36
37
38
39
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if len(words) == 0:
return []
word_len = len(words[0])
maxlen = len(words)

diction = {}
for word in words:
diction[word] = diction[word] + 1 if diction.__contains__(word) else 1
# print(diction)

ans = []
for i in range(word_len):
# print("------round:",i)
le = i
tmp_diction = {}
for word in words:
tmp_diction[word] = 0
while i < len(s):
new_word = s[i:(i+word_len)]
# print("new_word:",new_word)
if tmp_diction.__contains__(new_word):
tmp_diction[new_word] += 1
while tmp_diction[new_word] > diction[new_word]:
le_word = s[le:(le+word_len)]
tmp_diction[le_word] -= 1
le += word_len
if i - le == (maxlen-1)*word_len:
# print("append:", le)
ans.append(le)
else:
le = i + word_len
for word in words:
tmp_diction[word] = 0
i += word_len
# print(" le:",le,"i:",i)

return ans

Code WA $O(n)+O(dict)$ 秩字典

只能用于Words集合的元素两两互异的情况。

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
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if len(words) == 0:
return []
print(words)
word_len = len(words[0])
index = 0
maxlen = len(words)
diction = {}
ans = []
print("总有效长度:",maxlen*word_len)
i = 0
while i < len(s):
if diction.__contains__(s[i:(i+word_len)]):
index = max(index, diction[s[i:(i+word_len)]] + word_len)
while s[index:(index+word_len)] not in words:
index += word_len
diction[s[i:(i+word_len)]] = i
print(index, i)
if i - index == (maxlen - 1)*word_len:
print("append index:",index)
ans.append(index)
i += word_len

return ans

Maximum Subarray (easy)

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Code $O(n)+O(1)$ 减治

参考邓公的Great slice。

1553404489937

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
gs = nums[0] # random init
s = i = 0
while i < len(nums):
s += nums[i]
gs = max(gs, s)
s = max(s, 0)
i += 1
return gs

Code $O(nlogn)$ 分治

1553405039292

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 Solution:
def maxSubArray(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)
if hi - lo < 2:
return nums[lo]
mi = (lo + hi) >> 1

gsL, sL, i = nums[mi - 1], 0, mi - 1
while lo <= i:
sL += nums[i]
if gsL < sL:
gsL = sL
i -= 1

gsR, sR, j = nums[mi], 0, mi
while j < hi:
sR += nums[j]
if gsR < sR:
gsR = sR
j += 1

return max(gsL + gsR,
max( Solution.maxSubArray(self, nums[:mi]),
Solution.maxSubArray(self, nums[mi:])))

Count Primes (easy)

Count the number of prime numbers less than a non-negative number, n.

Example:

1
2
3
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Code $O(nloglogn)+O(n)$ 埃氏筛法

Python 类变量与实例变量

之前做过。。新手村-过程函数与递归-回文质数

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
class Solution:
MAX_N = 1500005
prime = [False] * MAX_N
def Eratosthenes(self, b):
for i in range(2, b+1):
self.prime[i] = True
i = 2
while i*i <= b:
if self.prime[i]:
j = i*i
while j <= b:
self.prime[j] = False
j += i
i += 1

def is_prime(self, number):
return self.prime[number]

def countPrimes(self, n: int) -> int:
Solution.Eratosthenes(self, n)
ans = 0
for i in range(2, n):
if Solution.is_prime(self, i):
ans += 1
return ans

Code $\approx O(n)+O(n+\frac{n}{logn})$ 欧拉筛法

由于要维护的数据变多,实际效率反而不如埃氏筛法。

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
class Solution:
MAX_N = 1500005
prime = [False] * MAX_N
p_numbers, size = [0] * MAX_N, 0
def Euler(self, b):
for i in range(2, b+1):
self.prime[i] = True
for i in range(2, b+1):
if self.prime[i]:
self.p_numbers[self.size] = i
self.size += 1
j = 0
while j < self.size and i*self.p_numbers[j]<b:
self.prime[ i*self.p_numbers[j] ] = False
if i % self.p_numbers[j] == 0:
break
j += 1

def is_prime(self, number):
return self.prime[number]

def countPrimes(self, n: int) -> int:
self.Euler(n)
ans = 0
for i in range(2, n):
if self.is_prime(i):
ans += 1
return ans

Code $O(\sqrt n+(b-a)loglogn)+O(\sqrt n+(b-a))$ 区间素数筛法

1
# 略略略

Code $O(logP)+O(P)$ 打表

打表法就是将题目中需要的答案集合提前算出来,存到代码里,根据题目所需取答案,这种方法通常只需要将程序挂着,在表打完后进行加工,最终取答案程序时间复杂度为O(1),空间复杂度为O(n)(n为答案规模); ——沃兹·基朔德

P是所有质数的数量。二分查找。

1
# 略略略

Code TLE $O(n^{1.5})+O(1)$ Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def is_prime(number):
i = 2
while i*i <= number: # O(n^0.5)
if not (number % i):
return False
i += 1
return True
def countPrimes(self, n: int) -> int:
ans = 0
for i in range(2, n): # O(n)
if Solution.is_prime(i):
ans += 1
return ans

Next Permutation (medium)

Implement next permutation(置换), which rearranges numbers into the lexicographically(字典序) next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory(就地算法).

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1
2
3
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Code $O(n)$

1
2


H-Index (medium)

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

1
2
3
4
5
6
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining
two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Code $O(n)$

首先直观感受一下H因子

1
2


Median of Two Sorted Arrays (hard)

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Code $O(n)$

1
2


Search Insert Position (easy)

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0

Code $O(n)$ 二分

就是求uppper_boundI have no idea.

1
2
3
4
5
6
7
8
9
10
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
le, ri = -1, len(nums) # Trick
while le < ri - 1:
mid = (le + ri) >> 1
if nums[mid] >= target:
ri = mid
else:
le = mid
return ri

Max Consecutive Ones (easy)

Given a binary array, find the maximum number of consecutive(连续) 1s in this array.

Example 1:

1
2
3
4
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

Code $O(n)$ Force

扫描一遍即可。

1
2
3
4
5
6
7
8
9
10
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
Max, tmp = 0, 0
for ele in nums:
if ele == 1:
tmp += 1
else:
tmp = 0
Max = max(Max, tmp)
return Max

Permutation Sequence(medium)

The set [1,2,3,...,*n*] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

1
2
Input: n = 3, k = 3
Output: "213"

Example 2:

1
2
Input: n = 4, k = 9
Output: "2314"

Code $O(n)$

1
2


Permutations II (medium)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

Code $O(n)$

1
2


Max Points on a Line (hard)

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6

Code $O(n)$

1
2


Contains Duplicate (Easy)

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

1
2
Input: [1,2,3,1]
Output: true

Example 2:

1
2
Input: [1,2,3,4]
Output: false

Example 3:

1
2
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Code $O(n?)+O(n)$ 集合法

跟之前的题(Find All Numbers Disappeared in an Array (easy))不一样。数据是可以超限的。

1
2
3
4
5
6
7
8
9
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
Set = set()
for ele in nums:
if ele in Set:
return True
else:
Set.add(ele)
return False

Code $O(n)+O(n)$ Hash法

1
2
3
4
5
6
7
8
9
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
Hash = {}
for ele in nums:
if Hash.__contains__(ele):
return True
else:
Hash[ele] = 1
return False

Contains Duplicate II (Easy)

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Code $O(n)$ Hash

1
2
3
4
5
6
7
8
9
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
Hash = {}
minLen = len(nums) + 1
for ele, i in zip(nums, range(len(nums))):
if Hash.__contains__(ele):
minLen = min(minLen, i - Hash[ele])
Hash[ele] = i
return minLen <= k and minLen != len(nums) + 1

Combination Sum (Medium)

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

Code $O(n)$

1
2


Combination Sum II (Medium)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
7
8
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

Example 2:

1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

Code $O(n)$

1
2


Minimum Window Substring (hard)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Code $O(n)$ 队列

1
2


Code $O(n)$

1
2


Code $O(n)$

1
2


Code $O(n)$

1
2


Code $O(n)$

1
2


练习表

练习表由今日青年提供。

Day 1

1
2
3
4
5
55 jump Game medium
45 jump Game2 hard
448. Find All Numbers Disappeared in an Array easy
3. Longest Substring Without Repeating Characters medium
30. Substring with Concatenation of All Words hard

Day 2

1
2
3
4
5
6
4	Median of Two Sorted Arrays (hard)
53 Maximum Subarray (easy)
31. Next Permutation (medium)
204. Count Primes (easy)
274. H-Index(medium)
60. Permutation Sequence (豆豆酱)

Day 3

1
2
3
4
5
47. Permutations II (Medium)
60. Permutation Sequence (Medium)
149. Max Points on a Line (hard)
35. Search Insert Position (easy)
485 Max Consecutive Ones (easy)

Day 4

1
2
3
4
5
39	Combination Sum	Medium  	
40 Combination Sum II Medium
217 Contains Duplicate Easy
219 Contains Duplicate II Easy
76 Minimum Window Substring

Template

Code $O(n)$

1
2


0%