刷题打卡贴-死磕秋招

喜欢楼主的总结方式，希望以后多多总结

6.6
重做：725. Split Linked List in Parts
23. Merge k Sorted Lists
25. Reverse Nodes in k-Group
143. Reorder List
328. Odd Even Linked List
100. Same Tree
101. Symmetric Tree
538. Convert BST to Greater Tree
572. Subtree of Another Tree
其中 bugfree: Odd Even Linked List, Same Tree
剩余4题全部出现了小问题：包括了笔误：笔误 curr.next = prev; 小的typo  val 少敲了一个l 写错成va, 数组的初始化写成 ListNode(k)
出现以前不会犯过的错误的主要原因是1.心态急躁，追求速度，因为这些题都是至少做过3次都没有bugfree的题，心里想着这次一定能够bugfree，于是在写代码的过程之中只关注了上一次或上两次犯过的错误不要重犯，而忽视了其它的细节。 2.基础不够扎实，对于java的语法不够熟练，比如数组初始化写成ListNode(k)就是一个十分典型的例子，这种小的typo如果足够敏感是可以在写题的过程中直接发现的甚至是完全不可能出现的。
总结： 对于多次反复练习过的没有bugfree的题目要更加谨慎的对待，反复做错的题目不能只记 一个思路，更要保证每一个细节都是十分熟悉和确定的。

6.7 LeetCode Tree + Easy Tag filter
101. Symmetric Tree
538. Convert BST to Greater Tree
572. Subtree of Another Tree

144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
lint448. Inorder Successor in BST
236. Lowest Common Ancestor of a Binary Tree
235. Lowest Common Ancestor of a Binary Search Tree
543. Diameter of Binary Tree
其中bug free:  101. Symmetric Tree 538. Convert BST to Greater Tree 94. Binary Tree Inorder Traversal
对于树的easy题目，做了大概10道题，都是3个月前做过的题目，发现一半多之前能够bugfree的题目现在不能够做到bugfree了， 这就说明了没有及时复习导致了一定程度的遗忘以及对于递归的理解不够深入，之前bugfree可能也仅仅是把答案背下来默写上去的而已。下一步先将easy的题目整理总结，并考虑寻找一些树的题目的模板以及递归的模板来强化练习一下对于递归的理解，最后能够做到写出来的每一个递归程序都能够在头脑中构建出其执行的顺序以及由一个思路来反向构建一个递归程序的水平。

Auguskong 发表于 2018-6-8 11:58
6.6
重做：725. Split Linked List in Parts
23. Merge k Sorted Lists

楼主相当赞啊。。。建议8月的时候比较好，职位很多其实open了但是大批的申请人还没开始申请，这样process会比较快，可以到时候联系我内推Google啊，可以交流一下面试经验，我觉得楼主这么加油刷题很稳！

嗯嗯 谢谢支持，我也是觉得尽量早点投简历的话能拿到的面试机会多一些，到时候还请前辈多多指教~

周末开着新买的小灰出去转了转，放松一下心情，周一正式开工。
6.11
完成Princeton算法I的第三周课程 + 作业，重点了解java的Comparable 和 Comparator，明天计划完成递归的重点练习。

看好楼主的刷题方式～很棒

6.12打卡
复习了一下《SICP》的第一章 线性迭代，线性递归，树形递归的内容。感觉收获很大，记录一下对我很有启发的几句话
“能够看清楚所考虑的动作的后果的能力，对于成为程序设计专家是至关重要的,.....,只有在此之后，人们才能进行反向推理” 读到这句话的时候，我感觉找到了学习递归对于刷题之外的更高级的目的在于了解整个程序的运行方式，以及对于程序设计至关重要的能力。
“一个过程就是一种模式，它描述了一个计算过程的局部演化方式，描述了这一计算过程中的每个步骤是怎样给予前面的步骤建立起来的” -》这句话让我想到了算法设计的整体性以及一种内在隐含的强制顺序要求，而在设计之初是需要进行一种超前的考虑的。
“代换模型揭示出一种先逐步展开而后收缩的形状，在展开阶段里，这一计算过程构造起一个推迟进行的操作所形成的链条，收缩阶段表现为这些运算的实际执行。“
“迭代过程是那种其状态可以用固定数目的状态变量描述的计算过程。”
“递归是一个预算法上的事实， 某个递归过程可以产生一个迭代的计算过程， 比如用来计算阶乘的 fact(product, count, maxCount) function,”
感觉对于递归来说，最主要的要分清楚什么时候是调用，什么时候是执行，比如最简单的二叉树前序遍历， 三句话 res.add(root.val), preorder(root.left), preorder(root.right), 第一句话就是递归的执行，将当前节点的val添加到最终的结果res list当中，而preorder(root.left) 以及 preorder(root.right)

143. Reorder List
725. Split Linked List in Parts
其中bug free: Reorder List

6.13 打卡
463. Island Perimeter
733. Flood Fill
lint 434. Number of island II
695. Max Area of Island
200. Number of Island
今天做了几道关于island的相关问题来强化对递归的理解，这一类题目的递归很明显，执行的操作是数个数/计算面积/记录是否属于同一岛屿, 调用的操作是对于当前位置的4个邻居做递归，继续查找（row + 1 col/ row - 1 col/ row col + 1/ row col - 1/，对于难度比较大的434，感觉不能仅仅使用通用的DFS模板来解决所有问题，需要参考Union Find的算法来进行一定的辅助操作。明天需要复习一下Union Find的内容。

