leetcode 刷题日记

239. Sliding Window Maximum

745. Prefix and Suffix Search
        with many method use trie or not, balance of time and space

673. Number of Longest Increasing Subsequence

535. Encode and Decode TinyURL
        design qps+storage+ read write pattern

239. Sliding Window Maximum

256. Paint House

265. Paint House II

276. Paint Fence

572. Subtree of Another Tree

637. Average of Levels in Binary Tree

653. Two Sum IV - Input is a BST

750. Number Of Corner Rectangles
        do not us dp

764. Largest Plus Sign

525. Contiguous Array

801. Minimum Swaps To Make Sequences Increasing
        思路类似 stock 的dp

126. Word Ladder II
72. Edit Distance
337. House Robber III
198. House Robber
213. House Robber II
279. Perfect Squares
152. Maximum Product Subarray
312. Burst Balloons
656. Coin Path
394. Decode String
309. Best Time to Buy and Sell Stock with Cooldown
188. Best Time to Buy and Sell Stock IV
123. Best Time to Buy and Sell Stock III

388. Longest Absolute File Path
681. Next Closest Time
482. License Key Formatting
346. Moving Average from Data Stream
686. Repeated String Match
281. Zigzag Iterator
251. Flatten 2D Vector
284. Peeking Iterator
361. Bomb Enemy
298. Binary Tree Longest Consecutive Sequence
394. Decode String
40. Longest Substring with At Most K Distinct Characters

刚面完事 懈怠了

别懈怠，加油啊！

159. Longest Substring with At Most Two Distinct Characters
683. K Empty Slots
        many ways by time  by position
737. Sentence Similarity II
734. Sentence Similarity
307. Range Sum Query - Mutable
308. Range Sum Query 2D - Mutable
418. Sentence Screen Fitting
        dp or join

425. Word Squares
        any better way ?

163. Missing Ranges
        possible min max value

393. UTF-8 Validation

66. Plus One
369. Plus One Linked List
271. Encode and Decode Strings
351. Android Unlock Patterns
332. Reconstruct Itinerary
766. Toeplitz Matrix
289. Game of Life

请问地主按啥刷的？类型？

687. Longest Univalue Path
288. Unique Word Abbreviation
320. Generalized Abbreviation
        all integer? len = 0
        integer > 10    124 from right to left!!!!
280. Wiggle Sort
324. Wiggle Sort II
42. Trapping Rain Water
407. Trapping Rain Water II
54. Spiral Matrix
59. Spiral Matrix II
81. Search in Rotated Sorted Array II
350. Intersection of Two Arrays II

sqf 发表于 2018-6-29 13:06
请问地主按啥刷的？类型？

最近按公司的tag刷 以前按题目类别

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;
               
        }