有效的数独

Date:2020-10-05 周一
image.png

  1. class Solution:
  2.     def isHas(self,board:List[str]) ->bool:
  3.         valueList = [0,0,0,0,0,0,0,0,0]
  4.         for val in board:
  5.             if val == ".":
  6.                 pass
  7.             elif int(val) > 9 or int(val) < 1:
  8.                 return False
  9.             else:
  10.                 val = int(val) - 1
  11.                 if(valueList[val] != 0):
  12.                     return False
  13.                 valueList[val] = 1
  14.         return True
  15.     def isValidSudoku(self, board: List[List[str]]) -> bool:
  16.         #检查行是否符合
  17.         for i in range(9):
  18.             result = self.isHas(board[i])
  19.             if not result:
  20.                 return False
  21.         #检查列是否符合
  22.         for j in range(9):
  23.             vauleList = []
  24.             for i in range(9):
  25.                 vauleList.append(board[i][j])
  26.             result = self.isHas(vauleList)
  27.             if not result:
  28.                 return False            
  29.         #检查3x3矩阵是否符合
  30.         index = 0
  31.         while index < 9:
  32.             vauleList = []
  33.             mid = index % 3
  34.             rows = range(mid * 3,(mid + 1) * 3)
  35.             if index < 3 :
  36.                 cols = range(0,3)
  37.             elif index < 6 :
  38.                 cols = range(3,6)
  39.             else:
  40.                 cols = range(6,9)
  41.             for i in rows:
  42.                 for j in cols:
  43.                     vauleList.append(board[i][j])
  44.             result = self.isHas(vauleList)
  45.             if not result:
  46.                 return False    
  47.             index +=1        
  48.         return True

官方解法-一次遍历

