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

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部分写完了。可以出去玩啦。开森。

不知道为什么没办法回复了。。。

hey123_1 发表于 2021-5-10 01:05
怎么加入呀 。

看我头像

改一下刷题记录的的格式。我不加答案了。。。

Day 3 2021-05-10
今天晚上的目标是干掉全部的BST。 7:00P到家吃饭吃掉五十分钟。。。

7:51PM-7:56PM https://leetcode.com/problems/validate-binary-search-tree/

7:56PM-8:23PM 中途去发了一会儿呆
https://leetcode.com/problems/inorder-successor-in-bst/

8:23PM - 8:36PM
我做法是创建iterator的时候全部inorder traverse一遍所有的node。
https://leetcode.com/problems/binary-search-tree-iterator/

8:36PM - 8:39PM
超级基础的一道题。。。。
https://leetcode.com/problems/search-in-a-binary-search-tree/

8:39PM - 8:43PM
https://leetcode.com/problems/insert-into-a-binary-search-tree/

8:43PM - 8:58PM
要找清楚BST每个node的前一个和后一个node是啥。
https://leetcode.com/problems/delete-node-in-a-bst/

9:07PM - 9:36PM
头好痛想睡觉了。。。 刷到困吧。
这道题，我之前用的heap做的。用bst的诀窍是，每个node存个count。
Kth Largest Element in a Stream

9:36PM - 9:43PM
https://leetcode.com/problems/lo ... r-of-a-binary-tree/

9:54PM 刷题有点无聊，😡 先去洗个澡。
10:08PM 洗完澡了。我洗澡好快啊。

10:08PM  
这道题就是，python里面没有treeset，是要自己写个bst的感觉。
https://leetcode.com/problems/contains-duplicate-iii/

10:16PM
https://leetcode.com/problems/balanced-binary-tree/

10:19PM
https://leetcode.com/problems/co ... binary-search-tree/

恋斌 发表于 2021-05-09 08:31:21
那问一下，想看答案，是只能看别人的解题思路了吗。。。

leetcode上题解有很多解题思路的，比较详细，不只是代码。

Day 3 2021-05-10

10:27PM 本来想去睡觉。但是头好痛睡不着，爬起来继续刷题好了。

10:36PM https://leetcode.com/problems/ba ... h-tree/submissions/

10:42PM
https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/
这道破题。其实用dfs就可以，但是还要判断这个subtree是不是bst，就有可能不是。

10:45PM
https://leetcode.com/problems/bi ... o-greater-sum-tree/


11:05PM头好痛啊。不刷题了。决定打一局王者，换种方式锻炼大脑。明天就是周一了，好好睡觉，好好工作。

Day 4 2021–05-11

9:30AM 起床先工作。
11:30AM         开了一个早上的会。 休息一下大脑。
12:26PM 吃了个饭，做道题再继续工作。
https://leetcode.com/problems/convert-bst-to-greater-tree/
这道题就是postorder然后把右边tree的sum加到自身的node val就可以。

12:44PM 这道题挺诡异的。先inorder找到一个tree的所有target-node.val值是多少，然后看root2里面有没有这个就可以了。
https://leetcode.com/problems/two-sum-bsts/

去工作啦。晚上再刷个几道题。

Day 5 2021–05-11 之前时间都搞错了。

今天太忙了只刷了一道题。https://leetcode.com/problems/meeting-rooms-ii/
明天继续。