秋招冲刺

• 开帖监督自己， 目标今年秋天sde全职
• 打卡任务： lc 每天精刷5道保底
• 为什么开帖： 今年秋招不太乐观，与其每天担心不如把300道题目好好学习1-2遍
  

补充内容 (2022-06-09 11:43 +8:00):
#参考：Neetcode + Blind75 + 代码随想录 +  还愿榜单 + 胖头鱼

6/9: 二分

1. 33. Search in Rotated Sorted Array, 题目要求： 旋转数组中是否有目标值
二分的精髓是迅速舍弃一部分数组， 旋转的数组中，左右两边至少有一边是sorted,那我们可以看targe值是否在sorted那边的范围内，如果是我们可以舍弃非sorted的那部分数组元素。


2. 81. Search in Rotated Sorted Array II， #33的follow up, 有重复元素
和#33 code几乎一样，多了

            while l < mid and nums[l] == nums[mid]:
                l += 1


3. 153. Find Minimum in Rotated Sorted Array， 题目要求： 旋转数组中的最小值
最小值在没有排序的那半边


4. 981. Time Based Key-Value Store，题目要求：按照时间存放string, 找出离某时间最近的string
二分， upper bound


5. 4. Median of Two Sorted Arrays, 题目要求: 在两个排序数组中找中间值
对其中一个数组二分查找，使得找到的元素满足两个数组归为左边的数值都小于右边

6. 162. Find Peak Element， 题目要求: 找出peak的下标，peak是指某个点的值大于它的邻居
只对上坡的那边进行查找

7. 240. Search a 2D Matrix II， 题目要求: 行/列是排序的，查找目标值是否存在
从第一行最后一列开始查找， 如果值小于target, r++, 如果大于，c--
            
           

6/10 Stack

计划： 下周要攻破tree/graph/bfs/dfs

1. 150. Evaluate Reverse Polish Notation, 题目要求: 计算机中的基础运用，数字push到栈顶，遇到运算符号，对栈顶两个数组进行计算
stack的基本运用

2. 22. Generate Parentheses， 题目要求：枚举所有有效括号的组合
回溯

3. 739. Daily Temperatures， 题目要求： 找下一个更大值
单调栈， 从后往前遍历数组

4. 853. Car Fleet，题目要求： 根据车的位置和速度，看他们能够组成几个车队
创建数组 - sorted([position, speed]) ，从后往前遍历， 离终点更远，所需时间更短的车和它的下一个组成一个车队

5. 155. Min Stack， 题目要求： O(1)时间内返回当前最小值
用空间换时间，创建一个regular stack, 一个min stack。

6. 20. Valid Parentheses, 题目要求: string里的括号是否匹配
stack基础应用

7. 84. Largest Rectangle in Histogram， 题目要求： 最大长方形的面积
stack里要存放[index, height], 当遇到下一个更小的height的柱子时，边pop边更新最大面积

8. 1249. Minimum Remove to Make Valid Parentheses, 题目要求：删除一些括号使得它们匹配
和#20很像

6/8: 二分

二分就是for loop的优化，在有序数组中通过对中间值的判断来迅速缩小搜算区间。

1. 704. Binary Search， 题目要求： 有序区间内搜索目标值
模版题，我的的是左边右开区间解法, left = 0 , right = len(nums), while left < right... if nums[mid] == ...

2. 35. Search Insert Position, 题目要求: 给定目标值，找出第一个数组元素大于等于它的下标。
找出lower bound, 不断放弃左/右区间，最后while loop退出条件是左右指针指向同一个为主， 返回左指针

3. 34. Find First and Last Position of Element in Sorted Array, 题目要求: 返回某一个目标值在数组中第一次/最后出现的下标
找出lower/upper bound, lower bound 右区间缩小的条件是if target <= nums[mid], 但upper bound右区间缩小的条件是if target < nums[mid]

4. 69. Sqrt(x), 题目要求: 返回x 的平方根在[0, x + 1)区间内找出 res ^ 2 <= x 的upper bound, 直接套用模版即可

5. 367. Valid Perfect Square， 题目要求：X的平方根是否存在
在[0, x + 1)区间内找出 res ^ 2 == x, 和#704一样。

续#6/8: 二分

6. 278. First Bad Version， 题目要求： 在n个version中，找出最早有问题的 -> [F, F, F, F, T, T]， 找出第一个T
在[1, n + 1) 区间内，找出lower bound. 同#34， #35

7. 875. Koko Eating Bananas， 题目要求： 在规定时间内吃完n堆香蕉， 最慢的速度是？在[1, max(nums) + 1) 区间内， 找出lower bound

8. 74. Search a 2D Matrix, 题目要求：在二维数组内查询是否存在目标值
这个题目有特殊性， 就是把二维数组拉平为一维， 数组是sorted, 那么后面就可以套用1D arrray 的二分

#6/9 计划: 二分7道：  33/153/981/81/4/162/240， neetcode: stack部分

补充内容 (2022-06-10 08:47 +8:00):
6/8: 二分

周末事情比较多，加上有点生病，基本没学习，周中补作业
6/11， 5道

226. Invert Binary Tree，题目要求： 反转二叉树
前序遍历，先做事（root.left, root.right = root.right, root.left), 再遍历左右树， 最后返回根节点

104. Maximum Depth of Binary Tree， 题目要求：最大深度，也就是最长的path上node的个数
后序遍历

543. Diameter of Binary Tree， 题目要求： 最长直径
同#104，但需要辅助函数不断更新全局变量

110. Balanced Binary Tree， 题目要求：是不是平衡树
同#543

100. Same Tree， 题目要求：两个树是不是一样
如果根节点一样，同时左树和右树也一样，那么两个树相同

6/12， 5道

1. 235. Lowest Common Ancestor of a Binary Search Tree, 题目要求：在BST中找出两个节点的公共祖先
BST特性， While + if else

2. 102. Binary Tree Level Order Traversal, 题目要求: 树的每一层依次打印
level traversal模版题

3. 199. Binary Tree Right Side View， 题目要求： 打印每一层的最后一个数
#102变形

4. 101. Symmetric Tree,  题目要求：一个数是否对称
#100变形

5. 111. Minimum Depth of Binary Tree， 题目要求： 最短高度
#104变形

6/13， 5道

1. 572. Subtree of Another Tree, 题目要求: 判断一个tree是否是另外一个tree的subtree
#100变形

2. 98. Validate Binary Search Tree， 题目要求: 判断一个数是否是BST
BST 中序遍历是sorted

3. 112. Path Sum， 题目要求: 从root 到leaf的和是否等于target
backtrack

4. 257. Binary Tree Paths, 题目要求: root-to-leaf的所有路径
backtrack

5. 404. Sum of Left Leaves, 题目要求:所有左leaf的和
前序遍历

6/14， 5道

1. 297. Serialize and Deserialize Binary Tree, 题目要求: 把tree转化成string,再把string转化成原来的tree
preorder traverse + dfs

2. 124. Binary Tree Maximum Path Sum, 题目要求: 所有path中和最大的值是？
#543的变形

3. 105. Construct Binary Tree from Preorder and Inorder Traversal， 题目要求： 根据preorder 和 inorder构建tree
构造二叉树，第一件事一定是找根节点，然后想办法构造左右子树。

4. 230. Kth Smallest Element in a BST， 题目要求：BST第k个最小值
inorder BST 是sorted

5. 1448. Count Good Nodes in Binary Tree, 题目要求: ..
辅助函数 + 全局变量 + 前序遍历