[找小伙伴一起刷题] 一起锻炼大脑。

有几年没刷题了，感觉自己变笨了。

刷题第一轮， 我的计划是按照topic刷，sort by frequency。把频率绿色的刷掉。

Day 1

先刷backtracking

https://leetcode.com/problems/generate-parentheses/
backtracking就用backtracking的做法

这道题的时间和空间复杂度算起来比较复杂。。。

1. class Solution(object):
   
2.     def generateParenthesis(self, n):
   
3.         """
   
4.         :type n: int
   
5.         :rtype: List[str]
   
6.         """
   
7.         self.n = n
   
8.         res = []
   
9.         self.dfs(0, 0, "", res)
   
10.         return res
    
11.     def dfs(self, left, right, cur, res):
    
12.         if right > left or right > self.n or left > self.n:
    
13.             return
    
14.         if left == right == self.n:
    
15.             res.append(cur)
    
16.             return
    
17.         self.dfs(left+1, right, cur+'(', res)
    
18.         self.dfs(left, right+1, cur+')', res)
    
19.         
    
20.         

复制代码

https://leetcode.com/problems/regular-expression-matching

这道题的时间和空间复杂度好像都很难算。

1. class Solution(object):
   
2.     def firstCharMatch(self, s, p):
   
3.         return len(s) > 0 and len(p) > 0 and p[0] in {'.', s[0]}
   
4.     def isMatch(self, s, p):
   
5.         """
   
6.         :type s: str
   
7.         :type p: str
   
8.         :rtype: bool
   
9.         """
   
10.         if len(p) == 0:
    
11.             return len(s) == 0
    
12.         if len(p) > 1 and p[1] == '*':
    
13.             return self.isMatch(s, p[2:]) or (self.firstCharMatch(s, p) and self.isMatch(s[1:], p))
    
14.         else:
    
15.             return self.firstCharMatch(s, p) and self.isMatch(s[1:], p[1:])
    
16.             

复制代码

Day 3

刚才刷了全部combination sum一共四道题。现在回来刷backtracking， 还差四道题就刷完backtracking的绿色部分了。我刷到两点出门玩～ 开森。

https://leetcode.com/problems/wildcard-matching/
11:38AM - 12:23PM

这是一道好烦人的题，重要的是要记住s和p的星星开始的位置。

1. class Solution(object):
   
2.     def isMatch(self, s, p):
   
3.         """
   
4.         :type s: str
   
5.         :type p: str
   
6.         :rtype: bool
   
7.         """
   
8.         si = pi = 0
   
9.         stari = starsi = -1
   
10.         while si<len(s):
    
11.             if pi < len(p) and p[pi] in {'?', s[si]}:
    
12.                 si+=1
    
13.                 pi+=1
    
14.             elif pi < len(p) and p[pi] == '*':
    
15.                 stari = pi
    
16.                 starsi = si
    
17.                 pi += 1
    
18.             elif stari > -1:
    
19.                 pi = stari+1
    
20.                 si = starsi+1
    
21.                 starsi = si
    
22.             else:
    
23.                 return False
    
24.         return all(x=='*' for x in p[pi:])
    
25.         

复制代码

https://leetcode.com/problems/permutations/
12:24PM - 12:27PM

1. class Solution(object):
   
2.     def permute(self, nums):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :rtype: List[List[int]]
   
6.         """
   
7.         res = []
   
8.         visited = set()
   
9.         def dfs(cur):
   
10.             if len(cur) == len(nums):
    
11.                 res.append(list(cur))
    
12.             for n in nums:
    
13.                 if n in visited:
    
14.                     continue
    
15.                 visited.add(n)
    
16.                 dfs(cur+[n])
    
17.                 visited.remove(n)
    
18.         dfs([])
    
19.         return res

复制代码

https://leetcode.com/problems/de ... rds-data-structure/
一看到这种题就是要用trie
12:28PM - 1:23PM 刚才顺便吃了个饭

1. class TrieNode:
   
2.     def __init__(self):
   
3.         self.children = collections.defaultdict(TrieNode)
   
4.         self.isWord = False
   
5. class WordDictionary:
   
6. 
   
7.     def __init__(self):
   
8.         """
   
9.         Initialize your data structure here.
   
