77. Combinations: 简单的backtracking。
78. Subsets: 又是一道backtracking,backtracking的题目就是要注意进入和出来的条件和相应变量状态的改变。
79. Word Search: 又是一个backtracking的题目,但是不是简单的loop,而是访问上下左右四种情况,同时要维护一个visited矩阵防止重复。有一点写法上的小技巧是:for x, y in [(i-1, j),(i+1, j),(i, j-1), (i, j+1)]:,然后判断x, y是否在范围内,写成这样比较方便一些, 否则要写一堆if语句。
80 . Remove Duplicates from Sorted Array II: 这题还是花了十来分钟来做的。要点是考虑清楚复制的时机,和复制后的状态,已经是否需要更新index
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 2:
return len(nums)
prev = 1
tail = 2
while tail < len(nums):
if nums[prev] == nums[prev-1] == nums[tail]:
tail += 1
else:
nums[prev+1] = nums[tail]
prev += 1
tail += 1
return prev+1
81. Search in Rotated Sorted Array II: 这道题如果有重复项就无法用二分搜索法了。
82. Remove Duplicates from Sorted List II: 记录一个prev节点,和一个prev value,然后对于每一个节点都先对比一下next value,如果当前节点和之前的不一样而且和下一个也不一样,那么更新prev,然后对每一次循环更新prev value(这题做的时候有点着急了,所以做错了后就直接看以前的submission,重做一次)
86. Partition List: 这题想法很简单,就是用两个dummyhead,然后一个一个连上去就可以了
89. Gray Code: 对于一个valid的code,先把所有的code前面加0,然后把这个code reverse, 再所有的加1,再拼接就可以了。
90. Subsets II: 在进入下一层的时候,记得检查一下,if i > pos and nums[i] == nums[i-1]: continue
91. Decode Ways: 动态规划来做。初始化的时候比较麻烦,然后递推公式情况比较多,不过可以抓住当前char是否为0,还有两位数和是否在11~26之间来做。