蜗居匹兹堡孤独刷题中

挂了亚麻onsite过去两周了，也没有别的像样的面试。每逢佳节倍思亲，孤独的春节更让人难熬。
开个刷题战拖吧，每天定一个目标，监督自己完成。

准备先根据分类刷，如果拿到重要公司的面试，就按公司题目再刷。
今天是２０１９年２月５日，今天的目标是Tree的题目，争取能做15道题，睡觉前再投５个公司。
根据自己目前的理解，这类题目主要是练习两种算法：BFS和DFS。
BFS一般就是iterative算法，用到Stack或者Queue。DFS就是递归的写法，关键点在于：1)如何定义这个递归函数；２）用这个函数来表示父子间关系，能不能递归下去；３）递归的出口是null还是leaf；４）如何传递结果；
目前自己已经掌握了preorder, inorder, postorder, level order的递归写法，也掌握了preorder, inorder的iterative写法，尚未掌握postorder的非递归写法。
今天做完15道题再总结一下。加油加油！

Wilson_2014 发表于 2019-2-6 12:09
真恨自己不是妹子。。。
太感谢了！我明天去转一圈碰碰运气。

没事儿！加油，祝好运！时间地点也贴给你呀 不过按道理讲他说这个intern和full time应该只是为了分流 上午下午摊子是不会变的你要是乐意的话，上午应该也可以去排

[size=14.6667px]Weigand Gym—on the first floor of the Cohon University Center

[size=14.6667px]10 a.m. - 12:45 p.m. - Internship Opportunities*
[size=14.6667px]1 p.m. - 2 p.m. - EMPLOYER LUNCH BREAK—Career Fair will be closed during this time
[size=14.6667px]2 p.m. - 4:45 p.m. - Full-time Opportunities*
[size=14.6667px]

[size=14.6667px]

Wilson_2014 发表于 2019-2-6 11:58
不是CMU的学生，能进去吗？

进场地要刷CMU的ID卡，你有在CMU的同学可以借你卡的吗？
楼楼你要是不是妹子的话可能我的卡借不了你哎，哭
不过这两天还有图森和高盛的tech talk，按道理讲这个应该是不用刷卡的，信息贴给你

Thursday, February 7, 2019 - 6:30 pm to 7:30 pm
TuSimple
ZEHUA HUANG
Vice President of Engineering
TuSimple
4305  Newell-Simon

Friday, February 8, 2019 - 4:15 pm to 5:30 pm
Goldman Sachs Resume Review / Interview Preparation Workshop
Reddy Conference Room 4405  Gates Hillman

加油鸭

Day 13 - 2019/02/17

今天虽然只做了两道题，只要感觉有收获就好吧

301. Remove Invalid Parentheses

最高票的那个解法，我只想用精妙绝伦来形容，花了不少时间才改写成功，使自己对这个逻辑相对清楚了一些.
但是还有一点不明白，就是这个代码是怎么保证对str做最小改变的？ How this algorithm avoid exhaust all possible valid substrings, but only shortest ones.
现在想明白了，因为这个算法之处理多出来的右括号，不管什么时候发现这个右括号，都能判断它需要被去掉，所以能保证只去掉必要的括号。  

方法一：回溯法：
        1. 不需要stack判断括号valid，只需要计算左括号和后括号的数量。
        2. 只处理右括号，只要右括号数量超过左括号数量，就说明直到当前位置的string需要处理
        3. 在处理过程中，我们规定只去掉第一个右括号，这样就可以避免重复解，所以我们要传入上一次去掉右括号的位置
        4. 通过for循环，回溯处理当前位置之前的字符串，在不同位置删除右括号，会产生不同的解
        5. 递归的定义：startPos之前的字符串是valid，上一次删除括号的位置是lastRemoved。
        6. 递归的分解：for循环找可以删除的右括号，分别将他们删除并向下递归
        7. 递归的出口：当开始位置到达最右边。
        8. 递归的除重：规定只从第一个右括号开始删除，这样可以避免递归过程中产生重复解。
        9. 右括号处理完毕之后，将字符串反转，以同样方法处理左括号，处理完左括号之后，将这个解加入rst。
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> rst = new ArrayList<>();
        remove(s, 0, 0, new char[]{'(',')'}, rst);
        return rst;
    }

    private void remove(String s, int startPos, int lastRemoved, char[] par, List<String> rst){
        int currInvalidPos = findInvalidPos(s, startPos, par);

        if(currInvalidPos == s.length()){
            String reversed = new StringBuilder(s).reverse().toString();
            if(par[0] == '('){
                remove(reversed, 0, 0, new char[]{')','('}, rst);
            }else{
                rst.add(reversed);
            }
            return;
        }
        
        for(int j = lastRemoved; j <= currInvalidPos; j++){
            if(s.charAt(j) == par[1] && (j == lastRemoved || s.charAt(j - 1) != par[1])){
                remove(s.substring(0, j) + s.substring(j + 1, s.length()), currInvalidPos, j, par, rst);
                //because we removed one character, currInvalidPos += 1, it will be the next startPos
            }
        }
    }
   
    private int findInvalidPos(String s, int startPos, char[] par) {
        int stack = 0;
        int i = startPos;
        while(i < s.length()){
            if(s.charAt(i) == par[0]) stack++;
            if(s.charAt(i) == par[1]) stack--;
            if(stack < 0) return i;
            i++;   
        }
        return s.length();
    }
}

