第五期学员_Tina
2022年2月21日 – 2022年3月6日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
每天5个小时 - 学习了那些题目：
第四期前两周的内容 - 遇到的问题：
1) 链表: leetcode题23 合并k升序链表 没掌握
2) Stack: 不明确在哪种情况下使用Stack，看了讲解可以做出来，但是拿到题无法直接想出用stack解决，譬如题224，739，42，239题
3) 排序: 题315 计算右侧小于当前元素的个数 没掌握
2022年3月7日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
2h - 学习了那些题目：
复习第一周linkedlist题目 - 遇到的问题：
92) 翻转列表的翻转操作 temp.next = pre.next
cur = pre.next
while right > left:
temp = cur.next
cur.next = cur.next.next
temp.next = pre.next
pre.next = temp
right -= 1
138) 复制链表
# 新建节点
visited[cur] = Node(cur.val, None, None)
# 给节点next random赋值
visited[cur].next = visited[cur.next] if cur.next else None
visited[cur].random = visited[cur.random] if cur.random else None
2022年3月8日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
2h - 学习了那些题目：
复习第一周stack相关题目 - 遇到的问题：
20) Valid Parentheses:
#add '(' '[' '{' to stack, if input is ')', ']', '}'
#check if paired with the peek of stack
224) Basic Calculator:
#记得每判断一次 i+= 1
#if '(', use stack to store the formerResult and formerSign
formersum + sign * current_sum
value = value * 10 + ord(s[i]) - ord('0')
155) Min Stack:
#用一个最小栈，记录最小值
#每增加一个数字，和栈顶元素比较，添加到最小栈
if not self.minstack or val <= self.minstack[-1]:
946) Validate Stack Sequences:
use stack to save the pushed value
pop if the peek of stack is equal to the peek of poped
用 while 遍历 popped中所有符合的元素
739) Daily Temperatures:
#用栈存储小于当前温度的[下标，值]
#遇到大于当前温度的值
#用while循环计算index差，赋值给res
#弹出已经记录过得值
42) Trapping Rain Water:
#Stack (monotonic stack)
#use the stack to store the left side and bottom
# pop up the bottom and compared with the right side
# 宽度： 凹右 - 凹左 - 1 => 注意是减一
# 高度： min(凹左，凹右）- 凹底
while stack and h > stack[-1][1]:
middle = stack.pop()
if stack:
res += (i - stack[-1][0] - 1) * (min(h, stack[-1][1]) - middle[1])
stack.append([i, h])
2022年3月9日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
4h - 学习了那些题目：
第一周 队列以及链表 - 遇到的问题：
232) 用栈实现队列:
在添加stack_out前判断其是否为空
def pop(self) -> int:
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop() if self.stack_out else None
239) 滑动窗口最大值
窗口起始位置是：(i – k + 1)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if k < 2: return nums
length = len(nums)
res = []
queue = []
# check the first k items in the nums
for i in range(k):
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
queue.append(i)
res.append(nums[queue[0]])
for i in range(k, length):
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
while queue and queue[0] < (i - k + 1):
queue.pop(0)
queue.append(i)
res.append(nums[queue[0]])
return res
3) K个一组翻转列表
用 pre, start, end, next_start 标记翻转的一组和下一组的起始位置
pre.next = self.reverselist(start)
2022年3月10日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
4h - 学习了那些题目：
二分查找 - 遇到的问题：
1) 注意代码规范
先写边界条件，判断是否为空
调用list判断list是否为空
704) 二分查找 基本模板
注意 1. left，right指针的初始范围，2. while: left <= right 或者 left < right, 3. left = mid/mid+1, right=mid/mid-1
if not nums: return -1
left, right = 0, len(nums)-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
return -1
2022年3月11日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
1h - 学习了那些题目：
位运算，可用^处理重复的问题 - 遇到的问题：
重点掌握按位与&， 按位异或^, 左移
268) 丢失的数字
missing = missing ^ nums[i] ^ (i + 1)
231) 2的幂
not (n & (n-1)) if n > 0 else False
191) 数字为1个数
while n:
n = n & (n - 1)
count += 1
2022年3月12日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
2h - 学习了那些题目：
位运算 - 遇到的问题：
318) 最大单词长度乘积
for i in range(len(words)):
word = words[i]
bit = 0
for j in range(len(word)):
# 得到该字符的位置
c = ord(word[j]) - ord('a')
# 左移1至该字符的位置
bit |= 1 << c
# 添加该单词到mask中
mask[i] = bit
461) 汉明距离
# ^ 异或 得到位不同的二进制数字
cur = x ^ y
res = 0
# 与判断只出现1的数字相同
while cur:
#用与来判断多少个1
cur = cur & (cur-1)
res += 1
return res
2022年3月13日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
3h - 学习了那些题目：
回溯 - 遇到的问题：
200) 岛屿数量
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
m , n = len(grid), len(grid[0])
# 创建二维矩阵记录是否被访问
mark = [[0 for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
# 未被访问且值为1，用dfs判断其左右上下
if mark[i][j] == 0 and grid[i][j] == '1':
self.DFS(grid, i, j, mark)
# 此处已经枚举尽所有连接的1，岛屿加一
count += 1
return count
def DFS(self, grid, x, y, mark):
# 记录访问过此节点
mark[x][y] = 1
# 解锁遍历右，左，下，上的方法
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
new_x = x + dx
new_y = y + dy
# 边界条件判断
if new_x < 0 or new_x > len(grid)-1 or new_y < 0 or new_y > len(grid[0]) - 1:
continue
# 若此处为1且未被访问，则用DFS继续寻找，直到遍历完所有相邻的1
if mark[new_x][new_y] == 0 and grid[new_x][new_y] == '1':
self.DFS(grid, new_x, new_y, mark)
51) N皇后
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def updateAttack(x, y, attack):
# 上、下、左、右、左上、左下、右上、右下
dx = [0, 0, -1, 1, -1, -1, 1, 1]
dy = [-1, 1, 0, 0, -1, 1, -1, 1]
# 循环8列n行，填充1
for j in range(8):
for i in range(n):
nx = x + i * dx[j]
ny = y + i * dy[j]
if nx < 0 or nx > n - 1 or ny < 0 or ny > n -1:
continue
attack[nx][ny] = 1
def backtrack(k, n, queen, attack):
#循环结束条件，k在第n行
if k == n:
rl = []
for i in queen:
#合并行，依次加入结果中
rl.append(''.join(i))
res.append(rl)
return
#循环n列
for i in range(n):
if attack[k][i] == 0:
#记录放置queen前的棋盘
temp = copy.deepcopy(attack)
queen[k][i] = 'Q'
#放置后改变目前棋盘的attack
updateAttack(k, i , attack)
# 再循环下一行，直到 k: n
backtrack(k+1, n , queen, attack)
# 若没有return，表示没有找到结果
# attack恢复， queen恢复
attack = temp
queen[k][i] = '.'
# 初始化 attack & queen
res = []
attack = [[0]*n for i in range(n)]
queen = [['.'] * n for i in range(n)]
backtrack(0, n, queen, attack)
return res
2022年3月14日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
3h - 学习了那些题目：
回溯 - 遇到的问题：
78) 子集
subset记录，dfs添加包含和不包含当前数字
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
def dfs(i):
# 当所有数字都被遍历完，返回全部子集
if i >= len(nums):
res.append(subset.copy())
return
# 左右子集
#包含该数
subset.append(nums[i])
dfs(i + 1)
# 不包含该数
subset.pop()
dfs(i + 1)
dfs(0)
return res
#另一种解法
res = [[]]
#循环每个新的数字
for num in nums:
# 添加新数字到现有的数组中，组成新的数组
res += [curr + [num] for curr in res]
return res
40) 组合总和 II
对数组排序，prev记录当前数，pos记录当前被访问的数字，dfs(curr, pos, target)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 排个序防止重复取值
candidates.sort()
res = []
# note use pos to mark the current position
def dfs(curr, pos, target):
if target == 0:
res.append(curr.copy())
if target <= 0:
return
# 用prev记录前一个数，若下一个数与prev相同，跳过不计
prev = -1
# 此时只记录从当前pos往后的数字
for i in range(pos, len(candidates)):
if prev == candidates[i]:
continue
curr.append(candidates[i])
#遍历下一个数，查看其是否能组成target， 此时总数变为target = target - 当前数
dfs(curr, i + 1, target - candidates[i])
# 弹出当前数
curr.pop()
prev = candidates[i]
dfs([], 0, target)
return res
2022年3月15日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
1h - 学习了那些题目：
回溯 - 遇到的问题：
22) 括号生成
两个条件：
1) n open and n close
2) only add open parenthesis if open < n
3) only add close parethesis if close < open
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
curr = []
def dfs(open, close):
# 终止条件：所有遍历完成
if open == close == n:
res.append("".join(curr))
return
# open 加一后的所有组合
if open < n:
curr.append("(")
dfs(open + 1, close)
# 弹出加入的括号
curr.pop()
# close 加一后所有组合
if close < open:
curr.append(")")
dfs(open, close + 1)
#弹出加入的括号
curr.pop()
dfs(0, 0)
return res
2022年3月16日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
3h - 学习了那些题目：
回溯和复习第二周星标题 - 遇到的问题：
473) 火柴拼正方形
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
# input matchsticks -> int
# output -> bool : true: can false: cannot
# 排序，求和判断corner case
# 长度和余数分开来算
length = sum(matchsticks) // 4
remain = sum(matchsticks) % 4
if len(matchsticks) < 4 or remain != 0 or max(matchsticks) > length : return False
lines = [0] * 4
matchsticks.sort()
# [1,1,2,2,2]
# matchsticks: input
# index: index of matches
# target: length of each line
# lines: list to store matches
def backtrack(index,target,lines):
if index < 0:
return True
for i in range(4):
# 查看加该值后，是否超过边长
if lines[i] + matchsticks[index] > target:
continue
lines[i] += matchsticks[index]
# 加入边长后，遍历下一个值，若遍历成功，则返回true
if backtrack(index - 1, target, lines):
return True
# 若没有成功，弹出该值，继续查看下一个line
lines[i] -= matchsticks[index]
# 注意是倒序
return backtrack(len(matchsticks)-1, length, lines)
2022年3月17日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
30 mins - 学习了那些题目：
回溯 - 遇到的问题：
473) 分割回文串
遍历子串，判断是否为回文子串
class Solution:
def partition(self, s: str) -> List[List[str]]:
if len(s) <= 1: return s
res = []
part = []
def dfs(i):
# 越界且该路径有回文子串，加copy到res中
if i >= len(s):
res.append(part.copy())
return
# 遍历从 i 到 s最后一位
for j in range(i, len(s)):
if not self.isPali(s, i, j):
continue
#若是回文子串，加入part中
part.append(s[i:j+1])
# 遍历下一个字符
dfs(j + 1)
part.pop()
dfs(0)
return res
# 判断是否含有回文子串
def isPali(self, s, l, r):
while l < r:
if s[l] != s[r]:
return False
l, r = l + 1, r - 1
return True
2022年3月18日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
30 mins - 学习了那些题目：
回溯 - 遇到的问题：
46) 全排列
遍历，交换字符
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) <= 1: return [nums]
res = []
def dfs(i):
if i >= len(nums):
res.append(nums[:])
for j in range(i, len(nums)):
# 交换
nums[i], nums[j] = nums[j], nums[i]
# 下一个字符
dfs(i + 1)
# 交换回来
nums[i], nums[j] = nums[j], nums[i]
dfs(0)
return res
2022年3月22日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
2h - 学习了那些题目：
二叉树 - 遇到的问题：
- 二叉树的高度：自下而上
- 二叉树的深度：自上而下
- 二叉树的遍历：Stack 记录parent，利用state来遍历 left, right, up
2022年3月23日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
4h - 学习了那些题目：
二叉树 - 遇到的问题：
- 从前序与中序遍历序列构造二叉树
对中序遍历创建Hashmap，依次循环前序遍历中的节点判断map中在根节点哪一侧 - 路径总和II
用stack保存路径中节点，if not node.left and not node.right and value targetSum - 二叉树的最近公共祖先
回溯，判断root左右返回的树是否不为空，即同时找到p和q，返回该node - 二叉树的右视图
和层序遍历一样，bfs，添加一层的所有元素，最后一个元素为最右侧元素
2022年3月25日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
2h - 学习了那些题目：
二叉树 - 遇到的问题：
- 二叉树展开为链表:
递归，tail的用法不清楚
2022年3月27日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
1h - 学习了那些题目：
二叉树 - 遇到的问题：
-
将有序数组转化为二叉搜索树
define middle item as root, recursively call the left (begin, mid -1) and right( mid + 1, end) asign root.left and root.right -
把二叉搜索树转换为累加树
modify right, add root.val to sum, root.val = sum, modify left -
删除二叉搜索树中的节点
三种情况：1 无左，return 右， 2. 无右，return 左 3. 有左有右，寻找右侧最小值，赋值给root，删除右侧最小值 -
全二叉树的节点个数
两种情况：1. left = right， 则左为满 2 left != right, 则右为满。 -
二叉树的最大深度
- 二叉树的最小深度
- 二叉树的所有路径
2022年3月28日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
1h - 学习了那些题目：
二叉树 - 遇到的问题：
-
平衡二叉树
递归判断该节点的左右子节点是否为平衡树 -
左叶子之和
用deque记录当前层节点，循环整个list，sum + node.left有值且为叶子结点 -
找树左下角的值
用deque记录当前层节点，循环整个list，i0处的节点为最左侧的值 -
修剪二叉搜索树
left< node< right， 若 node.val high， node = node.left，否则继续查找左右分支 -
二叉搜索树的最近公共祖先
pq在左侧 递归查找左侧，pq在右侧，递归查找右侧，否则返回root -
二叉搜索树的最小绝对差
inorder时计算差值 -
最大二叉树
找到最大值，作为根节点，循环遍历左侧，右侧找出最大值，作为根节点的左右节点，终止条件为该节点为空
2022年3月29日
- 今天是否学习了算法训练营的内容
是 - 学习时长：
4h - 学习了那些题目：
复习二分，回溯 - 遇到的问题：
- 二分法对于 left <= right 还是 left < right 判断比较模糊
