努橙刷题编: 2016

2016年10月8日星期六

[LeetCode] #200 Number of Islands

public class Solution {
    public int numIslands(char[][] grid) {
        int result = 0;
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return result;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        if (grid[i][j] != '1') {
            return;
        }
        
        grid[i][j] = '2';
        if (i - 1 >= 0) {
            dfs(grid, i - 1, j);
        }
        if (j - 1 >= 0) {
            dfs(grid, i, j - 1);
        }
        if (i + 1 < grid.length) {
            dfs(grid, i + 1, j);
        }
        if (j + 1 < grid[0].length) {
            dfs(grid, i, j + 1);
        }
    }
}

2016年9月27日星期二

[LeetCode] 287. Find the Duplicate Number

1. Imagine the array is a linked list. Take the value of each element as a pointer to next element. if there is a duplicate element, there must be a loop in the linked list. Use fast, slow pointer to find the loop. O(n)
2. BitMap - TODO

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}

2016年9月26日星期一

[LeetCode] 289. Game of Life

(1) Add a new 2D array to hold the new state - O(n ^ 2) space
(2) Bit operation - in place

public class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int[][] newState = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = isLive(i, j, board);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = board[i][j] >> 1;
            }
        }
    }
    
    private int isLive(int i, int j, int[][] board) {
        int liveNeighbor = 0;
        for (int m = i - 1; m < board.length && m <= i + 1; m++) {
            for (int n = j - 1; n < board[0].length && n <= j + 1; n++) {
                if (m < 0 || n < 0 || (m == i && n == j)) {
                    continue;
                }
                if ((board[m][n] & 0x0001) == 1) {
                    liveNeighbor++;
                }
            }
        }
        if (liveNeighbor <= 1 || liveNeighbor >= 4) {
            return board[i][j];
        } 
        if (liveNeighbor == 3) {
            return (board[i][j] | 2);
        }
        return (board[i][j] | (board[i][j] << 1));
    }
}

2016年9月20日星期二

[LeetCode] #148 Sort List

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (head == null) {
        return head;
    }
    return mergeSort(head);
};

var mergeSort = function(head) {
    var pre_mid = findMiddle(head);
    var mid = pre_mid.next;
    
    if (mid != null && mid.next != null) {
        mid = mergeSort(mid);
    }
    pre_mid.next = null;
    if (pre_mid != head) {
        head = mergeSort(head);
    }
    return merge(head, mid);
};

var merge = function(head1, head2) {
    var dummy = new ListNode(-1);
    var cur = dummy;
    while (head1 != null && head2 != null) {
        if (head1.val <= head2.val) {
            cur.next = head1;
            head1 = head1.next;
        } else {
            cur.next = head2;
            head2 = head2.next;
        }
        cur = cur.next;
    }
    if (head1 != null) {
        cur.next = head1;
    }
    if (head2 != null) {
        cur.next = head2;
    }
    return dummy.next;
};

var findMiddle = function(head) {
    var fast = head.next;
    var slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
};

2016年9月19日星期一

[LeetCode] #19 Remove Nth Node From End of List

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    var dummy = new ListNode(-1);
    dummy.next = head;
    
    var fast = head;
    var slow = head;
    var pre = dummy;
    
    for (; n > 0; n--) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        pre = slow;
        slow = slow.next;
    }
    pre.next = slow.next;
    
    return dummy.next;
    
};

2016年9月15日星期四

[LintCode] #102 LinkedList Cycle II

N - distance from head to the node of cycle begins
M - the number of nodes in the cycle
K - the distance from node of cycle begins to the node fast and slow pointer meet

fast = N + xM + K
slow = N + yM + K
fast = 2 slow

=> N + K = (x - 2y) * M

