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

hey123_1

Day 2

最近身体很差，但是也要保证大脑锻炼。

9:05PM - 11:13PM 中途无聊的打了三场王者。。。没关系，打游戏也算是锻炼大脑。

https://leetcode.com/problems/word-break-ii/

class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
mems = {}
wordDict = set(wordDict)
def dfs(s):
if s in mems:
return mems[s]
res = []
if s in wordDict:
res.append(s)
for i in range(len(s)):
right = s[i:]
if right in wordDict:
res += [w+ ' ' + right for w in dfs(s[:i])]
mems[s] = res
return mems[s]
return dfs(s)

复制代码

https://leetcode.com/problems/sudoku-solver/

class Solution(object):
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
self.board = board
return self.dfs(0, 0)
def dfs(self, row, col):
if row == 9:
return True
if col >= 9:
return self.dfs(row+1, 0)
if self.board[row][col] != '.':
return self.dfs(row, col+1)
for i in range(1, 10):
c = str(i)
if not self.isValid(row, col, c):
continue
self.board[row][col] = c
if self.dfs(row, col+1):
return True
self.board[row][col] = '.'
return False
def isValid(self, row, col, val):
# row and column
for i in range(9):
if self.board[i][col] == val:
return False
if self.board[row][i] == val:
return False
grid_row = row - row%3
grid_col = col - col%3
for i in range(3):
for j in range(3):
if self.board[grid_row+i][grid_col+j] == val:
return False
return True

复制代码

hey123_1

Day 2
11:21PM 不是很困，打算刷到困就去睡觉。leetcode 现在一共1162题。每天刷十道题就可以两个月不到全部刷完。
我来试试我能不能真的两个月全部刷完。做不到也没关系。。。就是为了锻炼大脑。

https://leetcode.com/problems/word-search-ii/

import collections
class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for l in word:
node = node.children[l]
node.isWord = word
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
rowN, colN = len(board), len(board[0])
trie = Trie()
for w in words:
trie.insert(w)
res = []
def dfs(node, row, col, res):
if node.isWord:
res.append(node.isWord)
node.isWord = False
if row < 0 or col < 0 or row >= rowN or col >= colN:
return
char = board[row][col]
node_child = node.children.get(char)
if not node_child:
return
board[row][col] = '#'
for (i, j) in [(0,1), (0,-1), (1,0), (-1,0)]:
dfs(node_child, row+i, col+j, res)
board[row][col] = char
for i in range(rowN):
for j in range(colN):
dfs(trie.root, i, j, res)
return res

复制代码

苏格拉底的猫

可以来加入我们

薇薇2020

请问怎么加楼主微信呢？

ZYwang_one

恋斌发表于 2021-05-08 03:55:55
我想请问，刷题有标准答案吗？我都只看到题目没有看到代码

没有，输出是对的，时间空间不超过就可

恋斌

ZYwang_one 发表于 2021-05-09 08:21:54
没有，输出是对的，时间空间不超过就可

那问一下，想看答案，是只能看别人的解题思路了吗。。。

hey123_1

苏格拉底的猫发表于 2021-5-9 15:02
可以来加入我们

怎么加入呀。

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 -

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

浏览过的版块