leetcode 刷题日记

自己开一个刷题日记，用来提醒和督促自己坚持刷题，上课学期借口学校课重，一题没刷的结果就是现在要从头再刷，，代价惨重。立贴为证， 除个赶due， 考试， 面试等特殊情况，leetocde每天五题以上！


补充内容 (2018-7-1 02:17):
走过路过加点米哈

居然忘了自己还有一个刷题贴。。
2.23: 主刷linkedlist
Odd Even Linked List   
Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Add Two Numbers II

203. Remove Linked List Elements
3. Longest Substring Without Repeating Characters
490. The Maze
505. The Maze II
lintcode 819. Word Sorting

两道面经题加无处安放的代码

//第一个把下面的格式的字符串变成树：node有键，值和子树。比如第一个的键是node1，值是‘aaaa'
        // <node1>aaaaa<node2>bbbbb<node5>csdfds</node5><node6>ddsdfdd</node6></node2><node3>cccc</node3><node4>dddd</node4></node1>
    public TreeNode solve(String s) {
            if (s == null || s.length() == 0) return null;
            Deque<TreeNode> stack = new LinkedList<>();
            char[] array = s.toCharArray();
            int i = 0;
            while(i < array.length) {
                    i = s.indexOf('<', i);
                    if (i == -1) break;
                        i++;
                        if (array[i] == '/') {   //end of a node
                                TreeNode cur = stack.pop();
                                i = s.indexOf('>', i);
                                if(!stack.isEmpty()) {
                                        TreeNode parent = stack.peek();
                                        parent.children.add(cur);
                                } else stack.push(cur);
                               
                        } else {   //deal with node name
                                int key_end = s.indexOf('>', i);
                                String key = s.substring(i,key_end);
                                i = key_end +1;
                                int val_end = s.indexOf('<', i);
                                String val = s.substring(i, val_end);
                                TreeNode cur = new TreeNode(key, val);
                                stack.push(cur);
                        }
            }
           
        return stack.peek();
    }
    class TreeNode {
            String key;
            String val;
   
            List<TreeNode> children;
            public TreeNode(String key, String val) {
                    this.val = val;
                    this.key = key;
                    children = new ArrayList<>();
            }
    }



字符串自然顺序比较，被提醒了各种corner case     a12和a9相比a9更小。a12和b9相比a12更小   a4b2 < a3c1
private void update(String s, int[] pairs) {
                pairs[2] = 0;
                if (pairs[0] >= s.length()) {
                        pairs[0]++;
                        return;
                }
                pairs[1] = s.charAt(pairs[0]);
                pairs[0]++;
                if(!Character.isDigit(s.charAt(pairs[0]))) pairs[2] = 1;
                else {
                        while(pairs[0] < s.length() && Character.isDigit(s.charAt(pairs[0]))) {
                                pairs[2]= pairs[2] * 10 + s.charAt(pairs[0])-'0';
                                pairs[0]++;
                        }
                }
        }

        public int compare(String s1, String s2) {
                if (s1.equals(s2)) return 0;
                int[] pairs_s1 = new int[]{0, 0, 0};  //pairs_s1 index        char digit
                int[] pairs_s2 = new int[]{0, 0, 0};
                while (pairs_s1[0] <= s1.length() && pairs_s2[0]<= s2.length()) {
                        if (pairs_s1[1] != pairs_s2[1]) return pairs_s1[1] - pairs_s2[1];
                        if (pairs_s1[2] == pairs_s2[2]) {
                                update(s1, pairs_s1);
                                update(s2, pairs_s2);
                        } else if (pairs_s1[2] < pairs_s2[2]) {
                                update(s1, pairs_s1);
                                pairs_s2[2] = pairs_s2[2]-pairs_s1[2];
                        } else {
                                update(s2, pairs_s2);
                                pairs_s1[2] = pairs_s1[2]-pairs_s2[2];
                        }
                       
                }
                if (pairs_s1[2] == 0 && pairs_s2[2] == 0) return 0;
                return pairs_s1[2] == 0? -1:1;
               
        }

//每行都是先0后1（比如00011111），输出0出现最早的那一行
        public int findrow (int[][]matrix) {
                if (matrix.length == 0 || matrix[0].length == 0) return 0;
                int m = matrix.length;
                int n = matrix[0].length;
                int res = 0;
                int i = m-1;
                int j = n-1;
                int pos = n;
                while (i >= 0 && j >= 0) {
                        while (j >= 0 && matrix[i][j]== 1) {
                                j--;
                        }
                        if (j < pos) {
                                pos = j;
                                res = i;
                        }
                        i--;
                }
                return res;
        }


18. 4Sum
454. 4Sum II
399. Evaluate Division
688. Knight Probability in Chessboard
270. Closest Binary Search Tree Value
272. Closest Binary Search Tree Value II

加油加油！

2.25
Find K Closest Elements 用两种方法解决 直接一次binary search 的方法 非常巧妙

2.26
Search for a Range
Longest Increasing Subsequence
Russian Doll Envelopes  只会dp解法 follow up 的binary search方法有待研究
queue by two stacks;
stack with min()

2.27
reorder list
partition list
subset I
subsetII
permutation I II 新方法 swap

支持楼主~顺便想问问楼主是大几呀QAQ

iterative way to  traverse binary tree(in-order post-order pre-order) (post-order is a reverse of pre-order which first go to right leaf, then left leaf)
Symmetric Tree
Balanced Binary Tree
Validate Binary Search Tree
tree 相关 还需要再练！还是不熟练invert binary tree
count unicalue subtree
maximum path sum binary tree

楼主加油!

6.8
1  301. Remove Invalid Parentheses
        变种题
        remain left remain right
        set deduplicate

2 273. Integer to English Words
        how to represent different number  array, hash map  enum?
        recursion or iteration
        corner case

3 67 add binary
        if (tooooo long)
        concise code

4 253 Meeting Room II

5 17 letter combination of a Phone Number

6 325. Maximum Size Subarray Sum Equals k

7 91. Decode Ways
        dp

8 639. Decode Ways II
        dp

9 task scheduler
        priority queue 解法 更make sense  O(n) 解法不具有通用性