Leetcode second round ---> starting on 8/15, wants to end on 8/30

leetcode的题目过了一遍了，242道题，但是仍然有一些觉得难的题目没有完成，希望在第二轮能完成，第二轮主要任务： 对每一道题尽量想出更多的方法，并且比较方法之间的优缺点，把每道题的run time降到最低；不知道现在自己有没有具备很强的总结以及扩展的能力，但是还是要强迫自己每道题多想想思路，方法，为什么要这么做，特别是对于做的不熟的题目； 每一道题写完不能再等着让compiler来检验能否通过了，因为在面试的时候一旦被面试官发现不能过的时候就会直接挂了， 有把握是对的时候再提交吧；242道题想在15天内完成，每天是需要做20题左右的，任务量还是很大，但是现在时间紧迫，还是要给自己打点鸡血了。当一天坚持不下去的时候，提醒自己能多做一题是一题，坚持下去就离目标近了！
 today's mission: 242 - 232 + small class 6questions
242 : valid anagram:
         M1: sort string --> compare : O(nlogn) 80ms
         M2: map and match O(nlogn)(map find method) + O(n) 72ms
         M3: since the char in the string is all lower case alphabets, we can use array to replace the map, in this way , we can save more time since we don't need to call the map methods, and we can also save some space.  O(n ) + O(n)  12ms
 Notes: if we first check if the size of two string is the same, we don't need to worry about the counter may not to be 0 after we check all the chars. 
241: different ways to add parentheses
        M1: dfs add (, ), then use caculator| to solve the string, very time consuming and not efficient.
        M2: use recursion --> for every op in the string, we can recursively calculate the left part of the op and the right part of the op,  then we can use the results we get to calculate the final result with only one op. 
we should care about: 
1. the base case is when the string only contains digits, we push it to the rst. eg: "1", "11" ,"1111", not only one char, but also all the digit chars. we should compute this.
2. the element in the string is char, not int, we should convert it to int when we calculate, very easy to forget to do this!!!
Use recursion to solve problems is like "divide and conquer". Recursion method always cut the big problem into small ones which has the same algorithm to solve. when we solve the smaller ones, we can return back to the larger problems. 
time complexity: n^n : n power of n
240:  search a 2D matrix
这个题目如果仍然用之前的那个binary search的方法是不能做的，因为matrix里面数字增减并没有直接的规律，只能看出来从左上角到右下角是递增的，
这个题目用的方法感觉很难看出来，这个题目利用的是从右上角到左下角的过程中，向左走是单调递减的，向下走是单调递增的。利用这个规律来找，是能找到所有在这个matrix里面的元素的，并且time complexity是O（n）
239:Sliding window maximum
这个题目是利用deque来模拟窗口，为什么用deque呢？ 因为窗口移动的时候需要移出左边的值，并且需要push-back新的值，而具备这个的只有deque可以，deque的front（）元素是每次的最大值，这个题目窗口里面存的是递减的序列，在一个新的element进来之前，需要把deque里面比这个数小的数都pop出来。并且每次需要移动窗口的时候，都需要把index - k位置的元素移出。
238: product array except self
这个题目的算法也是很常见的from left-right, from right -left的思想，这样做的目的是为了能很方便地找到以任意一个元素为参考元素，它的左边的product 和它的右边的product的值，最后很容易找出两者乘积。其实这里利用的是dp的思想，但是这里的直接的想法需要两个O（n）， 而dp的空间是容易压缩的，在计算第二个array的时候我们其实可以直接算，不需要存储。

237： Delete node in a linklist
这个题目看起来像是普通的delete node in a linklist,但是其实是只已知linklist里面要删的那个node, 并没有给定linklist的head，这个题目算法也很简单就跟在array里面删除某个元素一样，将后面元素的值依次赋值给前面元素，最后将linklist的尾节点删除。
出错的地方： 删除一个node, 并不是给一个linklist* node指向那个node， 然后node = NULL就可以了，那样只是把指针赋值了NULL，但是原linklist是没有变化的，删除一个Node正确做法是定义一个pre指针，pre->next指向next的那个Node, 必须利用next指针来修改。
236/235: 有一篇blog专门总结过， buttom-up recursion 略
234：Palindrome linked list
这个题目要求inplace， 这个题目不能像array那样做了，因为找n-1的node不好找，并且时间复杂度高，对于linked list的palindrome的判断，palindrome 是以中间点为对称点两边对称相等的，我们可以找到linkedlist的中间点，并且保证后半部分的node个数<= 前半段node的数目，然后reverse后面一部分，这样前后两部分是相同的。
233：Number of digit one
待补，目前还不太想去想！！我也是太懒了，有时候不愿动脑子啊
232：implement queue using stack
stack : fist in last out, queue: first in first out, 要想用stack来实现queue，只要用两个stack倒就可以了，这个题目的算法做的也是很熟了。push time complexity: O(1).
pop time  complexity: O(n) 但是armor time O(1)
但是如果是用queue来实现stack, 方法就跟这个不一样了， 因为queue是从尾进从头出，所以用一个queue就可以实现stack，在top 和 pop操作的时候， 先把queue里面除最后那个元素以外的元素push到queue尾部， 然后正常取和pop就好了。

