努橙刷题编: 八月 2016

2016年8月23日星期二

[LeetCode]103. Binary Tree Zigzag Level Order Traversal

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    var result = [];
    if (root == null) {
        return result;
    }
    var queue = [];
    queue.push(root);
    var isOdd = true;
    while (queue.length != 0) {
        var size = queue.length;
        var level = [];
        for (var i = 0; i < size; i++) {
            var node = queue.shift();
            if (node.left != null) {
                queue.push(node.left);
            }
            if (node.right != null) {
                queue.push(node.right);
            }
            level.push(node.val);
        }
        if (isOdd == false) {
            level.reverse();
        }
        result.push(level);
        isOdd = !isOdd;
    }
    return result;
};

[LeetCode]107. Binary Tree Level Order Traversal II

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    var result = [];
    if (root == null) {
        return result;
    }
    var queue = [];
    queue.push(root);
    while (queue.length != 0) {
        var size = queue.length;
        var level = [];
        for (var i = 0; i < size; i++) {
            var node = queue.shift();
            if (node.left != null) queue.push(node.left);
            if (node.right != null) queue.push(node.right);
            level.push(node.val);
        }
        result.push(level);
    }
    return result.reverse();
};

[LeetCode]102. Binary Tree Level Order Traversal

A
/ \
B C
/ \ \
D E F

(1) 2 queues
Q1: A
Q2: BC
Q1: DEF
Q2: [N]
Q1: [N]

(2) 1 queue + dummy node
Q: A#BC#DEF#

(3) 1 queue + queue.size

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (queue.size() != 0) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                level.add(node.val);
            }
            result.add(level);
        }
        return result;
    }
}

* Same if it's not binary tree

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {
    static class TreeNode {
        int val;
        List<TreeNode> children;
        public TreeNode(int val, TreeNode...nodes) {
            this.val = val;
            this.children = new LinkedList<TreeNode>();
            for (TreeNode node : nodes) {
                this.children.add(node);
            }
        }
        public int getVal() {
            return val;
        }
        public void setVal(int val) {
            this.val = val;
        }
        public List<TreeNode> getChildren() {
            return children;
        }
        public void setChildren(List<TreeNode> children) {
            this.children = children;
        }
    }
    
    public static List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(queue.size() != 0) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                for (TreeNode child : node.getChildren()) {
                    queue.offer(child);
                }
                level.add(node.val);
            }
            result.add(level);
        }
        return result;
    }
    
//            1
//          / | \
//        2   3   4
//       /|\  |   |
//      5 6 7 8   9
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(5), new TreeNode(6), new TreeNode(7)), new TreeNode(3, new TreeNode(8)), new TreeNode(4, new TreeNode(9)));
        List<List<Integer>> result = levelOrderTraversal(root);
        for (List<Integer> list : result) {
            for (Integer i : list) {
                System.out.print(i);
                System.out.print(' ');
            }
            System.out.println();
        }
    }
}

[LeetCode]#388 Longest Absolute File Path

public class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0 || !input.contains(".")) {
            return 0;
        }
        
        String[] list = input.split("\n");
        Deque<Integer> stack = new ArrayDeque();
        int curLength = 0;
        int maxLength = -1;
        for (String s : list) {
            int tabs = 0;
            while (s.charAt(tabs) == '\t') {
                tabs++;
            }
            while (tabs < stack.size()) {
                curLength -= stack.pop();
            }
            s = s.substring(tabs);
            if (s.contains(".")) {
                maxLength = Math.max(maxLength, curLength + s.length());
            } else {
                curLength += s.length() + 1;
                stack.push(s.length() + 1);
            }
        }
        return maxLength;
    }
}

[LeetCode]#386 Lexicographical Numbers

* Java comparator - O(nlogn) Time Limit Exceeded

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            result.add(i);
        }
        Collections.sort(result, new Comparator<Integer>(){
            @Override
            public int compare(Integer i1, Integer i2) {
                return (Integer.toString(i1)).compareTo(Integer.toString(i2));
            }
        });
        return result;
    }
}

*O(n) Solution

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<Integer>();
        if (n <= 0) {
            return result;
        }
        
        int tmp = 1;
        for (int i = 1; i <= n; i++) {
            result.add(tmp);
            if (tmp * 10 <= n) {
                tmp *= 10;
            } else if (tmp + 1 <= n && tmp % 10 != 9) {
                tmp += 1;
            } else if (tmp % 10 != 9) {
                tmp = tmp / 10 + 1;
            } else {
                tmp++;
                while (tmp == (tmp / 10) * 10) {
                    tmp /= 10;
                }
            }
        }
        
        return result;
    }
}

