7月缺米的来刷题/Mock interview活动

7.27 打卡

1. Minimum Possible Integer After at Most K Adjacent Swaps On Digits. Greedy + BIT。很好的一题。
2. Maximum Number of Non-Overlapping Substrings. Stack存储区间。
3. Construct Binary Tree from Inorder and Postorder Traversal. Recursion经典题。

Construct Binary Tree from Inorder and Postorder Traversal： 特别注意index 越界问题
Jump Game， Jump GameII greedy dp 都ok, greedy 要注意是否能够达到index I, fast > I && num[i] + I > fast--- fast  = num[i] + I;

Construct Binary Tree from Preorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal

今天刷了3道树的题目，还不是很理解这种。

7月27日 打卡第十一天 共计刷题10道

1.Height of Binary Tree
-getLeftHeight and rightHeight
-do it recursively

2.Check if Binary Tree is Balanced
-use the similar attribute
-check if the height != -1

3.Symmetric Binary Tree
-none null check

4.Tweaked Identical Binary Trees
-easier than symmetric
-and use two nodes to compare with each other

5.Is binary Search Tree Or Not
-check if all the nodes
-satisfied with the value range

6.Get keys in Binary Search Tree in Given Range
-rule out not valid keys
-recursively check from root
-put from smallest to largest

7.Search in BST

8.Insert in BST

9.Delete in BST
-4cases:
-1.single node
-2.only one kids(left)
-3.only one kids(right)
-4.two kids:
4.1 right kid doesn't have a left
4.2 find smallest

10.SmallestRectangle enclosed black pixels
-BFS / DFS to find the minX, minY, maxX, maxY;
-BinarySearch with only one method(hard, super hard)

7/27   DFS BFS

加米必回加！

求加米呀，实习期间只能摸鱼刷题了。

07/28打卡
100. 相同的树
102. 二叉树的层序遍历
104. 二叉树的最大深度
107. 二叉树的层次遍历 II

7.28打卡，leetcode 104, 867, 567, 318, 251, 314, 821, 866

谢谢各位大佬给分，继续努力
D26  打卡第26天 (UTC: 28/07/2020)
继续学习：数据结构 (stack) + 哈希表Hash

1: 331. Verify Preorder Serialization of a Binary Tree
将string变成array
遍历array，压栈，如果遇到“#”，且当前栈顶也是“#”说明栈顶#前面的那个节点已经有两个空子节点了，则将栈顶的#和前一个节点弹出，压入一个“#”表示空节点，
过程中如果有stack为空，则不是二叉树
最后如果栈里只剩一个“#”了就是二叉树


2： 272. Closest Binary Search Tree Value II 最近的二分搜索树的值之二

BST的中序遍历是递增序列
用栈实现BST的中序遍历。又因为求k个最接近的，也就是差值的绝对值最小的k个，可以用维护一个最大堆的方法

3： 149. Max Points on a Line

遍历每一个点，针对每一个点，用hashmap记录其余跟该点共线的点的个数，key是斜率，value是个数，
因为斜率相等的一定在同一直线。遇到跟该点重合的点需要单独累加个数
斜率要用分数形式存储，存分子和分母，这就需要计算最大公约数了。
没有什么算法，穷举。

今日刷题打卡