image.png

  1. class Solution:
  2.     def isValidSudoku(self, board):
  3.         """
  4.         :type board: List[List[str]]
  5.         :rtype: bool
  6.         """
  7.         # init data
  8.         rows = [{} for i in range(9)]
  9.         columns = [{} for i in range(9)]
  10.         boxes = [{} for i in range(9)]
  12.         # validate a board
  13.         for i in range(9):
  14.             for j in range(9):
  15.                 num = board[i][j]
  16.                 if num != '.':
  17.                     num = int(num)
  18.                     box_index = (i // 3 ) * 3 + j // 3
  20.                     # keep the current cell value
  21.                     rows[i][num] = rows[i].get(num, 0) + 1
  22.                     columns[j][num] = columns[j].get(num, 0) + 1
  23.                     boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
  25.                     # check if this value has been already seen before
  26.                     if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
  27.                         return False         
  28.         return True

解数独**

Date:2020-10-05 周一
image.png

递归

image.png

  1. class Solution:
  2.     def solveSudoku(self, board: List[List[str]]) -> None:
  3.         def dfs(pos: int):
  4.             nonlocal valid #nonlocal关键字用来在函数或其他作用域中使用外层(非全局)变量。
  5.             if pos == len(spaces):
  6.                 valid = True
  7.                 return
  9.             i, j = spaces[pos]
  10.             for digit in range(9):
  11.                 if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
  12.                     line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
  13.                     board[i][j] = str(digit + 1)
  14.                     dfs(pos + 1)
  15.                     line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
  16.                 if valid:
  17.                     return
  19.         line = [[False] * 9 for _ in range(9)]
  20.         column = [[False] * 9 for _ in range(9)]
  21.         block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
  22.         valid = False
  23.         spaces = list()
  25.         for i in range(9):
  26.             for j in range(9):
  27.                 if board[i][j] == ".":
  28.                     spaces.append((i, j))
  29.                 else:
  30.                     digit = int(board[i][j]) - 1
  31.                     line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
  33.         dfs(0)

组合总和**

Date:2020-10-07 周三
image.png

回溯+剪枝

image.png
image.pngimage.pngimage.png

  1. class Solution:
  2.     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
  3.         def dfs(candidates,begin,size,path,res,target):
  4.             if target < 0:
  5.                 return
  6.             if target == 0:
  7.                 res.append(path)
  8.                 return
  9.             for index in range(begin,size):
  10.                 dfs(candidates,index,size,path+[candidates[index]],res,target - candidates[index]) #[1, 2] + [3] 语法生成了新的列表
  11.         size = len(candidates)
  12.         if size == 0:
  13.             return []
  14.         path = []
  15.         res = []
  16.         dfs(candidates,0,size,path,res,target)
  17.         return res

组合总和Ⅱ**

Date:2020-10-07 周三
image.png

自己写的半吊子回溯

  1. class Solution:
  2.     def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
  3.         candidates.sort()
  5.         def dfs(candidates,begin,end,path,res,used,target):
  6.             if target < 0:
  7.                 return
  8.             if target == 0:
  9.                 res.add(str(path))
  10.                 # res.append(path)
  11.                 return
  12.             for i in range(begin,end):
  13.                 if used[i] == False:
  14.                     used[i] = True
  15.                     dfs(candidates,i,end,path + [candidates[i]],res,used,target - candidates[i])
  16.                     used[i] = False
  17.         end = len(candidates)
  18.         if end == 0:
  19.             return []
  20.         used = [False] * end
  21.         path = []
  22.         res = set()
  23.         dfs(candidates,0,end,path,res,used,target)
  24.         result = []
  25.         for val in res:
  26.             val = val[1:len(val)-1]
  27.             midList = []
  28.             for mid in val.split(","):
  29.                 midList.append(int(mid))
  30.             result.append(midList)
  31.         return result

大佬思路（重点是去重）

image.png
image.pngimage.png
image.png

  1. from typing import List
  4. class Solution:
  6.     def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
  7.         def dfs(begin, path, residue):
  8.             if residue == 0:
  9.                 res.append(path[:])
  10.                 return
  12.             for index in range(begin, size):
  13.                 if candidates[index] > residue:
  14.                     break
  16.                 if index > begin and candidates[index - 1] == candidates[index]:
  17.                     continue
  19.                 path.append(candidates[index])
  20.                 dfs(index + 1, path, residue - candidates[index])
  21.                 path.pop()
  23.         size = len(candidates)
  24.         if size == 0:
  25.             return []
  27.         candidates.sort()
  28.         res = []
  29.         dfs(0, [], target)
  30.         return res

缺失的第一个正数*

Date:2020-10-08 周四
image.png

又又没看到题目时间复杂度要求

  1. class Solution:
  2.     def firstMissingPositive(self, nums: List[int]) -> int:
  3.         nums.sort()
  4.         index = 0
  5.         while index < len(nums) and nums[index] <= 0: index += 1
  6.         num = 1
  7.         while index < len(nums) and nums[index] == num:
  8.             if index != len(nums) - 1 and nums[index] == nums[index + 1]:
  9.                 index += 1
  10.                 continue
  11.             num += 1
  12.             index += 1
  13.         return num

没看到时间复杂度要求做的，多了排序的过程。
image.png

哈希表

image.pngimage.png

  1. class Solution:
  2.     def firstMissingPositive(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         for i in range(n):
  5.             if nums[i] <= 0:
  6.                 nums[i] = n + 1
  8.         for i in range(n):
  9.             num = abs(nums[i])
  10.             if num <= n:
  11.                 nums[num - 1] = -abs(nums[num - 1])
  13.         for i in range(n):
  14.             if nums[i] > 0:
  15.                 return i + 1
  17.         return n + 1

接雨水**

Date:2020-10-08 周四
image.png

暴力（会超时）

image.png

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         ans = 0
  4.         for i in range(len(height)):
  5.             max_left, max_right = 0,0
  6.             # 寻找 max_left
  7.             for j in range(0,i):
  8.                 max_left = max(max_left,height[j])
  9.             # 寻找 max_right
  10.             for j in range(i,len(height)):
  11.                 max_right = max(max_right,height[j])
  12.             if min(max_left,max_right) > height[i]:
  13.                 ans += min(max_left,max_right) - height[i]
  15.         return ans

动态规划

image.png
image.png
image.png

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         # 边界条件
  4.         if not height: return 0
  5.         n = len(height)
  6.         maxleft = [0] * n
  7.         maxright = [0] * n
  8.         ans = 0
  9.         # 初始化
  10.         maxleft[0] = height[0]
  11.         maxright[n-1] = height[n-1]
  12.         # 设置备忘录，分别存储左边和右边最高的柱子高度
  13.         for i in range(1,n):
  14.             maxleft[i] = max(height[i],maxleft[i-1])
  15.         for j in range(n-2,-1,-1):
  16.             maxright[j] = max(height[j],maxright[j+1])
  17.         # 一趟遍历，比较每个位置可以存储多少水
  18.         for i in range(n):
  19.             if min(maxleft[i],maxright[i]) > height[i]:
  20.                 ans += min(maxleft[i],maxright[i]) - height[i]
  21.         return ans

双指针

image.png
image.png

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         # 边界条件
  4.         if not height: return 0
  5.         n = len(height)
  7.         left,right = 0, n - 1  # 分别位于输入数组的两端
  8.         maxleft,maxright = height[0],height[n - 1]
  9.         ans = 0
  11.         while left <= right:
  12.             maxleft = max(height[left],maxleft)
  13.             maxright = max(height[right],maxright)
  14.             if maxleft < maxright:
  15.                 ans += maxleft - height[left]
  16.                 left += 1
  17.             else:
  18.                 ans += maxright - height[right]
  19.                 right -= 1
  21.         return ans

字符串相乘**

Date:2020-10-09 周五
image.png

无视要求做。。。

  1. class Solution:
  2.     def getNum(self,num:str)->int:
  3.         return {"0":0,"1":1,"2":2,"3":3,"4":4,"5":5,"6":6,"7":7,"8":8,"9":9}.get(num,-1)
  4.     def multiply(self, num1: str, num2: str) -> str:
  5.         numInt1 = numInt2 = 0
  6.         index1 , index2 = (len(num1) - 1),(len(num2) - 1)
  7.         w = 0
  8.         while index1 >= 0:
  9.             numInt1 += self.getNum(num1[index1]) * (10 ** w)
  10.             w += 1
  11.             index1 -= 1
  12.         w = 0
  13.         while index2 >= 0:
  14.             numInt2 += self.getNum(num2[index2]) * (10 ** w)
  15.             w += 1
  16.             index2 -= 1
  17.         print(numInt1," ",numInt2)
  18.         return str(numInt1 * numInt2)

好吧，又是我没看清题意。。

做加法

image.png

  1. class Solution:
  2.     def multiply(self, num1: str, num2: str) -> str:
  3.         if num1 == "0" or num2 == "0":
  4.             return "0"
  6.         ans = "0"
  7.         m, n = len(num1), len(num2)
  8.         for i in range(n - 1, -1, -1):
  9.             add = 0
  10.             y = int(num2[i])
  11.             curr = ["0"] * (n - i - 1)
  12.             for j in range(m - 1, -1, -1):
  13.                 product = int(num1[j]) * y + add
  14.                 curr.append(str(product % 10))
  15.                 add = product // 10
  16.             if add > 0:
  17.                 curr.append(str(add))
  18.             curr = "".join(curr[::-1])
  19.             ans = self.addStrings(ans, curr)
  21.         return ans
  23.     def addStrings(self, num1: str, num2: str) -> str:
  24.         i, j = len(num1) - 1, len(num2) - 1
  25.         add = 0
  26.         ans = list()
  27.         while i >= 0 or j >= 0 or add != 0:
  28.             x = int(num1[i]) if i >= 0 else 0
  29.             y = int(num2[j]) if j >= 0 else 0
  30.             result = x + y + add
  31.             ans.append(str(result % 10))
  32.             add = result // 10
  33.             i -= 1
  34.             j -= 1
  35.         return "".join(ans[::-1])

image.png

做乘法

image.png
image.pngimage.pngimage.pngimage.png

  1. class Solution:
  2.     def multiply(self, num1: str, num2: str) -> str:
  3.         if num1 == "0" or num2 == "0":
  4.             return "0"
  6.         m, n = len(num1), len(num2)
  7.         ansArr = [0] * (m + n)
  8.         for i in range(m - 1, -1, -1):
  9.             x = int(num1[i])
  10.             for j in range(n - 1, -1, -1):
  11.                 ansArr[i + j + 1] += x * int(num2[j])
  13.         for i in range(m + n - 1, 0, -1):
  14.             ansArr[i - 1] += ansArr[i] // 10
  15.             ansArr[i] %= 10
  17.         index = 1 if ansArr[0] == 0 else 0
  18.         ans = "".join(str(x) for x in ansArr[index:])
  19.         return ans

通配符匹配**

Date:2020-10-10 周六
好家伙。。。果然直接硬解是不行的。。。只想到了是与T10的正则表达式类似的题，可能需要用DP，但是没敢尝试。。。

错误代码！！警示自己

image.png

贪心算法

image.png

  1. // 我们用 sIndex 和 pIndex 表示当前遍历到 s 和 p 的位置
  2. // 此时我们正在 s 中寻找某个 u_i
  3. // 其在 s 和 p 中的起始位置为 sRecord 和 pRecord
  5. // sIndex 和 sRecord 的初始值为 0
  6. // 即我们从字符串 s 的首位开始匹配
  7. sIndex = sRecord = 0
  9. // pIndex 和 pRecord 的初始值为 1
  10. // 这是因为模式 p 的首位是星号，那么 u_1 的起始位置为 1
  11. pIndex = pRecord = 1
  13. while sIndex < s.length and pIndex < p.length do
  14.     if p[pIndex] == '*' then
  15.         // 如果遇到星号，说明找到了 u_i，开始寻找 u_i+1
  16.         pIndex += 1
  17.         // 记录下起始位置
  18.         sRecord = sIndex
  19.         pRecord = pIndex
  20.     else if match(s[sIndex], p[pIndex]) then
  21.         // 如果两个字符可以匹配，就继续寻找 u_i 的下一个字符
  22.         sIndex += 1
  23.         pIndex += 1
  24.     else if sRecord + 1 < s.length then
  25.         // 如果两个字符不匹配，那么需要重新寻找 u_i
  26.         // 枚举下一个 s 中的起始位置
  27.         sRecord += 1
  28.         sIndex = sRecord
  29.         pIndex = pRecord
  30.     else
  31.         // 如果不匹配并且下一个起始位置不存在，那么匹配失败
  32.         return False
  33.     end if
  34. end while
  36. // 由于 p 的最后一个字符是星号，那么 s 未匹配完，那么没有关系
  37. // 但如果 p 没有匹配完，那么 p 剩余的字符必须都是星号
  38. return all(p[pIndex] ~ p[p.length - 1] == '*')

image.png

  1. class Solution:
  2.     def isMatch(self, s: str, p: str) -> bool:
  3.         def allStars(st: str, left: int, right: int) -> bool:
  4.             return all(st[i] == '*' for i in range(left, right))
  6.         def charMatch(u: str, v: str) -> bool:
  7.             return u == v or v == '?'
  9.         sRight, pRight = len(s), len(p)
  10.         while sRight > 0 and pRight > 0 and p[pRight - 1] != '*':
  11.             if charMatch(s[sRight - 1], p[pRight - 1]):
  12.                 sRight -= 1
  13.                 pRight -= 1
  14.             else:
  15.                 return False
  17.         if pRight == 0:
  18.             return sRight == 0
  20.         sIndex, pIndex = 0, 0
  21.         sRecord, pRecord = -1, -1
  22.         while sIndex < sRight and pIndex < pRight:
  23.             if p[pIndex] == '*':
  24.                 pIndex += 1
  25.                 sRecord, pRecord = sIndex, pIndex
  26.             elif charMatch(s[sIndex], p[pIndex]):
  27.                 sIndex += 1
  28.                 pIndex += 1
  29.             elif sRecord != -1 and sRecord + 1 < sRight:
  30.                 sRecord += 1
  31.                 sIndex, pIndex = sRecord, pRecord
  32.             else:
  33.                 return False
  35.         return allStars(p, pIndex, pRight)

image.png

跳跃游戏Ⅱ*

Date:2020-10-10 周六
image.png

暴力递归（超时）

  1. class Solution:
  2.     def jump(self, nums: List[int]) -> int:
  3.         ans = -1
  4.         def dfs(nums: List[int] , index: int, step: int):
  5.             nonlocal ans
  6.             if index == len(nums) - 1:
  7.                 ans = min(ans,step) if ans != -1 else step
  8.                 return
  9.             if index >= len(nums):
  10.                 return
  11.             for i in range(nums[index],0,-1):
  12.                 dfs(nums,index + i,step + 1)
  13.             return 
  15.         dfs(nums,0,0)
  16.         return  ans

贪心算法

反向查找出发位置

image.png
image.png

正向查找可到达的最大位置

image.png
image.png

  1. class Solution:
  2.     def jump(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         maxPos, end, step = 0, 0, 0
  5.         for i in range(n - 1):
  6.             if maxPos >= i:
  7.                 maxPos = max(maxPos, i + nums[i])
  8.                 if i == end:
  9.                     end = maxPos
  10.                     step += 1
  11.         return step

全排列

Date:2020-10-11 周日
image.png

递归

  1. class Solution:
  2.     def permute(self, nums: List[int]) -> List[List[int]]:
  3.         ans = []
  4.         def dfs(nums: List[int],numsUsed: List[bool],path: List[int]):
  5.             nonlocal ans
  6.             if len(path) == len(nums):
  7.                 ans.append(path)
  8.                 return
  9.             for i in range(len(nums)):
  10.                 if numsUsed[i] == False:
  11.                     numsUsed[i] = True
  12.                     dfs(nums,numsUsed,path + [nums[i]])
  13.                     numsUsed[i] = False
  14.             return
  16.         numsUsed = [False] * len(nums)
  17.         dfs(nums,numsUsed,[])
  18.         return ans

全排列Ⅱ

Date:2020-10-12 周一
image.png

递归+剪枝

  1. class Solution:
  2.     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
  3.         ans = []
  4.         def dfs(nums: List[int],numsUsed: List[bool],path: List[int]):
  5.             nonlocal ans
  6.             if len(path) == len(nums):
  7.                 ans.append(path)
  8.                 return
  9.             for i in range(len(nums)):
  10.                 if numsUsed[i] == False:
  11.                     # 剪枝
  12.                     if i > 0 and numsUsed[i - 1] == False and nums[i] == nums[i - 1]:
  13.                         continue
  14.                     numsUsed[i] = True
  15.                     dfs(nums,numsUsed,path + [nums[i]])
  16.                     numsUsed[i] = False
  17.             return
  19.         numsUsed = [False] * len(nums)
  20.         nums.sort() #先排序
  21.         dfs(nums,numsUsed,[])
  22.         return ans

image.png
剪枝是减去重复的树枝，只保留顺序的树枝，比如 [1,1,2] ，为了方便记做 [1,1’,2] 。只保留1 -> 1’ -> 2这样的顺序枝，而认为1’ -> 1 -> 2 这样的就是重复枝，把他剪掉。所以顺序枝的特点是遍历在重复的第二节点的时候其前一个数值相等的节点肯定遍历过。所以根据这个特点就可以精确剪枝了。

旋转图像

Date:2020-10-12 周一
image.png

DFS + 递推公式

这道题就是需要找规律。旋转90度体现在坐标上就是(i , j) -> (j , n - i)。每个位置都会存在一个圈圈，每四个为一圈（中心点除外）。每次DFS去顺时针挪动这四个对应位置的值即可。

  1. import math
  2. # (i , j) -> (j , n - i)
  3. class Solution:
  4.     def rotate(self, matrix: List[List[int]]) -> None:
  5.         if not matrix:
  6.             return
  7.         def dfs(matrix: List[List[int]],i:int,j:int,step:int,val:int):
  8.             mid = matrix[i][j]
  9.             if val != -999:  
  10.                 matrix[i][j] = val
  11.             if step == 4:
  12.                 return
  13.             dfs(matrix,j,(n - 1 - i),step + 1,mid)
  14.             return
  15.         n = len(matrix)
  16.         for i in range(0,math.ceil(n / 2)):
  17.             for j in range(i,n - i - 1):
  18.                 dfs(matrix,i,j,0,-999)

字母异位词分组*

Date:2020-10-13 周二
image.png

暴力（超时）

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def isMatch(str1:str,str2:str) -> bool: #匹配算法
            if str1 == "" and str2 == "":
                return True
            elif str1 == "" or str2 == "":
                return False
            elif len(str1) != len(str2):
                return False
            for s in str1:
                if str2.find(s) == -1:
                    return False
                str2 = str2[0:str2.find(s)] + str2[str2.find(s) + 1 : ]
            return True
        def pushAns(ans:List[List[str]],strs:str):#分组算法
            if not ans:
                ans.append([strs])
            else:
                matched = False
                for i in range(len(ans)):
                    if isMatch(ans[i][0],strs):
                        ans[i].append(strs)
                        matched = True
                if not matched:
                    ans.append([strs])
        ans = []
        for val in strs:
            pushAns(ans,val)
        return ans

排序数组分类

image.png
image.png

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]: 
        ans = collections.defaultdict(list) 
        # defaultdict 标准字典包含setdefault（）方法，用于检索值并在值不存在时建立默认值 缺少key会返回一个默认值 defaultdict允许调用者在容器初始化时指定默认的预先设置。
        for s in strs:
            ans[tuple(sorted(s))].append(s) # tuple(sorted(s)) -> ('a' , 'e' , 'r')
         return list(ans.values())

按计数分类

image.png
image.png

class Solution:
    def groupAnagrams(strs):
        ans = collections.defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)
        return ans.values()

Power(x,n)**

Date:2020-10-13 周二
image.png

暴力（超时）

class Solution:
    def myPow(self, x: float, n: int) -> float:
        ans = 1.0
        if n >= 0:
            for _ in range(n):
                ans *= x
        else:
            for _ in range(abs(n)):
                ans *= (1 / x)
        return ans if ans <= (2 ** 31 - 1) and ans >=(- 2 ** 31) else (2 ** 31 - 1) if ans > 0 else (-2 ** 31)

快速幂 + 递归

image.png

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y * x

        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

image.png

快速幂 + 迭代

image.png

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            ans = 1.0
            # 贡献的初始值为 x
            x_contribute = x
            # 在对 N 进行二进制拆分的同时计算答案
            while N > 0:
                if N % 2 == 1:
                    # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x_contribute
                # 将贡献不断地平方
                x_contribute *= x_contribute
                # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                N //= 2
            return ans

        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

image.png

N皇后 **

Date:2020-10-14 周三
image.pngimage.png

回溯+基于集合

image.png
image.png
image.png

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(row: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    queens[row] = i
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)

        solutions = list()
        queens = [-1] * n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions

image.png

N皇后Ⅱ

Date:2020-10-14 周三
image.pngimage.png
**

回溯+基于集合

算法同上

螺旋矩阵*

Date:2020-10-15 周四
image.png

模拟

image.png

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:return []

        x=y=0                                     # 矩阵元素位置初始化
        res = []                                  # 初始化，存储遍历后的矩阵元素
        dx = [ 0, 1, 0,-1]                        # 方向：右，下，左，上
        dy = [ 1, 0,-1, 0]                        # 注：与通常平面坐标系 记号 不同
        di = 0                                    # 初始化方向变量
        visited = set()                           # 初始化集合，存储已走过的坐标
        m,n = len(matrix),len(matrix[0])          # 矩阵的行列 

        for i in range(m*n):                                     # 
            res.append(matrix[x][y])                             # 存储遍历矩阵过的元素
            visited.add((x,y))                                   # 存储遍历过的坐标
            tx,ty = x+dx[di],y+dy[di]                            # 先记录下一步坐标，用于判断下一步怎么走
            if 0<=tx<m and 0<=ty<n and (tx,ty) not in visited:   # 判断坐标是否需变向，且没有遍历过
                x,y = tx,ty                                       
            else:                                                
                di = (di+1)%4                                    # 改变方向，右下左上为一圈，防止方向坐标越界
                x,y = x + dx[di],y+dy[di]                        # 下一步坐标
        return res

跳跃游戏**

Date:2020-10-16 周五
image.png

暴力递归（超时）

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        ans = False
        def dfs(nums:List[int],index:int):
            nonlocal ans
            if index > len(nums) - 1 or ans == True:
                return
            if index == len(nums) - 1:
                ans = True
                return
            for i in range(nums[index],0,-1):
                dfs(nums,index + i)
            return
        dfs(nums,0)    
        return ans

贪心：正向查找可到达的最大位置

思想同上跳跃游戏Ⅱ。
image.png
image.png

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        ans = True
        n = len(nums)
        maxPos, end = 0, 0
        for i in range(n - 1):
            if maxPos >= i:
                maxPos = max(maxPos, i + nums[i])
                if i == end:
                    end = maxPos
        if maxPos < n - 1:
            ans = False
        return ans

插入区间*

Date:2020-10-17 周六
image.png

贪心

image.pngimage.pngimage.png

class Solution:
    def insert(self, intervals: 'List[Interval]', newInterval: 'Interval') -> 'List[Interval]':
        # init data
        new_start, new_end = newInterval
        idx, n = 0, len(intervals)
        output = []

        # add all intervals starting before newInterval
        while idx < n and new_start > intervals[idx][0]:
            output.append(intervals[idx])
            idx += 1

        # add newInterval
        # if there is no overlap, just add the interval
        if not output or output[-1][1] < new_start:
            output.append(newInterval)
        # if there is an overlap, merge with the last interval
        else:
            output[-1][1] = max(output[-1][1], new_end)

        # add next intervals, merge with newInterval if needed
        while idx < n:
            interval = intervals[idx]
            start, end = interval
            idx += 1
            # if there is no overlap, just add an interval
            if output[-1][1] < start:
                output.append(interval)
            # if there is an overlap, merge with the last interval
            else:
                output[-1][1] = max(output[-1][1], end)
        return output

image.png

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        i = 0 
        n = len(intervals)
        res = []
        # 找左边重合区域
        while i < n and newInterval[0] > intervals[i][1]:
            res.append(intervals[i])
            i += 1
        tmp = [newInterval[0], newInterval[1]]
        # 找右边重合区域
        while i < n and newInterval[1] >= intervals[i][0]:
            tmp[0] = min(tmp[0], intervals[i][0])
            tmp[1] = max(tmp[1], intervals[i][1])
            i += 1
        res.append(tmp)
        while i < n :
            res.append(intervals[i])
            i += 1
        return res

螺旋矩阵Ⅱ

Date:2020-10-17 周六
image.png

模拟

算法同上 螺旋矩阵

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]: 
        ans = [[0] * n  for _ in range(n)] 
        postions = [[0,1],[1,0],[0,-1],[-1,0]]
        posIndex = 0
        x , y = 0 , 0
        visited = set()
        for i in range(n * n):
            ans[x][y] = i + 1
            visited.add((x,y))
            tx = postions[posIndex][0] + x
            ty = postions[posIndex][1] + y
            if 0 <= tx < n and 0 <= ty < n and (tx,ty) not in visited:
                x , y = tx , ty
            else:
                posIndex = (posIndex + 1) % 4
                x , y = x + postions[posIndex][0] , postions[posIndex][1] + y
        return ans