[LeetCode]#124 Binary Tree Maximum Path Sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    class Result {
        public int max; // max path not necessarily from current root to leaf
        public int maxPath; // max path from current root to leaf node
        
        public Result(int max, int maxPath) {
            this.max = max;
            this.maxPath = maxPath;
        }
    }
    
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Result result = getMaxPathSum(root);
        
        return result.max;
    }
    
    public Result getMaxPathSum(TreeNode root) {
        if (root == null) {
            return new Result(Integer.MIN_VALUE, Integer.MIN_VALUE);
        }
        
        Result left = getMaxPathSum(root.left);
        Result right = getMaxPathSum(root.right);
        
        int maxPath = Math.max(0, Math.max(left.maxPath, right.maxPath)) + root.val;
        int maxChild = Math.max(left.max, right.max);
        int maxPassRoot = Math.max(0, left.maxPath) + Math.max(0, right.maxPath) + root.val;
        
        int max = Math.max(maxPath, Math.max(maxChild, maxPassRoot));
        
        return new Result(max, maxPath);
        
    }
}

[笔记整理] 九章算法第五章 Dynamic Programming

2016年8月11日星期四

[LintCode] #89 K Sum

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    
    // state: f[i][j][t] - for the first i elements in A, pick j elements, how many solutions are there to get sum = t
    // function: f[i][j][t] = f[i - 1][j - 1][t - A[i]] + f[i - 1][j][t]
    // initialize: f[0][0][0] = 1;
    // result: f[A.length][k][target]
    public int kSum(int A[], int k, int target) {
        // write your code here
        if (A == null || A.length == 0 || k == 0) {
            return 0;
        }
        int[][][] f = new int[A.length + 1][k + 1][target + 1];
        
        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= k; j++) {
                for (int t = 0; t <= target; t++) {
                    if (j == 0 && t == 0) {
                        f[i][j][t] = 1;
                        break;
                    } else if (i == 0) {
                        f[i][j][t] = 0;
                        break;
                    } else if (j != 0 && t - A[i - 1] >= 0) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                }
            }
        }
        
        return f[A.length][k][target];
    }
}

[LeetCode] #29 Interleaving String

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    
    // state: dp[i][j] - whether s3.substring(0, i + j) is formed by s1.substring(0, i) and s2.substring(0, j)
    // function: dp[i][j] = (s3[i+j] == s1[i] && dp[i - 1][j]) ||
    //                      (s3[i+j] == s2[j] && dp[i][j - 1])
    // initialize: dp[0][0] = true
    //             dp[i][0] = s3[i] == s1[i] && dp[i - 1][0]
    // result: dp[s1.length()][s2.length()]
    
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        if (s1.length() + s2.length() < s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= s1.length() && i <= s3.length(); i++) {
            dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1][0]);
        }
        for (int j = 1; j <= s2.length() && j <= s3.length(); j++) {
            dp[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1) && dp[0][j - 1]);
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length() && i + j <= s3.length(); j++) {
                dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
            }
        }
        
        return dp[s1.length()][s2.length()];
    }
}

2016年8月10日星期三

[LeetCode] #115 Distinct Subsequences

public class Solution {
    // state: f[i][j] - number of distinct subsequence of T.substring(0, j] in S.substring(0, i]
    // function: f[i][j] = f[i - 1][j] +  (f[i - 1][j - 1], if T[j] == S[i]) // Attn!
    // initialize: f[i][0] = 1
    // result f[T.length()][S.length()]
    public int numDistinct(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return 0;
        }
        int[][] f = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            f[i][0] = 1;
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                f[i][j] = f[i - 1][j];
                if (t.charAt(j - 1) == s.charAt(i - 1)) {
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
        return f[s.length()][t.length()];
    }
}

http://www.cs.cmu.edu/~yandongl/distinctseq.html

2016年8月8日星期一

[LintCode] #119 Edit Distance

public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    
    // state: f[i][j] - min steps to convert word1.substring(0,i) to word2.substring(0,j) , Attn: when i = 0, j = 0
    // function: f[i][j] = f[i - 1][j - 1], word1[i] == word2[j]
    //                   = Min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1, word1[i] != word2[j]
    // initialze: f[i][0] = i - 1, word1[0] != word2[0]
    //            f[0][i] = i - 1
    // result: f[m][n]
    
    public int minDistance(String word1, String word2) {
        // write your code here
        if (word1 == null || word2 == null || (word1.length() == 0 && word2.length() == 0)) {
            return 0;
        }
        if (word1.length() == 0 || word2.length() == 0) {
            return word1.length() == 0 ? word2.length() : word1.length();
        }
        int[][] f = new int[word1.length() + 1][word2.length() + 1]; // Attn:Why +1?
        for (int i = 0; i <= word1.length(); i++) {
            f[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            f[0][j] = j;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i][j - 1], f[i - 1][j])) + 1;
                }
            }
        }
        return f[word1.length()][word2.length()];
    }
}