We know when fast and slow meet, they are at Kth node in the cycle, it takes N steps to move from the Kth node in the cycle to the first node in the cycle. How to move this N steps? We know the distance from head to the node where cycle begins is also N. So, we just need to move fast or slow to head and keep step+1 until the two pointers meet.

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {  
        // write your code here
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

2016年9月12日星期一

[LintCode] #99 Reorder List

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: void
     */
    public void reorderList(ListNode head) {  
        // write your code here
        if (head == null || head.next == null) {
            return;
        }
        ListNode mid = findMiddle(head);
        ListNode head2 = reverse(mid.next);
        mid.next = null;
        merge(head, head2);
    }
    
    private ListNode findMiddle(ListNode head) {
        if (head == null && head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    
    private static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    private void merge(ListNode head1, ListNode head2) {
        ListNode tmp = new ListNode(0);
        boolean switchToHead2 = false;
        while (head1 != null && head2 != null) {
            if (!switchToHead2) {
                ListNode p = head1.next;
                tmp.next = head1;
                head1 = p;
            } else {
                ListNode p = head2.next;
                tmp.next = head2;
                head2 = p;
            }
            tmp = tmp.next;
            switchToHead2 = !switchToHead2;
        }
        if (head1 != null) {
            tmp.next = head1;
        }
        if (head2 != null) {
            tmp.next = head2;
        }
    }
}

Quick Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        int pivot = A[start + (end - start) / 2];
        int index = partition(A, pivot, start, end);
        if (start < index - 1) {
            quickSort(A, start, index - 1);
        }
        if (index < end) {
            quickSort(A, index, end);
        }
    }
    
    private int partition(int[] A, int pivot, int start, int end) {
        while (start <= end) {
            while (start <= end && A[start] < pivot) {
                start++;
            }
            while (start <= end && A[end] > pivot) {
                end--;
            }
            if (start <= end) {
                swap(A, start, end);
                start++;
                end--;
            }
        }
        return start;
    }
    
    private void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Merge Sort

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return;
        }
        mergeSort(A, 0, A.length - 1);
    }
    
    private void mergeSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(A, start, mid);
        mergeSort(A, mid + 1, end);
        merge(A, start, mid, end);
    }
    
    private void merge(int[] A, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (A[i] <= A[j]) {
                temp[k++] = A[i++];
            } else {
                temp[k++] = A[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = A[i++];
        }
        while (j <= end) {
            temp[k++] = A[j++];
        }
        k--;
        while (k >= 0) {
            A[end--] = temp[k--];
        }
    }
}

2016年9月11日星期日

[LintCode] #102 LinkedList Cycle

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {  
        // write your code here
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast != null && slow == fast) {
                return true;
            }
        }
        return false;
    }
}

[LintCode] #96 Partition List

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    public ListNode partition(ListNode head, int x) {
        // write your code here
        ListNode leftDummy = new ListNode(-1);
        ListNode rightDummy = new ListNode(-1);
        ListNode leftHead = leftDummy;
        ListNode rightHead = rightDummy;
        while (head != null) {
            if (head.val < x) {
                leftHead.next = head;
                leftHead = leftHead.next;
            } else {
                rightHead.next = head;
                rightHead = rightHead.next;
            }
            head = head.next;
        }
        leftHead.next = rightDummy.next;
        rightHead.next = null; //Attn!!!!!
        return leftDummy.next;
    }
}

[LintCode] #113 Remove Duplicates from Sorted List II

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list
     * @return: ListNode head of the linked list
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                int val = cur.val;
                while (cur != null && cur.val == val) {
                    pre.next = cur.next;
                    cur = cur.next;
                }
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

2016年9月7日星期三

努橙的Javascript学习笔记

* Function declaration: A function declaration creates a function that you can call later in your code.
* Function expression: If you put a function where the interpreter would expected to see an expression, then it is treated as expression(aka function expression). In function expression, the name is usually omitted.

* What's the difference of usage between function declaration and function expression?
** The interpreter always looks for variables and function declarations before going through each section of a script, line-by-line. This means that a function created with a function declaration can be called before it has been declared. In function expression, the function is not processed until the interpreter gets to that statement. This means you cannot call this function before interpreter has discovered it.

* IFFE = immediately invoked function expressions

2016年9月1日星期四

[LintCode] 11. Search Range in Binary Search Tree

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param k1 and k2: range k1 to k2.
     * @return: Return all keys that k1<=key<=k2 in ascending order.
     */
    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        helper(root, k1, k2, result);
        return result;
    }
    private void helper(TreeNode root, int min, int max, List<Integer> result) {
        if (root == null) {
            return;
        }
        if (root.val > min && root.val < max) {
            helper(root.left, min, max, result);
            result.add(root.val);
            helper(root.right, min, max, result);
        } else if (root.val <= min) {
            if (root.val == min) {
                result.add(root.val);
            }
            helper(root.right, min, max, result);
        } else if (root.val >= max) {
            helper(root.left, min, max, result);
            if (root.val == max) {
                result.add(root.val);
            }
        }
    }
}

