加州 妹子一枚 监督自己每天⛽️刷题！！欢迎大家评论分享心得！！

jiang718 发表于 2018-9-22 01:06
巧呀，我也一样今年五月毕业，在加州，也是全天候刷题投公司。楼主加油！

谢谢你！你也加油💪

要向楼主看齐！我现在刷题简直龟速

稍微看了一下楼主刷的题, 刷起来没有什么章法，既没有按难度刷，也没有按数据结构分类刷，基本都是randomly挑一些题。
我建议还是从简单和中等开始刷，熟练了再做难题，而且多总结思路，那些什么难点易错点我觉得没什么必要计，都是因为你写的不熟练，写熟了有经验了就不会错。

The8023 发表于 2018-9-22 04:50
稍微看了一下楼主刷的题, 刷起来没有什么章法，既没有按难度刷，也没有按数据结构分类刷，基本都是randomly ...

好的，谢谢您的建议！已经在按topic做题了，多谢指导

ootsuka 发表于 2018-9-22 05:54
好的，谢谢您的建议！已经在按topic做题了，多谢指导

建议刷题时间也按照面试要求来吧, 简单15，中等15-30，难题20-40.  很少见面试上来就给一个hard, 一般面试官都会至少准备两个题目. 提高效率, full time刷题就提高效率缩短时间. 希望楼主早点刷完早点找工作早点赚钱买包.

The8023 发表于 2018-9-22 06:11
建议刷题时间也按照面试要求来吧, 简单15，中等15-30，难题20-40.  很少见面试上来就给一个hard, 一般面 ...

请问您觉得leetcode做多少题目才算是差不多可以去面试？

ootsuka 发表于 2018-9-20 02:18
你好，你是指explore里按topic分类的那些吗？最近做题顺序有些凌乱，想改变策略

in explore there is  a classification for easy,medium ,hard level topics, totally 151 problems, you can take a look

9/21 Fri 【Trees and Graphs 】的一天
116. Populating Next Right Pointers in Each Node
117. Populating Next Right Pointers in Each Node II
两题做法一摸一样，只用了currPtr 作为当前指针，nextDummyHead和ptr两个variable来将每一层进行串联
nextDummyHead 是下一层链表开始的的dummynode，保持不动，方便上一层iterate完可以让currPointer来找到下一层该iterate的位置。ptr从dummynode开始进行串联。
Kth Smallest Element in a BST
这道题是BST的典型题目，利用BST的性质，return inorder traversal来得到第k-1个数就是Kth samllerst element
回忆知识点 【BST】:
        • The left subtree of a node contains only nodes with keys less than the node's key.
        • The right subtree of a node contains only nodes with keys greater than the node's key.
        • Both the left and right subtrees must also be binary search trees.
回忆常见的BST题目
        • Validate BST 做法：不断检查subtree的root节点是否 > min && < max
        • 173 BST Iterator: 让用O（1）的时间返回下一个最小的数。也是利用了BST的性质，左subtree是偏小的，那么用stack data structure存所有left root的值，在pop出来一个后，再在stack中加该节点的right tree
        • 235 LCA of a BST ,给树的root节点，求P与q节点的LCA：做法也是利用节点value与root.val 的大小比较1）都在左边2）都在右边 3）一左一右，那么LCA就是root
        • 108. Convert Sorted Array to Binary Search Tree 因为要求是height-balanced：即左右子树的高度差不可超过1. 那么每次需要建立的root节点是mid未知的数： mid = left + (right - left)/2
Word Ladder
其实就是在图中找最短路径，用BFS，BFS一定会用到queue记录一层中所有当前的可能。同时这道题会用到Hashset来记录所给wordlist还剩下那些available的word，如果碰到wordlist中的某个单词，hashset中将其删掉，并且则将这个newString 加入到queue中，提供之后下一层的处理。BFS的题目是围绕queue来展开的，一开始加入什么element，进入while(!queue.isEmpty()) 的loop中，存下当前queue的size，for loops，每次进去，poll出一个元素，处理后，合适的加到queue中，等待下一层的处理。

        • 遇到一道新题就尝试理解，归类，翻出老题目进行对比。写code， 看热门答案，更正，优化自己的答案，如何想到这个topic/解，搜一下相关不熟悉的知识点
        • 遇到一个考的算法或者数据结构，比如trie tree，就会回去看所有trie树分类的题目，看题目，回忆解法
