8月刷题/Mock interview接龙活动（缺米刷题的来）

08/16 Day 16打卡：

Delete Node in a BST
Height Checker
Best Time to Buy and Sell Stock III

08/17

平衡二叉树 求树高度变形 中间加入高度差判断如果不平衡返回-1

组合总和 回溯解决 跟子序列是类似

二叉树寻路 利用对数确定label位置 然后查找 翻转奇数行

刷题第三天：
7整数反转const reverse = x => {    const limit = 2147483648;
    const k = x < 0 ? -1 : 1;
    const n = Number(String(Math.abs(x)).split('').reverse().join(''));
    return n > limit ? 0 : n * k;
};

8：字符串转换整数 (atoi)
var myAtoi = function(str) {
    let atoi = '';
    let string = str.replace(' ', '');
    let times = 1;
    if(string[0] === '-'){
        string = string.subString(1)
        times = -1;
    }

    for(let i=0; i< string.length; i++){
        while(Number.isInteger(string[i])){
            atoi += string[i];
        }
    }
    atoi = times *parseInt(atoi, 10);
    if(atoi > Math.pow(2, 31) - 1) {
        return Math.pow(2, 31) - 1;
    }
    if(atoi < Math.pow(-2, 31)) {
        return Math.pow(-2, 31);
    }
    return atoi;
};
9：回文数
var isPalindrome = function(x) {
    let even = true;
    let str = x.toString();
    let num = str.length/2;
    if(!Number.isInteger(num)){
        even = false;
        num = (str.length-1)/2;
    }
    for(let i= 0; i<num; i++){
        if(str[i] !== str[str.length-1-i]){
            return false
        }
    }
    return true;
};

wen jun fan 发表于 2020-8-17 10:08
刷题第三天：
7整数反转const reverse = x => {    const limit = 2147483648;
    const k = x < 0 ? -1 ...

啊昨天刷题时间超过半夜12点。。。导致今日缺米不能给前面小伙伴加分了，万恶的周六啊不好意思

Insert Delete GetRandom O(1): 用list来记val，用来随机抽取数字，用hashmap记value跟他在list里的idx，用于删除，删除的时候可以在list里跟last 位置swap，然后pop
Serialize and Deserialize Binary Tree：用level order traversal
Regular Expression Matching： 用的dp的方法，pattern里有"." 跟正常字母是是从dp[i-1][j-1]里看, 有'*'时是从dp[i][j-1],dp[i][j-2]和dp[i-1][j]里看，还可以用finite state machine的方法，可以了解下

今天做了Next Greater Element I, II, Daily Temperature，主要用到的是单调栈。值得注意的是，单调栈从后往前做的space complexity更优。

Day13 今天休息休息 两道题

8月打卡，day 14

8.16 Sort& Heap
#264. Ugly Number II
#313. Super Ugly Number
#1046. Last Stone weight

Ugly number: using heap and loop through prime list will cost O(n*k*logk)
But if we record the index and prime channel it will be O(n*logk)

For last stone, notice if hq[0] != 0, we dont add it back to the heap!

8月16日 刷题第十六天 打卡16天

-加油！

今天3道题

1. Find target successor at BST
-就是一个简单的inorder Traversal
-然后用一个boolean flag来记录有没有找到target
-如果找到target，那么下一个就是要找的元素
-如果target之后没有元素了，那么就返回-1；

2.All subsetsII（DFS升级版） -> 有重叠，无序的string
-转化成有序的array
-然后需要一个list，还需要一个set
-最后DFS处理的时候先处理第一次遇到的char，慢点遇到以后就
-直接去重

3.Leetcode 333 largest BST subtree（时间复杂度要求O(n))
High level:
Use recursion, and use a helper function and find left hand side largest BST subTree
and rightHandside largest BST subTree;
Besides, if root.value larger than the max value of left BST subTree and root.value smaller than min value of rightBST subTree ->
then this root itself can form a larger BST with both left and right BST;

Small trick here, use a int[] array to store the current minValue, maxValue and current longest BST subtree.

Details:
base case:
if (root == null) {
   return {Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
}

recursive rule
int[] left = helper(root.left);
int[] right = helper(root.right);
//initialize a new array;
int[] newArray = new int[3];
case 1:(root can be added to form a larger BST)
//if (root.key > left[1] && root.key < right[0]) {
   update current new array;
}
case 2:(otherwise)
// update the only new Array[2] -> max(left[2], right[2]);

//总结：O(n)的时间复杂度的做法结合recursion已经想到了；
//也考虑到使用int[] globalMax来记录最长的BST
//也考虑到使用int[] minAndMax用来表示当前的最大最小值
//关键是helper function当中的分左右情况没有考虑清楚，然后recursive rule 分析得太复杂了

//提炼一下：
//用一个int[] array当中带三个参数表达当前的最小值，最大值和最长BST节点个数
//在recursive rule里面，
//Step1: 分别建立属于left， right的两个arrays
//然后从helper function处拿到返回值
//Step2:
//建立当前的new Array，并去根据具体cases来分析并update
//case1(root 可以并做更大的subTree）
//case2(otherwise)
//返回当前的new Array

今日份的刷题就到这里，如果觉得对你也有参考价值，请点赞，加米，握手三连！谢谢！加油加油！