2016年8月7日星期日

[LintCode] #79 Longest Common Substring

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
     
    // state: f[i][j] - length of LCS of A.substring(0, i] and B.substring(0, j]
    // function: f[i][j] = f[i - 1][j - 1] + 1, if A[i] == B[j]
    //                   = 0, if A[i] != B[j]
    // initialize: 
    // result: f[0...A.length - 1][0...B.length - 1]
    
    public int longestCommonSubstring(String A, String B) {
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        int max = 0;
        int[][] f = new int[A.length()][B.length()];
        for (int i = 0; i < A.length(); i++) {
            f[i][0] = A.charAt(i) == B.charAt(0) ? 1 : 0;
            max = Math.max(max, f[i][0]);
        }
        for (int j = 0; j < B.length(); j++) {
            f[0][j] = A.charAt(0) == B.charAt(j) ? 1 : 0;
            max = Math.max(max, f[0][j]);
        }
        for (int i = 1; i < A.length(); i++) {
            for (int j = 1; j < B.length(); j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = 0;
                }
                max = Math.max(max, f[i][j]);
            }
        }
        return max;
    }
}

2016年8月4日星期四

[LintCode] #77 Longest Common Subsequence

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    
    // state: f[i][j] - longest LCS of A.substring(0, i] and B.substring(0, j]
    // function: f[i][j] = f[i - 1][j - 1] + 1, if A[i] == B[j]
    //                   = Max(f[i - 1][j], f[i][j - 1]), if A[i] != B[j]
    // initialize: f[i][0] = A[i] == B[0] ? 1 : 0,f[0][i] = A[0] == B[i] ? 1 : 0
    // result: f[A.length - 1][B.length - 1]
    
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        int[][] f = new int[A.length()][B.length()];
        for (int i = 0; i < A.length(); i++) {
            f[i][0] = A.charAt(i) == B.charAt(0) ? 1 : 0;
        }
        for (int j = 0; j < B.length(); j++) {
            f[0][j] = A.charAt(0) == B.charAt(j) ? 1 : 0;
        }
        for (int i = 1; i < A.length(); i++) {
            for (int j = 1; j < B.length(); j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[A.length() - 1][B.length() - 1];
    }
}

[LeetCode] #300 Longest Increasing Subsequence

public class Solution {
    // state: f[i] - length of LIS for nums[0...i]
    // function: f[i] = (Max(f[j] + 1), if nums[j] < nums[i]), for all 0 < j < i
    // initialze: f[0] = 1
    // result: Max(f[0...nums.length-1]) //Attn!
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] f = new int[nums.length];
        int maxLength = 1;
        for (int i = 0; i < nums.length; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                    maxLength = Math.max(maxLength, f[i]);
                }
            }
        }
        return maxLength;
    }
}

[LeetCode] #140 Word Break II

Recursion, time complexity: O(2^n), Time Limit Exceeded

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(s, wordDict, result, new ArrayList<String>(), 0);
        return result;
    }
    
    private void helper(String s, Set<String> wordList, List<String> result, List<String> path, int start) {
        if (start == s.length()) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (wordList.contains(s.substring(start, i))) {
                path.add(s.substring(start, i));
                helper(s, wordList, result, path, i);
                path.remove(path.size() - 1);
            }
        }
    }
}

Recursion + pruning(avoid repeated calculation)

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        boolean[] possible = new boolean[s.length() + 1];
        boolean[] initialized = new boolean[s.length() + 1];
        Arrays.fill(possible, false);
        Arrays.fill(initialized, false);
        helper(s, wordDict, result, new ArrayList<String>(), 0, possible, initialized);
        return result;
    }
    
    private void helper(String s, Set<String> wordList, List<String> result, List<String> path, int start, boolean[] possible, boolean[] initialized) {
        if (start == s.length()) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (wordList.contains(s.substring(start, i)) && (!initialized[i] || possible[i])) {
                int resultN = result.size();
                initialized[i] = true;
                path.add(s.substring(start, i));
                helper(s, wordList, result, path, i, possible, initialized);
                path.remove(path.size() - 1);
                possible[i] = resultN < result.size();
            }
        }
    }
}

订阅：博文 (Atom)