[LeetCode] 98. Validate Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean helper(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val >= max || root.val <= min) {
            return false;
        }
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

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

2016年7月31日星期日

[LeetCode] #139 Word Break


public class Solution {
    // f[i] - if s.substring(0, i) can be segmented
    // f[i] = f[j] && wordDict.contains(s.substring(j, i))
    // f[0] = true
    // result - f[s.length()]
    public boolean wordBreak(String s, Set wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            f[i] = false;
            for (int j = 0; j < i; j++) {
                f[i] = f[i] || (f[j] && wordDict.contains(s.substring(j, i)));
            }
        }
        return f[s.length()];
    }
}

[LintCode][要再做] #108 Palindrome Partitioning II


public class Solution {
    /**
     * @param s a string
     * @return an integer
     */
    public int minCut(String s) {
        // state: f[i] = min cuts needed for a palindrome partitioning of s.substring(0, i)
        // function: f[i] = Min(f[j] + 1, isPalindrome(s.substring(j, i)), for all j < i
        // initialize: f[0] = 0
        // result: f[s.length()]
        // write your code here
        
        //isPalindrome[i][j] = is s.substring(i, j + 1) a palindrome
        boolean [][] isPalindrome = getIsPalindrome(s);
        
        int f[] = new int[s.length() + 1];
        f[0] = -1;
        for (int i = 1; i <= s.length(); i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[s.length()];
    }
    
    private boolean[][] getIsPalindrome(String s) {
        boolean[][] p = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            p[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            p[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        for (int length = 2; length < s.length(); length++) {
            for (int i = 0; i + length < s.length(); i++) {
                p[i][i + length] = p[i + 1][i + length - 1] && s.charAt(i) == s.charAt(i + length);
            }
        }
        return p;
    }
    
};

2016年7月27日星期三

[LeetCode] #55 Jump Game

DP, time complexity: O(n^2) Time Limit Exceeded (这题要用贪心做T_T)

public class Solution {
    // state: f[i] = is ith element reachable
    // function: f[i] = OR(f[j], i - j <= nums[j])
    // initialize: f[0] = true
    // result = f[nums.length]
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        boolean[] f = new boolean[nums.length];
        f[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (f[j] && j + nums[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[nums.length - 1];
    }
}

Greedy, time complexity: O(n)

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int reachable = nums[0];
        for (int i = 0; i <= reachable && i < nums.length; i++) {
            reachable = Math.max(reachable, i + nums[i]);
        }
        
        return reachable >= nums.length - 1;
    }
}

2016年7月26日星期二

[LeetCode] #64 Minimum Path Sum

public class Solution {
    //f[i][j] = min path sum from (0,0) to (i,j)
    //f[i][j] = grid[i][j] + min(f[i - 1][j], f[i][j - 1])
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m][n];
        f[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            f[0][i] = f[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
}

[LeetCode] #70 Climbing Stairs

public class Solution {
    // f[i] = how many distinct ways from i to the top
    // f[i] = f[i + 1] + f[i + 2]
    public int climbStairs(int n) {
        if (n < 2) {
            return n;
        }
        int[] f = new int[n + 1];
        f[n] = 0;
        f[n - 1] = 1;
        if (n >= 2) {
            f[n - 2] = 2;
        }
        for (int i = n - 3; i >= 0; i--) {
            f[i] = f[i + 1] + f[i + 2];
        }
        return f[0];
    }
}

[LeetCode] #63 Unique Paths II

public class Solution {
    // f[i][j] = how many paths from (0,0) to (i,j)
    // f[i][j] = f[i - 1][j] + f[i][j - 1]
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1 || (i > 0 && f[i - 1][0] == 0)) {
                f[i][0] = 0;
            } else {
                f[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1 || (i > 0 && f[0][i - 1] == 0)) {
                f[0][i] = 0;
            } else {
                f[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                } else {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        return f[m - 1][n - 1];
    }
}

[LintCode] #114 Unique Path

public class Solution {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here 
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            f[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            f[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

2016年7月25日星期一

[LeetCode] #377 Combination Sum IV

public class Solution {
    // state[i]: how many combinations when target = i
    // state[i] += 1, when num == i
    //             state[i - num], num=nums[0], ..., nums[nums.length - 1]
    // result = state[target];
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int state[] = new int[target + 1];
        state[0] = 0;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num == i) {
                    state[i]++;
                } else if (num < i) {
                    state[i] += state[i - num];
                } else {
                    break;
                }
            }
        }
        return state[target];
    }
}

2016年7月22日星期五

[笔记整理]九章算法第一章 Part2

1. Subsets

2. Unique Subsets

3. Permutations

4. Unique Permutations

5. Combinations

6. Combination Sum

7. Combination Sum II

8. Combination Sum III

9. Letter Combinations of a Phone Number

10. Palindrome Partitioning

11. Restore IP Address

12. N Queens

[LeetCode] #51 N-Queens

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        helper(result, new ArrayList<Integer>(), n);
        return result;
    }
    
    private void helper(List<List<String>> result, List<Integer> path, int n) {
        if (path.size() == n) {
            result.add(generateResult(path));
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(path, i)) {
                path.add(i);
                helper(result, path, n);
                path.remove(path.size() - 1);
            }
        }
    }
    
    private List<String> generateResult(List<Integer> path) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < path.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < path.size(); j++) {
                if (j == path.get(i)) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            result.add(new String(sb));
        }
        return result;
    }
    
    private boolean isValid(List<Integer> path, int pos) {
        for (int i = 0; i < path.size(); i++) {
            if (path.get(i) == pos || path.get(i) == pos - path.size() + i 
            || path.get(i) == pos + path.size() - i) { // Attn!
                return false;
            }
        }
        return true;
    }
}

