面试刷题

Binary Search & LogN Algorithm

比O(n)更优的时间复杂度几乎只能是O(logn)的二分法
二分法模板: start + 1 < end; start + (end - start) / 2; A[mid] ==, <, >; A[start] A[end] ? target

704. Binary Search (Easy)

lintcode’s version

1
2
3
4
5
6
7
8
9
10
11
12
13
Find any position of a target number in a sorted array. Return -1 if target does not exist.

Example
Given [1, 2, 2, 4, 5, 5].

For target = 2, return 1 or 2.

For target = 5, return 4 or 5.

For target = 6, return -1.

Challenge
O(logn) time

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:
"""
@param: nums: An integer array sorted in ascending order
@param: target: An integer
@return: An integer
"""
def findPosition(self, nums, target):
# write your code here
if (len(nums) == 0):
return -1
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid] == target):
return mid
elif (nums[mid] < target):
start = mid
else:
end = mid
if (nums[start] == target):
return start
if (nums[end] == target):
return end
return -1

总结:背好模板,lintcode 的 test case 包含空输入数组,需要 python3 的 // 整除运算符才能过

LinC 14. First Position of Target (Easy)

1
2
3
4
5
6
7
8
9
10
11
Description
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

Have you met this question in a real interview?
Example
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Challenge
If the count of numbers is bigger than 2^32, can your code work properly?

思路:找到了不要 return,扔掉大的一半,继续找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
"""
@param nums: The integer array.
@param target: Target to find.
@return: The first position of target. Position starts from 0.
"""
def binarySearch(self, nums, target):
# write your code here
if (len(nums) == 0):
return -1
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid] >= target):
end = mid
else:
start = mid
if (nums[start] == target):
return start
if (nums[end] == target):
return end
return -1

总结:背好模板,模板 v5