方法二：回溯法：
相比之下，我更喜欢这个方法，思路上要清晰的多。
使用两个参数（maxOpenRm和maxCloseRm）保证 Remove the minimum number of invalid parentheses
联用unMatched保证curr是valid。这三个参数是非常好的设计。
然后就是结果要注意除重。
时间复杂度如果按搜索类问题来讲就是：答案个数 * 构造每个答案的时间
最坏情况我觉着是O(n * 2^n)，但是这个算法里有pruning，所以时间复杂度应该远小于这个。

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int maxOpenRm = 0;
        int maxCloseRm = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                maxOpenRm++;
            } else if (s.charAt(i) == ')'){
                if (maxOpenRm > 0) {
                    maxOpenRm--;
                } else {
                    maxCloseRm++;
                }
            }
        }
        Set<String> rstSet = new HashSet<>();
        dfs(s, 0, new StringBuilder(), rstSet, maxOpenRm, maxCloseRm, 0);
        return new ArrayList<>(rstSet);   
    }
   
    private void dfs (String s, int pos, StringBuilder curr, Set<String> rstSet, int maxOpenRm, int rmR, int unMatched) {
        //Limit max removal rmL and rmR for backtracking boundary.
        //Otherwise it will exhaust all possible valid substrings, not shortest ones.
        if (maxOpenRm < 0 || maxCloseRm < 0 || unMatched < 0) return;
        
        if (pos == s.length()) {
            //Check whether curr is valid
            if (maxOpenRm == 0 && maxCloseRm == 0 && unMatched == 0) {
                rstSet.add(curr.toString());
            }
            return;
        }
        
        int originalLen = curr.length();
        char c = s.charAt(pos);
        if (c == '(') {
            dfs(s, pos + 1, curr, rstSet, maxOpenRm - 1, maxCloseRm, unMatched);            //not adding this '(' to curr
            dfs(s, pos + 1, curr.append(c), rstSet, maxOpenRm, maxCloseRm, unMatched + 1);  // add to curr
        } else if (c == ')') {
            dfs(s, pos + 1, curr, rstSet, maxOpenRm, maxCloseRm - 1, unMatched);             // not adding this ')' to curr
            dfs(s, pos + 1, curr.append(c), rstSet, maxOpenRm, maxCloseRm, unMatched - 1);   // add to curr
        } else {
            dfs(s, pos + 1, curr.append(c), rstSet, maxOpenRm, maxCloseRm, unMatched);
        }
        curr.setLength(originalLen);
    }
}

方法三：BFS：
把每个str都当成一种状态，对于valid的str，加入rst，invalid的str，就改变其中的一个字符，然后加入Queue。
每个字符取和不取，一共有O(2^n)个subset，检查valid要O(n),一共是O(n*2^n)class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> rst = new ArrayList<>();
        if (s == null) return rst;
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(s);
        visited.add(s);
        
        boolean stopAdding = false;
        while (!q.isEmpty()) {
            String curr = q.poll();
            
            if (isValid(curr)) {
                rst.add(curr);
                stopAdding = true;
            }
            
            if (stopAdding) continue;
            
            for (int i = 0; i < curr.length(); i++) {
                if (curr.charAt(i) != '(' && curr.charAt(i) != ')') continue;
                String modified = curr.substring(0, i) + curr.substring(i + 1, curr.length());
                if (!visited.contains(modified)) {
                    q.offer(modified);
                    visited.add(modified);
                }
            }
        }
        return rst;
    }
   
    private boolean isValid(String s) {
        int count = 0;
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '(') count++;
            if (s.charAt(i) == ')') count--;
            if (count < 0) return false;
            i++;
        }
        return count == 0;
    }
}

394. Decode String
这道题从这个例子s = "3[a2[c]]",可以看出是一个递归比较合适的结构。