2016年7月21日星期四

[LeetCode] #93 Restore IP Addresses

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(result, new ArrayList<String>(), s, 0);
        return result;
    }
    
    private void helper(List<String> result, List<String> path, String s, int start) {
        if (start == s.length()) {
            if (path.size() == 4) { //Attn!
                result.add(String.join(".", path));
            }
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            if (!isValid(s.substring(start, i + 1))) {
                break;
            }
            if (path.size() == 3 && i + 1 != s.length()) {
                continue;
            }
            path.add(s.substring(start, i + 1));
            helper(result, path, s, i + 1);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean isValid(String s) {
        if (s.length() != Integer.toString(Integer.parseInt(s)).length()) {
            return false; //Attn!
        }
        int i = Integer.parseInt(s);
        return (i >= 0 && i <= 255);
    }
}

[LeetCode] #131 Palindrome Partitioning

What's time complexity for this?

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(result, new ArrayList<String>(), s, 0);
        return result;
    }
    
    private void helper(List<List<String>> result, List<String> path, String s, int start) {
        if (start >= s.length()) {
            result.add(new ArrayList<String>(path));
        }
        
        for (int i = start; i < s.length(); i++) {
            if (!isValid(s.substring(start, i + 1))) {
                continue;
            }
            path.add(s.substring(start, i + 1));
            helper(result, path, s, i + 1);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean isValid(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

[LeetCode] #125 Valid Palindrome

这题超烦@_@

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null) {
            return false;
        }
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            while (start < end && !isValid(s.charAt(start))) {
                start++;
            }
            while (start < end && !isValid(s.charAt(end))) {
                end--;
            }
            if (start < end && !equalsIgnoreCase(s.charAt(start), s.charAt(end))) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    
    private boolean equalsIgnoreCase(char a, char b) {
        if (a == b) {
            return true;
        }
        if (isChar(a) && isChar(b) && Math.abs(a - b) == Math.abs('A' - 'a')) {
            return true;
        }
        return false;
    }
    
    private boolean isValid(char a) {
        return isChar(a) || (a >= '0' && a <= '9');
    }
    
    private boolean isChar(char a) {
        if (a >= 'a' && a <= 'z') {
            return true;
        }
        if (a >= 'A' && a <= 'Z') {
            return true;
        }
        return false;
    }
}

Character.toLowerCase() would make it easier :P

[LeetCode] #17 Letter Combinations of a Phone Number

Time complexity: O(C^n), C = 3 or 4
Because T(n) = CT(n - 1)

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        helper(result, new StringBuilder(), digits.toCharArray(), 0);
        return result;
    }
    
    private void helper(List<String> result, StringBuilder sb, char[] chars, int start) {
        if (start == chars.length) {
            result.add(new String(sb));
            return;
        }
        
        for (char c : getLetters(chars[start])) {
            sb.append(c);
            helper(result, sb, chars, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    private char[] getLetters(char a) {
        switch(a) {
            case '2': return "abc".toCharArray();
            case '3': return "def".toCharArray();
            case '4': return "ghi".toCharArray();
            case '5': return "jkl".toCharArray();
            case '6': return "mno".toCharArray();
            case '7': return "pqrs".toCharArray();
            case '8': return "tuv".toCharArray();
            case '9': return "wxyz".toCharArray();
            default: return "".toCharArray();
        }
    }
}

[LeetCode] #216 Combination Sum III

Time complexity: O(2^n)

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (k < 1 || n < 1 || n > 45) {
            return result;
        }
        helper(result, new ArrayList<Integer>(), 0, k, n, 1); // Attn: starts from 1, not 0 
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int sum, int k, int n, int start) {
        if (path.size() == k && sum == n) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if (path.size() == k) {
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (sum + i > n) {
                break;
            }
            path.add(i);
            helper(result, path, sum + i, k, n, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

[LeetCode] #40 Combination Sum II

Time complexity: O(2^n)

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        helper(result, new ArrayList<Integer>(), 0, candidates, target, 0);
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int sum, int[] candidates, int target, int start) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (i > 0 && i != start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (sum + candidates[i] > target) {
                break;
            } else {
                path.add(candidates[i]);
                helper(result, path, sum + candidates[i], candidates, target, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
}

2016年7月20日星期三

[LeetCode] #39 Combination Sum

Time complexity: O(n!)
because T(n) = nT(n - 1) + k

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        helper(result, new ArrayList<Integer>(), 0, candidates, target, 0);
        return result;
    }
    private void helper(List<List<Integer>> result, List<Integer> path, int sum, int[] candidates, int target, int start) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for (int i = 0; i < candidates.length; i++) {
            if (start > 1 && start - 1 > i) {
                continue;
            }
            if (sum + candidates[i] <= target) {
                path.add(candidates[i]);
                helper(result, path, sum + candidates[i], candidates, target, i + 1);
                path.remove(path.size() - 1);
            } else {
                break;
            }
        }
    }
}

[LeetCode] #77 Combinations

Time complexity: O(2^n)
because T(n) = kn + T(n-1) + T(n-2) +...+ T(2) + T(1), => O(2^n) , see https://discuss.leetcode.com/topic/2163/what-is-the-time-complexity-of-the-recursive-solution-for-this-problem-how-to-get-it/3

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (n < 1 || k < 1) {
            return result;
        }
        helper(result, new ArrayList<Integer>(), n, k, 1);
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int n, int k, int start) {
        if (path.size() == k) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for (int i = start; i <= n; i++) {
            path.add(i);
            helper(result, path, n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

[LeetCode] #47 Permutations II

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        helper(result, new ArrayList<Integer>(), nums, new boolean[nums.length]);
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] selected) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && selected[i - 1] == false) {
                continue;
            }
            if (!selected[i]) {
                selected[i] = true;
                path.add(nums[i]);
                helper(result, path, nums, selected);
                path.remove(path.size() - 1);
                selected[i] = false;
            }
        }
    }
}

