1. Two Sum
考点
- 限制加和等于n。不要每一步都判断x+y=n，而是判断n-x=y
- 两次遍历。考虑不写2个for，而是1次遍历，把元素放到hashtable中
def twoSum(self, nums: List[int], target: int) -> List[int]:
tmp_dict = dict()
for i, j in enumerate(nums):
if j in tmp_dict:
return [tmp_dict[j], i]
tmp_dict[target - j] = i
2. Add Two Numbers
考点
- 对于链表，
curr.next指针向下走，这个不多说 curr1=curr1.next if curr1 else curr1这个操作，让遍历到尾部后，值保持curr1=None，好处是少些几行代码。作为配合，在其它行，可以用if curr1来判断是否到尾部- 链表还有个好处，如本例，
l3是含一个空的头的，返回l3.next即可
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry=0
l3=ListNode(None)
curr1,curr2,curr3=l1,l2,l3
while curr1 or curr2 or carry:
value=(curr1.val if curr1 else 0)+(curr2.val if curr2 else 0)+carry
carry,val=divmod(value,10)
curr3.next=ListNode(val)
curr1=curr1.next if curr1 else curr1
curr2=curr2.next if curr2 else curr2
curr3=curr3.next
return l3.next
3. Longest Substring Without Repeating Characters
考点：
- 2 sum 那道题里面写过，这种貌似需要两次遍历的题目。都可以想一下能不能用 hashTable 存下历史遍历，从而变成一次遍历。
def lengthOfLongestSubstring(self, s: str) -> int:
used = dict()
start = 0
res = 0
for i, c in enumerate(s):
if c in used and start <= used[c]:
start = used[c] + 1
else:
res = max(res, i - start + 1)
used[c] = i
return res
4. Median of Two Sorted Arrays
这个题目其实可以 cheat，俩列表加一起，然后用Python自代的sort，代码就不写了。
套路详解：https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation
考点：
- 中位数的定义：中位数两边的数量相等。
- 因此，num1 的分割和num2的分割存在一个恒等关系，len(left1)+len(left2)=len(right1)+len(right2)
- 这也就意味着，给定num1的分割，就立即能计算出num2的分割
- 本质上还是把两次遍历变成一次
- 如果if情况过多，考虑换一下两个变量，减少代码量。
(代码还是好难写，奇偶之类的)
def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0
5. Longest Palindromic Substring
没有套路。中间往外拓，平方级复杂度。
class Solution:
def helper(self, left, right):
while left >= 0 and right < len(self.s) and self.s[left] == self.s[right]:
left -= 1
right += 1
return left + 1, right - 1
def longestPalindrome(self, s: str) -> str:
self.s = s
left, right = 0, 0
for i in range(len(s)):
left1, right1 = self.helper(i, i)
left2, right2 = self.helper(i, i + 1)
if right1 - left1 > right - left:
left, right = left1, right1
if right2 - left2 > right - left:
left, right = left2, right2
return s[left:right + 1]
6. ZigZag Conversion
没有套路。按照ZigZag的字面意思，在s上做遍历。
（其实还可以先算出每个值所在的位置，不过有点儿费草稿纸）
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows==1 or (len(s)<numRows):
return s
res_list = [''] * numRows
location, direction = 0, -1 # 假想开头前面也迭代过程中，所以初始是负号
for i in s:
res_list[location] = res_list[location] + i
if location == 0 or location == numRows - 1:
direction = -direction
location += direction
return ''.join(res_list)
7. Reverse Integer
没有套路。
按位数颠倒一个整数。考虑负号和溢出。可以用字符串翻转作弊
int reverse(int x) {
long res=0;
while (x) {
res = res * 10 + x % 10;
x /= 10;
}
return res < INT32_MIN || res > INT32_MAX ? 0 : (int) res;
}
8. String to Integer (atoi)
实在无聊的题，就是各种边界条件。这题别做了，浪费时间。
# 3.13->3
# .1->0
# -+9->0
# -000123a123->-123
class Solution:
def get_num(self, sub_str):
res = []
for i in sub_str:
if i.isdigit():
res.append(i)
else:
break
if len(res) == 0:
return 0
return int(''.join(res))
def myAtoi(self, s: str) -> int:
s = s.lstrip()
if len(s) == 0:
return 0
if s[0] == '+':
res = self.get_num(s[1:])
elif s[0] == '-':
res = -self.get_num(s[1:])
else:
res = self.get_num(s)
if res < -2 ** 31:
return -2 ** 31
if res > 2 ** 31 - 1:
return 2 ** 31 - 1
return res
9. Palindrome Number
数字反转基本就这套路了
- 改进：跑一半就可以比较了
- python：
x_str == x_str[::-1]
pub fn is_palindrome(x: i32) -> bool {
if x < 10 && x >= 0 {
return true;
}
if x < 0 || x % 10 == 0 {
return false;
}
let mut num = 0;
let mut x = x;
while x > num {
num = num * 10 + x % 10;
x = x / 10;
}
if x == num || num / 10 == x {
return true;
}
false
}
10. Regular Expression Matching
好题！
套路：
- 递归（不是很容易想出）
- 递归的某些节点被反复调用。考虑存下来。（就是DP）
https://leetcode.com/problems/regular-expression-matching/solution/
class Solution:
def isMatch(self, s: str, p: str) -> bool:
len_s, len_p = len(s), len(p)
dp = [[None] * (len_p + 2) for _ in range(len_s + 2)]
def isMatch(i, j):
if j >= len_p:
return i >= len_s
if dp[i][j] is not None:
return dp[i][j]
first_match = (i < len_s) and p[j] in {s[i], '.'}
if len_p - j >= 2 and p[j + 1] == '*':
dp[i][j] = isMatch(i, j + 2) or (first_match and isMatch(i + 1, j))
return dp[i][j]
else:
dp[i][j] = first_match and isMatch(i + 1, j + 1)
return dp[i][j]
return isMatch(0, 0)
c版本
bool isMatch1(char *s, char *p, int len_s, int len_p, char dp[len_s + 2][len_p + 2], int i, int j) {
if (j >= len_p) {
return i >= len_s;
}
if (dp[i][j] != 2) {
return dp[i][j];
}
bool first_match = (i < len_s) && (p[j] == s[i] || p[j] == '.');
if (len_p - j >= 2 && p[j + 1] == '*') {
dp[i][j] = isMatch1(s, p, len_s, len_p, dp, i, j + 2) ||
(first_match && isMatch1(s, p, len_s, len_p, dp, i + 1, j));
return dp[i][j];
} else {
dp[i][j] = first_match && isMatch1(s, p, len_s, len_p, dp, i + 1, j + 1);
return dp[i][j];
}
}
11. Container With Most Water
好题！
- 像 2-sum 那个题目，看起来需要2次遍历，立即想到暂存历史计算，减少计算量。
- 先看看哪些情况是“不可能”的，把它们排除出去。左挡板从左向右遍历，如果后一个比前一个还短，那么这个不可能是 candidate，右挡板同样的道理。
- （到上面这一步已经可以写代码了，最坏平方级复杂度）还可以继续优化（这个看答案才想出来）。我们上一步把不可能的情况删掉后得到了递增的左挡板，和递增（从右往左看）的右挡板。如果左挡板低于右挡板，那么右挡板向左移动就不可能是 candidate，于是又排除了很多情况，变成 O(n) 复杂度。
a=[1,8,6,2,5,4,8,3,7]
i,j=0,len(a)-1
weight=0
while i<j:
weight=max(weight,(j-i)*min(a[i],a[j]))
if a[i]<a[j]:
i+=1
else:
j-=1
weight
12. Integer to Roman
无聊的题
all_symbols = [
['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
,['', 'X', 'XX', 'XXX','XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
, ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
,['', 'M', 'MM', 'MMM']
]
''.join([all_symbols[i][num//(10**i)%10] for i in range(3,-1,-1)])
13~15 无聊的题目
13
class Solution(object):
def romanToInt(self, s):
roman2num_dict={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
s_list=[roman2num_dict[i] for i in s[::-1]]
y=0
while len(s_list)>=2:
if s_list[0]>s_list[1]:
y+=s_list.pop(0)-s_list.pop(0)
else:y+=s_list.pop(0)
if len(s_list)==1:
y+=s_list[0]
return y
14
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res=''
for idx_j in range(len(strs[0])):
char=strs[0][idx_j]
for idx_i in range(1,len(strs)):
if idx_j>=len(strs[idx_i]):
return res
if strs[idx_i][idx_j]!=char:
return res
res+=char
return res
15
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
def sum2(nums,n):
his_dict=dict()
res=list()
for i,j in enumerate(nums):
if n-j in his_dict:
res.append((-n,n-j,j))
his_dict[j]=i
return res
res=[]
for i in range(len(nums)-2):
res.extend(sum2(nums[i+1:],-nums[i]))
return list(set(res))
16. 3Sum Closest
n-Sum 两种思路：
- 复用2sum，加一层遍历。2sum复杂度是n，3sum复杂度是O(n^2)
- 2sum还有另一种解法，先排序，然后使用
Container With Most Water的思路，找解复杂度是 O(n),但排序的复杂度是 O(nlgn)，所以2sum复杂度是 O(nlgn),3sum复杂度 O(n^2+nlgn)=O(n^2) - 所以2sum和3sum都可以用这个思路，复杂度一样
- 但3Sum Closest显然不能用1了，但可以用2
fn two_closest(nums: &[i32], target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
let mut closest = nums[left] + nums[right];
let mut diff = (closest - target).abs();
while left < right {
let sum2 = nums[left] + nums[right];
if sum2 == target { return target; }
let abs_sum2 = (sum2 - target).abs();
if abs_sum2 < diff {
closest = sum2;
diff = abs_sum2;
}
if sum2 > target {
right -= 1;
} else { left += 1; }
}
closest
}
impl Solution {
pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
let mut nums = nums;
nums.sort();
let mut res = nums[0] + nums[1] + nums[2];
let mut diff = (target - res).abs();
for idx in 0..nums.len() - 2 {
let tmp = two_closest(&nums[idx + 1..], target - nums[idx]);
let tmp_diff = (target - tmp - nums[idx]).abs();
if tmp_diff < diff {
diff = tmp_diff;
res = tmp + nums[idx];
}
}
res
}
}
17. Letter Combinations of a Phone Number
基础题，可以以此题为例子，把几种解法练熟了，甚至背下来。
- 利用 itertools
import itertools def letterCombinations(self, digits: str) -> List[str]: if len(digits)==0:return [] all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] candidate=[list(all_char[int(button)]) for button in digits] return [''.join(i) for i in itertools.product(*candidate)] - 递归。这个递归方法要求返回所有遍历到叶节点的路径。而不是成功访问1个叶节点就返回。这两种递归都要非常熟悉。
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] def letter_comb(digits): if len(digits)==0: return [] if len(digits)==1: return list(all_char[int(digits[0])]) prev=letter_comb(digits[:-1]) lst=all_char[int(digits[-1])] return [s+l for s in prev for l in lst] letter_comb(digits) - 递归（从前往后），另外，如果不考虑空的特殊情况，代码还可以再省一些
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] def letter_comb(digits): if len(digits)==0: return [''] prev=all_char[int(digits[0])] lst=letter_comb(digits[1:]) return [p+l for p in prev for l in lst] - 遇到笛卡尔积问题，优先使用这个套路。递归太容易写错，还是for循环好一些。
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] def letter_comb(digits): digits=[int(i) for i in digits] res=[''] for digit in digits: res=[i+j for i in res for j in all_char[digit]] return res - 事实证明，太多骚操作，复用就不方便。简简单单的for循环。（22题复用此代码）
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] res=[''] for i in digits: res=[term+char for term in res for char in all_char[int(i)]]
18. 4Sum
用递归，nSUM都能做出来
def find_2sum(nums,target):
i,j=0,len(nums)-1
res=[]
while i<j:
sum2=nums[i]+nums[j]
if sum2==target:
res.append([nums[i],nums[j]])
i+=1
elif sum2>target:
j-=1
else:
i+=1
return res
def find_Nsum(nums,target,N):
if N==2:
return find_2sum(nums,target)
res=[]
for i in range(len(nums)-N+1):
tmp=find_Nsum(nums[i+1:],target-nums[i],N-1)
if len(tmp)>0:
res.extend([[nums[i]]+t for t in tmp])
return res
nums=[1,0,-1,0,-2,2]
target=0
nums.sort()
find_Nsum(nums,target,N=4)
19. Remove Nth Node From End of List
考点：
- 凡是链表上的遍历问题，一律先想想能否使用单指针/双指针/多指针
- 如果处理的链表是不含空的头节点那种，一律加上空的头节点。这样往往可以减少很多处理边界条件的代码量。
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy=ListNode('')
dummy.next=head
curr1=dummy
for i in range(n):
curr1=curr1.next
curr2=dummy
while curr1.next:
curr1=curr1.next
curr2=curr2.next
curr2.next=curr2.next.next
return dummy.next
20. Valid Parentheses
好题目，用堆栈做，没什么难度
def isValid(self, s: str) -> bool:
stack=list()
pairs={'(':')','[':']','{':'}'}
pairs2={')':'(',']':'[','}':'{'}
for i in s:
if i in pairs:
stack.append(i)
elif i in pairs2:
if len(stack)==0:
return False
elif stack[-1]==pairs2[i]:
stack.pop()
else:
return False
return len(stack)==0
21. Merge Two Sorted Lists
基础题，
- 遇到链表，第一想到指针
- 处理链表，一律先转化成带空头节点的链表。可以减少一些边界条件的代码量，减少错误。
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None :
return l2
if l2 is None:
return l1
dummy1,dummy2=ListNode(),ListNode()
dummy1.next,dummy2.next=l1,l2
curr1,curr2=dummy1,dummy2.next
while curr2 and curr1.next:
if curr1.next.val>curr2.val:
tmp1,tmp2=curr1.next,curr2.next
curr1.next=curr2
curr2.next=tmp1
curr2=tmp2
curr1=curr1.next
else:
curr1=curr1.next
while curr1.next:
curr1=curr1.next
curr1.next=curr2
return dummy1.next
addition：其实熟练后可以不用全都加 dummy
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None:
return list2
dummy1=ListNode(None)
dummy1.next=list1
curr1,curr2=dummy1,list2
while curr1.next and curr2:
if curr1.next.val<=curr2.val:
curr1=curr1.next
else:
tmp1,tmp2=curr1.next,curr2.next
curr1.next=curr2
curr2.next=tmp1
curr1=curr1.next
curr2=tmp2
if curr1.next is None:
curr1.next=curr2
return dummy1.next
22. Generate Parentheses
用 f(n-1) 表示 f(n)，马上得出思路
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n==1:
return ['()']
res=set()
for term in self.generateParenthesis(n-1):
tmp=[term[:i]+'()'+term[i:] for i in range(2*n)]
res.update(tmp)
return list(set(res))
23. Merge k Sorted Lists
复用merge2
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists)==0:return None
if len(lists)==1:return lists[0]
def merge2(l1,l2):
if l1 is None :
return l2
if l2 is None:
return l1
dummy1,dummy2=ListNode(),ListNode()
dummy1.next,dummy2.next=l1,l2
curr1,curr2=dummy1,dummy2.next
while curr2 and curr1.next:
if curr1.next.val>curr2.val:
tmp1,tmp2=curr1.next,curr2.next
curr1.next=curr2
curr2.next=tmp1
curr2=tmp2
curr1=curr1.next
else:
curr1=curr1.next
while curr1.next:
curr1=curr1.next
curr1.next=curr2
return dummy1.next
l1=lists[0]
for i in range(1,len(lists)):
l1=merge2(l1,lists[i])
return l1
24. Swap Nodes in Pairs
考点都是在前面出现过的，必须都玩熟了：
- 遇到链表，无脑转成带空头节点的链表
- 用
curr.next and curr.next.next来规避curr.next是None的情况
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None:
return head
dummy = ListNode(None)
dummy.next = head
curr = dummy
while curr.next and curr.next.next:
tmp1,tmp2=curr.next,curr.next.next
tmp1.next=tmp2.next
curr.next=tmp2
tmp2.next=tmp1
curr=tmp1
return dummy.next
25. Reverse Nodes in k-Group
这个题就是两个逻辑的合并：取接下来的n个node，链表反转。
- 链表反转是一个基础考点。可以每次把最前面的节点放到后面。也可以每次把最后面的节点放到前面。
- 链表上的遍历，立即想到指针。
- 链表无脑转为带空头节点的链表。传入 reverse 函数的“子串”是前一级当成dummy来用，
- 代码逻辑不要混合，取k个与链表反转独立写。模块化适合考场。
class Solution:
def reverse(self,dummy,tail):
# first as dummy
head=dummy.next
curr=head
while curr is not tail:
tmp=curr.next
curr.next=tail.next
tail.next=curr
curr=tmp
dummy.next=tail
return dummy,head
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy=ListNode(None)
dummy.next=head
curr=dummy
i=k
start=curr
while curr.next:
curr=curr.next
i-=1
if i==0:
_,curr=self.reverse(start,curr)
start=curr
i=k
return dummy.next
26. Remove Duplicates from Sorted Array
很简单，也没总结出啥套路，下一题一样。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
curr1,curr2=0,1
while curr2<len(nums):
if nums[curr1]<nums[curr2]:
curr1+=1
nums[curr1]=nums[curr2]
curr2+=1
return curr1+1
27. Remove Element
很简单，不用看了，跟上一个提一样
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
curr1,curr2=0,0
while curr2<len(nums):
if nums[curr2]!=val:
nums[curr1]=nums[curr2]
curr1+=1
curr2+=1
return curr1
28. Implement strStr()
自带的 haystack.find(needle)
KMP算法也可以
29. Divide Two Integers
不用再做了
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
sign=1
if dividend<0:
sign=-sign
dividend=-dividend
if divisor<0:
sign=-sign
divisor=-divisor
res=sign*(dividend//divisor)
if res>2**31-1:
return 2**31-1
if res<-2**31:
return -2**31
return res
30. Substring with Concatenation of All Words
这个题目有一些特殊情况，例如 ['ab','ba'] 这种可能相互重叠的，还有 ['ab','cd','ab'] 这种重复的。
似乎比较好写的解决方式是每次移动一格，做暴力搜索。
???还没找到更好的方案
import collections
class Solution:
def is_good(self,text,words_dict,len_word,len_words):
words_dict=words_dict.copy()
for i in range(len_words):
term=text[i*len_word:(i+1)*len_word]
if term not in words_dict:
return False
elif words_dict[term]==0:
return False
words_dict[term]-=1
return True
def findSubstring(self, s: str, words: List[str]) -> List[int]:
res=[]
len_word=len(words[0])
len_words=len(words)
curr=0
words_dict=collections.Counter(words)
while curr<len(s)-len_word*len_words+1:
if self.is_good(s[curr:],words_dict,len_word,len_words):
res.append(curr)
curr+=1
return res
31. Next Permutation
想到有个递推公式：
- 如果
num[i+1:]有next，那么整体就有next，迭代为f(num[i:]) = [num[i]] + f(num[i+1:]) - 如果
num[i+1:]已经没有next，但是num[i]比num[i+1:]中的某个小。就让两个数字互换，并且num[i+1:]重新排序。例如2; 4, 3, 1就先换位置，变成3; 4, 2, 1，然后后者排序，变成3; 1, 2, 4 - 如果以上条件都不满足，说明
num[i:]是升序，就没有下一个了，按照题目要求，需要返回nums.sort()
另外：
- 题目中要求直接替换 nums，下面的代码用了额外空间配合for循环赋值实现。后续改改代码或许可以节省空间
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
def next_perm(nums):
if len(nums)<=1:
return False,None
part1,part2=nums[0],nums[1:]
has_next,next_nums = next_perm(part2)
if has_next:
return True,[part1] + next_nums
else:
if part1<max(part2):
next_idx=0
next_num=101
for idx,num in enumerate(part2):
if num>part1:
if num<next_num:
next_idx,next_num=idx,num
tmp=part2[next_idx]
part2[next_idx]=part1
part1=tmp
part2.sort()
return True,[part1]+part2
return False,None
has_next,next_nums=next_perm(nums)
if has_next:
for i in range(len(nums)):
nums[i] = next_nums[i]
else:
nums.sort()
32. Longest Valid Parentheses
- 两个计数器，left表示当前序列中，左括号数量。right表示当前序列中，右括号数量。
- 如果left=right，更新一次最大值
- 如果left<right，开始一个新的序列
- （关键）以上忽略了
(()这种情况，只需要把上面的算法从右向左再跑一次即可
class Solution:
def helper(self,s,mode):
left,right=0,0
res=0
for char in s:
if char==mode:
left+=1
else:
right+=1
if right>left:
left,right=0,0
if right==left:
res=max(res,left*2)
return res
def longestValidParentheses(self, s: str) -> int:
res1=self.helper(s,mode='(')
res2=self.helper(s[::-1],mode=')')
return max(res1,res2)
33. Search in Rotated Sorted Array
n种情况吧。（感觉下面的代码还可以优化，不过大体思路就是这样了）
class Solution:
# def find_pivot(self,nums):
# left,right=0,len(nums)-1
# head,tail=nums[left],nums[right]
# mid_idx=(left+right)//2
# return 0
def search(self, nums: List[int], target: int) -> int:
if nums[0]==target:
return 0
left,right=0,len(nums)-1
if nums[0]<=target:
while left<right:
mid=(left+right)//2
if nums[mid]<target:
if nums[mid]<nums[0]:
right=mid-1
else:
left=mid+1
elif nums[mid]>target:
right=mid-1
else:
return mid
else:
while left<right:
mid=(left+right)//2
if nums[mid]<target:
left=mid+1
elif nums[mid]>target:
if nums[mid]>=nums[0]:
left=mid+1
else:
right=right-1
else:
return mid
mid=left
if nums[mid]==target:
return mid
return -1
34. Find First and Last Position of Element in Sorted Array
先用二分法找左边，然后用二分法找右边。
- 应该有合起来找的方法，但是写的慢
- 下面的代码也有优化的空间
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
res=[-1,-1]
if len(nums)==0:
return res
# 寻找左边
left,right=0,len(nums)-1
while left<right:
mid=(left+right)//2
if nums[mid]>=target:
right = mid-1
else:
left = mid+1
if nums[left]<target:
if left==len(nums)-1:
return [-1,-1]
if nums[left+1]==target:
res[0]=left+1
else:
return [-1,-1]
elif nums[left]==target:
res[0]=left
else:
return [-1,-1]
# 寻找右边
left,right=res[0],len(nums)-1
while left<right:
mid=(left+right)//2
if nums[mid]<=target:
left=mid+1
else:
right=mid-1
if nums[left]>target:
res[1]=left-1
else:
res[1]=left
return res
35. Search Insert Position
基本的二分法
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left,right=0,len(nums)-1
while left<right:
mid=(left+right)//2
if nums[mid]<target:
left=mid+1
elif nums[mid]>target:
right=mid-1
else:
return mid
if nums[left]<target:
return left+1
else:
return left
36. Valid Sudoku
暴力解法
def is_good(lst):
tmp=[i for i in lst if i!='.']
return len(tmp)==len(set(tmp))
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
for line in board:
if not is_good(line):
return False
for i in range(9):
col=[board[j][i] for j in range(9)]
if not is_good(col):
return False
for i in range(3):
for j in range(3):
block=[board[3*i+i1][3*j+j1] for i1 in range(3) for j1 in range(3)]
if not is_good(block):
return False
return True
改进：可以用一个整数来表示列表，例如 [...,1,0,1,0] 表示2和4 存在，简写成 1010...。
- 一个新数 3 是否在已有呢？取决于
...1010 & (1<<3)是否为0 - 如何更新呢？
...1010 | (1<<3) - 答案如下：
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row, col, box = [0] * 9, [0] * 9, [0] * 9
for i in range(9):
for j in range(9):
if board[i][j] == '.':
continue
box_idx = (i // 3) * 3 + (j // 3)
num = 1 << (ord(board[i][j]) + 48)
if row[i] & num or col[j] & num or box[box_idx] & num:
return False
row[i] |= num
col[j] |= num
box[box_idx] |= num
return True
37. Sudoku Solver
练递归的好题！
用 set 来做，这个最易懂（跟我总结的公式有差别）
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
row = [set() for _ in range(9)]
col = [set() for _ in range(9)]
block = [[set() for _ in range(3)] for _ in range(3)] # 3*3
blank = []
# 初始化，按照行、列、宫 分别存入哈希表
for i in range(9):
for j in range(9):
ch = board[i][j]
if ch == ".":
blank.append((i, j))
else:
row[i].add(ch)
col[j].add(ch)
block[i//3][j//3].add(ch)
len_blank=len(blank)
def dfs(n):
if n == len_blank:
return True
i, j = blank[n]
rst = nums - row[i] - col[j] - block[i//3][j//3] # 可行解
if not rst:
return False
for num in rst:
board[i][j] = num
row[i].add(num)
col[j].add(num)
block[i//3][j//3].add(num)
if dfs(n+1):
return True
row[i].remove(num)
col[j].remove(num)
block[i//3][j//3].remove(num)
dfs(0)
用位运算优化加速
row[i], col[j], block[i//3][j//3]都是int类型，第k位为1，表示 k+1 出现过(~num) & 0x1ff，这个数的第 k 位为1，代表 k+1 没出现过，也就是k+1可以填入格子。（& 0x1ff是因为高于9的位没有意义）b & (−b) = b & (~b + 1)可以保留最低的 1，其它全变为0digit = bin(digitMask).count("0") - 1???用来计算最低位的1在第几位b ^ (b & (-b)) = b & (b - 1)可以消去最低位的1，可以以此来枚举下一个 1
官方答案
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def flip(i: int, j: int, digit: int):
line[i] ^= (1 << digit)
column[j] ^= (1 << digit)
block[i // 3][j // 3] ^= (1 << digit)
line = [0] * 9
column = [0] * 9
block = [[0] * 3 for _ in range(3)]
valid = [False]
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
else:
digit = int(board[i][j]) - 1
flip(i, j, digit)
def dfs(pos: int):
if pos == len(spaces):
valid[0] = True
return
i, j = spaces[pos]
mask = ~(line[i] | column[j] | block[i // 3][j // 3]) & 0x1ff
while mask:
digitMask = mask & (-mask)
digit = bin(digitMask).count("0") - 1
flip(i, j, digit)
board[i][j] = str(digit + 1)
dfs(pos + 1)
flip(i, j, digit)
mask &= (mask - 1)
if valid[0]:
return
dfs(0)
38. Count and Say
简单，一遍过
class Solution:
def countAndSay(self, n: int) -> str:
if n==1:
return '1'
tmp=self.countAndSay(n-1)
res=[]
curr_idx=0
curr_cnt=0
curr=tmp[curr_idx]
for idx,char in enumerate(tmp):
if char!=curr:
res.append(str(curr_cnt)+curr)
curr_cnt=0
curr=tmp[idx]
curr_cnt+=1
res.append(str(curr_cnt)+curr)
return ''.join(res)
39. Combination Sum
这题也简单，不过需要注意 [2,2,3] 和 [2,3,2] 算是同一个解，因此多引入一个变量，以判断和防止重复计入。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res_all=[]
def comb_sum(candidates,last_used,target,res):
if target<0:
return
if target==0:
res_all.append(res)
return
if target>0:
for candidate in candidates:
if candidate<last_used:
continue
last_used=candidate
comb_sum(candidates,last_used,target-candidate,res+[candidate])
comb_sum(candidates,0,target,list())
return res_all
40. Combination Sum II
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
res_all=[]
def comb_sum(candidates,target,res):
if target<0:
return
if target==0:
res_all.append(res)
return
if not candidates:
return
# if target>0:
for idx,candidate in enumerate(candidates):
new_candidates=candidates[idx+1:] if idx<len(candidates)-1 else []
comb_sum(new_candidates,target-candidate,res+[candidate])
comb_sum(candidates,target,[])
# 去重
res_all=set([tuple(i) for i in res_all])
res_all=list([list(i) for i in res_all])
return res_all
上面的答案有重复搜索，改为这个
import collections
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates = [[i,j] for i,j in collections.Counter(candidates).items()]
candidates.sort()
res_all=[]
def comb_sum(candidates,target,res):
if target<0:
return
if target==0:
res_all.append(res)
return
if not candidates:
return
# if target>0:
for idx,[candidate,candidate_cnt] in enumerate(candidates):
if candidate_cnt==0:
continue
new_candidate=candidates[idx:]
candidates[idx][1]-=1
comb_sum(new_candidate,target-candidate,res+[candidate])
candidates[idx][1]+=1
comb_sum(candidates,target,[])
return res_all
41. First Missing Positive
算作弊了
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums=list(set(nums))
nums.sort()
res=1
for i in nums:
if i<=0:
continue
if i==res:
res+=1
continue
else:
return res
return res
42. Trapping Rain Water
直接思路
- 左隔板为 left，寻找右边第一个大于 left 的隔板，记为 right
- 如果右边都小小于 left，就寻找右边最大的隔板，记为left
- 赋值 right = left，继续迭代。
想到之前有个隔板题，是从左到右遍历一次，然后从右往左遍历一次。因此想到，先把水填满，然后看看哪些流出去了。
（代码还可以优化）
class Solution:
def trap(self, height: List[int]) -> int:
max_height=max(height)
total_water=max_height*len(height)-sum(height)
left_min=-1
for num in height:
left_min=max(left_min,num)
total_water-=(max_height-left_min)
right_min=-1
for num in height[::-1]:
right_min=max(right_min,num)
total_water-=(max_height-right_min)
return total_water
43. Multiply Strings
class Solution:
def multiply(self, num1: str, num2: str) -> str:
return str(int(num1)*int(num2))
44. Wildcard Matching
各种超时
"babbbbaabababaabbababaababaabbaabababbaaababbababaaaaaabbabaaaabababbabbababbbaaaababbbabbbbbbbbbbaabbb"
"b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a"
超时的原因是有些地方被反复计算了，用 functools.lru_cache 做缓存（击败5%）
import functools
class Solution:
def isMatch(self, s: str, p: str) -> bool:
@functools.lru_cache(maxsize=None, typed=False)
def is_match(text,pattern):
if pattern=='':
return text==''
if pattern=='*':
return True
if text=='':
return False
if pattern[0]=='?':
return is_match(text[1:],pattern[1:])
elif pattern[0]=='*':
return is_match(text,pattern[1:]) or is_match(text[1:],pattern)
else:
return text[0]==pattern[0] and is_match(text[1:],pattern[1:])
p_list=[]
last_is_star=False
for i in p:
if i=='*':
if last_is_star:
last_is_star=True
continue
else:
p_list.append(i)
last_is_star=True
else:
p_list.append(i)
last_is_star=False
p=''.join(p_list)
return is_match(s,p)
下面这个用了dp方法，不会超时
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, n + 1):
if p[i - 1] == '*':
dp[0][i] = True
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
45. Jump Game II
动态规划基本题目，注意0
class Solution:
def jump(self, nums: List[int]) -> int:
len_nums=len(nums)
dp=[0]*len_nums
for i in range(len(nums)-2,-1,-1):
# print(dp)
if nums[i]==0:
dp[i]=100000
else:
dp[i]=min(dp[i+1:i+nums[i]+1])+1
return dp[0]
46. Permutations
用工具很方便
itertools.permutations(nums)
工具和递归的效率差不多，
- 对nums做回溯（+递归），sep 左边代表已经填入的，右边代表待填入的
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def permute_func(sep):
if sep==len(nums):
return res.append(nums.copy())
for idx in range(sep,len(nums)):
nums[idx],nums[sep]=nums[sep],nums[idx]
permute_func(sep+1)
nums[idx],nums[sep]=nums[sep],nums[idx]
len_nums=len(nums)
res=[]
permute_func(0)
return res
47. Permutations II
照抄上一题，在结果中去重：
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res=set()
len_nums=len(nums)
def permute(sep):
if sep==len_nums:
res.add(tuple(nums))
for idx in range(sep,len_nums):
nums[idx],nums[sep]=nums[sep],nums[idx]
permute(sep+1)
nums[idx],nums[sep]=nums[sep],nums[idx]
permute(0)
return [list(i) for i in res ]
!!!还有性能更高的做法，待研究
48. Rotate Image
第一次不是很容易想到这个：
- 旋转90度不容易，但是
- 上下镜像、左右镜像、主对角线镜像是容易实现的
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n=len(matrix)
for i in range(n):
for j in range(i):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
for i in range(n):
matrix[i]=matrix[i][::-1]
49. Group Anagrams
简单，sort即可
import collections
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res=collections.defaultdict(list)
for term in strs:
res[''.join(sorted(term))].append(term)
return list(res.values())
50. Pow(x, n)
x**n (开个玩笑)
class Solution:
def myPow(self, x: float, n: int) -> float:
def my_pow(x,n):
if n==1:
return x
if n==0:
return 1
if n==-1:
return 1/x
tmp=my_pow(x,n//2)
return tmp*tmp*my_pow(x,n%2)
return my_pow(x,n)
递归调用会使用栈空间，因此，时间复杂度 $\log n$，空间复杂度 $\log n$
用位运算，可以把空间复杂度降低到 $\log n$，本质上是计算 $2^{k0} \times 2^{k1} \times 2^{k2} \times …$
class Solution:
def myPow(self, x: float, n: int) -> float:
def my_pow(n):
res=1
val=x
while n:
n,k=divmod(n,2)
if k:
res*=val
val*=val
return res
return my_pow(n) if n>=0 else 1/my_pow(-n)
51. N-Queens
回溯法典型题目，!!! 多练习几遍
class Solution:
def solveNQueens(self, n: int):
col = [0] * n
diagonal_1 = [0] * (2 * n - 1) # 副对角线
diagonal_2 = [0] * (2 * n - 1) # 对角线
solution = [[0] * n for i in range(n)]
res = []
chars = {0: '.', 1: 'Q'}
def n_queens(col, diagonal_1, diagonal_2, solution, i):
if i == n:
res.append([''.join([chars[i] for i in line]) for line in solution])
return
for j in range(n):
if col[j] or diagonal_1[i + j] or diagonal_2[i - j + n - 1]:
continue
col[j] = diagonal_1[i + j] = diagonal_2[i - j + n - 1] = solution[i][j] = 1
n_queens(col, diagonal_1, diagonal_2, solution, i + 1)
col[j] = diagonal_1[i + j] = diagonal_2[i - j + n - 1] = solution[i][j] = 0
n_queens(col, diagonal_1, diagonal_2, solution, 0)
return res
52. N-Queens II
跟上面的题一样
class Solution:
def totalNQueens(self, n: int) -> int:
res=[0]
cols=[0]*n
diag_1=[0]*(2*n-1)
diag_2=[0]*(2*n-1)
def n_queens(cols,diag_1,diag_2,i):
if i==n:
res[0]+=1
return
for j in range(n):
if cols[j] or diag_1[i+j] or diag_2[i-j+n-1]:
continue
cols[j]=diag_1[i+j] =diag_2[i-j+n-1]=1
n_queens(cols,diag_1,diag_2,i+1)
cols[j]=diag_1[i+j] =diag_2[i-j+n-1]=0
n_queens(cols,diag_1,diag_2,0)
return res[0]
53. Maximum Subarray
好题！
不容易想出来：
f(i)定义为：第 i 位结尾的最大序列，因此f(i) = max(f(i-1)+nums[i], nums[i])- 然后求
max(f(i))即可 - 下面的代码中，把
f(i)写到 nums 中，以节省内存空间
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
if nums[i-1]>0:
nums[i]=nums[i-1]+nums[i]
return max(nums)
54. Spiral Matrix
- 想到像削苹果一样，每次旋转90度，削头
list(zip(*matrix))是按照主对角线反转，配合::-1可以达到逆时针旋转。（这一步参考48题）
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
while matrix:
# 削头（第一层）
res += matrix.pop(0)
# 将剩下的逆时针转九十度，等待下次被削
matrix = list(zip(*matrix))[::-1]
return res
!!!改进为 one line，非常惊艳！
class Solution:
def spiralOrder(self, matrix):
return matrix and list(matrix.pop(0))+self.spiralOrder(list(zip(*matrix))[::-1])
如果pop结尾，会快很多。上下颠倒，每次削脚，然后顺时针旋转。
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
matrix.reverse()
res=[]
while matrix:
res.extend(matrix.pop())
matrix.reverse()
matrix=list(zip(*matrix))
return res
55. Jump Game
普通的dp方法
class Solution:
def canJump(self, nums: List[int]) -> bool:
dp=[False]*len(nums)
dp[0]=True
for idx,num in enumerate(nums):
if dp[idx]:
if idx+num+1>=len(nums):
return True
for i in range(idx+1,idx+num+1):
dp[i]=True
return dp[-1]
不知道能不能改进
56. Merge Intervals
简单，按照字面意思做
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
res=[intervals[0]]
for i in range(1,len(intervals)):
if res[-1][1]>=intervals[i][0]:
if res[-1][1]<intervals[i][1]:
res[-1][1]=intervals[i][1]
else:
res.append(intervals[i])
return res
##
直白的if-else
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals:
return [newInterval]
res=[]
has_insert_new=False
for interval in intervals:
if interval[1]<newInterval[0]:
res.append(interval)
elif interval[0]>newInterval[1]:
if not has_insert_new:
res.append(newInterval)
has_insert_new=True
res.append(interval)
else:
if not has_insert_new:
res.append(newInterval)
has_insert_new=True
newInterval[0]=min(newInterval[0],interval[0])
newInterval[1]=max(newInterval[1],interval[1])
if not has_insert_new:
res.append(newInterval)
return res
O(n) 复杂度
感觉直接抄上一题也就 nlog(n) 复杂度
58. Length of Last Word
class Solution:
def lengthOfLastWord(self, s: str) -> int:
meet_word=False
res=0
for idx in range(len(s)-1,-1,-1):
if s[idx]==' ':
if meet_word:
return res
else:
continue
else:
meet_word=True
res+=1
return res
60. Permutation Sequence
下面是抄的，太漂亮了
class Solution:
def getPermutation(self, n: int, k: int) -> str:
factorial=[1]
for i in range(1,n):
factorial.append(factorial[-1]*i)
res=[]
k-=1
nums=list(range(1,n+1))
for mul in factorial[::-1]:
div,k=divmod(k,mul)
res.append(str(nums.pop(div)))
return ''.join(res)
61. Rotate List
本来想直接写个耦合性高但性能好的解，发现还是解耦更好
class Solution:
def get_len(self,head):
length=0
curr=head
while curr:
length+=1
curr=curr.next
return length
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None:
return None
dummy=ListNode(val=None,next=head)
curr1=curr2=dummy
length=self.get_len(head)
k=k%length
for _ in range(k):
curr2=curr2.next
while curr2.next is not None:
curr1=curr1.next
curr2=curr2.next
if curr1 is dummy:
return dummy.next
curr2.next=dummy.next
dummy.next=curr1.next
curr1.next=None
return dummy.next
##
阶乘
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
perm=[0]*(m+n-1)
perm[0]=1
for k in range(1,m+n-1):
perm[k]=k*perm[k-1]
return int(perm[m+n-2]/perm[m-1]/perm[n-1])
63. Unique Paths II
dfs，需要注意 要加cache （也就是 dp）
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
h,w=len(obstacleGrid),len(obstacleGrid[0])
if obstacleGrid[0][0] or obstacleGrid[h-1][w-1]:
return 0
visited={(0,0):1}
def cal_path(idx_i,idx_j):
if obstacleGrid[idx_i][idx_j]:
return 0
if (idx_i,idx_j) in visited:
return visited[(idx_i,idx_j)]
if idx_i==0:
part_up=0
else:
part_up=cal_path(idx_i-1,idx_j)
if idx_j==0:
part_left=0
else:
part_left=cal_path(idx_i,idx_j-1)
visited[(idx_i,idx_j)]=part_up+part_left
return visited[(idx_i,idx_j)]
cal_path(h-1,w-1)
return visited[(h-1,w-1)]
##
上一个题用了 dfs+dp，这题用 bfs
class Solution:
def minPathSum(self, grid) -> int:
h,w=len(grid),len(grid[0])
queue={(0,0)}
visited={(0,0):grid[0][0]}
while queue:
new_queue=set()
for point in queue:
for move in ((1,0),(0,1)):
next_point=point[0]+move[0],point[1]+move[1]
if next_point[0]<h and next_point[1]<w:
visited[next_point]=min(
visited.get(next_point,10**8),
visited[point]+grid[next_point[0]][next_point[1]]
)
new_queue.add(next_point)
queue=new_queue
return visited[(h-1,w-1)]
65～69
65-别做了
66-直白
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
cap=1
for idx in range(len(digits)-1,-1,-1):
digits[idx]+=cap
cap,digits[idx]=divmod(digits[idx],10)
if cap==0:
break
if cap==1:
digits=[1]+digits
return digits
67-作弊
class Solution:
def addBinary(self, a: str, b: str) -> str:
return bin(int(a,2)+int(b,2))[2:]
68-别做了
69-作弊 int(sqrt(x))
其实可以用二分法
class Solution:
def mySqrt(self, x: int) -> int:
left,right=0,x
while left<right:
mid=(left+right)//2
# print(left,right,mid)
if mid*mid<x:
left=mid+1
elif mid*mid>x:
right=mid-1
else:
return mid
if (left-1)*(left-1)<x<left*left:
return left-1
else:
return left
70
dfs+dp
class Solution:
def climbStairs(self, n: int) -> int:
visited={0:1,1:2}
def dfs(i):
if i in visited:
return visited[i]
cnt=dfs(i-1)+dfs(i-2)
visited[i]=cnt
return cnt
return dfs(n-1)
71
别做
72
- 这类题基本上都是递归+dp了，
- 一开始思路卡在了增加一个字母怎样做dp，看答案发现第二个串删除一个字母相当于第一个串增加一个字母
- 然后就变成简单题了
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
len1, len2 = len(word1), len(word2)
visited = dict()
def min_dist(i, j):
if (i, j) in visited:
return visited[(i, j)]
if i == len1:
dist = len2 - j
elif j == len2:
dist = len1 - i
elif word1[i] == word2[j]:
dist = min_dist(i + 1, j + 1)
else:
dist = min(min_dist(i + 1, j) + 1, min_dist(i, j + 1) + 1, min_dist(i + 1, j + 1) + 1)
visited[(i, j)] = dist
return dist
return min_dist(0, 0)
75. Sort Colors
作弊 nums.sort()
##
双指针+need，这类的题需要总结一下
class Solution:
def minWindow(self, s: str, t: str) -> str:
need_dict = dict()
for char in t:
if char in need_dict:
need_dict[char] += 1
else:
need_dict[char] = 1
curr1 = curr2 = 0
res_len, res_s = len(s) + 1, ''
if s[0] in need_dict:
need_dict[s[0]] -= 1
while curr1 < len(s) and curr2 < len(s):
if all(i <= 0 for i in need_dict.values()):
if curr2 - curr1 < res_len:
res_len = curr2 - curr1
res_s = s[curr1:curr2 + 1]
if s[curr1] in need_dict:
need_dict[s[curr1]] += 1
curr1 += 1
else:
curr2 += 1
if curr2 == len(s):
break
if s[curr2] in need_dict:
need_dict[s[curr2]] -= 1
return res_s
77. Combinations
组合基础题，必背！
dfs+dp
class Solution:
def combine(self, n: int, k: int):
cache = dict()
def dfs(n, k):
if (n, k) in cache:
return cache[(n, k)]
if k > n or k == 0:
res = [[]]
elif k == n:
res = [list(range(1,n+1))]
else:
res = [i + [n] for i in self.combine(n - 1, k - 1)] + self.combine(n - 1, k)
cache[(n, k)] = res
return res
return dfs(n, k)
##
放回抽样基础题，必背！
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res=[[]]
for i in nums:
res=[item+next_choice for item in res for next_choice in ([],[i])]
return res
79. Word Search
找一个解即可，dfs
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
h,w=len(board),len(board[0])
res=[False]
def dfs(i,j,k):
if res[0]:
return
if board[i][j]!=word[k]:
return
if k==len(word)-1:
res[0]=True
return
for move_i,move_j in ((-1,0),(1,0),(0,1),(0,-1)):
new_i,new_j=i+move_i,j+move_j
if 0<=new_i<h and 0<=new_j<w:
char,board[i][j]=board[i][j],None
dfs(new_i,new_j,k+1)
board[i][j]=char
for i in range(h):
for j in range(w):
dfs(i,j,0)
return res[0]
80. Remove Duplicates from Sorted Array II
双指针，作为练习题
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
curr1=curr2=0
tmp_dict=dict()
while curr2<len(nums):
if nums[curr2] not in tmp_dict:
nums[curr1]=nums[curr2]
tmp_dict[nums[curr1]]=1
curr1+=1
curr2+=1
elif tmp_dict[nums[curr2]]==1:
nums[curr1]=nums[curr2]
tmp_dict[nums[curr1]]=2
curr1+=1
curr2+=1
else:
curr2+=1
return curr1
82. Remove Duplicates from Sorted List II
遇到对节点有增、删的，先无脑加 dummy
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy=ListNode(val=None,next=head)
curr1=dummy
while curr1.next:
if curr1.next.next:
if curr1.next.val==curr1.next.next.val:
curr2=curr1.next
while curr2 and curr2.val==curr1.next.val:
curr2=curr2.next
curr1.next=curr2
continue
curr1=curr1.next
return dummy.next
83. Remove Duplicates from Sorted List
同上
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None:
return None
dummy=ListNode(val=None,next=head)
curr=dummy.next
while curr.next:
if curr.next.val==curr.val:
curr.next=curr.next.next
else:
curr=curr.next
return dummy.next
84. Largest Rectangle in Histogram
这题很难，看了很多答案才明白
想象锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最戳出来的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那我继续开开心心往右找更高的。
当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
res=0
heights.append(0)
for i,height in enumerate(heights):
for j in range(i-1,-1,-1):
if heights[j] > height:
res = max(res,heights[j]*(i-j))
heights[j] = height
else:
break
return res
还有性能上进一步优化的空间：被锯掉的部分其实不用保存了，下次也不用遍历它。不过需要额外一个list来保存index信息。内存消耗多了，时间消耗少了。
86. Partition List
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
dummy = ListNode(next=head)
dummy_bigger = ListNode()
curr1 = dummy
curr2 = dummy_bigger
while curr1.next:
if curr1.next.val < x:
curr1 = curr1.next
else:
curr2.next = curr1.next
curr2 = curr2.next
curr1.next = curr1.next.next
curr2.next=None
curr1.next = dummy_bigger.next
return dummy.next
87. Scramble String
这题很难想出来，但是想出来后很容易
class Solution:
@lru_cache(None)
def isScramble(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2) or s1 == '' or sorted(s1) != sorted(s2): return False
if s1 == s2: return True
for i in range(1, len(s1)):
if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]): return True
if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]): return True
return False
88. Merge Sorted Array
作弊
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
for i in range(n):
nums1[i+m]=nums2[i]
nums1.sort()
89. Gray Code
背下来
gray2real（这个还需要调整）：
b = gray_code.cumsum(axis=1) % 2
mask = np.logspace(start=1, stop=len_gray_code, base=0.5, num=len_gray_code)
return (b * mask).sum(axis=1) / mask.sum()
real2gray:
gray[i] = i ^ (i>>1)
90. Subsets II
这个题
- 顺序交换算是同一个
- 要去重
思路就是基本的无放回抽样，一分钟写出来
import collections
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums = collections.Counter(nums)
res = [[]]
for num, cnt in nums.items():
tmp = [[num] * i for i in range(cnt + 1)]
res = [line + k for line in res for k in tmp]
return res
91. Decode Ways
class Solution:
def __init__(self):
self.valid_nums1 = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
self.valid_nums2 = {'22', '24', '16', '18', '10', '11', '12', '17', '23', '21', '19', '20', '14', '13', '25',
'15', '26'}
def numDecodings(self, s: str) -> int:
visited = dict()
def dfs(s):
if s in visited:
return visited[s]
res = 0
if len(s) == 1:
if s in self.valid_nums1:
res += 1
elif len(s) == 2:
res = 0
if s in self.valid_nums2:
res += 1
if s[0] in self.valid_nums1 and s[1] in self.valid_nums1:
res += 1
else:
if s[0] in self.valid_nums1:
res += dfs(s[1:])
if s[:2] in self.valid_nums2:
res += dfs(s[2:])
visited[s] = res
return res
return dfs(s)
93. Restore IP Addresses
dfs+dp，会背了
class Solution:
num_1 = {'8', '1', '2', '3', '9', '4', '0', '5', '7', '6'}
num_2 = {'62', '57', '34', '32', '47', '60', '65', '71', '75', '92', '52', '91', '68', '99', '28', '86', '94', '64',
'85', '70', '87', '76', '30', '21', '79', '10', '33', '67', '56', '14', '31', '41', '88', '45', '54', '37',
'12', '46', '20', '77', '27', '97', '49', '58', '51', '18', '50', '69', '96', '74', '36', '93', '59', '61',
'29', '82', '22', '90', '84', '43', '42', '15', '24', '16', '26', '23', '73', '98', '38', '55', '66', '25',
'48', '63', '72', '35', '13', '81', '95', '44', '53', '80', '39', '78', '89', '40', '17', '11', '19', '83'}
num_3 = {'218', '237', '101', '118', '239', '186', '122', '126', '175', '184', '208', '156', '232', '245', '219',
'211', '216', '169', '125', '133', '167', '197', '136', '152', '123', '174', '188', '231', '236', '114',
'246', '148', '207', '234', '131', '150', '177', '144', '159', '113', '204', '129', '222', '130', '155',
'171', '230', '242', '238', '124', '196', '128', '235', '138', '100', '137', '194', '140', '111', '105',
'199', '201', '249', '170', '200', '193', '109', '223', '127', '203', '247', '165', '153', '185', '224',
'221', '158', '139', '183', '252', '253', '190', '151', '157', '206', '143', '146', '213', '187', '147',
'163', '226', '102', '110', '198', '145', '179', '182', '161', '180', '189', '116', '142', '244', '251',
'115', '120', '243', '112', '132', '250', '104', '103', '176', '225', '214', '119', '154', '134', '233',
'168', '255', '240', '121', '108', '229', '254', '141', '217', '202', '191', '135', '215', '181', '209',
'212', '160', '210', '228', '172', '149', '162', '107', '117', '248', '220', '192', '178', '227', '241',
'164', '205', '173', '106', '166', '195'}
def restoreIpAddresses(self, s: str):
cache = dict()
def dfs(s, i):
if (s, i) in cache:
return cache[(s, i)]
res = []
if i == 1:
if len(s) == 1 and s in self.num_1:
res = [s]
elif len(s) == 2 and s in self.num_2:
res = [s]
elif len(s) == 3 and s in self.num_3:
res = [s]
elif len(s) == 0:
res = []
else:
if s[0] in self.num_1:
res.extend([s[0] + '.' + item for item in dfs(s[1:], i - 1)])
if s[:2] in self.num_2:
res.extend([s[:2] + '.' + item for item in dfs(s[2:], i - 1)])
if s[:3] in self.num_3:
res.extend([s[:3] + '.' + item for item in dfs(s[3:], i - 1)])
cache[(s, i)] = res
return res
return dfs(s, 4)
96. Unique Binary Search Trees
递归，结果为左子树的情况数乘以右子树的情况树 f(n)= f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(1)
class Solution:
def numTrees(self, n: int) -> int:
cache=[None]*(n+1)
def func(n):
if cache[n] is not None:
return cache[n]
if n==0:
res=1
else:
res=0
for i in range(n):
res+=func(i)*func(n-i-1)
cache[n]=res
return res
return func(n)
95. Unique Binary Search Trees II
思路同上，dfs+cache
class Solution:
def generateTrees(self, n: int):
cache = dict()
def myfunc(left, right):
if (left, right) in cache:
return cache[(left, right)]
if right < left:
res = [None]
else:
res = []
for i in range(left, right + 1):
for left_node in myfunc(left, i - 1):
for right_node in myfunc(i + 1, right):
root = TreeNode(val=i)
root.left = left_node
root.right = right_node
res.append(root)
cache[(left, right)] = res
return res
return myfunc(1, n)
97. Interleaving String
dfs+cache
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
res = [False]
cache = set()
def dfs(s1, s2, s3):
if res[0]:
return
if (s1, s2, s3) in cache:
return
else:
cache.add((s1, s2, s3))
if len(s1) + len(s2) != len(s3):
return
if len(s1) == 0:
if s2 == s3:
res[0] = True
return
elif len(s2) == 0:
if s1 == s3:
res[0] = True
return
else:
if s1[0] == s3[0]:
dfs(s1[1:], s2, s3[1:])
if s2[0] == s3[0]:
dfs(s1, s2[1:], s3[1:])
dfs(s1, s2, s3)
return res[0]
98. Validate Binary Search Tree
- 还是 dfs，
- 因为是树，所以无须cache
- 貌似是中序遍历？？？它们的内在关系之后研究一下
- “左子树的所有节点都小于此节点”等价于“左子树的最大节点小于父节点”
class Solution:
int_min = -2 ** 32
int_max = 2 ** 32
def isValidBST(self, root: TreeNode) -> bool:
res = [True]
def dfs(node, parent_min, parent_max):
if res[0] is False:
return
if node is None:
return
if not parent_min < node.val < parent_max:
res[0] = False
return
dfs(node.left, parent_min, node.val)
dfs(node.right, node.val, parent_max)
dfs(root, self.int_min, self.int_max)
return res[0]
99. Recover Binary Search Tree
很直白的步骤：
- inorder 得到一个本应该递增的序列
- 在 inorder 结果上找到不对的节点
- 交换
class Solution:
def inorder(self, root):
return [] if (root is None) else self.inorder(root.left) + [root.val] + self.inorder(root.right)
def recoverTree(self, root) -> None:
"""
Do not return anything, modify root in-place instead.
"""
nums = self.inorder(root)
wrong_nodes = []
nums_sorted = sorted(nums)
for i in range(len(nums)):
if nums[i] != nums_sorted[i]:
wrong_nodes.append(i)
val1, val2 = nums[wrong_nodes[0]], nums[wrong_nodes[1]]
def dfs(node):
if node is None:
return node
if node.val == val1:
node.val = val2
elif node.val == val2:
node.val = val1
dfs(node.left)
dfs(node.right)
dfs(root)
return root