10.         """
    
11.         self.root = TrieNode()
    
12.         
    
13. 
    
14.     def addWord(self, word: str) -> None:
    
15.         node = self.root
    
16.         for char in word:
    
17.             node = node.children[char]
    
18.         node.isWord = True
    
19.    
    
20.     def searchWord(self, word, node, index):
    
21.         if index == len(word):
    
22.             return node.isWord
    
23.         if word[index] == '.':
    
24.             for c in node.children.values():
    
25.                 if c and self.searchWord(word, c, index+1):
    
26.                     return True
    
27.             return False
    
28.         else:
    
29.             return node.children[word[index]] and self.searchWord(word, node.children[word[index]], index+1)
    
30. 
    
31.     def search(self, word: str) -> bool:
    
32.         return self.searchWord(word, self.root, 0)
    

复制代码

https://leetcode.com/problems/n-queens/
这个N皇后问题其实蛮简单的重要的是可以写清楚什么时候放皇后是valid的情况。然后用dfs。

1. class Solution:
   
2.    
   
3.     def isValid(self, row, col):
   
4.         for k in range(row):
   
5.             if self.queens[k][col] == 'Q':
   
6.                 return False
   
7.         for k in range(col):
   
8.             if self.queens[row][k] == 'Q':
   
9.                 return False
   
10.         
    
11.         for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
    
12.             if self.queens[i][j] == 'Q':
    
13.                 return False
    
14.         for i, j in zip(range(row-1, -1, -1), range(col+1, self.n)):
    
15.             if self.queens[i][j] == 'Q':
    
16.                 return False
    
17.         return True
    
18.    
    
19.     def dfs(self, row):
    
20.         if row == self.n:
    
21.             self.res.append(self.format_queens())
    
22.         for col in range(self.n):
    
23.             if self.isValid(row, col):
    
24.                 self.queens[row][col] = 'Q'
    
25.                 self.dfs(row+1)
    
26.                 self.queens[row][col] = '.'
    
27.    
    
28.     def format_queens(self):
    
29.         res = []
    
30.         for row in self.queens:
    
31.             res.append(''.join(row))
    
32.         return res
    
33.    
    
34.     def solveNQueens(self, n: int) -> List[List[str]]:
    
35.         self.n = n
    
36.         self.queens = [['.' for _ in range(n)] for _ in range(n)]
    
37.         self.res = []
    
38.         self.dfs(0)
    
39.         return self.res
    
40.         
    
41.         

复制代码

1:24PM -

Day 3

刚才写了三道题不知道为啥没有了？

https://leetcode.com/problems/wildcard-matching/
这道题的重点是找到星号开始的地方

1. class Solution(object):
   
2.     def isMatch(self, s, p):
   
3.         """
   
4.         :type s: str
   
5.         :type p: str
   
6.         :rtype: bool
   
7.         """
   
8.         si = pi = 0
   
9.         stari = starsi = -1
   
10.         while si<len(s):
    
11.             if pi < len(p) and p[pi] in {'?', s[si]}:
    
12.                 si+=1
    
13.                 pi+=1
    
14.             elif pi < len(p) and p[pi] == '*':
    
15.                 stari = pi
    
16.                 starsi = si
    
17.                 pi += 1
    
18.             elif stari > -1:
    
19.                 pi = stari+1
    
20.                 si = starsi+1
    
21.                 starsi = si
    
22.             else:
    
23.                 return False
    
24.         return all(x=='*' for x in p[pi:])
    
25.         

复制代码

https://leetcode.com/problems/permutations/
一秒做完

1. class Solution(object):
   
2.     def permute(self, nums):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :rtype: List[List[int]]
   
6.         """
   
7.         res = []
   
8.         visited = set()
   
9.         def dfs(cur):
   
10.             if len(cur) == len(nums):
    
11.                 res.append(list(cur))
    
12.             for n in nums:
    
13.                 if n in visited:
    
14.                     continue
    
15.                 visited.add(n)
    
16.                 dfs(cur+[n])
    
17.                 visited.remove(n)
    
18.         dfs([])
    
19.         return res

复制代码

https://leetcode.com/problems/de ... rds-data-structure/
这道题用Trie

1. class TrieNode:
   
2.     def __init__(self):
   
3.         self.children = collections.defaultdict(TrieNode)
   
4.         self.isWord = False
   
5. class WordDictionary:
   
6. 
   
7.     def __init__(self):
   
8.         """
   
9.         Initialize your data structure here.
   
10.         """
    
11.         self.root = TrieNode()
    
12.         
    
13. 
    
14.     def addWord(self, word: str) -> None:
    
15.         node = self.root
    
16.         for char in word:
    
17.             node = node.children[char]
    
18.         node.isWord = True
    
19.    
    
20.     def searchWord(self, word, node, index):
    
21.         if index == len(word):
    
22.             return node.isWord
    
23.         if word[index] == '.':
    
24.             for c in node.children.values():
    
25.                 if c and self.searchWord(word, c, index+1):
    
26.                     return True
    
27.             return False
    
28.         else:
    
29.             return node.children[word[index]] and self.searchWord(word, node.children[word[index]], index+1)
    
30. 
    
31.     def search(self, word: str) -> bool:
    
32.         return self.searchWord(word, self.root, 0)
    

复制代码

https://leetcode.com/problems/n-queens/

这题其实不难，主要是把valid情况写清楚，然后用dfs

1. class Solution:
   
2.    
   
3.     def isValid(self, row, col):
   