第K个排列*

Date:2020-10-23 周五
image.png

暴力递归（超时）

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        if not n:
            return ""
        def dfs(nList:List[int] , used:List[bool],path:str):
            if len(path) == n:
                ans.append(path)
                return
            if len(ans) >= k:
                return
            for i in range(n):
                if used[i] == False:
                    used[i] = True
                    dfs(nList,used,path + str(nList[i]))
                    used[i] = False
            pass
        nList = []
        for i in range(n):
            nList.append(i+1)
        used = [False] * n
        ans = []
        dfs(nList,used,"")
        return ans[-1]

毫无疑问把暴力递归是可以的，但是这个题的随着n的增加，题目的复杂度是指数级别增长的。哪怕是让递归到题目要求的k时停止，还是会超时。
image.png

数学思路

image.png
image.png

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        allFactorial = [1, 1]
        for i in range(2, n+1):
            allFactorial.append(allFactorial[-1]*i)

        s, k, res = list(range(1, n+1)), k-1, ""
        for i in range(len(s)-1, -1, -1):
            res += str(s[k // allFactorial[i]])
            del s[k // allFactorial[i]]
            k %= allFactorial[i]
        return res

旋转链表

Date:2020-10-23 周五
image.png

空间换时间

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        listNode = []
        while head!=None:
            listNode.append(head)
            head = head.next
        index , k= (len(listNode) - k) % len(listNode) , len(listNode)
        indexNode = listNode[index]
        res = indexNode
        while k > 1:
            k -= 1
            index = (index + 1) % len(listNode)
            indexNode.next = listNode[index]
            indexNode = indexNode.next
        indexNode.next = None
        return res

不同路径*

Date:2020-10-24 周六
image.pngimage.png

暴力递归（超时）

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        res = 0
        def dfs(x:int,y:int):
            nonlocal res
            if x == n - 1 and y == m - 1:
                res += 1
            for i in range(2):
                tx = x + positions[i][0]
                ty = y + positions[i][1]
                if tx < n and ty < m:
                    dfs(tx,ty)
        positions = [[0,1] , [1,0]]
        dfs(0,0)
        return res

排列组合

image.png

def uniquePaths(self, m: int, n: int) -> int:
        return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))

动态规划

image.png

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
        print(dp)
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

动态规划(DP)+滚动数组

image.png

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [0 for _ in range(m)]
        f[0] = 1
        for i in range(0,n):
            for j in range(1,m):
                f[j] += f[j-1]
        return f[m-1]

不同路径Ⅱ

Date:2020-10-24 周六
image.png

动态规划

该题的答题思路同上题。只是题目中加上了障碍物，就需要去针对障碍物进行处理。
我们令 f[i][j] 是到达i , j 最多路径。动态方程仍然是f[i][j] = f[i - 1][j] + f[i][j - 1]。
在边界时需要注意：
第一行：如果全为0 f中第一行就全为1。如果一旦某点出现一个1，也就是意味着该点之后的所有点在f中都只能为0，因为此路不通。
第一列同理。
在遍历时只需要针对路障处理，只要点i , j为路障，就将其f[i][j]设为0，否则f[i][j] = f[i - 1][j] + f[i][j - 1]。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
      if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0
      rows , cols = len(obstacleGrid) , len(obstacleGrid[0])
      f = [[0] * cols for _ in range(rows)]
      f[0][0] = 1
      for j in range(1,cols):
        f[0][j] = 1 if obstacleGrid[0][j] == 0 and f[0][j - 1] == 1 else 0
      for i in range(1,rows):
        f[i][0] = 1 if obstacleGrid[i][0] == 0 and f[i - 1][0] == 1 else 0      
      for i in range(1,rows):
        for j in range(1,cols):
          if obstacleGrid[i][j] == 0:
            f[i][j] = f[i - 1][j] + f[i][j - 1]
          else:
            f[i][j] = 0
      return f[-1][-1]

最小路径和

Date:2020-10-24 周六
image.png

动态规划

res[i][j]为到达点(i,j)所走最短路径。
可以贪心的认为保证步步局部最优，最终所得到的即为全局最优。
由于只能向右或向下走，也就是说在点(i,j)时，到达该点的最短路径为到达点(i - 1,j)的最短路径和到达点(i,j - 1)最短路径中最小的那个加上其本身的所需距离，即为到达点(i ,j)的最短路径。
=> res[i][j] = min(res[i - 1][j],res[i][j - 1]) + grid[i][j]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
      rows , cols = len(grid) , len(grid[0])
      res = [[0] * cols for _ in range(rows)]
      res[0][0] = grid[0][0]
      for j in range(1,cols):
        res[0][j] = res[0][j - 1] + grid[0][j]
      for i in range(1,rows):
        res[i][0] = res[i - 1][0] + grid[i][0]      
      for i in range(1,rows):
        for j in range(1,cols):
          res[i][j] = min(res[i - 1][j],res[i][j - 1]) + grid[i][j]
      return res[-1][-1]

有效数字

Date:2020-10-25 周日
image.png

正则匹配

能够成功转成十进制的有”.1” “1.” “-01” “.1e3” “2.e3” “2e-3”等。即写出对应的正则表达式即可。

class Solution:
    def isNumber(self, s: str) -> bool:
      int()
      s = s.strip()
      if len(s) == 0:
        return False
      p_ne = re.compile(r'(^((\+|\-)?\d+\.{1}\d*)|((\+|\-)?\d*\.{1}\d+)|((\+|\-)?\d+)$)',re.I)
      p_e = re.compile(r'(^((\+|\-)?\d+\.{1}\d*e{1}(\+|\-)?\d+)|((\+|\-)?\d*\.{1}\d+e{1}(\+|\-)?\d+)|((\+|\-)?\d+e{1}(\+|\-)?\d+)$)',re.I)
      result = None
      if 'e' in s :
        result = re.search(p_e,s)
      else:
        result = re.search(p_ne,s)
      if result != None:
        # print(result.group())
        if len(result.group()) == len(s):
          return True
      return False

别人家的正则

class Solution:
    def isNumber(self, s: str) -> bool:
        return bool(re.match(r'\s*[+-]?([\d]+(\.[\d]*)?|\.[\d]+)(e[+-]?[\d]+)? *$', s))
# [\d]+(\.[\d]*)? 是一体的
或者是:
[+-]?((\d+(\.\d*)?)|\.\d+)([e][+-]?\d+)?

文本左右对齐

Date:2020-10-25 周日
image.pngimage.png
image.png

按照题意 硬解 （空间复杂度高）

就是先根据单词大小分组，然后再根据每行的单词数量进行计算所需空格数量，然后再根据题目要求进行将单词和空格合并。

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
      res = []
      wordLenList = []
      wordLen = 0
      rowsList = []
      for val in words:
        if wordLen + len(val) + len(rowsList) <= maxWidth:
          rowsList.append(val)
          wordLen += len(val)
        else:
          res.append(rowsList)
          wordLenList.append(wordLen)
          rowsList = [val]
          wordLen = len(val)
      if len(rowsList) != 0:
        res.append(rowsList)
        wordLenList.append(wordLen)
      for i in range(len(res)):
        row = ""
        sList = [0] * (len(res[i]) - 1)
        index = 0
        # 计算所需空格数
        if len(res[i]) == 1:
          sList.append(maxWidth - wordLenList[i])
        else:
          sNum = maxWidth - wordLenList[i] # 所需空格总数
          while sNum > 0:
            sList[index] = 1 + sList[index]
            index = (index + 1) % (len(res[i]) - 1)
            sNum -= 1
          if i == len(res) - 1: # 最后一行空格单独处理
            sList = [] 
            for _ in range(len(res[i]) - 1):
              sList.append(1)
            sList.append(maxWidth - wordLenList[i] - (len(res[i]) - 1)) 
        # print(sList)
        for j in range(len(res[i])):
          if j == len(res[i]) - 1:
            if i != len(res) - 1 and len(res[i]) != 1:
              row += res[i][j]
            else:
              row += res[i][j] + " " * sList[j]
          else:
            row += res[i][j] + " " * sList[j]
        res[i] = row
      return res

爬楼梯*

Date:2020-10-26 周一
image.png

直接递归（超时）

class Solution:
    def climbStairs(self, n: int) -> int:
      res = 0
      def dfs(n:int,path:int):
        nonlocal res
        if path == n:
          res += 1
          return
        if path > n:
          return
        for i in range(1,3):
          dfs(n,path+i)
        return
      dfs(n,0)
      return res

# 直接递归解法，容易超时，python可以加个缓存装饰器，这样也算是将递归转换成迭代的形式了
# 除了这种方式，还有增加步长来递归，变相的减少了重复计算
# 还有一种方法，在递归的同时，用数组记忆之前得到的结果，也是减少重复计算
class Solution:
    @functools.lru_cache(100)  # 缓存装饰器
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

动态规划

image.pngimage.pngimage.png

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <=2:
            return n
        dp = [0]*n
        dp[0] = 1
        dp[1] = 2
        for i in range(2,n):
            dp[i] = dp[i-1]+dp[i-2]
        return dp[n-1]

image.png

滚动数组

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        a = 1
        b = 2 
        for i in range(3,n+1):
            t = b
            b = a + b
            a = t
        return b

简化路径

Date:2020-10-26 周一
image.pngimage.png

正则+栈

import re
class Solution:
    def simplifyPath(self, path: str) -> str:
      path = re.sub(r'/+','/',path) # 替换连续的/
      if len(path) > 1 and path[-1] == "/": # 去除最后一个/
        path = path[0:-1]
      strList = path.split("/")
      stack = []
      for val in strList:
        if val == ".":
          continue
        elif val == ".." :
          if len(stack) > 1:
            stack.pop()
        else:
          stack.append(val)
      res = "/".join(stack) if len(stack) > 1 else "/"
      return res

编辑距离*

Date:2020-10-26 周一
image.png
image.png

动态规划

image.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.png

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n = len(word1)
        m = len(word2)

        # 有一个字符串为空串
        if n * m == 0:
            return n + m

        # DP 数组
        D = [ [0] * (m + 1) for _ in range(n + 1)]

        # 边界状态初始化
        for i in range(n + 1):
            D[i][0] = i
        for j in range(m + 1):
            D[0][j] = j

        # 计算所有 DP 值
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = D[i - 1][j] + 1
                down = D[i][j - 1] + 1
                left_down = D[i - 1][j - 1] 
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1
                D[i][j] = min(left, down, left_down)

        return D[n][m]

矩阵置零

Date:2020-10-27 周二

O(mn)的空间复杂度

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
      rows , cols = len(matrix) , len(matrix[0])
      mStr = ",".join(str(matrix[i][j]) for i in range(rows) for j in range(cols)).split(",")
      # print(mStr)
      for index in range(len(mStr)):
        if mStr[index] == "0":
          i , j  = index // cols ,  index % cols
          print(i,j)
          for mi in range(rows):
            matrix[mi][j] = 0
          for mj in range(cols):
            matrix[i][mj] = 0
      # print(matrix)
      pass

O(1)空间复杂度

image.png
image.png

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        is_col = False
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            # Since first cell for both first row and first column is the same i.e. matrix[0][0]
            # We can use an additional variable for either the first row/column.
            # For this solution we are using an additional variable for the first column
            # and using matrix[0][0] for the first row.
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, C):
                # If an element is zero, we set the first element of the corresponding row and column to 0
                if matrix[i][j]  == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        # Iterate over the array once again and using the first row and first column, update the elements.
        for i in range(1, R):
            for j in range(1, C):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        # See if the first row needs to be set to zero as well
        if matrix[0][0] == 0:
            for j in range(C):
                matrix[0][j] = 0

        # See if the first column needs to be set to zero as well        
        if is_col:
            for i in range(R):
                matrix[i][0] = 0

