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

hey123_1

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

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

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

class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
def dfs(index, current, target):
if target == 0:
res.append(list(current))
if target < 0:
return
for i in range(index, len(candidates)):
current.append(candidates[i])
dfs(i, current, target-candidates[i])
current.pop()
dfs(0, [], target)
return res

复制代码

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

class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
res = []
def dfs(index, current):
if len(current) == k:
res.append(list(current))
for i in range(index+1, n+1):
current.append(i)
dfs(i, current)
current.pop()
dfs(0, [])
return res

复制代码

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

class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = sorted(candidates)
res = []
print(candidates)
def dfs(index, current, target):
if target == 0:
res.append(list(current))
if target < 0:
return
for i in range(index, len(candidates)):
if candidates[i] > target:
break
if i > index and candidates[i] == candidates[i-1]:
continue
current.append(candidates[i])
dfs(i+1, current, target-candidates[i])
current.pop()
dfs(0, [], target)
return res

复制代码

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

11:06AM - 11:13AM

class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
res = []
def dfs(current_number, current, target):
if target == 0 and len(current) == k:
res.append(list(current))
if target < 0 or len(current) >= k:
return
for i in range(current_number, 10):
if i > target:
break
dfs(i+1, current+[i], target-i)
dfs(1, [], n)
return res

复制代码

hey123_1

Day 3
https://leetcode.com/problems/combination-sum-iv/

11:13AM - 11:30AM

class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums = sorted(nums)
mem = {0:1}
def calculate(remain, mem):
if remain in mem:
return mem[remain]
res = 0
for n in nums:
if remain - n < 0:
break
res += calculate(remain-n, mem)
mem[remain] = res
return res
calculate(target, mem)
return mem[target]

复制代码

匿名用户-RMMGT *2021-5-10 04:26:15* · 2021-5-10 04:26:15

Day 3

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

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

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

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
si = pi = 0
stari = starsi = -1
while si<len(s):
if pi < len(p) and p[pi] in {'?', s[si]}:
si+=1
pi+=1
elif pi < len(p) and p[pi] == '*':
stari = pi
starsi = si
pi += 1
elif stari > -1:
pi = stari+1
si = starsi+1
starsi = si
else:
return False
return all(x=='*' for x in p[pi:])

复制代码

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

class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
visited = set()
def dfs(cur):
if len(cur) == len(nums):
res.append(list(cur))
for n in nums:
if n in visited:
continue
visited.add(n)
dfs(cur+[n])
visited.remove(n)
dfs([])
return res

复制代码

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

class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word:
node = node.children[char]
node.isWord = True
def searchWord(self, word, node, index):
if index == len(word):
return node.isWord
if word[index] == '.':
for c in node.children.values():
if c and self.searchWord(word, c, index+1):
return True
return False
else:
return node.children[word[index]] and self.searchWord(word, node.children[word[index]], index+1)
def search(self, word: str) -> bool:
return self.searchWord(word, self.root, 0)

复制代码

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

class Solution:
def isValid(self, row, col):
for k in range(row):
if self.queens[k][col] == 'Q':
return False
for k in range(col):
if self.queens[row][k] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if self.queens[i][j] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, self.n)):
if self.queens[i][j] == 'Q':
return False
return True
def dfs(self, row):
if row == self.n:
self.res.append(self.format_queens())
for col in range(self.n):
if self.isValid(row, col):
self.queens[row][col] = 'Q'
self.dfs(row+1)
self.queens[row][col] = '.'
def format_queens(self):
res = []
for row in self.queens:
res.append(''.join(row))
return res
def solveNQueens(self, n: int) -> List[List[str]]:
self.n = n
self.queens = [['.' for _ in range(n)] for _ in range(n)]
self.res = []
self.dfs(0)
return self.res

复制代码

1:24PM -

hey123_1

Day 3

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

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

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
si = pi = 0
stari = starsi = -1
while si<len(s):
if pi < len(p) and p[pi] in {'?', s[si]}:
si+=1
pi+=1
elif pi < len(p) and p[pi] == '*':
stari = pi
starsi = si
pi += 1
elif stari > -1:
pi = stari+1
si = starsi+1
starsi = si
else:
return False
return all(x=='*' for x in p[pi:])

复制代码

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

class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
visited = set()
def dfs(cur):
if len(cur) == len(nums):
res.append(list(cur))
for n in nums:
if n in visited:
continue
visited.add(n)
dfs(cur+[n])
visited.remove(n)
dfs([])
return res

复制代码

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

class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word:
node = node.children[char]
node.isWord = True
def searchWord(self, word, node, index):
if index == len(word):
return node.isWord
if word[index] == '.':
for c in node.children.values():
if c and self.searchWord(word, c, index+1):
return True
return False
else:
return node.children[word[index]] and self.searchWord(word, node.children[word[index]], index+1)
def search(self, word: str) -> bool:
return self.searchWord(word, self.root, 0)

复制代码

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

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

class Solution:
def isValid(self, row, col):
for k in range(row):
if self.queens[k][col] == 'Q':
return False
for k in range(col):
if self.queens[row][k] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if self.queens[i][j] == 'Q':
return False
for i, j in zip(range(row-1, -1, -1), range(col+1, self.n)):
if self.queens[i][j] == 'Q':
return False
return True
def dfs(self, row):
if row == self.n:
self.res.append(self.format_queens())
for col in range(self.n):
if self.isValid(row, col):
self.queens[row][col] = 'Q'
self.dfs(row+1)
self.queens[row][col] = '.'
def format_queens(self):
res = []
for row in self.queens:
res.append(''.join(row))
return res
def solveNQueens(self, n: int) -> List[List[str]]:
self.n = n
self.queens = [['.' for _ in range(n)] for _ in range(n)]
self.res = []
self.dfs(0)
return self.res

复制代码

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

匿名用户-RMMGT *2021-5-10 04:36:05* · 2021-5-10 04:36:05

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

苏格拉底的猫

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

看我头像

hey123_1

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

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/

ZYwang_one

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

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

	23垅无效楼层，该帖已经被删除

	24垅无效楼层，该帖已经被删除

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

浏览过的版块