6.14
重做
463. Island Perimeter
733. Flood Fill
695. Max Area of Island
200. Number of Island
Union Find内容复习
quick Find算法 find: return id[p] union: find(p) find(q) for loop遍历整个id去调整id[i] == pID的节点
quick Union算法 find: while(p != id[p]) p = id[p]; 直到找到根触点停止find()操作， union: pRoot = find(p); qRoot = find(q); if(pRoot == qRoot) return; id[pRoot] = qRoot;
加权quick-Union算法: 在union过程中添加树的大小比较 if(size[i] < size[j]) { id[i] = j; size[j] += size[i];} else: {id[j] = i; size[i] += size[j];}

6.15
752. Open the Lock
743. Network Delay Time
417. Pacific Atlantic Water Flow
BFS + 最短路径
6.16
Dijkstra 算法梳理
Dijkstra是由一个单一的源点出发，计算整个联通分享之中与之相连元素的最短路径算法。算法的实现需要维护一个minHeap来记录当前的最短路径，通过比较res[i] 与 res[node] + grid[node][i](weight) 来更新res中的各个节点最短距离。

6.17
重做
752. Open the Lock
743. Network Delay Time
417. Pacific Atlantic Water Flow
PriorityQueue的实现，Princeton《算法》教材2.4节，感受到了数据结构的威力，之前在实现Dijkstra算法中使用到了PriorityQueue, 但是没有太多深入实现的部分，仔细研究之后发现PriorityQueue可以使用最简单的数组来实现(借助于完全二叉树的特性），同时由于堆结构自身的特性(root 为最小节点，且每一个root都小于自己的child节点) 保证了插入和删除操作的时间复杂度都是LogN(N为待处理的元素总数）。注意实现的过程不是直觉性的将每个新的输入和已知的M个最大的元素作比较，因为这样作比较的代价很高。
k: 当前节点
k/2: 当前节点的父节点
2k or 2k + 1: 当前节点的子节点
而是利用堆的整体特性，
insert()操作将元素添加到最底层： 并使用swim()操作将新插入的节点上浮到一个适当的位置
private void swim(int k) {
  while(k > 1 && less(k / 2, k)) {
    exch(k / 2, k);
    k = k / 2;
  }
}
delete()操作将元素从根节点删除并交换最底层最后一个节点到根节点 + sink() 操作
private void sink(int k) {
  while (2 * k <= N) {
    int j = 2 * k;
    if (j < N && less(j, j + 1)) j++; // change the larger element
    if (!less(k, j)) break;
    exch(k, j);
    k = j; //update the pointer
  }
}

6.18 重做
463. Island Perimeter
733. Flood Fill
695. Max Area of Island
200. Number of Island
其中bug free 463. Island Perimeter 733. Flood Fill
复习基本的java 语法 String Class
substring(int startIndex, int endIndex) substring(int startIndex)
char charAt(int index)
String trim()
boolean equals(Object other) //return true if the string equals other `==` only determine whether or not the strings are stored in the same position
int compareTo(String s1, String s2); 错误，应改为-> int compareTo(String other) // `-` string 在other之前，`0`两者相等，`+` string 在other之后
int indexOf(String str)
int indexOf(String str, int fromIndex)

when build up strings from shorter strings, such as keystrokes or words from a file. It would be inefficient to use string concatenation, using StringBuilder
StringBuilder() // constructs an empty string builder
StringBuilder append(String str)
StringBuilder append(char c)
StringBuilder insert(int offset, String str)
StringBuilder insert(int offset, char c)
StringBuilder delete(int startIndex, int endIndex)
String toString() //return a string with the same data as the builder or buffer contents 多用于build结束之后

6.19
重做
752. Open the Lock
417. Pacific Atlantic Water Flow
新题-DP
62. Unique Paths
322. Coin Change
55. Jump Game
53. Maximum Subarray
152. Maximum Product Subarray
518. Coin Change II

熟悉 坐标型 最值型 计数型动态规划
动态规划四个关键：
状态 -> 每一个数组存什么
初始化->最开始的起点状态是什么
边界 -> 更新的边界条件 + 终点的边界
结果 -> 返回什么

6.21重做
752. Open the Lock
417. Pacific Atlantic Water Flow
62. Unique Paths
322. Coin Change
55. Jump Game
53. Maximum Subarray
152. Maximum Product Subarray
518. Coin Change 2

6.22
House Robber I/II/III
逻辑有错误
6.23九章动态规划第二节课

了解三种类型的动态规划：
坐标型
序列型
划分型
Unique Path II
Decode Ways
Bomb Enemy

坐标型是最简单直接的类型，直接声明与给定数组/矩阵大小一致的数组/矩阵即可 一般返回f[i - 1][j - 1]
序列型的动态规划可能需要多个状态变量，以及对应的多个转移方程，需要考虑的全面一些
划分型的动态规划没太听懂，需要继续复习