解法一：recursion
感觉这道题不太适合用递归，想不到什么方法能够不用全局变量。主要是不知道对subStr进行递归后，指针的终止位置在哪里，只要用一个全局变量postion。

解法二：stack
要想到用两个stack，这样会方便许多。count用一个stack，因为当第二个number出现的时候，第一个还没法处理。然后就是需要另一个stack
存当前的字符串，每次遇到']’的时候，就是进行repeat的时候了，这时候要把之前处理的结果pop出来：
要搞清楚什么时候push，什么时候pop，要多练几遍。

加油 我也在孤独的刷题 不知道前路在哪里 共勉

hadoopG 发表于 2019-2-6 07:47
加油 我也在孤独的刷题 不知道前路在哪里 共勉

握握爪

孤独刷题+1, 求建一个孤独刷题群

哈哈楼楼平常活动范围是匹村哪里呀

Opus_A 发表于 2019-2-6 11:03
哈哈楼楼平常活动范围是匹村哪里呀

我在waterfront住，这两天是不是CMU有招聘会啊？

Day 1

102. Binary Tree Level Order Traversal
练习了一下DFS，每次传入level，并传入List<List<Integer>> rst用来记录结果。
BFS先不练了。

114. Flatten Binary Tree to Linked List
这道题我先用了一个Divide & Conque的解法，定义了RstType作为递归的返回值，返回这个Tree被Flatten之后的起点和终点。
这个写法比较繁琐，有两个地方容易出错，第一，注意在preorder traversal的时候，把每个node的左指针指向null。第二，对左右儿子单独为null的讨论。

看了别人的postorder加全局变量prev的写法，学写一遍。
还有preorder不用全局变量的写法，这个写法比较直观，先记录一下左右儿子，然后对左右子树分别flatten，关键是用一个指针找到左子树flatten之后的末尾node，学写一遍。
非递归不太好掌握，以后再写吧。

96. Unique Binary Search Trees
95. Unique Binary Search Trees II
这两道都是看答案才写出来的。一个是求所有方案的个数，一个是求所有方案。所以第一用DP，第二个用DFS。有两点需要注意：1）对于选定pivot，方案数等于左子树所有方案数乘以右子树所有方案数。2）DFS的时候，List<TreeNode>得作为结果返回，而不是才参数中进行传递。这和我经常使用的DFS求所有方案有所不同的地方。
这道题的时间复杂度需要一些数学推算，暂时懒得算了，到时候就直接说等于方案总数乘以构建每个方案的时间得了。

116. Populating Next Right Pointers in Each Node
这道题用递归不太好想，非递归用Queue比较直观，但是写起来比较繁琐。

543. Diameter of Binary Tree
这个题跟124是一个解法。关键点在于递归函数的返回值不是最终要的结果，要用一个全局变量，在递归过程中不断更新这个变量，从而求得极值。

199. Binary Tree Right Side View
这道题我用preorder做的，因为要先遍历左子树，所以传入了level和一个map，更新同一level的map值。最后返回的时候new ArrayList<Integer>(map.values())也算是通过了。
讨论区有个更好的解法是先遍历右子树，这样就不用map了。
这个题的iterative的解法先不练了。
这次亚麻的onsite第四轮，出的题是从上往下看，找到没有遮住的点，然后按从左往右的顺序打印。这个题我现在还没有做到，写到这里mark一下。

111. Minimum Depth of Binary Tree
这道题我有用全局变量了，其实完全不用。还是不想练iterative

107. Binary Tree Level Order Traversal II
懒，还是只用了level order递归。 用了Arraylist.add(0, xxx)方法每次加到list最前面。

112. Path Sum
我怎么又画蛇添足定义了一个helper

437. Path Sum III
这道题非常好，以后要多做

103. Binary Tree Zigzag Level Order Traversal

337. House Robber III
找三代间的关系，似乎有很多重复计算啊？用不用dp优化一下？

106. Construct Binary Tree from Inorder and Postorder Traversal
把图画好，最后用具体例子测试一遍，确保index都是对的。

653. Two Sum IV - Input is a BST
老老实实写一个hashset吧，这个和Path Sum III不一样

538. Convert BST to Greater Tree
这道题要老老实实写一遍非递归，明早背一遍postorder的非递归，今天实在是脑子不想转了

Wilson_2014 发表于 2019-2-6 11:31
我在waterfront住，这两天是不是CMU有招聘会啊？

有哎，明天还有~

Opus_A 发表于 2019-2-6 11:48
有哎，明天还有~

不是CMU的学生，能进去吗？