96. Unique Binary Search Trees
Input为n，求用从1～n的数能组成多少种BST？
130 Surround Region Graph的题目 ->BFS
题目要求：让将图中间被包围的地方变成‘X’--》做法：从四周出发，从'O'的地方入手，将O变成W，注完水后，将W的地方变成O其他地方全是X
注水的这一过程是用BFS来完成的，分别用qx和qy两个queue来分别存储左边的x和y坐标，BFS只操作周围是“O”的地方，那么进入bfs，如果是X则return不处理。
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0}; //小技巧用来处理向四周变化的坐标
的题目，如果问第几小/da，或inorder/preorder 排序中排在下一个的element是什么，那么就需要用一个helper function来将所有的排序存在一个list中，然后就能轻易找到答案

楼主加油~~~~

【9/22 Sat】Tree-base DFS
Binary Tree Problems:
考点本质：DFS
        • 第一类：求值，求路径类二叉树的问题
        • 第二类：结构变化类二叉树问题
        • 第三类：BST 问题

【第一类：求值，求路径类二叉树的问题】
Tree的题目离不了的是recursion下面的三道题目就是一种类型，利用recursive helper function分别recursion出left subtree和right subtree 的结果，再合并不断update result
124 binary tree maximum path sum the path must contain at least one node
687 longest univalue path find the length of the longest path where each node in the path has the same value
543 diameter of binary tree compute the longest length of the diameter of the tree
分析：需要求整棵树上最大/最长的path或者sum， 一定是需要走完整棵树才知道结果，那么需要一个recursive的helper function来不断向下面走。同时需要一个global variable来不断update记录所遇到过的最大的答案
做法：在主函数中callhelper function即可，在helper fucntion中
        • 首先要有return case which you need to return 0 at this moment.
        • 然后用int left  = helper(root.left); int right = helper(root.right) 来分别记录当前left subtree 和right subtree 的答案 (devide 步骤)
                ○ 有时在做选择的时候，如max path sum需要subtree sum为正数，相加才最大，那么
                ○ int left = Math.max(0,helper(root.left)) 表示subtree可选可不选
        • 再update global variable 如：longest = Math.max(longest, left + right + root.val)是情况而定
        • 最后return helper function的值，记住是半边tree的subresult
                ○ 如 return Math.max(left, right) + root.val;

Subtree with maximum average(lintcode597)是124题目的拓展
这道题有点棘手，因为在不断dfs的recursion中既要知道当前subtree最大的sum又要知道subtree节点的个数。解决的方法就是：新建一个ResultType  class，其中包括sum和count这两个preperty。那么dfs每次返回的是resultType的obect instead of just int variable。这个时候就需要有两个global variable，一个是最后返回的subtree node和当前最优秀的resultType object。在dfs中比较当前subtree的sum average并即使update。
**另外一个小策略：当想比较 a/b > c/d时不妨表示成： a * d > c * b 避免了整出后的取整问题
226. Invert Binary Tree
Example:
Input:
     4
   /   \
  2     7
/ \   / \
1   3 6   9
Output:
     4
   /   \
  7     2
/ \   / \
9   6 3   1

public void invertBinaryTree(TreeNode root) {
         if (root == null) { return; }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertBinaryTree(root.left);
        invertBinaryTree(root.right);
        }

124 binary tree maximum path sum && minimum subtree 题目看似相似但其实不同
124: 只要找到 maximum的path就好，所以每次面临的是两个选择：左tree or 右tree，所以每次dfs返回的值也是左tree或右tree较大的那个 + root.val

Minimum subtree
每次就是为了得到subtree的值：left + right + root.val


257 Binary Tree Paths: 返回所有root to leaf 的paths
DFS 每次查看左节点和右节点是否同时为null，不是的话，就分别用dfscall下一个左节点 or 右节点

【第二类：二叉树结构/形态发生变化】
114. Flatten Binary Tree to Linked List
【第三类：BST】
• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.
【题目】
230. Kth Smallest Element in a BST
Follow up: 当BST经常被修改，怎么优化Kth smallest 这个操作？
在 TreeNode 中增加一个 counter，代表整个树的节点个数也可以用一个 HashMap<TreeNode, Integer> 来存储某个节点为代表的子树的节点个数在增删查改的过程中记录不断更新受影响节点的 counter
85. Insert Node in a Binary Search Tree
Given a binary search tree and a new tree node, insert the node into the tree. Return the node of the new BST.
public TreeNode insertNode(TreeNode root, TreeNode node) {
if (root == null) { return node; }
if (root.val > node.val) { root.left = insertNode(root.left, node); }
else { root.right = insertNode(root.right, node); } return root; }


补充内容 (2018-9-24 01:41):
将DFS分为三类复习：Tree-based dfs, combination based dfs, graph&permutation based dfs. 今天复习后两类。