278. First Bad Version (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

思路:前面 first position of target 的变体,可以不做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
start, end = 0, n
while (start + 1 < end):
mid = start + (end - start) // 2
if (isBadVersion(mid)):
end = mid
else:
start = mid
if (isBadVersion(start)):
return start
if (isBadVersion(end)):
return end
return -1

总结:可不做

34. Find First and Last Position of Element in Sorted Array (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

思路:二分法找 Target, 两次二分法,一次找左边界,一次找右边界

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(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
ans = [-1, -1]
if len(nums) == 0:
return ans
l, r = 0, len(nums) - 1
# 找左边界
while l + 1 < r:
mid = l + (r - l ) // 2
if nums[mid] < target:
l = mid
else:
r = mid

if nums[l] == target:
ans[0] = l
elif nums[r] == target:
ans[0] = r
else:
return ans

# 找右边界
r = len(nums) - 1
while l + 1 < r:
mid = l + (r - l) // 2
if nums[mid] <= target:
l = mid
else:
r = mid
if nums[r] == target:
ans[1] = r
elif nums[l] == target:
ans[1] = l
return ans

总结:按今天的水平,写的时候注意 while 的终止条件是 while l + 1 < r (l, r 不要重合就终止循环)。 两年多前写了稍微更简洁些的版本。可以回头再看看能不能写得出。

LinC 61. Search for a Range (Medium)

1
2
3
4
5
6
7
8
9
10
Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Challenge
O(log n) time.

思路:找一个数的第一次和最后一次出现的 index

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
class Solution:
"""
@param A: an integer sorted array
@param target: an integer to be inserted
@return: a list of length 2, [index1, index2]
"""
def searchRange(self, A, target):
# write your code here
firstO, lastO = -1, -1
if len(A) == 0:
return [firstO, lastO]
start, end = 0, len(A) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (A[mid] < target):
start = mid
else:
end = mid
if (A[end] == target):
firstO = end
if (A[start] == target):
firstO = start
start, end = 0, len(A) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (A[mid] <= target):
start = mid
else:
end = mid
if (A[start] == target):
lastO = start
if (A[end] == target):
lastO = end
return [firstO, lastO]

总结:注意检查空输入!

LinC 460. Find K Closest Elements (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a target number, a non-negative integer k and an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.

Example
Given A = [1, 2, 3], target = 2 and k = 3, return [2, 1, 3].

Given A = [1, 4, 6, 8], target = 3 and k = 3, return [4, 1, 6].

Challenge
O(logn + k) time complexity.

Notice
The value k is a non-negative integer and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 10^4
Absolute value of elements in the array and x will not exceed 10^4

思路:二分查找找到 start end 以后,用两个判断条件来限制取值范围。当 left 超过取值范围之后,只取 right 以后的数。
当 right 超过取值范围之后,只取 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
25
26
27
28
29
30
31
32
33
34
class Solution:
"""
@param A: an integer array
@param target: An integer
@param k: An integer
@return: an integer array
"""
def kClosestNumbers(self, A, target, k):
# write your code here
start, end = 0, len(A) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (A[mid] < target):
start = mid
else:
end = mid
left, right = start, end
result = []
while (k > 0):
if (left >= 0 and right <= len(A) - 1):
if (target - A[left] <= A[right] - target):
result.append(A[left])
left -= 1
else:
result.append(A[right])
right += 1
elif (left < 0):
result.append(A[right])
right += 1
else:
result.append(A[left])
left -= 1
k -= 1
return result

总结,一开始没有充分理解题目,题目说的是 k closest elements to x in the array, 找到离 x 最近的点以后要往两边看 k 次。解题方法多少有点需要背的因素。

LinC 585. Maximum Number in Mountain Sequence (Medium)

852. Peak Index in a Mountain Array

1
2
3
4
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10

思路:一开始以为跟上题一样,返回 start 就行了,也许是不值得做的题,可是没有考虑到后面不是递增而是递减。所以,需要改算法为切一刀,判断递增就扔左边,递减就扔右边, 不然就找到了中点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
# write your code here
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid - 1] < nums[mid] < nums[mid + 1]):
start = mid
elif (nums[mid - 1] > nums[mid] > nums[mid + 1]):
end = mid
else:
return nums[mid]
return nums[end] if nums[start] < nums[end] else nums[start]

162. Find Peak Element (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
Note:

Your solution should be in logarithmic complexity.

思路:和前面 Lintcode 585. Maximum Number in Mountain Sequence 应该是一个路子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if (len(nums) == 0):
return -1
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid - 1] < nums[mid] < nums[mid + 1]):
start = mid
elif (nums[mid - 1] < nums[mid] > nums[mid + 1]):
return mid
else:
end = mid
if nums[start] > nums[end]:
return start
else:
return end

总结:确实和前面一样, 不用做

74. Search a 2D Matrix (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:

Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:

Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false

思路:二分查找,不过是放到二维数组里了

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
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0:
return False
if len(matrix[0]) == 0:
return False
startR, endR = 0, len(matrix) - 1
startC, endC = 0, len(matrix[0]) - 1
while(startR + 1 < endR):
midR = startR + (endR - startR) // 2
if (matrix[midR][0] == target):
return True
elif (matrix[midR][0] < target):
startR = midR
else:
endR = midR
if (matrix[startR][0] == target or matrix[endR][0] == target):
return True
elif (matrix[endR][0] < target):
targetR = endR
else:
targetR = startR
while(startC + 1 < endC):
midC = startC + (endC - startC) // 2
if (matrix[targetR][midC] == target):
return True
elif (matrix[targetR][midC] < target):
startC = midC
else:
endC = midC
if (matrix[targetR][startC] == target or matrix[targetR][endC] == target):
return True
return False

总结:注意检查空输入

153. Find Minimum in Rotated Sorted Array (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:
Input: [3,4,5,1,2]
Output: 1

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

思路:找 pivot,pivot > 0 时返回 nums[pivot + 1]。找 pivot 时,如果 mid < start, 扔 end, 如果 mid > start 扔 start

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if (nums[0] < nums[len(nums) - 1]):
return nums[0]
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if (nums[mid] < nums[start]):
end = mid
else:
start = mid
return nums[end]

总结:应改为 Easy 难度的题。
Follow up: 如果有重复的数? 无法保证在 Log(N) 的时间复杂度内解决 例子:[1,1,1,1,1….,1] 里藏着一个 0.最坏情况下需要把每个位置上的1都看一遍,才能找到最后一个有0 的位置. 考点:能想到这个最坏情况的例子

33. Search in Rotated Sorted Array (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

思路:第一感觉是得知道 pivot 在哪,有 pivot 一侧不能随便扔,但是更优的方法是查单调的侧是否可以扔

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
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
start, end = 0, len(nums) - 1
while (start + 1 < end):
mid = start + (end - start) // 2
if nums[start] < nums[mid]:
if nums[start] <= target <= nums[mid]:
end = mid
else:
start = mid
else:
if nums[mid] <= target <= nums[end]:
start = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1

总结: 注意 [1, 3, 5] target 为 1 这种边界条件, 判断 target 在单调这边需要加等号

LinC 140. Fast Power (Medium)

1
2
3
4
5
6
7
8
9
Calculate the a**n % b where a, b and n are all 32bit integers.

Example
For 2**31 % 3 = 2

For 100**1000 % 1000 = 0

Challenge
O(logn)

思路:第一感觉是:需要用某种数学方法,取模只取决于这个数取模后剩下的数加多少次,可以将次方换成乘法,再取模,乘法可以换算成 n 次幂取模 b 再乘 a。
总结:递归版本: (a b) % p = (a % p b % p) % p 将 a^n % b 分解为 (a^(n/2) a^(n/2) (a)) %b = ((a^(n/2) a^(n/2))%b (a)%b) %b = ((a^(n/2)%b a^(n/2)%b)%b (a)%b) %b; 非递归版本,思路是转换为二进制

50. Pow(x, n) (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]

思路:递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
return 1 / self.power(x, -n)
else:
return self.power(x, n)
def power(self, x, n):
if n == 0:
return 1
result = self.power(x, n // 2)
if n % 2 == 0:
return result * result
else:
return x * result * result

总结:有固定写法套路的题目, 不值得做。

228. Summary Ranges (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input: [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.
Example 2:

Input: [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

思路:最土的办法就是 O(n), Medium 题肯定是利用 index 和 value 增量的关系用二分法找断点,然后将上一个断点连上

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
# 先写 O(n) 的再优化
class Solution:
def summaryRanges(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
if len(nums) == 0:
return nums
if len(nums) == 1:
return [str(nums[0])]
ans = []
slow, fast = 0, 0
while fast < len(nums):
if fast + 1 < len(nums) and nums[fast + 1] == nums[fast] + 1:
# fast keeps going
fast += 1
elif slow == fast:
# need to put slow in the ans
ans.append(str(nums[slow]))
fast += 1
slow = fast
else:
# create range
ans.append(str(nums[slow]) + '->' + str(nums[fast]))
fast += 1
slow = fast
return ans

总结:O(n) 一次写过都不容易,注意 1.slow 和 fast 都从 0 开始;2.循环条件 fast < len(nums); 3.三种情况:fast 前进,fast 不前进 fast 和 slow 在一起, fast 不前进 fast 在 slow 前面 4。fast 前进的判断 if fast + 1 < len(nums) and nums[fast + 1] == nums[fast] + 1。比两年多前的写法要略优一点。

Two pointers

LinC 373. Partition Array by Odd and Even (Easy)

1
2
3
4
Partition an integers array into odd number first and even number second.

Example
Given [1, 2, 3, 4], return [1, 3, 2, 4]

思路:双指针一头一尾,碰到不符合的就换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
"""
@param: nums: an array of integers
@return: nothing
"""
def partitionArray(self, nums):
# write your code here
if len(nums) < 2:
return
l, r = 0, len(nums) - 1
while l < r:
while l < r and nums[l] % 2 != 0:
l += 1
while l < r and nums[r] % 2 == 0:
r -= 1
if nums[l] % 2 == 0 or nums[r] % 2 != 0:
nums[l], nums[r] = nums[r], nums[l]
if nums[l] % 2 == 0 or nums[r] % 2 != 0:
nums[l], nums[r] = nums[r], nums[l]

总结:送两个测试数据进去就能写对。 最后两个 if 可以简化。

26. Remove Duplicates from Sorted Array (Easy)

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
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.
Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.
Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

思路:简单题, 慢指针只有在快指针碰到不同的值才走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
slow, fast = 0, 1
while fast < len(nums):
if nums[fast] == nums[slow]:
fast += 1
else:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1

总结:纯热身,秒解

28. Implement strStr() (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

思路:快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if len(needle) == 0:
return 0
if len(haystack) == 0:
return -1
for i in range(len(haystack)):
if haystack[i] == needle[0]:
if i + len(needle) - 1 < len(haystack):
if needle == haystack[i: i + len(needle)]:
return i
else:
return -1
return -1

总结: 思路是双指针没问题,实际用 python 的时候可以用 python 的性质直接取子串

160. Intersection of Two Linked Lists (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3
begin to intersect at node c1.

Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

思路:统计两条链走到头的长度,lenA 和 lenB, 然后让长的那条先走两者的差值,然后一起走,返回相遇的那点

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

class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
savedHeadA, savedHeadB = headA, headB
if headA == None or headB == None:
return None
lenA, lenB = 1, 1
while headA.next != None:
headA = headA.next
lenA += 1
while headB.next != None:
headB = headB.next
lenB += 1
if lenA > lenB:
diff = lenA - lenB
for x in xrange(diff):
savedHeadA = savedHeadA.next
else:
diff = lenB - lenA
for x in xrange(diff):
savedHeadB = savedHeadB.next
while savedHeadA != None:
if savedHeadA == savedHeadB:
return savedHeadA
else:
savedHeadA = savedHeadA.next
savedHeadB = savedHeadB.next
return None

总结:1.注意空输入(不能假设 headA 或 B 有 next)2.注意 headA headB 是一个节点 i.e. 合体的情况

141. Linked List Cycle (Easy)

1
2
3
4
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

思路:记得应该是慢的 +1 快的 +2 如果有 loop 会重逢。。。可能不那么值得做,热身吧

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

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None or head.next == None:
return False
slow, fast = head, head.next.next
while fast != None and fast.next != None and fast.next.next != None:
if slow == fast:
return True
slow = slow.next
fast = fast.next.next
return False

总结:有点意思,适合热身,代码写好后要测的情况比较多, 1 -> 2 无 loop,1 -> 2 -> 3 -> 4 loop 回 2 这些情况都要测一下。防止 next 和 next.next 不存在的情况

142. Linked List Cycle II (Medium)

1
2
3
4
5
6
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

思路:记得好像是找到有 loop 以后走多久能找到 cycle 的起点。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return None
slow, fast = head, head
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
while head != slow:
head = head.next
slow = slow.next
return head
return None
```
总结:slow fast 同时在 head,先走再判断。不然容易出错。有数学关系,面试当场不一定能推导出来。就算推导出来也要注意前面的 slow,fast写法。
a b
A ------ B --------+
| |
c | |
+-------- C

* A: 起始点
* B: Cycle Begins
* C: 1st 快慢指针相遇点

* A->B: a
* B->C: b
* C->B: c
* 环的长度 (b+c) 为 R

第一次相遇时,慢指针所走步数为 a + b 快指针走的步数为 *a + b + nR*
我们知道快指针是慢指针速度的2倍,因此 2(a + b) = a + b + nR 那么 a + b = nR
同时 b + c = R 所以 a = (n - 1)R + c;
也就是说,从A点和C点同时出发,以相同的速度前进,相遇的位置将是B。

### [283. Move Zeroes (Easy)](https://leetcode.com/problems/move-zeroes/description/)
```html
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

思路:第一感觉是快指针直接跑到最后, 慢指针遇到 0 就接快指针面;仔细读题才发现是数组 in place 转换;那就快指针到第一个非 0 的数,直到快指针到最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if len(nums) == 0 or len(nums) == 1:
return
slow, fast = 0, 0
while fast < len(nums) and nums[fast] == 0:
fast += 1
while slow < len(nums) - 1 and fast < len(nums):
if nums[slow] == 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
while fast < len(nums) and nums[fast] == 0:
fast += 1
slow += 1
if slow > fast:
fast += 1
while fast < len(nums) and nums[fast] == 0:
fast += 1

总结:思路简单,但是情况很多, 需要考虑,无 0, 0 在前, 后, 中四种情况 [1,2], [0, 1, 2], [1, 0, 0], [1, 0, 0, 1] 才能写对

125. Valid Palindrome (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:

Input: "race a car"
Output: false

思路:头尾双指针, 碰头了返回 True,相同继续走,不同返回 False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if len(s) == 0 or len(s) == 1:
return True
head, tail = 0, len(s) - 1
while head < tail:
while not s[head].isalnum() and head < tail:
head += 1
while not s[tail].isalnum() and head < tail:
tail -= 1
if s[head].lower() != s[tail].lower():
return False
else:
head += 1
tail -= 1
return True

总结:思路简单, 但是要想到的 case 很多。考虑带标点符号,连续两个位置都是标点符号,整个字符串都是标点符合这三个情况才能写对

680. Valid Palindrome II (Easy)

1
2
3
4
5
6
7
8
9
10
11
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

思路:目前网上看到大部分答案都以贪心算法为主,等看贪心了再刷这题。再看一眼感觉就是统计有没有 > 2 单数的题,撸之

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if len(s) <= 2:
return True
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
break
l += 1
r -= 1
if l >= r:
return True
# 要么删左边,要么删右边
return self.isPalindrome(s[:l] + s[l + 1:]) or self.isPalindrome(s[:r] + s[r + 1:])
def isPalindrome(self, s):
return s == s[::-1]

总结:没那么简单,还要考虑这些情况 1.如果有 2 个 single 均不在 mid 位置;2. 去掉 single 点后的 string 仍然不是 palindrome; 3. 1 个 single,多个位置可以删除; 然后就抓狂了。 看了答案, 真他妈的妖。双指针算法。从两头走到中间,发现第一对不一样的字符之后,要么删左边的,要么删右边的。

1. Two Sum (Easy)

1
2
3
4
5
6
7
8
9
10
11

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路:固定一个找另一个

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for index1 in xrange(len(nums)):
for index2 in xrange(index1 + 1, len(nums)):
if nums[index1] + nums[index2] == target:
return [index1, index2]

总结: 第二层循环的起始数字注意条件 you may not use the same element twice

167. Two Sum II - Input array is sorted (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

思路:增加了 sorted 这个条件, 第一感觉是可以折半查找了。固定 index1,index2 用折半查找获得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for index1 in range(len(numbers)):
start, end = index1 + 1, len(numbers) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if numbers[index1] + numbers[mid] == target:
return [index1 + 1, mid + 1]
elif numbers[index1] + numbers[mid] < target:
start = mid + 1
else:
end = mid - 1
if numbers[index1] + numbers[start] == target:
return [index1 + 1, start + 1]
elif numbers[index1] + numbers[end] == target:
return [index1 + 1, end + 1]

总结:要细心。1.题中 answers are not zero-based 2.要测两个情况 [2, 7, 19], 9 和 [5, 25, 75] 可以测出代码的问题

LinC 607. Two Sum III - Data structure design (Easy)

1
2
3
4
5
6
7
8
9
Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

Example
add(1); add(3); add(5);
find(4) // return true
find(7) // return false

思路:add 的时候把 sum 都存 dict 里面, 查的时候直接返回 dict 里面有没有 sum. 会超时。

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 TwoSum:
keys = {}
"""
@param: number: An integer
@return: nothing
"""
def add(self, number):
# write your code here
if number not in self.keys:
self.keys[number] = 1
else:
self.keys[number] = 2
"""
@param: value: An integer
@return: Find if there exists any pair of numbers which sum is equal to the value.
"""
def find(self, value):
# write your code here
for key in self.keys:
if value - key in self.keys:
if value - key == key:
if self.keys[key] == 2:
return True
else:
return True
return False

总结:虽然是一道容易题, 第一反应的思路会超时。 需要在 find 的时候判断能凑出答案的另一个 key 是不是已经在 keys 里了。而不是先存好 sum。 还要判断两个数相同的时候有没有存过两个数。

15. 3Sum (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

思路:可以吧 a + b + c = 0 变为 a + b = - c 的问题,问题则变为, 对于任意数 a,dict 里是否存在 -c - a 这么个数, a 和 c 是两层循环
二刷:可以把天真的第一想法扔掉了:)。 就是以当前遍历的点 i 为基础的双指针。二刷比一刷有一点改进空间。python 的 list 就带一定的去重机制,可以少写几行去重代码。3 年前写的还是很牛逼的。。。靠,三年前的写法会 TLE。。。真是难度越来越高了。。。尼玛。。。注意:当 sum == 0 的时候需要在 ans.appen(); l += 1; r -= 1; 的基础上加 while l < r and nums[l] == nums[l - 1]: l += 1 和 while l < r and nums[r] == nums[r + 1]: r -= 1 这样的跳过语句才能 AC。。。

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
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
results = []
nums.sort()
for index1 in range(len(nums) - 2):
if index1 and nums[index1] == nums[index1 - 1]:
continue
head = index1 + 1
tail = len(nums) - 1
while head < tail:
if nums[index1] + nums[head] > -nums[tail]:
tail -= 1
elif nums[index1] + nums[head] < -nums[tail]:
head += 1
else:
results.append([nums[index1], nums[head], nums[tail]])
head += 1
tail -= 1
while head < tail and nums[head] == nums[head - 1]:
head += 1
while head < tail and nums[tail] == nums[tail + 1]:
tail -= 1
return results

总结:三层循环是暴力方法,去重会受阻,这个时候需要想到给输入数组先排个序,因为结果里,没有要求元素的顺序,这是个重要的提示。排序以后每次固定一个数 index1,然后找的过程是:head = index1 + 1, tail = len(nums) - 1; while head < tail: if nums[index1] + nums[head] > - nums[tail]: tail -= 1, elif nums[index1] + nums[head] < -nums[tail]: head += 1, else: results.append()
代码还需要考虑的几个情况:1.对于已经用过的元素需要跳过, 这里要用到 if index1 and nums[index1] == nums[index1 - 1]; 2.如果碰到了一个 result,要跳过所有重复的元素,需要用到 while head < tail and nums[head] == nums[head - 1]: 和相应的 …nums[tail + 1]

LinC 382. Triangle Count (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?

Example
Given array S = [3,4,6,7], return 3. They are:

[3,4,6]
[3,6,7]
[4,6,7]
Given array S = [4,4,4,4], return 4. They are:

[4(1),4(2),4(3)]
[4(1),4(2),4(4)]
[4(1),4(3),4(4)]
[4(2),4(3),4(4)]

思路: 判断能不能做三角形以后全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
"""
@param S: A list of integers
@return: An integer
"""
def triangleCount(self, S):
# write your code here
S.sort(reverse=True)
sum = 0
for index1, longest in enumerate(S):
head, tail = index1 + 1, index1 + 2
while tail < len(S) and S[head] + S[tail] > longest:
tail += 1
tail -= 1
while head < tail:
sum += tail - head
head += 1
while head < tail and S[head] + S[tail] <= longest:
tail -= 1
return sum

总结:看清题目,问的是有多少个这样的三角形, 返回数就行。 全排列效率比较低。 更优解是每次定下最长边, 寻找符合条件的另外两个边的数量。 双指针的解法是将 tail 推到最小不能组成三角形的位置, 退一步, 然后从 tail 到 head 的位置的都可以组, 因为他们相加只会比最长边更长。 然后将 head 进一步(缩短),tail 边加长到大于最长边的位置,新 tail 到 head 的位置又都可以组。

16. 3Sum Closest (Medium)

1
2
3
4
5
6
7
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路:3sum 的思路是先排序,固定一个点以后,开始用双指针搜索符合条件的数。closest 感觉已经是 4sum,需要记 delta,然后往 delata 小的方向走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
ans = None
nums.sort()
for index1, val in enumerate(nums):
head = index1 + 1
tail = len(nums) - 1
while head < tail:
sum = nums[index1] + nums[head] + nums[tail]
if ans == None or abs(target - sum) < abs(target - ans):
ans = sum
if sum < target:
head += 1
elif sum > target:
tail -= 1
else:
return target
return ans

总结:比 3sum 省事的是不需要优化跳过重复的元素也可以过。pyhton 可以用 None 就不用想 Java 那样吧 ans 初始化为 MAX_VALUE 了

86. Partition List (Medium)

1
2
3
4
5
6
7
8
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

思路:慢快指针,慢指针在最后一个 < x 的位置, 快指针在最后一个 >= x 的位置,快指针碰到一个 < x 的就和慢指针换

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

class Solution:
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
if head == None or head.next == None:
return head
fakie = ListNode(-1)
fakie.next = head
slow, fast = fakie, None
while slow != None:
while slow != None and slow.next != None and slow.next.val < x:
slow = slow.next
if fast == None:
fast = slow
while fast != None and fast.next != None and fast.next.val >= x:
fast = fast.next
if fast.next == None or slow.next == None:
break
savedFastNext = fast.next
fast.next = fast.next.next
savedSlowNext = slow.next
slow.next = savedFastNext
savedFastNext.next = savedSlowNext
slow = slow.next
return fakie.next

总结:链表的问题需要先放一个假头,注意 1->1 x = 0, 1->1 x = 2, 2->1 x = 2 这三种情况和题中的例子情况 1->4->3->2->5->2 才能写对。

LinC 31. Partition Array (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Description
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:

All elements < k are moved to the left
All elements >= k are moved to the right
Return the partitioning index, i.e the first index i nums[i] >= k.

You should do really partition in array nums instead of just counting the numbers of integers smaller than k.

If all elements in nums are smaller than k, then return nums.length
Example
If nums = [3,2,2,1] and k=2, a valid answer is 1.

Challenge
Can you partition the array in-place and in O(n)?

思路:和 partition list 很像, 数组的话就只能用双指针了. l 是最后一个 < k, r 是最后一个 >= k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
"""
@param nums: The integer array you should partition
@param k: An integer
@return: The index after partition
"""
def partitionArray(self, nums, k):
# write your code here
if len(nums) == 0:
return 0
l, r = 0, len(nums) - 1
while l <= r:
while l < len(nums) and nums[l] < k:
l += 1
while r >= 0 and nums[r] >= k:
r -= 1
if l > r:
break
nums[l], nums[r] = nums[r], nums[l]
return l

总结:因为数组比链表好操作的多, 比 partition list 解法简单, 需要注意:1。while 的条件是 l <= r 2。l 往右走,r 往左走不要越界,r 往左需要 r >= 0 3.l > r 的时候需要 break

215. Kth Largest Element in an Array (Medium)

1
2
3
4
5
6
7
8
9
10
11
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

思路:应该是不去排序的基础上找到第 K 大的数。现场想是基本没戏的。网上答案:quickselect 算法,基于 quicksort. 1.选第一个数为 pivot 2.比 pivot 大的放左边, 不然右边 3.如果 pivot 是第 k, 返回该值, 大于 k 扔掉右边, 否则扔掉左边

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 findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
k -= 1
def quickSelect(s, e):
l, r = s + 1, e
while l <= r:
if nums[l] > nums[s]:
l += 1
else:
nums[l], nums[r] = nums[r], nums[l]
r -= 1
nums[s], nums[r] = nums[r], nums[s]
if r == k:
return nums[r]
elif r > k:
return quickSelect(s, r - 1)
else:
return quickSelect(r + 1, e)
return quickSelect(0, len(nums) - 1)

总结:要背 pivot 的部分,如果第一个数是 pivot,那么走一遍,碰到比他大的不动,小的塞右边,l <= r 走完把 pivot 和 r 值互换,r 左边就是大于 pivot 数的子数组. 注意:递归调用的时候记得函数名前要加 return 否则不会返回任何值。由于完全抛弃另一侧,时间复杂度平均由 quick sort 的 O(nlogn) 降为 O(n) 因为输入变小了, quicksort 的输入一直是 n, 最差情况 O(n^2)

75. Sort Colors (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

思路:因为只有 3 种颜色,1 pass 就是设好 l, r 两个指针,分别代表颜色的边界,碰到不属于边界的就往正确的边界内交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
if len(nums) == 0 or len(nums) == 1:
return
index, l, r = 0, 0, len(nums) - 1
while l < r and index <= r:
while nums[l] == 0 and l < r:
l += 1
while nums[r] == 2 and l < r:
r -= 1
if l > index:
index = l
if nums[index] == 0:
nums[l], nums[index] = nums[index], nums[l]
if nums[index] == 1:
index += 1
continue
if nums[index] == 2:
nums[index], nums[r] = nums[r], nums[index]

总结:counting sort:数一下每个元素有多少个,一次给写到结果里; 这种写法基本上秒出 :),想当年傻逼呵呵的这种简单题都面试的时候挂掉,哎。。。如今得换种 1 pass 高级点的;一开始想的思路有个问题,就是如果只有两个指针,两个指针都指 1, 中间夹一大堆 2 就没办法了。 改成三指针, l, r 维持边界,index 从 l 走到 r; 要一次写对得注意:1.当 l 大于 index 的时候, index 要追上来 2.整个循环的终止条件需要 l < r and index <= r, 不然过不了 [2, 0, 1] (index <= r), [0, 0], [1, 1] (l < r) 这两个情况

658. Find K Closest Elements (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
Note:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 104
Absolute value of elements in the array and x will not exceed 104
UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

思路:看答案思路还是比较清楚的,1.二分法查找 target,将 l, r 指针放到正确的位置;2.左右按 diff 走 k;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
33
34
35
36
37
38
class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
if len(arr) <= 1:
return arr
ans = []
l, r = 0, len(arr) - 1
# 将 l, r 放到正确的位置, 如果 mid 值 < k, 扔左边, else 仍右边
while l < r - 1:
mid = l + (r - l) // 2
if arr[mid] < x:
l = mid
else:
r = mid
# l,r 都在正确的位置了,左右按 diff 搜集 k 个
count = 0
while l >= 0 and r <= len(arr) - 1 and count < k:
if abs(arr[l] - x) <= abs(arr[r] - x):
ans.append(arr[l])
l -= 1
else:
ans.append(arr[r])
r += 1
count += 1
while l >= 0 and count < k:
ans.append(arr[l])
l -= 1
count += 1
while r <= len(arr) - 1 and count < k:
ans.append(arr[r])
r += 1
count += 1
return sorted(ans)

总结:注意:1.结果需要是 sorted;2.题目中的一个条件 “If there is a tie, the smaller elements are always preferred.”

18. 4Sum (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

思路:看了下三年前的答案,不是特别直观。看了九章的答案,貌似好理解一点:去重,枚举一个数,然后用 3Sum 的做法,O(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
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
ans = []
for i in range(0, len(nums) - 3):
if i and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 2):
if j != i + 1 and nums[j] == nums[j - 1]:
continue
l, r = j + 1, len(nums) - 1
while l < r:
sum = nums[i] + nums[j] + nums[l] + nums[r]
if sum == target:
ans.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif sum < target:
l += 1
else:
r -= 1
return ans

总结:有一个自己肯定想不出的条件就是第二层循环怎么跳过:if j != i + 1 and nums[j] == nums[j - 1]: continue; 非常勉强能过 AC. 看了网上和三年前的,都是用 dict 先存 2sum,然后再 loop 两遍,用 if pair[0] > j 来去重(第三个元素的 index 要大于前面两个)。todo:有兴致二刷的时候写优化的算法吧。不是那么值得二刷。先这么地了。

BFS 广度优先搜索

图的遍历 Traversal in Graph

  • 层级遍历 Level Order Traversal
  • 由点及面 Connected Component
  • 拓扑排序 Topological Sorting

最短路径 Shortest Path in Simple Graph

  • 仅限简单图求最短路径。即,图中每条边长度都是1,或者边长都相等

695. Max Area of Island (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

思路:没啥太多好说的,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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if len(grid) == 0:
return 0
ans = 0
for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == 1:
ans = max(self.bfs(grid, row, col), ans)
return ans
def bfs(self, grid, row, col):
import collections
q = collections.deque()
q.append((row, col))
grid[row][col] = 0
size = 0
while q:
row, col = q.popleft()
size += 1
if self.isValid(grid, row - 1, col) and grid[row - 1][col] == 1:
q.append((row - 1, col))
grid[row - 1][col] = 0
if self.isValid(grid, row + 1, col) and grid[row + 1][col] == 1:
q.append((row + 1, col))
grid[row + 1][col] = 0
if self.isValid(grid, row, col - 1) and grid[row][col - 1] == 1:
q.append((row, col - 1))
grid[row][col - 1] = 0
if self.isValid(grid, row, col + 1) and grid[row][col + 1] == 1:
q.append((row, col + 1))
grid[row][col + 1] = 0
return size
def isValid(self, grid, row, col):
return row >= 0 and row < len(grid) and col >= 0 and col < len(grid[0])

总结:在上下左右走的时候注意入 q 以后立刻将该点标为 0, 以防同一个点入两次。

102. Binary Tree Level Order Traversal (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

思路:热身阶段,先看答案

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
# 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):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
ans = []
if root == None:
return ans
q = [root]
while q:
new_q = []
temp = []
for node in q:
temp.append(node.val)
if node.left:
new_q.append(node.left)
if node.right:
new_q.append(node.right)
ans.append(temp)
q = new_q
return ans

总结:看来答案还是很简单的,注意只需要处理 root 为空,记得返回 ans
二刷:107. Binary Tree Level Order Traversal II (Easy) 没毛病,注意:list.reverse() 是 in place, 不返回 list 可以 ans.reverse() return ans, 或者啰嗦点的 list(reversed(ans)) 返回 list。用 deque 其实是多余的,因为每个 level 的 q 都直接扔掉(拼出来的下一层的 newQ 取代),可以用 list,for 循环一遍就可以了。

103. Binary Tree Zigzag Level Order Traversal (Medium)

LinC 71. Binary Tree Zigzag Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

思路:reverse 初始为 0,每层 1 - reverse, reverse == 1 就 reverse

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

class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
q = [root]
ans = []
reverse = 0
while q:
temp = []
newQ = []
for node in q:
temp.append(node.val)
if node.left:
newQ.append(node.left)
if node.right:
newQ.append(node.right)
if reverse:
temp.reverse()
reverse = 1 - reverse
ans.append(temp)
q = newQ
return ans

总结:一次过,可做可不做吧

133. Clone Graph (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


OJ's undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
/ \
/ \
0 --- 2
/ \
\_/

思路:BFS, 用一个 dict 存当前节点的邻居,如果没见过就加 dict 存 queue,queue 出来建 node,放 neighbor;概念上比较好懂,写码可能有坑

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 undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []

class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if node == None:
return None
dict = {}
_cloneNode = UndirectedGraphNode(node.label)
dict[node] = _cloneNode
q = [node]
while q:
new_q = []
for _node in q:
for neighbor in _node.neighbors:
if neighbor not in dict:
_cloneNode = UndirectedGraphNode(neighbor.label)
dict[neighbor] = _cloneNode
new_q.append(neighbor)
dict[_node].neighbors.append(dict[neighbor])
q = new_q
return dict[node]

总结:思路用 dict 来存当前节点的邻居是错的,需要用 dict 存当前节点和克隆节点的映射关系。因为反正映射关系在,加邻居可以后加. 邻居是不能直接 copy 或者 = 的, 因为邻居的类型也是节点, 需要创造以后加进去。测一下,然后 debug 细一点, 要测出

1
dict[_node].neighbors.append(dict[neighbor])

127. Word Ladder (Medium)

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
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

思路:确实是寻找路径的问题,从 beginWord 到 endWord 是否存在最短路径让他俩相连,最短路径取决于词库里有哪些词(路径)。怎么实现很不清晰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import string
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if beginWord == endWord:
return 0
wordSet = set(wordList)
q = collections.deque([[beginWord, 1]])
while q:
word, level = q.popleft()
for index in range(len(word)):
for char in 'abcdefghijklmnopqrstuvwxyz':
newWord = word[:index] + char + word[index + 1:]
if newWord in wordSet:
if newWord == endWord:
return level + 1
wordSet.remove(newWord)
q.append([newWord, level + 1])
return 0

总结:看了下答案,网上答案解释的比较好理解的是,起始词是树的根节点,每一层是从第一个字母到最后一个字母,每次一个字母,从 a - z 替换过一遍,同时又在 wordList 里的词。从上往下 BFS,找到 endWord 即返回当前 level。啧啧啧,强大的应用题。逻辑对还得不 TLE 需要1.将 wordList 转成 set;2.使用 collections.deque;3.碰到 wordSet 中的词,先该词在 wordSet 中删除,再入 deque

200. Number of Islands (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
Input:
11110
11010
11000
00000
Output: 1

Example 2:
Input:
11000
11000
00100
00011
Output: 3

思路:遍历矩阵,碰到 1 就上下左右 BFS,碰到 0 跳过。BFS 访问过的标 0

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
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if len(grid) == 0:
return 0
ans = 0
for rowI in range(len(grid)):
for colI in range(len(grid[0])):
if grid[rowI][colI] == "1":
ans += 1
q = collections.deque([[rowI, colI]])
grid[rowI][colI] = "0"
while q:
row, col = q.popleft()
# up
if (row > 0) and grid[row - 1][col] == "1":
q.append([row - 1, col])
grid[row - 1][col] = '0'
# down
if (row < len(grid) - 1) and grid[row + 1][col] == "1":
q.append([row + 1, col])
grid[row + 1][col] = '0'
# left
if (col > 0) and grid[row][col - 1] == "1":
q.append([row, col - 1])
grid[row][col - 1] = '0'
# right
if (col < len(grid[0]) - 1) and grid[row][col + 1] == "1":
q.append([row, col + 1])
grid[row][col + 1] = '0'
return ans

总结:对于 leetcode ac 比较重要的细节是,gird[][] = ‘0’ 这句话要在 while 的每个 if 里面,否则逻辑 OK 但是会 TLE

LinC 611. Knight Shortest Path (Medium)

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
Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if knight can not reached.

source and destination must be empty.
Knight can not enter the barrier.

Clarification
If the knight is at (x, y), he can get to the following positions in one step:

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)
Example
[[0,0,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2] return 2

[[0,1,0],
[0,0,0],
[0,0,0]]
source = [2, 0] destination = [2, 2] return 6

[[0,1,0],
[0,0,1],
[0,0,0]]
source = [2, 0] destination = [2, 2] return -1

思路:没什么思路, 看了下答案,就是 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""

class Solution:
"""
@param grid: a chessboard included 0 (false) and 1 (true)
@param source: a point
@param destination: a point
@return: the shortest path
"""
def shortestPath(self, grid, source, destination):
# write your code here
if len(grid) == 0 or (len(grid[0]) == 1 and grid[0][0] == 1):
return -1
ans = 0
dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [2, -2, 2, -2, 1, -1, 1, -1]
q = collections.deque([source])
grid[source.x][source.y] = 1
while q:
qlen = len(q)
next_q = collections.deque()
for i in range(qlen):
pt = q.popleft()
if pt.x == destination.x and pt.y == destination.y:
return ans
for move in range(len(dx)):
nextPt = Point(pt.x + dx[move], pt.y + dy[move])
if (self.isInbound(grid, nextPt) and grid[nextPt.x][nextPt.y] == 0):
next_q.append(nextPt)
grid[nextPt.x][nextPt.y] = 1
ans += 1
q = next_q
return -1
def isInbound(self, grid, pt):
return pt.x >= 0 and pt.x < len(grid) and pt.y >= 0 and pt.y < len(grid[0])

总结:注意 isInbound 要查的是 >=0 和 < len(), 其他的问题可以通过跑一个测试数据发现

785. Is Graph Bipartite? (Medium)

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
Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.


Note:

graph will have length in range [1, 100].
graph[i] will contain integers in range [0, graph.length - 1].
graph[i] will not contain i or duplicate values.
The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

思路:光理解题目就要花一点时间,现场想几乎是不可能的。用染色的方法,可以用 DFS, BFS 给所有 node 染上两种色中的一种,如果存在相邻的两个 node 能染上同一个颜色,那么就不是 bipartite。具体实现先看答案。看到一个比较好理解的,不知道对不对。 1.初始化 colors 为 -1 的数组,遍历,如果没有染色,如果 bfs() 为 False 则 返回 False;2.bfs 内 while q: 如未染色,入 q, 染上 1 - c 的色,如已染色,检查是否是 1 - c 的色

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
class Solution:
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
if len(graph) <= 2:
return True
colors = [-1] * len(graph)
for i in range(len(graph)):
if colors[i] == -1:
if not self.bfs(graph, colors, 0, i):
return False
return True
def bfs(self, graph, colors, color, node):
q = collections.deque()
q.append(node)
colors[node] = color
while q:
cur = q.popleft()
curColor = colors[cur]
for i in graph[cur]:
if colors[i] == -1:
colors[i] = 1 - curColor
q.append(i)
else:
if colors[i] != 1 - curColor:
return False
return True

总结:遍历的时候注意需要加如果还未染色这个条件。较变态的题,还有 DFS 的解法,todo 吧

LinC 178. Graph Valid Tree (Medium)

Leetcode 261. Graph Valid Tree 加锁

1
2
3
4
5
6
7
8
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

思路:树的两个条件是不能有环,不能有孤儿节点。怎么实现想不太出来。看了答案,用 defaultdict(list) 放节点之间的关系, 有没有环其实不用管,因为只要确保边的数量 == n - 1, 并且 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
25
26
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def validTree(self, n, edges):
# write your code here
if len(edges) == 0 and n == 1:
return True
if len(edges) != n - 1:
return False
mapping = collections.defaultdict(list)
for edge in edges:
mapping[edge[0]].append(edge[1])
mapping[edge[1]].append(edge[0])
visited = set()
q = [0]
while q:
node = q.pop()
visited.add(node)
for neighbor in mapping[node]:
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
return len(visited) == n

总结:相当值得做的一道 BFS 题。注意 已经访问过的节点不要入 q,不然无向图的边会导致死循环

Topological sorting 拓扑排序

LinC 127. Topological Sorting (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.
Find any topological order for the given graph.

You can assume that there is at least one topological order in the graph.

Clarification
[Learn more about representation of graphs](http://www.lintcode.com/help/graph)

Example
For graph as follow:

graph example

1
2
3
The topological order can be:
[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]

思路:拓扑排序,算法貌似是:1.统计每个点的入度;2.将入度为 0 的点入 queue;3.从队列中 pop 点,去掉所有指向别的点的边: 相应点入度 -1;4.新入度为 0 的点入 queue

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""
Definition for a Directed graph node
class DirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
"""


class Solution:
"""
@param: graph: A list of Directed graph node
@return: Any topological order for the given graph.
"""
def topSort(self, graph):
# write your code here
if len(graph) == 0:
return []
ans = []
inBound = {}
for node in graph:
if node not in inBound:
inBound[node] = 0
for neighbor in node.neighbors:
if neighbor not in inBound:
inBound[neighbor] = 0
inBound[neighbor] += 1
q = collections.deque()
for node in inBound:
if inBound[node] == 0:
q.append(node)
while q:
zNode = q.popleft()
ans.append(zNode)
for node in zNode.neighbors:
inBound[node] -= 1
if inBound[node] == 0:
q.append(node)
return ans
```
总结:顺利。但是题目没有说清楚 return 的是一个拓扑排序好的 node 的 list

### [207. Course Schedule (Medium)](https://leetcode.com/problems/course-schedule/description/)
```html
There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

思路:其实是问拓扑顺序存不存在,具体实现得看答案

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
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
if len(prerequisites) == 0 or len(prerequisites[0]) == 0 or len(prerequisites[0]) == 1:
return True
graph = {}
inBound = {}
for prereqs in prerequisites:
for index, course in enumerate(prereqs):
if course not in graph:
graph[course] = []
if course not in inBound:
inBound[course] = 0
if index < len(prereqs) - 1:
graph[course].append(prereqs[index + 1])
if index > 0:
inBound[course] += 1
q = collections.deque()
for key in inBound:
if inBound[key] == 0:
q.append(key)
while q:
course = q.popleft()
for neighbor in graph[course]:
inBound[neighbor] -= 1
if inBound[neighbor] == 0:
q.append(neighbor)
for key in inBound:
if inBound[key] > 0:
return False
return True

总结:有向图有环则拓扑顺序不存在,题可以变为如何检测有向图有环的问题。算法的核心是计算所有节点的入度,然后做类似上题的 BFS,每遍历一次邻居,入度减一,如果遍历完以后还有点的入度 > 0,则图有环。具体实现两个 dict,一个存节点和邻居们, 一个存节点和入度, 再加个 queue; 注意下 prerequisites 是个 list of list 别的没什么

210. Course Schedule II (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .

Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

思路:是前两道题的延伸,既要计算所有节点的入度, BFS,又要做拓扑排序,记下拓扑的顺序。 如果结束时还有入度 > 0 的节点,则图有环,无解

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
40
41
42
43
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
ans = []
if len(prerequisites) == 0 or len(prerequisites[0]) == 0:
for i in range(numCourses):
ans.append(i)
return ans[::-1]
graph = {}
inBound = {}
for prereqs in prerequisites:
for index, course in enumerate(prereqs):
if course not in graph:
graph[course] = []
if course not in inBound:
inBound[course] = 0
if index < len(prereqs) - 1:
graph[course].append(prereqs[index + 1])
if index > 0:
inBound[course] += 1
q = collections.deque()
for course in inBound:
if inBound[course] == 0:
ans.append(course)
q.append(course)
while q:
course = q.popleft()
for neighbor in graph[course]:
inBound[neighbor] -= 1
if inBound[neighbor] == 0:
ans.append(neighbor)
q.append(neighbor)
for course in inBound:
if inBound[course] > 0:
return []
for i in range(numCourses):
if i not in inBound:
ans.append(i)
return ans[::-1]

总结:值得做的题的边缘,要满足些很琐碎的细节才能 AC,和 Course Schedule 题不同点在于这题需要用 numCourses。如果有些节点在 prerequisites 里不出现的话,需要在答案里加进去

LinC 605. Sequence Reconstruction (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example
Given org = [1,2,3], seqs = [[1,2],[1,3]]
Return false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Given org = [1,2,3], seqs = [[1,2]]
Return false
Explanation:
The reconstructed sequence can only be [1,2].

Given org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Return true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Given org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Return true

思路:没什么思路,被考点吸引,如何构建图,如何拓扑排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
"""
@param org: a permutation of the integers from 1 to n
@param seqs: a list of sequences
@return: true if it can be reconstructed only one or false
"""
def sequenceReconstruction(self, org, seqs):
# write your code here
if len(seqs) == 0 and len(org) == 0:
return True
if len(seqs) == 0 and len(org) != 0:
return False
if len(seqs) != 0 and len(org) == 0:
return False
graph = {}
indegree = {}
for seq in seqs:
if len(seq) > len(org):
return False
for val in seq:
if val not in graph:
graph[val] = []
if val not in

总结:看了网上答案,记录入度,记录邻居,拓扑排序拓扑排序出来要有唯一解(q 每次长度都是 1)和 org 的相应位置的值要相等结束才能返回 True。写了一半实在是不想写了。 回头在写吧。todo item

DFS 深度优先搜索

Binary Tree & Tree-based DFS 二叉树与树上的深度优先搜索

104. Maximum Depth of Binary Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
return its depth = 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
33
34
35
36
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

# Divide and Conquer 分治
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return max(left, right) + 1

# Traverse 遍历
class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
self.helper(root, 1)
return self.ans
def helper(self, root, curDepth):
if not root:
return
self.ans = max(self.ans, curDepth)
self.helper(root.left, curDepth + 1)
self.helper(root.right, curDepth + 1)

总结:热身:), 非递归据说需要 postorder traversal (Hard)
二刷:一刷的递归用的是分治, 当时没看出来而已, 加了遍历方法。

226. Invert Binary Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Invert a binary tree.

Example:

Input:

4
/ \
2 7
/ \ / \
1 3 6 9
Output:

4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

思路:咋一看略懵逼,看了下三年前的答案,两层循环。。。
二刷:还有递归的 DFS 写法。非递归更像 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

# 非递归
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return root
processQ = []
processQ.append(root)
while processQ:
nextLevel = []
for node in processQ:
if node.left:
nextLevel.append(node.left)
if node.right:
nextLevel.append(node.right)
node.left, node.right = node.right, node.left
processQ = nextLevel
return root

# DFS 递归
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return root
self.dfs(root)
return root
def dfs(self, root):
root.left, root.right = root.right, root.left
if root.left:
self.dfs(root.left)
if root.right:
self.dfs(root.right)

总结:三年前还是挺牛逼的。。。二刷加了 DFS 递归写法。

701. Insert into a Binary Search Tree (Medium)

LinC Insert Node in a Binary Search Tree

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
Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:
4
/ \
2 7
/ \
1 3
And the value to insert: 5
You can return this binary search tree:

4
/ \
2 7
/ \ /
1 3 5
This tree is also valid:

5
/ \
2 7
/ \
1 3
\
4

思路:没什么思路,看答案好像就是根据 BST 的性质二分查找下去,这跟二分查找没关系啊。。。

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

class Solution:
def insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
node = TreeNode(val)
cur = root
while cur.val != node.val:
if cur.val < node.val:
if not cur.right:
cur.right = node
cur = cur.right
else:
if not cur.left:
cur.left = node
cur = cur.left
return root

总结:不懂为什么 Leetcode 要标 medium 难度。我把这题放热身区

257. Binary Tree Paths (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

1
/ \
2 3
\
5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

思路:既然是 DFS 环节,看着就是 DFS 的解法。实现应该有坑

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

class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
ans = []
if root == None:
return ans
self.helper(root, '', ans)
return ans
def helper(self, root, path, ans):
if root.left == None and root.right == None:
ans.append(path + str(root.val))
return
if root.left != None:
self.helper(root.left, path + str(root.val) + '->', ans)
if root.right != None:
self.helper(root.right, path + str(root.val) + '->', ans)

总结:递归的模板需要记,需要 path, 总答案 ans,每次进入递归函数时:1.如果已经到底,将 path append 上 root.val 并加入到 ans;2.如有左边递归左边,如有右边递归右边。注意 python + string 要先把 int 变成 str

236. Lowest Common Ancestor of a Binary Tree (Medium)

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
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
according to the LCA definition.

Note:
All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.

思路:很久没刷过题了,这题第一感觉是 DFS 回溯,但是没有多的灵感。看答案。

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(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root == None or root == p or root == q:
return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if (l == p and r == q) or (l == q and r == p):
return root
if l != None:
return l
if r != None:
return r

总结:答案的算法是 DFS,从叶子节点向上,如果子树中有目标节点,返回目标节点。否则为 None。如果左右子树都有目标节点,则找到 LCA,如果在 p 为跟节点的子树中有 q,则 p 为 LCA 反之亦然。最后为子树返回目标节点非常 tricky,必须要用 l != None。 直觉上更好理解的 l == p or l == q 过不了, 不知道为什么。 已经在讨论区问了

235. Lowest Common Ancestor of a Binary Search Tree (Easy)

思路:跟上题一样,除了多一个 BST 树的条件, 将题变成了一个二分查找的题

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

class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if root == None or root == p or root == q:
return root
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root

总结:稍微看一下就行。 不值得刷的题。

144. Binary Tree Preorder Traversal (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?

思路:递归写熟了确实是简单。
二刷:看了下 traverse 背后的逻辑,“拿着一个记事本, 顺着二叉树走, 走过一个, 在本子上面记下来”
preorder-traverse-logic-image

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

# 递归 Traverse
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if root == None:
return ans
self.helper(root, ans)
return ans
def helper(self, root, ans):
if root == None:
return
ans.append(root.val)
self.helper(root.left, ans)
self.helper(root.right, ans)

# 非递归
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if not root:
return ans
stack = []
stack.append(root)
while stack:
n = stack.pop()
ans.append(n.val)
if n.right:
stack.append(n.right)
if n.left:
stack.append(n.left)
return ans

# Divide and Conquer 分治
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if not root:
return ans
left = self.preorderTraversal(root.left)
right = self.preorderTraversal(root.right)
ans.append(root.val)
ans.extend(left)
ans.extend(right)
return ans

总结:非递归要记住 pop,push right, push left 这个算法。就可以写对.
二刷:因为栈是先进后出,所以先 push right。分治的代码里要用 extend 来把 list 填充到另一个 list 里。

94. Binary Tree Inorder Traversal (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

思路:递归和用栈各写一遍
二刷:递归如果不想用 instance variable,就将 ans 传到 helper 里去。

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
40
41
42
43
44
45
46
47
48
49
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

# 二刷递归
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ans = []
if root == None:
return ans
self.helper(root, ans)
return ans
def helper(self, root, ans):
if root == None:
return
self.helper(root.left, ans)
ans.append(root.val)
self.helper(root.right, ans)

# 非递归 / stack
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
ans = []
if root == None:
return ans
while root:
stack.append(root)
root = root.left
while stack:
node = stack.pop()
ans.append(node.val)
if node.right:
node = node.right
while node:
stack.append(node)
node = node.left
return ans

总结:递归好理解的方法需要用一个全局变量, 目前还没有想到不用 class 变量的方法。非递归 / stack 需要记住套路:1.从 root 往左全入栈;2. pop 栈,ans.append(node.val);3.有右子节点的话走到右子节点,将右子节点及所有左子节点全入栈
二刷:不用 class 变量就把 ans 传入 helper / dfs 函数, 把一刷的递归去掉了,看题的时候方便点。

LinC 448. Inorder Successor in BST (Medium)

Leetcode 285. Inorder Successor in BST 带锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

If the given node has no in-order successor in the tree, return null.

It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)

Example
Given tree = [2,1] and node = 1:

2
/
1
return node 2.

Given tree = [2,1,3] and node = 2:

2
/ \
1 3
return node 3.

Challenge
O(h), where h is the height of the BST.

思路:DFS 找这个 node, 返回这个 node inorder 的下一个 node

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
"""
Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Solution:
"""
@param: root: The root of the BST.
@param: p: You need find the successor node of p.
@return: Successor of p.
"""
def inorderSuccessor(self, root, p):
# write your code here
if not root:
return root
stack = []
while root:
stack.append(root)
root = root.left
found = False
while stack:
n = stack.pop()
if found:
return n
if n.val == p.val:
found = True
if n.right:
n = n.right
while n:
stack.append(n)
n = n.left
return None

总结:递归怎么都写不对, 先抄一个非递归能理解的。 todo 二刷的时候刷个能理解的递归 DFS 方法。

98. Validate Binary Search Tree (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:

Input:
2
/ \
1 3
Output: true
Example 2:

5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.

思路:感觉是二叉树 DFS 加两个判断,如果左边不比 root 小就 false,如果右边不比 root 大就 false,遍历结束返回 true

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

# 九章的 inorder traversal 写法。虽然有点流氓但是优雅。
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None or (root.left == None and root.right == None):
return True
self.lastVal = None
self.ans = True
self.inOrder(root)
return self.ans
def inOrder(self, root):
if root == None or self.ans == False:
return
self.inOrder(root.left)
if self.lastVal != None and self.lastVal >= root.val:
self.ans = False
return
self.lastVal = root.val
self.inOrder(root.right)

# Divide and conquer 分治
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None or (root.left == None and root.right == None):
return True
return self.helper(root, -sys.maxsize, sys.maxsize)
def helper(self, root, minVal, maxVal):
if root == None:
return True
if root.val <= minVal or root.val >= maxVal:
return False
return self.helper(root.left, minVal, min(root.val, maxVal)) and self.helper(root.right, max(root.val, minVal), maxVal)

# 非递归 / DFS 方法
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None or (root.left == None and root.right == None):
return True
stack = []
while root:
stack.append(root)
root = root.left
lastN = None
while stack:
n = stack[-1]
if lastN and lastN.val >= n.val:
return False
lastN = n
if n.right:
n = n.right
while n:
stack.append(n)
n = n.left
else:
n = stack.pop()
while stack and stack[-1].right == n:
n = stack.pop()
return True

总结:看答案大多是 Divide and Conquer,一次用递归写不对,因为没有考虑子树里 valid 但是放到上面一级不 valid 的情况,比如这棵树:[10,5,15,null,null,6,20]。
九章的 python 答案用了一个 class variable 记 last val 然后 inorder traversal 中序遍历这样只要 last val >= root.val 就不是 valid BST,好流氓,但是好喜欢,撸之。测一下那个子树 valid 但是上面一级不 valid 的数就能写对。
正确的 Divide and Conquer / 分治方法是将当前 root 允许的 max 和 min 值传下去;注意:1.分治最后一句 minVal 和 maxVal 的传法是 return f(root.left, minVal, min(root.val, maxVal)) and f(root.right, max(root.val, minVal), maxVal) 思考方法为,如果从 最上面的 root 下来,传下来的是 -max 和 max,如何处理,就能写对;2.min max 是函数名,变量名要用 minVal maxVal
DFS 的解法最后一部分非常关键:1.如果有 lastN and lastN.val >= n.val: return False, lastN = n; 2.if n.right: DFS 套路,往右走一个然后往左到底 3. else: n = stack.pop() while stack and stack[-1].right == n: n = stack.pop() 这部分没办法,todo 反复写 :(。

230. Kth Smallest Element in a BST (Medium)

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
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1

Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

思路:第一感觉是一直往下,找到最小,然后利用 BST 左边比 root 小,root 不大于右边的特性找到 K。 具体怎么实现得看答案。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

# 第一次写能 ac 的土递归办法
class Solution(object):
cnt = 0
ans = 0
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.helper(root, k)
return self.ans
def helper(self, root, k):
if root == None:
return
self.helper(root.left, k)
self.cnt += 1
if self.cnt == k:
self.ans = root.val
return
self.helper(root.right, k)

# 非递归 / 栈
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack = []
while root:
stack.append(root)
root = root.left
cnt = 0
while stack:
node = stack.pop()
cnt += 1
if cnt == k:
return node.val
if node.right:
node = node.right
while node:
stack.append(node)
node = node.left

总结:答案基本就是中序遍历,统计当前遍历的步数,到 k 返回。递归算法还是需要全局变量:(。非递归 / 栈算法用上题的套路加一个 counter 就很容易写对。 Follow up: 二叉树经常被修改 如何优化 kthSmallest 这个操作? 在 TreeNode 中增加一个 counter,代表整个树的节点个数,也可以用一个 HashMap<TreeNode, Integer> 来存储某个节点为代表的子树的节点个数。在增删查改的过程中记录不断更新受影响节点的 counter, 在 kthSmallest 的实现中用类似 Quick Select 的算法去找到 kth smallest element 时间复杂度为 O(h),h 为树的高度。

173. Binary Search Tree Iterator (Medium)

1
2
3
4
5
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

思路:看了代码 “Your BSTIterator will be called like this” 后感觉这个 iterator 需要存一个中序遍历的队列, next() 就 popleft,hasNext() 就返回该队列是否为空。use O(h) 内存暂时不知道怎么实现

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

class BSTIterator(object):
q = collections.deque()
def __init__(self, root):
"""
:type root: TreeNode
"""
if root == None:
return
stack = []
while root:
stack.append(root)
root = root.left
while stack:
node = stack.pop()
self.q.append(node.val)
if node.right:
node = node.right
while node:
stack.append(node)
node = node.left

def hasNext(self):
"""
:rtype: bool
"""
return len(self.q) > 0

def next(self):
"""
:rtype: int
"""
return self.q.popleft()

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

总结:注意全局变量(和 class method)前面加 self.,别的没什么,想好了比较好写的题

LinC 900. Closest Binary Search Tree Value (Easy)

1
2
3
4
5
6
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example
Given root = {1}, target = 4.428571, return 1.

思路:如果中序遍历的话是从小到大,这题要找离 target 最近的点,中序遍历以后可以用二分查找直接找到那个点

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
40
41
42
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""

class Solution:
"""
@param root: the given BST
@param target: the given target
@return: the value in the BST that is closest to the target
"""
# 最直观
def closestValue(self, root, target):
# write your code here
ans = root.val
while root:
if abs(root.val - target) < abs(ans - target):
ans = root.val
if root.val < target:
root = root.right
else:
root = root.left
return ans

# 递归回溯
def closestValue(self, root, target):
# write your code here
tempA = root.val
if tempA < target:
root = root.right
else:
root = root.left
if root == None:
return tempA
tempB = self.closestValue(root, target)
if abs(tempA - target) < abs(tempB - target):
return tempA
else:
return tempB

总结:看了答案以后,最直观的还是根据 BST 性质二分查找;除此之外还有递归(回溯),迭代 / stack / todo 中序遍历(还要维护一个最小值),多种写法。直观写法需要注意:1.ans 赋值的条件;2.root 往哪边走的条件。 递归(回溯)写法要注意:1.返回的条件放的位置(在决定往哪边走之后);递归完之后还要判断最后返回哪个值

LinC 11.Search Range in Binary Search Tree (Medium)

1
2
3
4
5
6
7
8
9
10
Given a binary search tree and a range [k1, k2], return all elements in the given range.

Example
If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].

20
/ \
8 22
/ \
4 12

思路:inorder traversal 的话出来的是从小到大,把符合 k1, k2 条件的返回就行了。 至于 DFS 没啥思路。看看 inorder traversal 的 DFS

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
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
# first attempt DFS
class Solution:
"""
@param root: param root: The root of the binary search tree
@param k1: An integer
@param k2: An integer
@return: return: Return all keys that k1<=key<=k2 in ascending order
"""
def searchRange(self, root, k1, k2):
# write your code here
if not root:
return []
ans = []
self.dfs(root, k1, k2, ans)
return ans
def dfs(self, root, k1, k2, ans):
if not root:
return
self.dfs(root.left, k1, k2, ans)
if root.val <= k2 and root.val >= k1:
ans.append(root.val)
self.dfs(root.right, k1, k2, ans)

总结:放个测试数据就能写对。其实是 inorder :’(… BST inorder 是从小到大。。。哎。。。这么基本的问题,好伤。。。 todo 二刷用非递归

Combination based DFS - 基于组合的深度优先搜索

78. Subsets (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

思路:不太擅长组合和排列的题。这道题确实更像排列题,子集全排。DFS 模板:1.遍历输入元素;2.将当前元素加入 path;3。遍历递归当前元素之后的元素 i + 1;4:剪枝,将最后一个元素从 path 中去掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
ans = []
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.ans = []
self.dfs([], 0, nums)
return self.ans
def dfs(self, path, index, nums):
self.ans.append(path[:])
for innerIndex in range(index, len(nums)):
path.append(nums[innerIndex])
self.dfs(path, innerIndex + 1, nums)
path.pop()

总结:在 dfs 里,往 self.ans 添加答案的时候需要用 deep copy,不然的话会发生 self.ans 里面全是空的状况(感觉是因为最后剪枝的原因)。时间复杂度为 O(n*2^n) 指数级时间, 因为产生 2^n 个子 list,每个 list 的长度是 n 级的
二刷:这类 combination 的题要用 start,遍历递归时递归 i + 1 元素; 模板不直接遍历元素了, 下一题 permutation 三刷把代码改成模板,就没有 confusion 了。

39. Combination Sum (Medium)

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
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:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

思路:看了下答案,DFS 模板搞定,和上一题的区别是允许重复使用一个数, 把入递归的时候 innerIndex + 1 改为 innerIndex 就行了。答案说需要排序, 我想先试试看不排序会出什么样的错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.ans = []
if len(candidates) == 0:
return self.ans
self.dfs(candidates, target, [], 0)
return self.ans
def dfs(self, candidates, target, path, index):
if target < 0:
return
if target == 0:
self.ans.append(path[:])
return
for innerIndex in range(index, len(candidates)):
path.append(candidates[innerIndex])
self.dfs(candidates, target - candidates[innerIndex], path, innerIndex)
path.pop()

总结:注意不要在进入递归前改变 target, 因为 target 在后面几次循环中还需要使用。不需要把 input list 排序也能 AC,欧耶。

40. Combination Sum II (Medium)

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

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:

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

思路:第一反应感觉跟上题比只差个进递归的 innerIndex 和 innerIndex + 1 的区别,可能写了才知道坑在哪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
self.ans = []
if len(candidates) == 0:
return self.ans
self.dfs(sorted(candidates), target, [], 0)
return self.ans
def dfs(self, candidates, target, path, index):
if target < 0:
return
if target == 0 and path not in self.ans:
self.ans.append(path[:])
for innerIndex in range(index, len(candidates)):
path.append(candidates[innerIndex])
self.dfs(candidates, target - candidates[innerIndex], path, innerIndex + 1)
path.pop()

总结:没他大问题, 注意:1.这时就需要 sort 了, 因为要 append 到 self.ans 的时候要去重
二刷:去重容易钻到 if i and candidates[i] == candidates[i - 1]: continue 这个坑里, 这题注意用 if target == 0 and path not in ans: 来去重

216. Combination Sum III (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

思路:纯凭感觉写的,有前面两题做铺垫,这题可以直接写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
if k == 0:
return []
ans = []
self.dfs(k, n, [], 1, ans)
return ans
def dfs(self, k, n, path, start, ans):
if len(path) == k:
if sum(path) == n:
ans.append(path[:])
return
for i in range(start, 10):
path.append(i)
self.dfs(k, n, path, i + 1, ans)
path.pop()

总结:基本一次写对,注意 append(path[:]) 要 deep copy

131. Palindrome Partitioning (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

思路:看了下答案, 唯一不太好懂的地方是 start >= len(s) 才入 self.ans, 写好以后用测试数据看看为什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
self.ans = []
if len(s) == 0:
return self.ans
self.dfs(s, [], 0)
return self.ans
def dfs(self, s, path, start):
if start >= len(s):
self.ans.append(path[:])
return
for index in range(start, len(s)):
subS = s[start:index + 1]
if self.isPalindrome(subS):
path.append(subS)
self.dfs(s, path, index + 1)
path.pop()
def isPalindrome(self, s):
return s == s[::-1]

总结:注意:1.subStr[0:1] 返回第一个 char,[0:2] 返回 [0][1] 位置的 subStr;2.python 检查 palindrom 可以用 s == s[::-1];3.self.ans.append(path[:]) 以后记得 return; 4.range(start, len(s)) 可以通过测试数据纠正。之所以用 start >= len(s) 是因为要把 s 拆完一遍才能入 self.ans

93. Restore IP Addresses (Medium)

1
2
3
4
5
6
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

思路:从上面的 131. Palindrome Partitioning (Medium) 和 LinC 680. Split String (Easy) 获得了灵感

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:
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
if len(s) > 12 or len(s) < 4:
return []
ans = []
self.dfs(s, '', 0, ans)
return ans
def dfs(self, s, path, start, ans):
if path.count('.') > 4:
return
if len(path) == len(s) + 4:
ans.append(path[:-1])
return
for i in range(start, len(s)):
if self.isValid(s[start:i + 1]):
path += s[start:i + 1] + '.'
self.dfs(s, path, i + 1, ans)
path = path[:-(i + 2 - start)]
def isValid(self, s):
if len(s) > 3:
return False
if len(s) > 1 and s[0] == '0':
return False
return int(s) >= 0 and int(s) <= 255

总结:很多细节:1. start 跟着 i 走,没有前进;2. 遍历字符串取子串的时候要 range(, len + 1), 不然会取不到最后一个字符
不算二刷,以上注意的第 2 点可以简化为取 s[start:i + 1]; 从 131. Palindrome Partitioning (Medium) 学的。

LinC 680. Split String (Easy)

1
2
3
4
5
Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possible results.

Example
Given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]

思路:看了下答案,主要的文章就在递归退出的条件和 DFS 中 for 循环的起始条件。边写边想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
"""
@param: : a string to be split
@return: all possible split string array
"""

def splitString(self, s):
# write your code here
if len(s) == 0:
return [[]]
self.ans = []
self.dfs(s, [], 0)
return self.ans
def dfs(self, s, path, start):
if start >= len(s):
self.ans.append(path[:])
return
for index in range(start, start + 2):
if index < len(s):
path.append(s[start:index + 1])
self.dfs(s, path, index + 1)
path.pop()

总结:空输入的输出有点 wacky,for 循环内注意查越界(可以通过测试一个数据实现)

77. Combinations (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

思路:和 combination sum I, II 类似, 但是又有点不同:没有重复输入, 同一个数不能用两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
if k == 0:
return []
ans = []
self.dfs(n, k, [], 0, ans)
return ans
def dfs(self, n, k, path, start, ans):
if len(path) == k:
ans.append(path[:])
return
for i in range(start, n):
path.append(i + 1)
self.dfs(n, k, path, i + 1, ans)
path.pop()

总结:注意 dfs 中需要 start; dfs 内循环需要 for i in range(start, n); 调用 dfs 时, start 参数为 i + 1 来实现同一个数不用两次。

90. Subsets II (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

思路:经典 subset 的延伸,允许 input 中有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
ans = []
nums.sort()
self.dfs(nums, [], 0, ans)
return ans
def dfs(self, nums, path, start, ans):
if path not in ans:
ans.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
self.dfs(nums, path, i + 1, ans)
path.pop()

总结:permutation 要记 visited, permutation 有 dup 的要 i and nums[i] == nums[i - 1] and visited…: continue 避免重复的元素被重复选为起始元素。subset / combination 去重用的 not in ans。注意:not in ans: ans.append 以后不能 return!, 否则会导致递归在此退出,因为这是 dfs 递归进来无条件做的第一件事。input 要 sort,不然如:[4,4,4,4,4,1,4,4] 这种情况会出错,因为需要产生的是 set, 顺序不重要。

Permutation based DFS - 基于排列的深度优先搜索

46. Permutations (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,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
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
ans = []
self.visited = {}
for i in range(len(nums)):
self.visited[i] = False
self.dfs(nums, [], ans)
return ans
def dfs(self, nums, path, ans):
if len(path) == len(nums):
ans.append(path[:])
return
for i in range(len(nums)):
if self.visited[i]:
continue
path.append(nums[i])
self.visited[i] = True
self.dfs(nums, path, ans)
path.pop()
self.visited[i] = False

总结:思路 OK 的话貌似没有什么明显的坑
二刷:和 subset 和 combination sum 不同点在于排列进入 dfs 不需要 start 这个参数; 记得要有 self.visited, 存 path 的时候要 deep copy
三刷:遍历进递归的循环走 i, 和其他 DFS 模板保持一致。这题可以通过 if self.visited[i]: continue 来记需要一个 self.visited

47. Permutations II (Medium)

1
2
3
4
5
6
7
8
9
10
11
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

思路:看了下答案,比上一题要多处理的两件事:1.要排序;2.对于相同的数在 for 循环里跳过;此处 for 循环要用 index 了因为有重复的数,要用 dict 统计该位置是否被用过

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
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.ans = []
if len(nums) == 0:
return self.ans
self.visited = {}
for i in range(len(nums)):
self.visited[i] = False
self.dfs(sorted(nums), [])
return self.ans
def dfs(self, nums, path):
if len(path) == len(nums):
self.ans.append(path[:])
return
for i in range(len(nums)):
if not self.visited[i]:
if i > 0 and nums[i] == nums[i - 1] and not self.visited[i - 1]:
continue
path.append(nums[i])
self.visited[i] = True
self.dfs(nums, path)
path.pop()
self.visited[i] = False

总结:注意相同数的跳过方法,需要用 if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1] i.e. 如果相等,需要前面的已经用过了才能用(相等且 i - 1 用过了就 continue,就是说这个重复的数是给前面的轮次在用)
二刷:和 combination sum II 的类似之处是 input 都可能有重复的元素。 和 permutation 类似之处是也需要 visited 记录已使用的元素。不同是 iterate 的时候要用 i, 还要 i == i - 1 and visited[i - 1] == False 来去重; dfs 里 iterate 的时候记得 if not self.visited;要细心,…and visited[i - 1] == false

LinC 862. Next Closest Time (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example:
Given time = "19:34", return "19:39".
Explanation:
The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.

Given time = "23:59", return "22:22".
Explanation:
The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

思路:属于对我来说现场想很费时的题。直接看答案找思路

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
40
class Solution:
"""
@param time: the given time
@return: the next closest time
"""
def nextClosestTime(self, time):
# write your code here
s = set(time)
if len(s) == 2:
return time
digits = time[0:2] + time[3:5]
self.ans = ''
self.minDiff = sys.maxsize
self.target = int(time[0:2]) * 60 + int(time[3:5])
self.dfs(digits, '', 0)
return self.ans
def dfs(self, digits, path, start):
if start == 4:
# path 产生了一个合法的时间,判断和 target 距离 diff 和 self.minDiff 的关系
m = int(path[0:2]) * 60 + int(path[2:4])
diff = m - self.target
if diff == 0:
return
if diff < 0:
diff = 24 * 60 + diff
if diff < self.minDiff:
self.minDiff = diff
self.ans = path[0:2] + ':' + path[2:4]
return
for digit in digits:
# 处理 path, 把不合适的时间都 continue 过去, 但是怎么判断现在处理的是哪个位置?看了下答案, 其实不需要 enumerate
if start == 0 and int(digit) > 2:
continue
if start == 1 and int(path) * 10 + int(digit) > 23:
continue
if start == 2 and int(digit) > 5:
continue
if start == 3 and int(path[2:3]) * 10 + int(digit) > 59:
continue
self.dfs(digits, path + digit, start + 1)

总结:python3 把 sys.maxint 改成 sys.maxsize 了。要一次对的话,很多取数的细节需要留心。1.input time 要取 [0:2] [3:5] 来跳过 ‘:’; 2.diff 是负数的时候要用 24 * 60 + diff(而不是 -);3.for 循环里面的 digit 记得包上 int()

22. Generate Parentheses (Medium)

1
2
3
4
5
6
7
8
9
10
11
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路:既然是 backtracking / permutation based dfs 的题,先看看套路。有两个可能的路径, 第一种是:先 n 对括号的全排列,然后留 valid;第二种是:直接从 n 对括号里拼 valid 的排列,先试试第一种, 比较直观好理解。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n == 0:
return []
s = '(' * n + ')' * n
self.visited = {}
for i in range(n * 2):
self.visited[i] = False
self.ans = []
self.dfs(s, '')
return self.ans
def dfs(self, s, path):
if len(path) == len(s):
if self.isValid(path):
self.ans.append(path)
return
for i in range(len(s)):
if i and s[i] == s[i - 1] and not self.visited[i - 1]:
continue
self.visited[i] = True
path += s[i]
self.dfs(s, path)
path = path[:-1]
self.visited[i] = False
def isValid(self, path):
if path[0] == ')':
return False
stack = []
for paren in path:
if paren == '(':
stack.append(paren)
if paren == ')':
if stack:
stack.pop()
else:
return False
return len(stack) == 0

# 二刷,稍微妖一点的 DFS 解法
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n == 0:
return []
ans =[]
self.dfs(n, n, '', ans)
return ans
def dfs(self, left, right, path, ans):
if left == 0 and right == 0:
ans.append(path)
return
if left > 0:
self.dfs(left - 1, right, path + '(', ans)
if right > 0 and left < right:
self.dfs(left, right - 1, path + ')', ans)

总结:还挺佩服我自己的,调试下居然能过。。。虽然效率及其低下。。。立刻二刷吧。。。
二刷没什么好说的,left < right ( 比 ) 数量多就 paren 就 valid。

Graph based DFS 基于图的深度优先搜索

17. Letter Combinations of a Phone Number (Medium)

1
2
3
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

keypad example

1
2
3
4
5
6
7
Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

思路:看着像 DFS,但是没有特别具体的思路,看答案。看了下三年前写的代码,还挺牛逼的。。。

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
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
self.ans = []
if len(digits) == 0:
return self.ans
self.mapping = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
self.dfs(digits, '', 0)
return self.ans
def dfs(self, digits, path, start):
if start == len(digits):
self.ans.append(path)
return
for letter in self.mapping[digits[start]]:
self.dfs(digits, path + letter, start + 1)

总结:只能说三年前写的还挺牛逼的。。。

79. Word Search (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

思路:知道是 DFS 以后超级明显的一道题,两年多前居然写过。。。

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
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
for row in range(0, len(board)):
for col in range(0, len(board[0])):
if self.dfs(board, row, col, word, 0):
return True
return False
def dfs(self, board, row, col, word, start):
if start == len(word):
return True
if row < 0 or row > len(board) - 1:
return False
if col < 0 or col > len(board[0]) - 1:
return False
if board[row][col] != word[start]:
return False
board[row][col] = '#'
# up
if self.dfs(board, row - 1, col, word, start + 1):
return True
# down
if self.dfs(board, row + 1, col, word, start + 1):
return True
# left
if self.dfs(board, row, col - 1, word, start + 1):
return True
# right
if self.dfs(board, row, col + 1, word, start + 1):
return True
board[row][col] = word[start]
return False

总结:已经决定了不喜欢 x, y 千万不要动摇,row, col 到底。注意越界判断的时候要用 len(board) - 1 和 len(board[0]) - 1 而非 word。这次用了新写法,比两年多前的版本少了大约 10 行左右代码。

数据结构

Binary Tree & Divide Conquer 二叉树与分治

110. Balanced Binary Tree (Easy)

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
Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

3
/ \
9 20
/ \
15 7
Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.

思路:没什么思路,但是这种左右子树都得符合某种条件的题型感觉得用分治

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

class ResultType:
def __init__(self, balanced, maxDepth):
self.isBalanced = balanced
self.maxDepth = maxDepth

class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.helper(root).isBalanced
def helper(self, root):
if not root:
return ResultType(True, 0)
left = self.helper(root.left)
right = self.helper(root.right)

if not left.isBalanced or not right.isBalanced:
return ResultType(False, -1)
if abs(left.maxDepth - right.maxDepth) > 1:
return ResultType(False, -1)
return ResultType(True, max(left.maxDepth, right.maxDepth) + 1)

总结:加了 ResultType(isBalanced, maxDepth),就好办很多, 记住递归 helper 函数最后一句;return ResultType(True, max(left.maxDepth, right.maxDepth) + 1)

114. Flatten Binary Tree to Linked List (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:

1
\
2
\
3
\
4
\
5
\
6

思路:看着像典型的 DFS,不知道有什么坑,直接写吧
二刷:网上比较靠谱的思路,先把左右子树flattern了, 再把root的右接左子树, 左子树的最后接右子树
114graph

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(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if root == None:
return
self.flatten(root.left)
self.flatten(root.right)
if root.left == None:
return
p = root.left
while p.right:
p = p.right
p.right = root.right
root.right = root.left
root.left = None

总结:基本靠套路。1.None 既 return,左右到底, 左边为空既 return 2. 到左边一个,往右到底, 套路:p.right = root.right; root.right = root.left; root.left = null i.e.:将 root 右边接到 p(尾巴上), root 右节点变为 root 左节点, root 左节点置空

Stack 栈

20. Valid Parentheses (Easy)

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
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true

思路:stack 题,open 的就入栈,close 的就出栈,对不上就 return false,栈空就 true

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(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if len(s) == 0:
return True
if len(s) % 2 != 0:
return False
mapping = {'(': ')', '{': '}', '[': ']'}
stack = []
stack.append(s[0])
cur = 1
while stack:
if cur > len(s) - 1:
return False
if s[cur] in mapping.keys():
stack.append(s[cur])
cur += 1
else:
tmp = stack.pop()
if tmp not in mapping:
return False
if s[cur] != mapping[tmp]:
return False
cur += 1
return True

总结:注意一开始就是 ), },] 这类的,会被初始化到 stack 里,需要加判断 tmp not in mapping: false

Queue 队列

LinC 642. Moving Average from Data Stream (Easy)

1
2
3
4
5
6
7
8
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example
MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // return 1.00000
m.next(10) = (1 + 10) / 2 // return 5.50000
m.next(3) = (1 + 10 + 3) / 3 // return 4.66667
m.next(5) = (10 + 3 + 5) / 3 // return 6.00000

思路:建个 window size 的队列,返回队列的平均值

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
class MovingAverage:
q = collections.deque()
sum = 0
maxLen = 0
"""
@param: size: An integer
"""
def __init__(self, size):
# do intialization if necessary
self.maxLen = size
"""
@param: val: An integer
@return:
"""
def next(self, val):
# write your code here
self.q.append(val)
self.sum += val
if len(self.q) > self.maxLen:
temp = self.q.popleft()
self.sum -= temp
avg = self.sum / len(self.q)
return avg

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param = obj.next(val)

总结:注意 class 变量要加 self,另外 sum 不要每次都 loop 一遍算, 直接放到 class 变量里,每次只增 and / or 减一次。

Hash 哈希表

290. Word Pattern (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

思路:关键在于懂得建立 pattern 里每个字母和 str 里每个 word 的映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
words = str.split(' ')
if len(words) != len(pattern):
return False
mapping = {}
for i, char in enumerate(pattern):
if char in mapping:
if mapping[char] != words[i]:
return False
else:
if words[i] in mapping.values():
return False
mapping[char] = words[i]
return True

总结:注意需要用 enumerate, 因为要同时遍历 pattern 和 str. 很好的哈希表热身题。Word Pattern II 的 str 里没有空格了,不能直接 split,难度直接推到 Hard。目前刷题的水平先跳过吧 :(

387. First Unique Character in a String (Easy)

1
2
3
4
5
6
7
8
9
10
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.

思路:过两遍,第一遍数出现多少次, 第二遍把第一个为 1 的 index 返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return -1
if len(s) == 1:
return 0
dict = {}
for char in s:
if char not in dict:
dict[char] = 1
else:
dict[char] += 1
for index, char in enumerate(s):
if dict[char] == 1:
return index
return -1

总结:基本题,注意 dict entry 初始化为 1 的情况

409. Longest Palindrome (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

思路:得知道每个字母出现的次数,每出现两次就放两边(长度加 2),最后用一个变量记单数的个数,> 0 就长度加 1,O(n); 写到一半发现这题更适合放 hashmap,先写了再看双指针写法。
二刷 DP: f 为该位置能组最长回文的长度;f[0] = 1, f[1] = 2 if f[1] 有偶数个 else f[1] = f[0], f[2] = f[1] + 2 if s[i] 有偶数个 else f[2] = f[1], else f[1], f[3] = f[2] + f[i] = f[i - 1] + 2 if s[i] 能和 s[0, i - 1] 形成回文, else f[i - 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) <= 1:
return len(s)
singleCounter = 0
hashMap = {}
ans = 0
for char in s:
if char not in hashMap:
hashMap[char] = 1
singleCounter += 1
else:
hashMap[char] += 1
if hashMap[char] % 2 == 0:
singleCounter -= 1
ans += 2
else:
singleCounter += 1
if singleCounter > 0:
ans += 1
return ans

# 二刷 DP
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
if n <= 1:
return n
f = [0] * n
hashmap = {}
for i in range(n):
if s[i] in hashmap:
hashmap[s[i]] += 1
if hashmap[s[i]] % 2 == 0:
f[i] = f[i - 1] + 2
else:
f[i] = f[i - 1]
else:
hashmap[s[i]] = 1
f[i] = f[i - 1]
for value in hashmap.values():
if value % 2 != 0:
return f[n - 1] + 1
return f[n - 1]

总结:hashmap 没毛病,看看双指针答案。靠,九章答案根本就不是双指针。hashmap 题
二刷:注意 f[i] = f[i - 1] + 1 或 f[i - 1] 不要搞错; 第一感觉是有问题的, 拿 ‘abc’, ‘abb’, ‘bbb’,就能测出来,需要用 f[i] = f[i - 1] + 2 如果是偶数个 else f[i] = f[i - 1], 初始都是 0, 返回的时候过一遍 map, 如果有单数的,返回 f[n - 1] + 1. 不然返回 f[n - 1]; 还要注意 s[i] 在不在 map 里,f[i] 都要 = f[i - 1](在 map 里有两种情况)

380. Insert Delete GetRandom O(1) (Medium)

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
Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

思路:看答案知道需要用 list 和 dictionary,因为要满足 O(1), 因为仅有 list 的 in 操作不能满足 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class RandomizedSet(object):

def __init__(self):
"""
Initialize your data structure here.
"""
self.list = []
self.dict = {}

def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val in self.dict:
return False
else:
self.list.append(val)
self.dict[val] = len(self.list) - 1
return True

def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val in self.dict:
index, lastVal = self.dict[val], self.list[len(self.list) - 1]
self.list[index], self.dict[lastVal] = lastVal, index
self.list.pop()
self.dict.pop(val)
return True
else:
return False

def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
return self.list[random.randint(0, len(self.list) - 1)]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

总结:可能是用 python 的原因,搞明白问什么了一次过

LinC 960. First Unique Number in a Stream II (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
Description
We need to implement a data structure named DataStream. There are two methods required to be implemented:

void add(number) // add a new number
int firstUnique() // return first unique number
You can assume that there must be at least one unique number in the stream when calling the firstUnique.

Example
add(1)
add(2)
firstUnique() => 1
add(1)
firstUnique() => 2

思路:维持一个 deque / queue,碰到相同的就 popleft 出去

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 DataStream:

def __init__():
# do intialization if necessary
self.q = collections.deque()
self.dict = {}
"""
@param num: next number in stream
@return: nothing
"""
def add(self, num):
# write your code here
if num in self.dict:
self.dict[num] += 1
else:
self.dict[num] = 1
self.q.append(num)
"""
@return: the first unique number in stream
"""
def firstUnique(self):
# write your code here
while len(self.q) > 0 and self.dict[self.q[0]] > 1:
self.q.popleft()
return self.q[0]

总结:1.popleft 要在 firstUnique 里面,不然有些 testcase 过不了;2.注意 popleft 的条件要用 while, 用 for 会出错

Heap (Priority Queue)

264. Ugly Number II (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

思路:九章的 python 答案可以 work,但是实在是不好理解。写个好理解一点的版本。heapq 和 hashMap, 从 heapq 中取 n - 1 次(第一个数为 1),每取一次将原始 ugly numbers 2, 3, 5 过一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
primes = [2, 3, 5]
q = [2, 3, 5]
hashMap = {}
for i in range(3):
hashMap[q[i]] = True
import heapq
heapq.heapify(q)
ans = 1
for i in range(n - 1):
ans = heapq.heappop(q)
for j in range(3):
new_val = ans * primes[j]
if new_val not in hashMap:
heapq.heappush(q, new_val)
hashMap[new_val] = True
return ans

总结:可以 AC,也可以理解,good enough

LinC 612. K Closest Points (Medium)

1
2
3
4
5
6
Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin.
Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.

Example
Given points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
return [[1,1],[2,5],[4,4]]

思路:看了下答案,比较可理解的方法是用一个 heapq 存 distance 的 2 的负值,这样 > K 以后就开始 pop(最小值就是最远的点), 所有点过完一遍以后将 heapq 里的点都 pop 出来然后 reverse 就是从小到大的顺序了,需要写一个 class PointDis 里面有 initlt 正常写。 getDis() 返回 distance 的 2 负值

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
40
41
42
43
44
45
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = bDefinition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
class PointDis:
def __init__(self, dist, point):
self.dist = dist
self.point = point
def __lt__(self, other):
if self.dist != other.dist:
return self.dist < other.dist
if self.point.x != other.point.x:
return self.point.x > other.point.x
return self.point.y > other.point.y
class Solution:
"""
@param points: a list of points
@param origin: a point
@param k: An integer
@return: the k closest points
"""
def kClosest(self, points, origin, k):
# write your code here
q = []
import heapq
heapq.heapify(q)
for point in points:
negD2 = self.getNegDis2(point, origin)
heapq.heappush(q, PointDis(negD2, point))
if len(q) > k:
heapq.heappop(q)
ans = []
for i in range(k):
ans.append(heapq.heappop(q).point)
ans.reverse()
return ans
def getNegDis2(self, point, origin):
return - (point.x - origin.x) ** 2 - (point.y - origin.y) **2

总结:有个地方要注意, 当 dist 用的是距离平方的负数来比较产生 max heap 的时候,如果距离相等时比 x 和 x 相等时比 y 的 < 符号就要反过来了。 看着还是很别扭的。 name dist 用距离平方的负数还不如就直接用距离的平方然后把 PointDis class 里比方向距离的 < 符号反一下。不过已经 AC 了就不改了。

LinC 545. Top k Largest Numbers II (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Implement a data structure, provide two interfaces:
add(number). Add a new number in the data structure.
topk(). Return the top k largest numbers in this data structure. k is given when we create the data structure.

Example
s = new Solution(3);
>> create a new data structure.
s.add(3)
s.add(10)
s.topk()
>> return [10, 3]
s.add(1000)
s.add(-99)
s.topk()
>> return [1000, 10, 3]
s.add(4)
s.topk()
>> return [1000, 10, 4]
s.add(100)
s.topk()
>> return [1000, 100, 10]

思路:看着是非常直观的 min heap 问题。。。

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:
"""
@param: k: An integer
"""
def __init__(self, k):
# do intialization if necessary
self.k = k
self.q = []
"""
@param: num: Number to be added
@return: nothing
"""
def add(self, num):
# write your code here
import heapq
heapq.heappush(self.q, num)
if len(self.q) > self.k:
heapq.heappop(self.q)
"""
@return: Top k element
"""
def topk(self):
# write your code here
return sorted(self.q, reverse = True)

总结:一句 sorted(self.q, reverse = True) 完爆。。。哎, python 的 buit-in function 返回一个 sorted new list…学习了。

LinC 486. Merge K Sorted Arrays (Medium)

Array 数组

LinC 6. Merge Two Sorted Arrays (Easy)

1
2
3
4
5
6
7
8
9
10
11
Merge two given sorted integer array A and B into a new sorted integer array.

Example
A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge
How can you optimize your algorithm if one array is very large and the other is very small?

思路:热身题,直接做

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
class Solution:
"""
@param A: sorted integer array A
@param B: sorted integer array B
@return: A new sorted integer array
"""
def mergeSortedArray(self, A, B):
# write your code here
ans = []
indexA = 0
indexB = 0
indexC = 0
while indexC < len(A) + len(B):
if indexA == len(A) or indexB == len(B):
if indexA == len(A):
ans.append(B[indexB])
indexB += 1
else:
ans.append(A[indexA])
indexA += 1
else:
if A[indexA] < B[indexB]:
ans.append(A[indexA])
indexA += 1
else:
ans.append(B[indexB])
indexB += 1
indexC += 1
return ans

总结:非常值得刷的一道热身题, 需要考虑两个 array 越界的问题。看了下答案用三个 while 循环也可以。

88. Merge Sorted Array (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

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

思路:直觉上想不太出来怎么不创建新的存储空间把小数组 merge 到大数组里。看了答案,如果 nums1 后面空着这么些空,就从后面开始填。哎,曾经是能自主想的出的。。。正着困难的话就反着试试

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
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
if len(nums2) == 0:
return
if len(nums1) == len(nums2):
for i in range(len(nums2)):
nums1[i] = nums2[i]
return
index1 = m - 1
index2 = n - 1
index3 = len(nums1) - 1
while index3 >= 0 and index2 >= 0:
if index1 < 0:
nums1[index3] = nums2[index2]
index2 -= 1
else:
if nums1[index1] < nums2[index2]:
nums1[index3] = nums2[index2]
index2 -= 1
else:
nums1[index3] = nums1[index1]
index1 -= 1
index3 -= 1

总结:虽然是 easy 题,要考虑情况:1.nums1 和 nums2 一样大的话需要逐个考过去;2.index2 如果走到最前面就可以结束了。注意题目的输入包含了 m 和 n 要利用好

LinC 839. Merge Two Sorted Interval Lists (Easy)

1
2
3
4
5
6
Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.

The intervals in the given list do not overlap.
The intervals in different lists may overlap.
Example
Given list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)], return [(1,4),(5,6)].

思路:非常不擅长的提醒,todo 需要寻找并练习这类题。看了答案以后明白 merge 函数只需要判断 res 的最后一个区间的 end 是否 >= 被 merge interval 的 start, 是的话就将该 end 设为 max(该 end, interval 的 end), 否的话直接 res.append(interval)

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
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""

class Solution:
"""
@param list1: one of the given list
@param list2: another list
@return: the new sorted list of interval
"""
def mergeTwoInterval(self, list1, list2):
# write your code here
index1, index2 = 0, 0
ans = []
while index1 < len(list1) or index2 < len(list2):
if index1 == len(list1):
self.merge(ans, list2[index2])
index2 += 1
elif index2 == len(list2):
self.merge(ans, list1[index1])
index1 += 1
elif list1[index1].start < list2[index2].start:
self.merge(ans, list1[index1])
index1 += 1
else:
self.merge(ans, list2[index2])
index2 += 1
return ans
def merge(self, ans, interval):
if not ans:
ans.append(interval)
elif ans[-1].end >= interval.start:
ans[-1].end = max(ans[-1].end, interval.end)
else:
ans.append(interval)

总结:懂的将早开始的先送进 ans,merge 的时候只需要判断 ans 最后一个的 end 是否 >= interval.start 这个核心算法比较重要。

LinC 486. Merge K Sorted Arrays (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Given k sorted integer arrays, merge them into one sorted array.

Example
Given 3 sorted arrays:

[
[1, 3, 5, 7],
[2, 4, 6],
[0, 8, 9, 10, 11]
]
return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

Challenge
Do it in O(N log k).

N is the total number of integers.
k is the number of arrays.

思路:看答案,用 heap 屌爆了。加了链接到上面 heap 的部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
"""
@param arrays: k sorted integer arrays
@return: a sorted array
"""
def mergekSortedArrays(self, arrays):
# write your code here
import heapq
q = []
for level, array in enumerate(arrays):
if len(array) == 0:
continue
heapq.heappush(q, (array[0], level, 0))
ans = []
while q:
cur, level, index = heapq.heappop(q)
ans.append(cur)
if index + 1 < len(arrays[level]):
heapq.heappush(q, (arrays[level][index + 1], level, index + 1))
return ans

总结:只能说 python 的 heapq 屌爆了

121. Best Time to Buy and Sell Stock (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

思路:寻找左边值比右边值小的最大的差值,感觉是双指针问题,看了九章的答案,比较不直观
二刷:DP, f 为目前为止的最大收益,f[i] = f[i - 1] 如果 f[i] < f[i - 1] else: f[i] = prices[i] - lowest, 初始均为 0, lowest 初始为 f[0], 遍历最后更新 lowest

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
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
low, ans = sys.maxint, 0
for price in prices:
if price < low:
low = price
if price - low > ans:
ans = price - low
return ans

# 二刷 DP
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) <= 1:
return 0
f = []
n = len(prices)
for i in range(n):
f.append(0)
lowest = prices[0]
for i in range(1, n):
if prices[i] < prices[i - 1]:
f[i] = f[i - 1]
else:
f[i] = max(prices[i] - lowest, f[i - 1])
lowest = min(lowest, prices[i])
return f[n - 1]

总结:不能 sort 这个数组,双指针好像也不太好使。看了答案得用比较土的办法 sys.maxint; 或者用 dp;dp 单独找个时间再刷吧
二刷:看来还是要保存最低点,返回 f[n - 1], 注意:1. 检查输入为空;2. 计算 f[i] 时要判断 prices[i] 和 prices[i - 1] 的关系

Trie

208. Implement Trie (Prefix Tree) (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

思路:没啥思路,看答案

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
40
41
42
43
44
45
46
47
48
49
50
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.word=False
self.children={}

class Trie:

def __init__(self):
self.root = TrieNode()

# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
node=self.root
for i in word:
if i not in node.children:
node.children[i]=TrieNode()
node=node.children[i]
node.word=True

# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
node=self.root
for i in word:
if i not in node.children:
return False
node=node.children[i]
return node.word

# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
node=self.root
for i in prefix:
if i not in node.children:
return False
node=node.children[i]
return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

总结:1.需要加 TrieNode 2. Leetcode 的 python3 找不到 class 是个 bug

Bit Manipulation

231. Power of Two (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true
Explanation: 2^0 = 1
Example 2:

Input: 16
Output: true
Explanation: 2^4 = 16
Example 3:

Input: 218
Output: false

思路:既然是 bit manipulation 的题,肯定是变成 bits 操作,稍微看一下 2 的倍数都是 1 后面全是 0。怎么用 python 检查这个比较没思路。。。

1
2
3
4
5
6
7
8
9
class Solution:
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
if n == 1:
return True
return bin(n)[2:] == '1'.ljust(len(bin(n)) - 2, '0')

总结:看了三年前比较屌的 trick 是 return n & n - 1, 当然 bin 这种土办法也 OK 的。

DP Dynamic Programming 动态规划

题型多为: 1. 求最大值或者最小值 2. 判断方案是否可行 3. 统计方案的个数
DP 四要素:1. 状态 state,也就是f[i]或者f[i][j]的物理意义是什么 2. 方程 function,也就是f[i]和f[i - 1]的关系 3. 初始化 initialization,这个方程涉及2个相邻state所以对于state 0肯定是需要初始化的 4. 答案 最大的状态是什么?规划的重点是什么?

70. Climbing Stairs (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

思路:f[n] 是为 n 时的方案数,f[1] 是为 1 时的方案数 = 1。那么爬到第n层的方法要么是从第n-1层一步上来的,要不就是从n-2层2步上来的,所以递推公式非常容易的就得出了:f[n] = f[n - 1] + f[n - 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return n
f = [0] * (n + 1)
f[1] = 1
f[2] = 2
for i in range(3, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]

总结:和三年前比没有变化,呵呵呵

120. Triangle (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路:看了 top down 的 DP, 还是比较好理解的。f 代表到达 row 和 col 位置的最小 sum,f[i][j] 和 f[i - 1][j - 1] 的关系是:f[i][j] = mins(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]. 规划的目标是最后一行中的最小值。;DP 以外还有三种解法,DFS:Traverse, DFS:Divide and Conquer, DFS:Divide and Conquer 加 memorization todo 估计也不会刷 DFS 了, Divide and Conquer 有点可能性吧

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 minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
if len(triangle) == 0:
return 0
if len(triangle) == 1:
return triangle[0][0]
f = []
f.append([triangle[0][0]])
n = len(triangle)
for i in range(1, n):
f.append([0] * (i + 1))
for i in range(1, n):
f[i][0] = f[i - 1][0] + triangle[i][0]
f[i][i] = f[i - 1][i - 1] + triangle[i][i]
for row in range(2, n):
for col in range(1, row):
f[row][col] = min(f[row - 1][col - 1], f[row - 1][col]) + triangle[row][col]
ans = f[n - 1][0]
for i in range(1, n):
ans = min(ans, f[n - 1][i])
return ans

总结:填充 f 每行第一个和最后一个的时候别忘了 + triangle[i][0] 和 triangle[i][i]

409. Longest Palindrome (Easy)

121. Best Time to Buy and Sell Stock (Easy)

skipped

Binary Tree & Divide and Conquer 分治

九章曾经有个专题是这个,可以看一下,把常见的题型刷一刷。

98. Validate Binary Search Tree (Medium)

94. Binary Tree Inorder Traversal (Medium)

120. Triangle (Medium)

LinC 649. Binary Tree Upside Down (Medium)

Leetcode 156. Binary Tree Upside Down 加锁了。可能是我傻逼,也可能是题傻逼。浪费了很多时间,网上非递归的答案都不能 AC。一气之下给挪到 skipped 的部分了。 等有高人指导了再研究下。

DP Dynamic Programming 动态规划

Best Time to Buy and Sell Stock II & III

53. Maximum Subarray (Easy)

Minimum Path Sum

Jump Game

Longest Increasing Subsequence

Word Break

Longest Common Subsequence

44. Wildcard Matching (Hard)

也可以用 DFS, 双指针解

240. Search a 2D Matrix II (Medium)

LinC Search a 2D Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example:

Consider the following matrix:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.

思路:感觉还是 binary search 吧,虽然九章说是 two pointers

1
2
3
4
5
6
7
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""

Bit Manipulation

29. Divide Two Integers (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

思路:算法还是略妖的。先把除数位移放大到比被除数大,然后将这个数一步步位移缩小,并且用被除数的绝对值减这个数直到被除数的绝对值小于除数为止 ans += level

1
2
3
4
5
6
7
class Solution:
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""

总结:

Trie

211. Add and Search Word - Data structure design (Medium)

Trie 和 DFS 组合题

Two pointers

LinC Sort Colors II (medium)

快排:https://github.com/awangdev/LintCode/blob/master/Java/Sort%20Colors%20II.java 桶排:https://www.cnblogs.com/yuzhangcmu/p/4177326.html

Interleaving Positive and Negative Numbers (Medium)

Sort Letters by Case (Medium)

600. Smallest Rectangle Enclosing Black Pixels (Hard)

Heap

577. Merge K Sorted Interval Lists (Medium)

347. Top K Frequent Elements (Medium)

related:
http://www.lintcode.com/problem/top-k-largest-numbers/
http://www.lintcode.com/problem/kth-smallest-number-in-sorted-matrix/

23. Merge k Sorted Lists (Hard)

三种方法,都需要练习. 方法一:使用 PriorityQueue 方法二:类似归并排序的分治算法 方法三:自底向上的两两归并算法. 时间复杂度均为 O(NlogK) Strong Hire: 能够用至少2种方法进行实现,代码无大 BUG

Hash

349. Intersection of Two Arrays (Easy)

350. Intersection of Two Arrays II (Easy)

http://www.lintcode.com/problem/subarray-sum/
http://www.lintcode.com/problem/copy-list-with-random-pointer/
http://www.lintcode.com/problem/anagrams/
http://www.lintcode.com/problem/longest-consecutive-sequence/

146. LRU Cache (Hard)

九章的答案是单向列表,在 Hash 中存储 Singly List 中的 prev node,如 linked list = dummy->1->2->3->null 时 hash[1] = dummy, hash[2] = node1 …
双向链表要容易写一点

Combination DFS

九章:DFS算法的掌握,主要在练习; 一个题第一遍不顺利,就要写第二遍,第三遍; 像 Word Break II 纯 DFS 版本 和 Regular Expression Matching 这样的问题,要练到 30 分钟内在 LintCode 上 AC。做不到就反复再练。

LinC 90. k Sum II (Medium)

和 combination sum 类似的题

140. Word Break II (Hard)

Strong Hire: DFS+DP优化
Hire / Weak Hire: DFS 能写完,且 Bug free or Bug 不多,不需要提示 or 需要少量提示

44. Wildcard Matching (Hard)

10. Regular Expression Matching (Hard)

Permutation DFS

51. N-Queens (Hard)

还有 N-Queens II,问方案总数

31. Next Permutation (Medium)

答案很妖,没有用 DFS 模板。还有 Next Permutation II (Medium)

197. Permutation Index (Easy)

肯定不是 easy, 没有用 DFS 模板。还有 II:http://www.lintcode.com/problem/permutation-index-ii/

Graph DFS

212. Word Search II (Hard)

126. Word Ladder II (Hard)

Word Ladder 是 BFS,II 是 DFS

LinC 829. Word Pattern II (Hard)

做法和 Wildcard Match / Regular Expression Match 类似

DFS / backtracking 回溯

LinC 901. Closest Binary Search Tree Value II (Hard)

这个双栈答案看着比较优雅:http://www.cnblogs.com/grandyang/p/5247398.html O(logn + k) 时间复杂度 O(logn) 空间复杂度

postorder traversal (Hard) 后序遍历

104. Maximum Depth of Binary Tree (Easy)

非递归需要用 postorder traversal (Hard) 或者 http://www.cnblogs.com/grandyang/p/6058061.html

BFS

矩阵上的BFS LinC Build Post Office II (Hard)

LinC 892. Alien Dictionary (Hard)

LinC 7. Serialize and Deserialize Binary Tree (Medium)

Array

LinC 944. Maximum Submatrix (Medium)

某家 sb 公司的电面,只写出了最傻的方法。挂了。九章有比较优化的方法
我当时写的 sb 代码,没刷过的题电面现场想真的是作死。

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:
# arr: M x N matrix[][]
# return int largest sum of subArray

def maxSum(self, arr):
ans = []
for rowStart in range(len(arr)):
for colStart in range(len(arr[0])):
for rowEnd in range(rowStart, len(arr)):
for colEnd in range(colStart, len(arr[0])):
sum = 0
for i in range(rowStart, rowEnd + 1):
for j in range(colStart, colEnd + 1):
sum += arr[i][j]
ans.append(sum)
ans.sort()
print(ans)
return ans[-1]

s = Solution()
# -1 -1 -1
# -1 1 -1
# -1 -1 5
# O(n^3)
# dp[][] biggest at teach point
# O(n^2)
# return max(dp[][])
print(s.maxSum([[-1,-1,-1],[-1,-1,-1],[-1,-1,1]]))

57. Insert Interval (Hard)

8. String to Integer (atoi) (Medium)