4.         for k in range(row):
   
5.             if self.queens[k][col] == 'Q':
   
6.                 return False
   
7.         for k in range(col):
   
8.             if self.queens[row][k] == 'Q':
   
9.                 return False
   
10.         
    
11.         for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
    
12.             if self.queens[i][j] == 'Q':
    
13.                 return False
    
14.         for i, j in zip(range(row-1, -1, -1), range(col+1, self.n)):
    
15.             if self.queens[i][j] == 'Q':
    
16.                 return False
    
17.         return True
    
18.    
    
19.     def dfs(self, row):
    
20.         if row == self.n:
    
21.             self.res.append(self.format_queens())
    
22.         for col in range(self.n):
    
23.             if self.isValid(row, col):
    
24.                 self.queens[row][col] = 'Q'
    
25.                 self.dfs(row+1)
    
26.                 self.queens[row][col] = '.'
    
27.    
    
28.     def format_queens(self):
    
29.         res = []
    
30.         for row in self.queens:
    
31.             res.append(''.join(row))
    
32.         return res
    
33.    
    
34.     def solveNQueens(self, n: int) -> List[List[str]]:
    
35.         self.n = n
    
36.         self.queens = [['.' for _ in range(n)] for _ in range(n)]
    
37.         self.res = []
    
38.         self.dfs(0)
    
39.         return self.res
    
40.         
    
41.         

复制代码

好了 backtracking绿色frequency部分写完了。可以出去玩啦。开森。

Day 3
今天起床比较晚。吃了两片面包。开始刷，等下出去玩。

这里把一系列的combination都做掉好了。

10:09AM - 10:26AM
https://leetcode.com/problems/combination-sum/

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

复制代码

10:26AM - 10:29AM
https://leetcode.com/problems/combinations/

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

复制代码

https://leetcode.com/problems/combination-sum-ii/
10:29AM - 11:05AM
这道题和之前的combination sum最大的区别是不能有重复的数字。

1. class Solution(object):
   
2.     def combinationSum2(self, candidates, target):
   
3.         """
   
4.         :type candidates: List[int]
   
5.         :type target: int
   
6.         :rtype: List[List[int]]
   
7.         """
   
8.         candidates = sorted(candidates)
   
9.         res = []
   
10.         print(candidates)
    
11.         def dfs(index, current, target):
    
12.             if target == 0:
    
13.                 res.append(list(current))
    
14.             if target < 0:
    
15.                 return
    
16.             for i in range(index, len(candidates)):
    
17.                 if candidates[i] > target:
    
18.                     break
    
19.                 if i > index and candidates[i] == candidates[i-1]:
    
20.                     continue
    
21.                 current.append(candidates[i])
    
22.                 dfs(i+1, current, target-candidates[i])
    
23.                 current.pop()
    
24.         dfs(0, [], target)
    
25.         return res
    
26.         

复制代码

https://leetcode.com/problems/combination-sum-iii/

11:06AM - 11:13AM

1. class Solution(object):
   
2.     def combinationSum3(self, k, n):
   
3.         """
   
4.         :type k: int
   
5.         :type n: int
   
6.         :rtype: List[List[int]]
   
7.         """
   
8.         res = []
   
9.         
   
10.         def dfs(current_number, current, target):
    
11.             if target == 0 and len(current) == k:
    
12.                 res.append(list(current))
    
13.             if target < 0 or len(current) >= k:
    
14.                 return
    
15.             for i in range(current_number, 10):
    
16.                 if i > target:
    
17.                     break
    
18.                 dfs(i+1, current+[i], target-i)
    
19.         dfs(1, [], n)
    
20.         return res
    
21.             
    
22.                     
    
23.         

复制代码

Day 1
https://leetcode.com/problems/word-search/

1. class Solution(object):
   
2.     def exist(self, board, word):
   
3.         """
   
4.         :type board: List[List[str]]
   
5.         :type word: str
   
6.         :rtype: bool
   
7.         """
   
8.         for row in range(len(board)):
   
9.             for col in range(len(board[0])):
   
10.                 if self.search(board, row, col, word):
    
11.                     return True
    
12.         return False
    
13.    
    
14.     def search(self, board, row, col, word):
    
15.         if len(word) == 0:
    
16.             return True
    
17.         if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]) or board[row][col] != word[0]:
    
18.             return False
    
19.         board[row][col] = '#'
    
20.         for (i, j) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
    
21.             res = self.search(board, row+i, col+j, word[1:])
    
22.             if res:
    
23.                 break
    
24.         board[row][col] = word[0]
    
25.         return res
    
26.             

复制代码

加个微信 一起刷题

我想请问，刷题有标准答案吗？我都只看到题目没有看到代码

求组队 紫薯紫薯

加油 一起刷题！ 可以拉个群

加个微信一起刷题

加我一个来来

加我一个，请问怎么加啊