small class 8/15
Q2：给一个范围，要求计算一个BST在这个范围内的Node的个数
M1: 这个题目首先想到的是如果这棵树不是BST的话，我们可以get left and get right， then check the root and return left + right +1。
但是题目中给定的是BST，肯定需要利用到BST的性质对这个题目的时间复杂度进行优化，或者对这个问题进行剪枝
对于current node， 如果他的value比range的左边界还要小，那么这个node的左侧是不存在介于range中间的数，只能在右侧找， 如果他的value比range的右边界还要大，那么这个Node的右侧是不存在介于range 中间的数，只能从左侧找。如果在中间，那么就需要get left , get right并且return left + right + 1了。
M2: 这个题目其实和之前做过的那个get keys in a given range in BST 是一样的，算法是如果current node > minimal, 那么可以找到左子树的nodes， 如果当前nodes 介于两者之间那么 rst + 1； 如果current node < maximal，那么可以找到右子树的nodes,
void helper(int &rst, TreeNode* root, int min, int max) {
    //base case
    if (root == NULL) return;
    if (root->value > min) {
      helper(rst, root->left, min, max);
    }
    //in order to keep the result in ascending order, for binary search tree, we have to use inorder traversal
    if (root->value <= max && root->value >= min) rst++;
    if (root->value < max) {
      helper(rst, root->right, min, max);
    }   
  }


Q3: check if an array is a valid postorder traversal of a BST
对于BST的题目，首先要知道一定要利用BST的性质来有效剪枝，或者利用BST的性质来check是否满足性质。
对于这个题目， valid BST means for every node in the tree, all nodes in left subtree is smaller than the root value, and all nodes in right subtree is larger than the root value. 我们需要对任何一个node都进行这样的判断，只有满足所有的node都是valid的时候，才是一棵valid的BST。
首先postorder + BST是可以把一棵树重建起来的，但是这个题目并不需要重建一棵BST的树， 从Postorder 我们可以找到root, 然后我们通过从left->right来判断左子树和右子树的范围，所有左子树的节点值都是比root小，所有右子树的节点值都是比root大，如果在扫描的过程中，我们发现有一个应该存在于右子树的节点的值比root小，那么这棵树是invalid。
我们可以通过这样的方法递归判断所有的node是否valid。

Bool isBST(vector<int> &postorder, int left, int right) {

   If (postorder.size() == 0) return true;

   //find the root

   Int root = postorder[right];

   //from left to right find the first cut with nodes smaller than root

   int cut = 0;

   while (cut < right && postorder[cut] < root) ++cut;

   for(int j = cut; j < right; j++) {

      if (postorder[j] < root) return false;

   }

   Return isBST(postorder, left, cut) && isBST(postorder, cut+1, right);

}

Q4：
longest bitonic sequence:
bitonic sequence : 0-i is in ascending order, i-n is in descending order
find the longest bitonic sequence to find the longest bitonic sequence

这个题目跟之前的一个题目很类似，之前那个题目是求int array里面的一个index i，使得0-i 的sum 和 i+1 - n的sum的差值最大。 对于这种一个array里面分段每段满足什么条件的题目，可以使用一个很常见的算法，从left->right扫一遍, 从 right->left扫一遍，分别对每一段单独进行分析，

//use dp to solve this problem

For every element in the array, two things will be kept

1.  From 0-I, longest ascending subsequence

2.  From right – I, longest ascending subsequence

3. combine this two result, and get the largest sum of dp1[i]+dp2[i+1]

 

Q5:

Q5.  Diagonal Sum of a Binary Tree

Consider lines of slope -1 passing between nodes (dotted lines in below diagram). Diagonal sum in a binary tree is sum of all node’s data lying through these lines. Given a Binary Tree, print all diagonal sums. For the following input tree, output should be 11, 14, 5.

感觉这个像是一个观察题，其实slope = -1的在同一条线上的点，是任意一个node起向左走相同的距离的所有点的和，要找到不同的距离上的不同的点，我们可以用一个map来记录并且在traverse整个tree的时候记录距离。

这个题目感觉算法很简单，就是遍历树的时候，如果向左走，距离就+1，如果向右走，距离就不变，在current node的时候把这个node对应的index的值 + current node value。 

但是实现这个算法过程中遇到很多错误，对递归的掌握还是很差！

首先： 记录index的那个值 idx需要维护在一条递归路径上的值，index不发生在当前同一层，也不是一个global的量，所以是在一条递归路径上的，需要作为一个参数传到递归function的signiture中；

其次: 向左走距离+1，向右走距离不变，这个怎么实现？ 对于树的遍历常见的有几种情况，preorder, inorder, postorder， 但是这些都是以根的遍历顺序来的，先左后右，在这三种情况下的任何一个地方加上idx+1都是不合适的，这个时候我们应该想到如果先走右子树，然后在走左子树的同时idx+1,这样就能实现这个算法了：

 class Solution {
public:
    void helper(TreeNode* root, vector<int> &rst, int idx ,map<int,int> &sum) {
    if (root == NULL) return;
    helper(root->right, rst, idx, sum);
    sum[idx] += root->val;
    helper(root->left, rst, ++idx, sum);
}
vector<int> diagonalSum(TreeNode* root) {
    vector<int> rst;
    if (root == NULL) return rst;
    map<int, int> sum;
    helper(root, rst, 0, sum);

    return rst;
}
};

遇到新的问题一定要冷静分析一下，一步一步怎么做，知道能够实现的算法了怎么去实现，比如这个题目肯定是要对整个树进行遍历才能得到答案的，然后要想到常见的遍历算法是什么，能不能实现，如何去进行修改。 不要慌，不去想没有思路。