2016年7月19日星期二

Time Complexity of Permutations and Subsets

Subsets
~~T(n) = T(n - 1) + T(n-2) +...+ T(2) + T(1) + C (Q: How to calculate this?)~~ (Wrong!)

T(n) = kn + T(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (1)
T(n - 1) = k(n - 1) + T(n - 2) + ... + T(2) + T(1) ---- (2)

(1) - (2)
<=> T(n) - T(n - 1) = kn - k(n - 1) + T(n - 1)
<=> T(n) = 2T(n - 1) + k
<=> O(2^n)

Permutations
T(n) = nT(n-1) + C
<=> O(n!)

[LeetCode] #46 Permutations

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        helper(result, new ArrayList<Integer>(), nums, new boolean[nums.length]);
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] selected) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && selected[i - 1] == false) {
                continue;
            }
            if (!selected[i]) {
                selected[i] = true;
                path.add(nums[i]);
                helper(result, path, nums, selected);
                path.remove(path.size() - 1);
                selected[i] = false;
            }
        }
    }
}

2016年7月18日星期一

[LeetCode] #90 Subset II

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null ||nums.length == 0) {
            return result;
        }
        Arrays.sort(nums);
        helper(result, new ArrayList<Integer>(), nums, 0);
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
        result.add(new ArrayList<Integer>(path));
        
        for (int i = start; i < nums.length; i++) {
            if (i > 0 && i != start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            helper(result, path, nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

[LintCode] #142 O(1) Check Power of 2

class Solution {
    /*
     * @param n: An integer
     * @return: True or false
     */
    public boolean checkPowerOf2(int n) {
        // write your code here
        return (Integer.bitCount(n << 1) == 1); // edge case: -2147483648
    }
};

2016年7月17日星期日

[LintCode] #181 Flip Bits

class Solution {
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    public static int bitSwapRequired(int a, int b) {
        // write your code here
        return Integer.bitCount(a ^ b);
    }
};

2016年7月15日星期五

[LeetCode] #78 Subsets

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        helper(result, new ArrayList<Integer>(), nums, 0);
        return result;
    }
    
    private void helper(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
        result.add(new ArrayList<>(path));
        
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            helper(result, path, nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

2016年7月14日星期四

[笔记整理] 九章算法第二章 Binary Search & Sorted Array Part2

1. Search for a Range

<=> How many times did a number appear? range[x1, x2] => x2-x1+1

2. Search Insert Position

* The insertion position may not be in current array

* Find the insertion position, 3 positions to check: x<start, start<x<end, x>end

3. Search In Rotated Sorted Array

* No duplicate

* 2 possible position for mid: [mid] >= [0], [mid] < [0]

* 4 possible position for target: [0]<T<[mid], [0]<[mid]<T, T<[mid]<[0], [mid]<T<[0]

4. Search In Rotated Sorted Array II

* Duplicate

* Worst case for binary search - O(n) e.g. If in every iteration, [mid]==[0]/[mid]==[length-1] =>O(n)

5. Search a 2D Matrix

* Any element in row1 < Any element in row 2

* Use binary search for 2 times, 1st time find the row of target, 2nd time find the column of target

6. Search a 2D Matrix II

[1 0 2 4]

[1 2 6 9]

[3 5 7 10]

[7 8 9 11]

* Quadrate search O(n)

* Search from left bottom to right top, exclude 1 row/column each iteration, O(m + n)

7. Find First Bad Version

8. Find Peak

* peak <=> A[p] > A[p - 1] && A[p] >A[p + 1]

9. Remove Duplicate from Sorted Array

10. Remove Duplicate from Sorted Array II

11. Merge Sorted Array

12. Median of Two Sorted Array

* Merge + Find O(m + n)

* Find kth largest O(logn)

when (m+n) is odd=>k=(m+n)/2+1

when (m+n) is even=>k1=(m+n)/2, k2=(m+n)/2+1

* How to find kth largest?

Throw away each k/2 elements in each iteration

13. Recover Rotated Sorted Array

* Sort, O(1) space O(nlogn) time

* 3 times reverse, O(1) space O(n) time

14. Rotate String

* abcdefg, offset=3 => efgabcd

15. Reverse Word List

* reverse each word, then reverse the entire string

[LintCode] #53 Reverse Words in a String

* reverse each word, and then reverse the entire string
sky_is_blue => yks_si_eulb => blue_is_sky

public class Solution {
    /**
     * @param s : A string
     * @return : A string
     */
    public String reverseWords(String s) {
       if (s == null || s.length() == 0) {
           return s;
       }
       
       String[] A = s.split(" ");
       if (A.length == 0 ) {
           return "";
       }
       
       StringBuilder sb = new StringBuilder();
       for (int i = A.length - 1; i >= 0; i--) {
           sb.append(A[i]);
           if (i != 0) {
               sb.append(" ");
           }
       }
       
       return new String(sb);
    }
}

* This one not working, because of it can't remove redundant spaces

public class Solution {
    public String reverseWords(String s) {
       char[] tmp = s.toCharArray();
       int start = 0;
       while(start < tmp.length) {
           while (start < tmp.length && tmp[start] == ' ') {
               start++;
           }
           if (start >= tmp.length) {
               break;
           }
           
           int end = start;
           while (end < tmp.length && tmp[end] != ' ') {
               end++;
           }
           if (start < tmp.length && end <= tmp.length) {
               reverse(start, end - 1, tmp);
           }
           
           start = end;
       }
       reverse(0, tmp.length - 1, tmp);
       return new String(tmp);
    }
    
    private void reverse(int start, int end, char[] A) {
        while (start < end) {
            char tmp = A[start];
            A[start] = A[end];
            A[end] = tmp;
            
            start++;
            end--;
        }
    }
}

2016年7月12日星期二

[LintCode] #8 Rotate String

1) when offset > str.length!!!!!

public class Solution {
    /**
     * @param str: an array of char
     * @param offset: an integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
        // write your code here
        if (str == null || str.length == 0 || offset < 0) {
            return;
        }
        offset = offset % str.length; //T_T!!!!!!!
        reverse(str, 0, str.length - offset - 1);
        reverse(str, str.length - offset, str.length - 1);
        reverse(str, 0, str.length - 1);
    }
    
    private void reverse(char[] str, int start, int end) {
        while (start < end) {
            char tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            
            start++;
            end--;
        }
    }
}

[LintCode] #159 Find Minimum in Rotated Sorted Array

1) [mid] > [start] move right, else move left
2) edge case: the array is sorted

public class Solution {
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] < nums[nums.length - 1]) { //T_T!!!!!
            return nums[0];
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[0] < nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] < nums[end]) {
            return nums[start];
        } else {
            return nums[end];
        }
    }
}

2016年7月8日星期五

[LintCode] #39 Recover Rotated Sorted Array

1) in place == re-sort O(nlogn)
2) O(n) space, O(n) time
3) 3 time reverse, O(1) space, O(n) time

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: The recovered sorted array
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        int i;
        for (i = 1; i < nums.size(); i++) {
            if (nums.get(i) < nums.get(i - 1)) {
                break;
            }
        }
        
        reverse(nums, 0, i - 1);
        reverse(nums, i, nums.size() - 1);
        reverse(nums, 0, nums.size() - 1);
    }
    
    private void reverse(ArrayList<Integer> nums, int start, int end) {
        for (; start < end; start++, end--) {
            int tmp = nums.get(start);
            nums.set(start, nums.get(end));
            nums.set(end, tmp);
        }
    }
}

2016年7月7日星期四

[LeetCode] #4 Median of Two Sorted Arrays

1) Merge + find median O(m + n)
2) Find kth largest element in two arrays O(logk), k = (m + n)/2, because every time throw away k/2^n

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0.0;
        }
        if ((nums1.length + nums2.length) % 2 != 0) {
            return findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2 + 1);
        } else {
            return (findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2) + findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2 + 1)) / 2.0;
        }
    }
    
    private int findKthElem(int[] nums1, int[] nums2, int start1, int start2, int k) {
        if (start1 >= nums1.length) {
            return nums2[start2 + k - 1];
        }
        if (start2 >= nums2.length) {
            return nums1[start1 + k - 1];
        }
        
        if (k == 1) {
            return nums1[start1] > nums2[start2] ? nums2[start2] : nums1[start1];
        } 
        
        int value1 = start1 + k/2 - 1 < nums1.length ? nums1[start1 + k/2 - 1] : Integer.MAX_VALUE; // use max value here to throw away first k/2 elems in nums2 
        int value2 = start2 + k/2 - 1 < nums2.length ? nums2[start2 + k/2 - 1] : Integer.MAX_VALUE;
        if (value1 > value2) {
            return findKthElem(nums1, nums2, start1, start2 + k/2, k - k/2); // the rest elems to find
        } else {
            return findKthElem(nums1, nums2, start1 + k/2, start2, k - k/2);
        }
    }
}

2016年7月6日星期三

[LintCode] #61 Search for a Range

public class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        // write your code here
        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;
        if (A == null || A.length == 0) {
            return result;
        }
        
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] >= target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (A[start] == target) {
            result[0] = start;
        } else if (A[end] == target){
            result[0] = end;
        } else {
            return result; //!!!!!
        }
        
        
        start = 0;
        end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] <= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] == target) {
            result[1] = end;
        } else if (A[start] == target) {
            result[1] = start;
        } else {
            result[0] = -1;
        }
        
        return result;
    }
}

[LintCode] #183 Wood Cut

public class Solution {
    /** 
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        if (L == null || L.length == 0) {
            return 0;
        }
        
        int max = 0;
        for (int i = 0; i < L.length; i++) {
            max = max < L[i] ? L[i] : max;
        }
        
        int start = 0;
        int end = max;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (numberOfPieces(L, mid) < k) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (numberOfPieces(L, end) >= k) {
            return end;
        } else {
            return start;
        }
    }
    
    private int numberOfPieces(int[] L, int length) {
        int pieces = 0;
        for (int i = 0; i < L.length; i++) {
            pieces += L[i] / length;
        }
        return pieces;
    }
}

订阅：博文 (Atom)