搜索二维矩阵

Date:2020-10-27 周二
image.pngimage.png
**

二分查找

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
      if not matrix:
        return False
      rows , cols = len(matrix) , len(matrix[0])
      sumLen = rows * cols
      left , right = 0 , sumLen - 1
      while left <= right:
        mid = (left + right) // 2
        i , j = mid // cols , mid % cols
        if matrix[i][j] == target:
          return True
        elif matrix[i][j] < target:
          left = mid + 1
        else:
          right = mid - 1
      return False

颜色分类

Date:2020-10-28 周三
image.png

单指针

image.png

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        n = len(nums)
        ptr = 0
        for i in range(n):
            if nums[i] == 0:
                nums[i], nums[ptr] = nums[ptr], nums[i]
                ptr += 1
        for i in range(ptr, n):
            if nums[i] == 1:
                nums[i], nums[ptr] = nums[ptr], nums[i]
                ptr += 1

image.png

双指针

image.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.pngimage.png

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        n = len(nums)
        p0 = p1 = 0
        for i in range(n):
            if nums[i] == 1:
                nums[i], nums[p1] = nums[p1], nums[i]
                p1 += 1
            elif nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                if p0 < p1:
                    nums[i], nums[p1] = nums[p1], nums[i]
                p0 += 1
                p1 += 1

最小覆盖子串

Date: 2020-10-28 周三
image.png

滑动窗口

image.pngimage.pngimage.png

    def minWindow(self, s: str, t: str) -> str:
        need=collections.defaultdict(int)
        for c in t:
            need[c]+=1
        needCnt=len(t)
        i=0
        res=(0,float('inf'))
        for j,c in enumerate(s):
            if need[c]>0:
                needCnt-=1
            need[c]-=1
            if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
                while True:      #步骤二：增加i，排除多余元素
                    c=s[i] 
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                if j-i<res[1]-res[0]:   #记录结果
                    res=(i,j)
                need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
                needCnt+=1
                i+=1
        return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

组合

Date: 2020-10-30 周四
image.png

递归

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def dfs(path:List[int]):
            if len(path) == k:
                res.append(path)
                return
            for index in range(n):
                if len(path)  == 0 or(len(path) > 0 and path[-1] < index + 1):
                    dfs(path+[index+1])
            return
        dfs([])
        return res

时空复杂度太高了。。。3000ms+了。
image.png

迭代器 - itertools函数

https://docs.python.org/zh-cn/3/library/itertools.html
image.png

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
         return list(itertools.combinations(range(1,n+1),k))

子集

Date: 2020-10-30 周四
image.png

迭代器 - itertools函数

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for n in range(1,len(nums) + 1):
            for l in list(itertools.combinations(nums,n)):
                res.append(list(l))
        return res

单词搜索

Date: 2020-10-30 周四
image.pngimage.png

DFS 回溯

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])

        visited = [[False] * n for _ in range(m)]
        rows = [-1, 0, 1, 0]
        cols = [0, 1, 0, -1]
        def dfs(x, y, idx):
            if board[x][y] != word[idx]:
                return False
            if idx == len(word) - 1:
                return True
            # 先标记
            visited[x][y] = True
            # 找到符合的字母时开始向四个方向扩散搜索
            for i in range(4):
                nx = x + rows[i]
                ny = y + cols[i]
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and dfs(nx, ny, idx+1):
                        return True
            # 扩散未搜索对应的字母，释放标记
            # 继续往其他方位搜索
            visited[x][y] = False
            return False
        for x in range(m):
            for y in range(n):
                if dfs(x, y, 0):
                    return True
        return False