package leetcode.queue;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreeLevelOrderTraversal_102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

package leetcode.queue;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreeLevelOrderTraversalII_107 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            res.add(0, list);
        }
        return res;
    }
}

package leetcode.queue;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreeZigzagLevelOrderTraversal_103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int flag = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (flag % 2 == 1)
                    list.add(node.val);
                else
                    list.add(0, node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            res.add(list);
            flag++;
        }
        return res;
    }
}

package leetcode.queue;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreeRightSideView_199 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1)
                    res.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }
        return res;
    }
}

package leetcode.queue;
import leetcode.linkedList.ListNode;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class MergeKSortedLists_23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {
            if (node != null)
                queue.add(node);
        }
        while (!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
            if (p.next != null)
                queue.add(p.next);
        }
        return dummy.next;
    }
}

package leetcode.queue;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class TopKFrequentElements_347 {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        //统计数组中的元素出现的频率，key-num, value-次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i])+1);
            } else {
                map.put(nums[i],1);
            }
        }
        //扫描map，维护当前频率最高的k个元素,
        PriorityQueue<Pair> queue = new PriorityQueue<>(k);
        for (Integer i : map.keySet()) {
            if (queue.size() == k) {
                if (map.get(i) > queue.peek().freq){
                    queue.poll();
                    queue.add(new Pair(map.get(i),i));
                }
            } else {
                queue.add(new Pair(map.get(i), i));
            }
        }
        //遍历优先队列，将num加入到结果集中
        for (Pair pair : queue) {
            res.add(0, pair.num);
        }
        return res;
    }
    class Pair implements Comparable<Pair>{
        int freq;
        int num;
        public Pair(int freq, int num) {
            this.freq = freq;
            this.num = num;
        }
        @Override
        public int compareTo(Pair o) {
            return this.freq - o.freq;
        }
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class AddTwoNumber_2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode h1 = l1, h2 = l2;
        ListNode result = new ListNode(0);
        ListNode cur;
        int c = 0;
        cur = result;
        while (h1 != null || h2 != null || c == 1) {
            int tmp;
            if (h1 == null && h2 == null) {
                tmp = c;
            } else if (h1 == null) {
                tmp = c + h2.val;
            } else if (h2 == null) {
                tmp = c + h1.val;
            } else {
                tmp = c + h1.val + h2.val;
            }
            cur.next = new ListNode(tmp % 10);
            c = tmp / 10;
            cur = cur.next;
            if (h1 != null)
                h1 = h1.next;
            if (h2 != null)
                h2 = h2.next;
        }
        return result.next;
    }
}

package leetcode.linkedList;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class AddTwoNumbersII_445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode cur1 = l1, cur2 = l2;
        while (cur1 != null) {
            stack1.push(cur1.val);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            stack2.push(cur2.val);
            cur2 = cur2.next;
        }
        int c = 0;
        ListNode result = new ListNode(0);
        while (!stack1.isEmpty() || !stack2.isEmpty() || c == 1) {
            int tmp = 0;
            if (stack1.isEmpty() && stack2.isEmpty())
                tmp = c;
            else if (stack1.isEmpty())
                tmp = c + stack2.pop();
            else if (stack2.isEmpty())
                tmp = c + stack1.pop();
            else
                tmp = stack1.pop() + stack2.pop() + c;
            ListNode node = new ListNode(tmp % 10);
            c = tmp / 10;
            node.next = result.next;
            result.next = node;
        }
        return result.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class DeleteNodeInALinkedList_237 {
    public void deleteNode(ListNode node) {
        if (node == null)
            return;
        if (node.next == null) {
            node = null;
            return;
        }
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveLinkedListElement_203 {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head, pre = dummy;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = pre.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveNthNodeFromEndOfList_19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode l = dummy;
        ListNode r =dummy;
        for (int i = 0; i < n + 1; i++) {
            r = r.next;
        }
        while (r != null) {
            l = l. next;
            r = r.next;
        }
        l.next = l.next.next;
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class InsertionSortList_147 {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null && cur.next.val < cur.val) {
                while (pre.next.val < cur.next.val)
                    pre = pre.next;
                ListNode tmp = cur.next;
                cur.next = cur.next.next;
                tmp.next = pre.next;
                pre.next = tmp;
                pre = dummy;
            }  else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class MergeTwoSortedLists_21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode node1 = l1;
        ListNode node2 = l2;
        ListNode curr = dummy;
        while (node1 != null || node2 != null) {
            if (node1 == null) {
                curr.next = node2;
                break;
            } else if (node2 == null) {
                curr.next = node1;
                break;
            } else {
                if (node1.val <= node2.val) {
                    curr.next = node1;
                    node1 = node1.next;
                } else {
                    curr.next = node2;
                    node2 = node2.next;
                }
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class SortList_148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head, slow = head;
        ListNode prev = null, left, right;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        left = sortList(head);
        right = sortList(slow);
        return mergeTwoList(left, right);
    }
    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        if (l1 != null)
            prev.next = l1;
        if (l2 != null)
            prev.next = l2;
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class OddEvenLinkedList_328 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode odd = new ListNode(0);
        ListNode even = new ListNode(0);
        ListNode lastOdd = odd;
        ListNode lastEven = even;
        ListNode cur = head;
        int i = 1;
        while (cur != null) {
            if (i % 2 == 0) {
                lastEven.next = cur;
                lastEven = lastEven.next;
            } else {
                lastOdd.next = cur;
                lastOdd = lastOdd.next;
            }
            cur = cur.next;
            i++;
        }
        lastEven.next = null;
        lastOdd.next = even.next;
        return odd.next;
    }
}

package leetcode.linkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class PartitionList_86 {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null)
            return head;
        ListNode smaller = new ListNode(0);
        ListNode bigger = new ListNode(0);
        ListNode lastSmall = smaller;
        ListNode lastbig = bigger;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x){
                lastSmall.next = cur;
                lastSmall = lastSmall.next;
            }
            if (cur.val >= x) {
                lastbig.next = cur;
                lastbig = lastbig.next;
            }
            cur = cur.next;
        }
        lastbig.next = null;
        lastSmall.next = bigger.next;
        return smaller.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RecordList_143 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = reverseList(slow.next);
        fast = slow.next;
        ListNode node = head;
        while (node != slow) {
            slow.next = fast.next;
            fast.next = node.next;
            node.next = fast;
            node = fast.next;
            fast = slow.next;
        }
    }
    private ListNode reverseList(ListNode head) {
        if (head == null)
            return head;
        ListNode p = head.next;
        head.next = null;
        while (p != null) {
            ListNode tmp = p;
            p = p.next;
            tmp.next = head;
            head = tmp;
        }
        return head;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveDuplicatesFromSortedList {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == pre.val)
                pre.next = cur.next;
            else {
                pre.next = cur;
                pre = pre.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RemoveDuplicatesFromSortedListII_82 {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        boolean repeat = false;
        while(cur.next != null){
            if(cur.val == cur.next.val){
                repeat = true;
                cur = cur.next;
            } else {
                cur = cur.next;
                if(!repeat){
                    pre = pre.next;
                }
                pre.next = cur;
                repeat = false;
            }
        }
        if(repeat) pre.next = null;
        return dummy.next;
    }
}

package leetcode.linkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ReverseLinkedList_206 {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    /**
     * 创建一个链表
     * @param arr
     * @param n
     * @return
     */
    public static ListNode createLinkedList(int arr[], int n) {
        if (n == 0)
            return null;
        ListNode head = new ListNode(arr[0]);
        ListNode curNode = head;
        for (int i = 1; i < n; i++) {
            curNode.next = new ListNode(arr[i]);
            curNode = curNode.next;
        }
        return head;
    }
    public static void printLinkedList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println("NULL");
    }
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5};
        int n = arr.length;
        ListNode head = createLinkedList(arr, n);
        printLinkedList(head);
        head = new ReverseLinkedList_206().reverseList(head);
        printLinkedList(head);
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ReverseLinkedListII_92 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null)
            return null;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode pre= newHead;
        for (int i = 0; i < m-1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next = cur.next;
        for (int j = 0; j < n-m; j++) {
           cur.next = next.next;
           next.next = pre.next;
           pre.next = next;
           next = cur.next;
        }
        return newHead.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ReverseNodesInKGroup_25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        ListNode start = dummy;
        dummy.next = head;
        while (true) {
            ListNode node = start, cur, n = node;
            start = node.next;
            for (int i = 0; i < k && n != null; i++)
                n = n.next;
            if (n == null)
                break;
            for (int i = 0; i < k - 1; i++) {
                cur = node.next;
                node.next = cur.next;
                cur.next = n.next;
                n.next = cur;
            }
        }
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class RotateLIst_61 {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode left = dummy, right = dummy, br = dummy;
        int length = 0;
        while (right.next != null) {
            length++;
            right = right.next;
        }
        for (int j = length - k%length; j> 0; j--)
            left = left.next;
        right.next = dummy.next;
        dummy.next = left.next;
        left.next = null;
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class SwapNodewsInPairs_24 {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode node1, node2, next;
        while (pre.next != null && pre.next.next != null) {
            node1 = pre.next;
            node2 = node1.next;
            next = node2.next;
            node2.next = node1;
            node1.next = next;
            pre.next = node2;
            //靠后的一对节点
            pre = node1;
        }
        return dummy.next;
    }
}

package leetcode.linkedList;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class PalindromeLinkedList_234 {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = reverseList(slow.next);
        fast = slow.next;
        ListNode node = head;
        while (fast != null) {
            if (node.val != fast.val)
                return false;
            node = node.next;
            fast = fast.next;
        }
        return true;
    }
    private ListNode reverseList(ListNode head) {
        if (head == null)
            return head;
        ListNode p = head.next;
        head.next = null;
        while (p != null) {
            ListNode tmp = p;
            p = p.next;
            tmp.next = head;
            head = tmp;
        }
        return head;
    }
}

package leetcode.search;
import java.util.HashSet;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/6
 */
public class ContainsDuplicate_217 {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> record = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (record.contains(nums[i]))
                return true;
            record.add(nums[i]);
        }
        return false;
    }
}

package leetcode.search;
import java.util.HashMap;
import java.util.HashSet;
/**
 * Created by cdx0312
 * 2018/4/6
 */
public class ContainsDuplicateII {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> record = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (record.contains(nums[i]))
                return true;
            record.add(nums[i]);
            if (record.size() == k + 1)
                record.remove(nums[i-k]);
        }
        return false;
    }
}

package leetcode.search;
import java.util.HashSet;
import java.util.TreeSet;
/**
 * Created by cdx0312
 * 2018/4/6
 */
public class ContainsDuplicateIII {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.length < 2 || k == 0) {
            return false;
        }
        TreeSet<Long> set = new TreeSet<>();
        int i = 0;
        while (i < nums.length) {
            Long floor = set.floor((long) nums[i]);
            Long ceiling = set.ceiling((long) nums[i]);
            if ((floor != null && nums[i] - floor <= t ) ||
                    (ceiling != null && ceiling - nums[i] <= t)) {
                return true;
            }
            set.add((long) nums[i++]);
            if (i > k) {
                set.remove((long) nums[i - k - 1]);
            }
        }
        return false;
    }
}

package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class TwoSum_1 {
    //1、暴力O(N^2)
    public int[] twoSum3(int[] nums, int target) {
        int[] res = new int[2];
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
    //O(N) O(N)
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> record = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (record.containsKey(complement)) {
                res[1] = i;
                res[0] = record.get(complement);
                return res;
            }
            record.put(nums[i], i);
        }
        return res;
    }
}

package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/5
 */
public class FourSumII_454 {
    //查找表中记录C,D中任意两个和的可能次数O(N^2)
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        HashMap<Integer, Integer> record = new HashMap<>();
        for (int aC : C) {
            for (int aD : D) {
                int tmp = aC + aD;
                if (record.containsKey(tmp)) {
                    record.put(tmp, record.get(tmp) + 1);
                } else {
                    record.put(tmp, 1);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int tmp = 0 - A[i] - B[j];
                if (record.containsKey(tmp)) {
                    count += record.get(tmp);
                }
            }
        }
        return count;
    }
}

package leetcode.search;
import java.util.HashSet;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class IntersectoionOfTwoArray {
    public int[] intersection(int[] num1, int[] num2) {
        HashSet<Integer> record = new HashSet<>();
        HashSet<Integer> result = new HashSet<>();
        for (int aNum1 : num1) {
            record.add(aNum1);
        }
        for (int aNum1 : num2) {
            if (record.contains(aNum1))
                result.add(aNum1);
        }
        int[] resultA = new int[result.size()];
        int j = 0;
        for (int i : result) {
            resultA[j++] = i;
        }
        return resultA;
    }
}

package leetcode.search;
import java.util.HashSet;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class IsomorphicStrings_205 {
    public boolean isIsomorphic(String s, String t) {
        int[] num = new int[256];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < num.length; i++)
            num[i] = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int tmp = t.charAt(i);
            if (num[s.charAt(i)] == Integer.MAX_VALUE) {
                num[s.charAt(i)] = tmp;
                if (set.contains(tmp))
                    return false;
                else
                    set.add(tmp);
            } else {
                if (tmp != num[s.charAt(i)])
                    return false;
            }
        }
        return true;
    }
}

package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/5
 */
public class NumberOfBoomerangs_447 {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for (int i = 0; i < points.length; i++) {
            //和i点的距离，距离出现的频率
            HashMap<Integer, Integer> record = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (j != i) {
                    int dis = dis(points[i], points[j]);
                    if (record.containsKey(dis)){
                        record.put(dis, record.get(dis)+1);
                    } else {
                        record.put(dis, 1);
                    }
                }
            }
            for (Integer integer : record.keySet()) {
                if (record.get(integer) >= 2) {
                    res += record.get(integer) * (record.get(integer)-1);
                }
            }
        }
        return res;
    }
    private int dis(int[] point, int[] point1) {
        return (point[0] - point1[0]) * (point[0] - point1[0])
                + (point[1] - point1[1]) * (point[1] - point1[1]);
    }
}

package leetcode.search;
import java.util.*;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class SortCharactersByFrequency_451 {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else
                map.put(c, 1);
        }
        List<Character> [] bucket = new List[s.length() + 1];
        for (char key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null)
                bucket[freq] = new ArrayList<>();
            bucket[freq].add(key);
        }
        StringBuilder sb = new StringBuilder();
        for (int j = bucket.length - 1; j >= 0; j--) {
            if (bucket[j] != null) {
                for (char ch : bucket[j]) {
                    for (int i = 0; i < map.get(ch); i++)
                        sb.append(ch);
                }
            }
        }
        return sb.toString();
    }
}

package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class ValidAnagram_242 {
    public boolean isAnagram(String s, String t) {
        if (s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        if (s.length() != t.length())
            return false;
        HashMap<Character, Integer> sMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);
            if (sMap.containsKey(s1))
                sMap.put(s1, sMap.get(s1)+1);
            else
                sMap.put(s1,1);
            if (sMap.containsKey(t1))
                sMap.put(t1, sMap.get(t1)-1);
            else
                sMap.put(t1, -1);
        }
        for (Character ch : sMap.keySet()) {
            if (sMap.get(ch) != 0)
                return false;
        }
        return true;
    }
    public boolean isAnagram1(String s, String t) {
        int[] chars = new int[26];
        for (char c : s.toCharArray()) {
            chars[c-'a']++;
        }
        for (char c : t.toCharArray()) {
            chars[c-'a']--;
        }
        for (int i : chars) {
            if (i != 0)
                return false;
        }
        return true;
    }
}

package leetcode.search;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class WordPattern_290 {
    public boolean wordPattern(String pattern, String str) {
        if (pattern == null || str == null)
            return false;
        HashMap<Object, Integer> map = new HashMap<>();
        char[] chars = pattern.toCharArray();
        String[] strings = str.split(" ");
        if (chars.length != strings.length)
            return false;
        for (int i = 0; i < chars.length; i++) {
            if (!Objects.equals(map.put(chars[i], i), map.put(strings[i], i)))
                return false;
        }
        return true;
    }
    public boolean wordPattern1(String pattern, String str) {
        char[] chars = pattern.toCharArray();
        String[] strings = str.split(" ");
        String[] pat = new String[26];
        if (chars.length != strings.length)
            return false;
        Set<String> set = new HashSet<>();
        for (int i = 0; i < chars.length; i++) {
            if (pat[chars[i]-'a'] == null) {
                pat[chars[i]-'a'] = strings[i];
                if (set.contains(strings[i]))
                    return false;
                else
                    set.add(strings[i]);
            } else {
                if (!strings[i].equals(pat[chars[i]-'a']))
                    return false;
            }
        }
        return true;
    }
}

package leetcode.search;
import java.util.HashSet;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class HappyNum_202 {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        int sum = 0;
        while (n != 1) {
            set.add(n);
            while (n != 0) {
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            n = sum;
            sum = 0;
            if (set.contains(n))
                return false;
        }
        return true;
    }
}

package leetcode.stack;
import java.awt.event.ComponentAdapter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreeInOrderTraversal_94 {
    List<Integer> res = new ArrayList<>();
    //递归方法
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            res.add(root.val);
            inorderTraversal(root.right);
        }
        return res;
    }
    //非递归方法
    public List<Integer> inorderTraversal1(TreeNode root) {
        if (root == null)
            return res;
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while (!stack.isEmpty()) {
            Command command = stack.pop();
            if (command.s.equals("print"))
                res.add(command.node.val);
            else {
                if (command.node.right != null)
                    stack.push(new Command("go", command.node.right));
                stack.push(new Command("print", command.node));
                if (command.node.left != null)
                    stack.push(new Command("go", command.node.left));
            }
        }
        return res;
    }
    class Command{
        String s;  //print,go
        TreeNode node;
        public Command(String s, TreeNode node) {
            this.s = s;
            this.node = node;
        }
    }
}

package leetcode.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreePrecoderTraversal_144 {
    List<Integer> res = new ArrayList<>();
    //递归方法
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root != null) {
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return res;
    }
    //非递归方法
    public List<Integer> preorderTraversal1(TreeNode root) {
        if (root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
        return res;
    }
}

package leetcode.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class BinaryTreePostorderTraversal_145 {
    List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null)
            return res;
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go", root));
        while (!stack.isEmpty()) {
            Command command = stack.pop();
            if (command.s.equals("print"))
                res.add(command.node.val);
            else {
                stack.push(new Command("print", command.node));
                if (command.node.right != null)
                    stack.push(new Command("go", command.node.right));
                if (command.node.left != null)
                    stack.push(new Command("go", command.node.left));
            }
        }
        return res;
    }
    class Command {
        String s;//print, go
        TreeNode node;
        public Command(String s, TreeNode node) {
            this.s = s;
            this.node = node;
        }
    }
}

package leetcode.stack;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class EvaluateReversePolishNotation_150 {
    public int evalRPN(String[] tokens) {
        Stack<Integer> number = new Stack<>();
        Stack<Character> operators = new Stack<>();
        for (String s : tokens) {
            switch (s) {
                case "*":
                    number.push(number.pop() * number.pop());
                    break;
                case "+":
                    number.push(number.pop() + number.pop());
                    break;
                case "-":
                    number.push(-(number.pop() - number.pop()));
                    break;
                case "/":
                    int tmp1 = number.pop();
                    int tmp2 = number.pop();
                    number.push(tmp2 / tmp1);
                    break;
                default:
                    number.push(Integer.valueOf(s));
                    break;
            }
        }
        return number.pop();
    }
}

package leetcode.stack;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class SimplifyPath_71 {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] strings = path.split("/");
        for (String s : strings) {
            switch (s) {
                case "." :
                    break;
                case "..":
                    if (!stack.isEmpty())
                        stack.pop();
                    break;
                default:
                    if (!s.equals(""))
                        stack.push(s);
                    break;
            }
        }
        StringBuilder sb = new StringBuilder();
        if (stack.isEmpty())
            return "/";
        while (!stack.isEmpty()) {
            sb.insert(0,  "/" + stack.pop());
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        SimplifyPath_71 simplifyPath_71 = new SimplifyPath_71();
        String s = "/...";
        System.out.println(simplifyPath_71.simplifyPath(s));
    }
}

package leetcode.stack;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/8
 */
public class FlattenNestedListIterator_341 implements Iterator<Integer>{
    Stack<NestedInteger> stack = new Stack<>();
    Stack<Integer> integers = new Stack<>();
    public FlattenNestedListIterator_341(List<NestedInteger> nestedList) {
        for (NestedInteger i : nestedList) {
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            NestedInteger nestedInteger = stack.pop();
            if (nestedInteger.isInteger()) {
                integers.push(nestedInteger.getInteger());
            } else {
                for (NestedInteger j : nestedInteger.getList()){
                    stack.push(j);
                }
            }
        }
    }
    @Override
    public boolean hasNext() {
        return !integers.isEmpty();
    }
    @Override
    public Integer next() {
        return integers.pop();
    }
}

package leetcode.stack;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/7
 */
public class ValidParentheses_20 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch =='{' || ch == '[')
                stack.push(ch);
            else {
                if (stack.isEmpty())
                    return false;
                char cha = stack.pop();
                char match;
                switch (ch) {
                    case '(' :
                        match = ')';
                        break;
                    case '[':
                        match=']';
                        break;
                    default:
                        match='}';
                        break;
                }
                if (cha != match)
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

package sort;
import java.util.Arrays;
/**
 * Created by cdx0312
 * 2018/3/28
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {53, 23, 45, 86, 12, 33, 10, 90, 36, 70, 43, 88, 60, 29};
        System.out.println("排序之前： " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序之后： " + Arrays.toString(arr));
    }
    /**
     * 堆排序方法
     * @param arr 待排序的数组
     */
    private static void heapSort(int[] arr) {
        //1、创建大根堆，从第一个非叶子节点向堆首元素进行交换
        for (int i = arr.length / 2; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }
        //最后一个节点与root节点交换，然后调整成大根堆，
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i);
        }
    }
    /**
     * 构建堆的过程
     * @param arr 需要排列的数组
     * @param i 需要构建堆的根节点的序号
     * @param length 堆元素的个数，随着出堆不断的减少
     */
    private static void heapAdjust(int[] arr, int i, int length) {
        int child;
        for (int fathre = arr[i]; leftChild(i) < length; i = child) {
            child = leftChild(i);
            //选择节点i的较大的孩子节点
            if (child != length - 1 && arr[child] < arr[child+1]) {
                child++;
            }
            //如果父节点的值小于其较大的孩子节点，则交换二者的值
            if (fathre < arr[child]) {
                swap(arr, i, child);
            } else {
                break;
            }
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp =arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    private static int leftChild(int i) {
        return 2 * i+ 1;
    }
}

package sort;
import java.util.Arrays;
/**
 * Created by cdx0312
 * 2018/3/28
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {53, 23, 45, 86, 12, 33, 10, 90, 36, 70, 43, 88, 60, 29};
        System.out.println("排序之前： " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序之后： " + Arrays.toString(arr));
    }
    public static void quickSort(int[] arr) {
        quickSortHelp(arr, 0, arr.length - 1);
    }
    private static void quickSortHelp(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSortHelp(arr, low, pivot - 1);
            quickSortHelp(arr, pivot + 1, high);
        }
    }
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot)
                high--;
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot)
                low++;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }
    private static void swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class Combinations_77 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if (n <= 0 || k <= 0 || k > n)
            return res;
        combine(n, k, 1, new ArrayList<>());
        return res;
    }
    /**
     * 求解C(n,k),
     * @param n
     * @param k
     * @param start
     * @param list
     */
    private void combine(int n, int k, int start, List<Integer> list) {
        if (list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i <= n- (k - list.size()) + 1; i++) {
            list.add(i);
            combine(n, k, i + 1, list);
            list.remove(list.size() - 1);
        }
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class CombinationSum_39 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSum(candidates, target, new ArrayList<>(), 0);
        return res;
    }
    private void combinationSum(int[] candidates, int target, ArrayList<Integer> list, int pos) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            if (target < candidates[i]) {
                return;
            } else {
                list.add(candidates[i]);
                combinationSum(candidates, target - candidates[i], list, i);
                list.remove(list.size() - 1);
            }
        }
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class CombinationSumII_40 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSum(candidates, target, new ArrayList<>(), 0);
        return res;
    }
    private void combinationSum(int[] candidates, int target, ArrayList<Integer> list, int pos) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            if (i != pos && candidates[i] == candidates[i-1])
                continue;
            if (target < candidates[i]) {
                return;
            } else {
                list.add(candidates[i]);
                combinationSum(candidates, target - candidates[i], list, i+1);
                list.remove(list.size() - 1);
            }
        }
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class CombinationSumIII_216 {
    List<List<Integer>> res = new ArrayList<>();
    public static final int[] nums = {1,2,3,4,5,6,7,8,9};
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k <= 0 || n <= 0)
            return res;
        combinationSum3(k, n, 0, new ArrayList<Integer>());
        return res;
    }
    private void combinationSum3(int k, int sum, int index, ArrayList<Integer> list) {
         if (k == 0 && sum == 0){
             res.add(new ArrayList<>(list));
             return;
         }
         for (int i = index; i < nums.length; i++) {
             if (sum < nums[index])
                 return;
             list.add(nums[i]);
             combinationSum3(k-1, sum- nums[i], i + 1, list);
             list.remove(list.size() - 1);
         }
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class LetterCombinationsOfAPhoneNumber_17 {
    private static final String[] letterMap  =  {" ", "","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    private List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits == null || Objects.equals(digits, ""))
            return res;
        findCombation(digits, 0, "");
        return res;
    }
    private void findCombation(String digits, int index, String s) {
        if (index == digits.length()) {
            //保存s
            res.add(s);
            return;
        }
        char c = digits.charAt(index);
        String letters = letterMap[c - '0'];
        for (int i = 0; i < letters.length(); i++) {
            findCombation(digits, index + 1, s + letters.charAt(i));
        }
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class NQueens_51 {
    private List<List<String>> res = new LinkedList<>();
    boolean[] col, dia1, dia2;
    public List<List<String>> solveNQueens(int n) {
        res.clear();
        List<Integer> row = new LinkedList<>();
        col = new boolean[n];
        dia1 = new boolean[2*n - 1];
        dia2 = new boolean[2*n - 1];
        putQueen(n, 0, row);
        return res;
    }
    /**
     *
     * @param n n皇后问题
     * @param index 第index行
     * @param row 数组，row[0]=i表示第0行第i列放皇后
     */
    private void putQueen(int n, int index, List<Integer> row) {
        if (index == n) {
            res.add(generateBoard(n, row));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index-i+n-1]) {
                row.add(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index-i+n-1] = true;
                putQueen(n, index + 1, row);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index-i+n-1] = false;
                row.remove(row.size() -1);
            }
        }
    }
    private List<String> generateBoard(int n, List<Integer> row) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j ++) {
                if (j == row.get(i)) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            board.add(sb.toString());
        }
        return board;
    }
    public static void main(String[] args) {
        NQueens_51 queen = new NQueens_51();
        queen.solveNQueens(8);
        System.out.println(queen.res);
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class PacificAtlanticWaterFlow_417 {
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new LinkedList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return res;
        }
        int n = matrix.length, m = matrix[0].length;
        boolean[][] pacific = new boolean[n][m];
        boolean[][] atlantic = new boolean[n][m];
        for(int i=0; i<n; i++){
            dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
            dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);
        }
        for(int i=0; i<m; i++){
            dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
            dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (pacific[i][j] && atlantic[i][j])
                    res.add(new int[] {i, j});
        return res;
    }
    int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){
        int n = matrix.length, m = matrix[0].length;
        if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
            return;
        visited[x][y] = true;
        for(int[]d:dir){
            dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);
        }
    }
}

package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class NumbersOfIslands_200 {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != '1')
            return;
        grid[x][y] = '2';
        dfs(grid, x-1, y);
        dfs(grid, x+1,y);
        dfs(grid, x, y-1);
        dfs(grid, x, y + 1);
    }
}

package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class SurroundedRegions_130 {
    int m;
    int n;
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        m = board.length;
        n = board[0].length;
        //从最外圈寻找O,找到之后dfs标记与O相连的O
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O')
                dfs(board, i, 0);
            if (board[i][n-1] == 'O')
                dfs(board, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O')
                dfs(board, 0, j);
            if (board[m-1][j] == 'O')
                dfs(board, m-1, j);
        }
        //修改
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 'Z'){
                    board[i][j] = 'X';
                } else {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
            return;
        board[i][j] = 'Z';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class PalindromePartitioning_131 {
    private List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        List<String> list = new ArrayList<>();
        partition(list, s, 0, "");
        return res;
    }
    private void partition(List<String> list, String s, int pos, String sub) {
        if (pos == s.length()) {
            if (sub.equals(""))
                res.add(new ArrayList<>(list));
            return;
        }
        String tmp = sub + s.charAt(pos);
        if (isPalindrome(tmp)) {
            list.add(tmp);
            partition(list, s, pos + 1, "");
            list.remove(list.size() - 1);
        }
        partition(list, s, pos + 1, tmp);
    }
    private boolean isPalindrome(String s) {
        for (int i = 0; i < s.length()/2; i += 1) {
            if (s.charAt(i) != s.charAt(s.length()-1-i))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        String s = "aab";
        System.out.println(new PalindromePartitioning_131().partition(s));
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class RestoreIpAddress_93 {
    private List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        for (int i = 1; i < 4 && i < len - 2; i++) {
            for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
                for (int k = j + 1; k < j + 4 && k < len; k++) {
                    String s1 = s.substring(0,i);
                    String s2 = s.substring(i,j);
                    String s3 = s.substring(j,k);
                    String s4 = s.substring(k,len);
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
                        StringBuilder sb = new StringBuilder();
                        sb.append(s1).append(".").append(s2).append(".").append(s3)
                                .append(".").append(s4);
                        res.add(sb.toString());
                    }
                }
            }
        }
        return res;
    }
    private boolean isValid(String s) {
        return s.length() <= 3 && s.length() != 0 && (s.charAt(0) != '0' || s.length() <= 1) && Integer.parseInt(s) <= 255;
    }
    public List<String> restoreIpAddresses1(String s) {
        dfs(new StringBuilder(), 0, s, 0, 0);
        return res;
    }
    /**
     * DFS方法，回溯法应用
     * @param sb 拼接的字符串
     * @param pos 字符串的下标
     * @param s 输入的字符串
     * @param num 组成的数字
     * @param dot 点的个数
     */
    private void dfs(StringBuilder sb, int pos, String s, int num, int dot) {
        //终止条件，当检查晚最后一个元素时，如果点为3个，将字符串添加到res中
        if (pos == s.length()) {
            if (dot == 3)
                res.add(sb.toString());
            return;
        }
        //pos时，检查将其添加到当前数字中是否小于255，小于说明可以添加，则将其添加过去，遍历下一位
        if (num * 10 + s.charAt(pos)-'0' <= 255) {
            if (pos == 0 || num != 0) {
                sb.append(s.charAt(pos));
                dfs(sb, pos + 1, s,num * 10 + s.charAt(pos)-'0', dot);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        //不管pos能否添加，都不添加，而直接加点，迭代下一位
        if (dot < 3 && pos > 0){
            sb.append(".");
            sb.append(s.charAt(pos));
            dfs(sb,pos + 1, s, s.charAt(pos) - '0', dot + 1);
            sb.deleteCharAt(sb.length() - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class Permutations_46 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        dfs(list, nums,0, used);
        return res;
    }
    private void dfs(List<Integer> list, int[] nums, int pos, boolean[] used) {
        if (pos == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                list.add(nums[i]);
                used[i] = true;
                dfs(list, nums, pos + 1, used);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

package leetcode.backtracking;
import sun.misc.Perf;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class PermutationsII_47 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(list, nums, used);
        return res;
    }
    private void dfs(List<Integer> list, int[] nums, boolean[] used) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i])
                continue;
            if (i > 0 && nums[i-1] == nums[i] && !used[i-1])
                continue;
            used[i] = true;
            list.add(nums[i]);
            dfs(list, nums, used);
            used[i] = false;
            list.remove(list.size()-1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {2,2,1,1};
        PermutationsII_47 p = new PermutationsII_47();
        p.permuteUnique(nums);
        System.out.println(p.res);
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class SubSets_78 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        subsets(nums, 0, new ArrayList<Integer>());
        return res;
    }
    private void subsets(int[] nums, int index, ArrayList<Integer> list) {
        res.add(new ArrayList<>(list));
        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            subsets(nums, i + 1, list);
            list.remove(list.size() - 1);
        }
    }
    public static void main(String[] args) {
        SubSets_78 s = new SubSets_78();
        int[] num = {1,2,3};
        s.subsets(num);
        System.out.println(s.res);
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class SubSetsII_90 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        Arrays.sort(nums);
        subsets(nums, 0, new ArrayList<Integer>());
        return res;
    }
    private void subsets(int[] nums, int index, ArrayList<Integer> list) {
        if (nums.length == index) {
            res.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[index]);
        subsets(nums, index + 1,list);
        list.remove(list.size() - 1);
        while (index + 1 < nums.length && nums[index + 1] == nums[index])
            index++;
        subsets(nums, index + 1, list);
    }
}

package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class Sudoku_Solver_37 {
    public void solveSudoku(char[][] board) {
        doSolve(board, 0, 0);
    }
    private boolean doSolve(char[][] board, int row, int col) {
        for (int i = row; i < 9; i++, col = 0) {
            for (int j = col; j < 9; j++) {
                if (board[i][j] != '.')
                    continue;
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (doSolve(board, i, j + 1))
                            return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, char num) {
        int blkrow = row / 3 * 3, blkcol = col / 3 * 3;
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num || board[row][i] == num || board[blkrow + i / 3][blkcol + i % 3] == num)
                return false;
        }
        return true;
    }
}

package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class WorldSearch_79 {
    public boolean exist(char[][] board, String word) {
        boolean[][] flag = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++)
                if (seachWord(board, word, 0, i, j, flag))
                    return true;
        }
        return false;
    }
    private boolean seachWord(char[][] board, String word, int index, int x, int y, boolean[][] flag) {
        if (index == word.length() - 1)
            return board[x][y] == word.charAt(index);
        if (board[x][y] == word.charAt(index)) {
            flag[x][y] = true;
            if (x - 1 >= 0 && !flag[x-1][y] && seachWord(board, word, index+1,x-1, y, flag))
                return true;
            if (x + 1 < board.length && !flag[x+1][y] && seachWord(board, word, index + 1, x + 1, y, flag))
                return true;
            if (y-1 >= 0 && !flag[x][y-1] && seachWord(board, word, index + 1, x, y-1, flag))
                return true;
            if (y + 1 <board[0].length && !flag[x][y+1] && seachWord(board, word, index + 1, x, y+1, flag))
                return true;
            flag[x][y] = false;
        }
        return false;
    }
}

package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class BinaryWatch_401 {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        int[] nums1 = new int[]{8,4,2,1};
        int[] nums2 = new int[]{32,16,8,4,2,1};
        for (int i = 0; i <= num; i++) {
            List<Integer> list1 = generateDigit(nums1, i);
            List<Integer> list2 = generateDigit(nums2, num - i);
            for (int num1 : list1) {
                if (num1 >= 12)
                    continue;
                for (int num2 : list2) {
                    if (num2 >= 60)
                        continue;
                    res.add(num1 + ":"+ (num2 < 10 ? "0" + num2 : num2));
                }
            }
        }
        return  res;
    }
    private List<Integer> generateDigit(int[] nums, int count) {
        List<Integer> res = new ArrayList<>();
        generateDigit(nums, count, 0, 0, res);
        return res;
    }
    private void generateDigit(int[] nums, int count, int pos, int sum, List<Integer> res) {
        if (count == 0) {
            res.add(sum);
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            generateDigit(nums, count - 1, i + 1, sum + nums[i], res);
        }
    }
}

public class Fib {
    //O(2^N)
    public int fib(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        return fib(n-1) + fib(n-2);
    }
    //O(N)
    public int fib2(int n) {
        int[] res = new int[n + 1];
         res[0] = 0;
        res[1] = 1;
        for (int i = 2; i < n+1; i++){
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }
    public static void main(String[] args) {
        Fib fib = new Fib();
        long startTime = System.currentTimeMillis();
        int n = 42;
        System.out.println("fib(" + n + ") = " + fib.fib(n));
        System.out.println("time : " + (System.currentTimeMillis() - startTime));
        long startTime1 = System.currentTimeMillis();
        System.out.println("fib(" + n + ") = " + fib.fib2(n));
        System.out.println("time : " + (System.currentTimeMillis() - startTime1));
    }
}

package leetcode.dp;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class ClimbingStairs_70 {
    //dp
    public int climbStairs(int n) {
        int[] res = new int[n + 1];
        res[1] = 1;
        res[2] = 2;
        for (int i = 3; i <= n; i++) {
            res[i] = res[i-1] + res[i - 2];
        }
        return res[n];
    }
    //递归
    public int climbStairs1(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbStairs1(n-1) + climbStairs1(n-2);
    }
}

package leetcode.dp;
/**
 * Created by cdx0312
 * 2018/4/12
 */
public class CoinChange_322 {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        int n = amount + 1;
        for (int coin : coins) {
            int curr = 0;
            if (amount >= coin) {
                int next = coinChange(coins, amount - coin);
                if (next >= 0)
                    curr = 1 + next;
            }
            if (curr > 0)
                n = Math.min(n, curr);
        }
        return n == amount + 1 ? -1 : n;
    }
    public int coinChange1(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length; i++)
            dp[i] = amount + 1;
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i)
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(new CoinChange_322().coinChange1(new int[]{2}, 3));
    }
}

public int maxProfit(int[] prices) {
    if (prices.length <= 1)
        return 0;
    int[] s0 = new int[prices.length];
    int[] s1 = new int[prices.length];
    int[] s2 = new int[prices.length];
    s1[0] = -prices[0];
    s2[0] = Integer.MIN_VALUE;
    for (int i = 1; i < prices.length; i++) {
        s0[i] = Math.max(s0[i-1], s2[i-1]);
        s1[i] = Math.max(s1[i-1], s0[i-1] - prices[i]);
        s2[i] = s1[i-1] + prices[i];
    }
    return Math.max(s0[prices.length - 1], s2[prices.length - 1]);
}

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

package leetcode.dp;
import java.util.Arrays;
/**
 * Created by cdx0312
 * 2018/4/12
 */
public class CombinationSumIV_377 {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0)
            return 1;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i])
                res += combinationSum4(nums, target - nums[i]);
        }
        return res;
    }
    public int combinationSum41(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <nums.length; j++) {
                if (i - nums[j] >= 0)
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}

package leetcode.dp;
/**
 * Created by cdx0312
 * 2018/4/12
 * 最长公共子序列
 */
public class LongestCommonSequence {
    //递归
    public int longest(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0)
            return 0;
        return longest(s1, s2, s1.length()-1, s2.length()-1);
    }
    private int longest(String s1, String s2, int m, int n) {
        if (m < 0 || n < 0)
            return 0;
        if (s1.charAt(m) == s2.charAt(n))
            return 1 + longest(s1,s2,m-1,n-1);
        else
            return Math.max(longest(s1,s2,m-1, n), longest(s1,s2,m,n-1));
    }
    public static void main(String[] args) {
        LongestCommonSequence LCS = new LongestCommonSequence();
        String s1 = "abcd";
        String s2 = "abcdefg";
        System.out.println(LCS.longest(s1,s2));
        System.out.println(LCS.longest2(s1,s2));
    }
    //DP
    public int longest2(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0)
            return 0;
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 0; i <= len1; i++)
            dp[i][0] = 0;
        for (int i = 0; i <= len2; i++)
            dp[0][i] = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}

package leetcode.dp;
import java.util.Arrays;
/**
 * Created by cdx0312
 * 2018/4/12
 * 最长上升子序列问题
 */
public class LongestIncreasingSubsequence_300 {
    //O(N^2)
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0)
            return 0;
        int[] dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            max = Math.max(dp[i], max);
        }
        return max;
    }
    public static void main(String[] args) {
        int[] arr = {1,3,6,7,9,4,10,5,6};
        System.out.println(new LongestIncreasingSubsequence_300().lengthOfLIS(arr));
    }
}

package leetcode.dp;
/**
 * Created by cdx0312
 * 2018/4/12
 * 0-1背包问题
 */
public class Knapsack01 {
    int[][] dp;
    //递归
    public int knapscak01(int[] w, int[] v, int C) {
        dp = new int[w.length][C + 1];
        return bestValue(w,v, w.length-1,C);
    }
    private int bestValue(int[] weight, int[] value, int index, int capacity) {
        if (index < 0 || capacity <= 0)
            return 0;
        int res = bestValue(weight, value, index - 1, capacity);
        if (capacity > weight[index])
            res = Math.max(value[index] + bestValue(weight, value, index - 1, capacity - weight[index]), res);
        return res;
    }
    //dp O(N*C) O(N*C)
    public int knapscak01_2(int[] w, int[] v, int C) {
        int n = w.length;
        if (n == 0)
            return 0;
        int[][] dp = new int[n][C + 1];
        for (int j = 0; j <= C; j++)
            dp[0][j] = (j >= w[0] ? v[0] : 0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= C; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= w[i])
                    dp[i][j] = Math.max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
            }
        }
        return dp[n-1][C];
    }
    //dp O(C) O(N*C)
    public int knapscak01_3(int[] w, int[] v, int C) {
        int n = w.length;
        if (n == 0)
            return 0;
        int[][] dp = new int[2][C + 1];
        for (int j = 0; j <= C; j++)
            dp[0][j] = (j >= w[0] ? v[0] : 0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= C; j++) {
                dp[i%2][j] = dp[(i-1)%2][j];
                if (j >= w[i])
                    dp[i%2][j] = Math.max(dp[i%2][j], v[i] + dp[(i-1)%2][j-w[i]]);
            }
        }
        return dp[(n-1)%2][C];
    }
    //dp O(C) O(N*C)
    public int knapscak01_4(int[] w, int[] v, int C) {
        int n = w.length;
        if (n == 0)
            return 0;
        int[] dp = new int[C + 1];
        for (int j = 0; j <= C; j++)
            dp[j] = (j >= w[j] ? v[0] : 0);
        for (int i = 1; i < n; i++) {
            for (int j = C; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], v[i] + dp[j-w[i]]);
            }
        }
        return dp[C];
    }
}

package leetcode.dp;
import java.util.Arrays;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class PerfectSquares_279 {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++)
            dp[i] = Integer.MAX_VALUE;
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= (int)Math.sqrt(i); j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println(new PerfectSquares_279().numSquares(13));
    }
}

package leetcode.dp;
import java.util.Arrays;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class UniquePaths_62 {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m; i++)
            dp[i][0] = 0;
        for (int j = 0; j < n; j++)
            dp[0][j] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        for (int i = 0; i <= m; i++)
            System.out.println(Arrays.toString(dp[i]));
        return dp[m][n];
    }
    public static void main(String[] args) {
        System.out.println(new UniquePaths_62().uniquePaths(3,7));
    }
}

package leetcode.dp;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class HouseRobber_198 {
    //dp[i]表示考虑抢劫nums[i...n]所获得的最大收益
    int[] dp;
    public int rob(int[] nums) {
        dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        return tryRob(nums, 0);
    }
    //考虑抢劫nums[index..nums.length]这个范围内的所有房子
    private int tryRob(int[] nums, int index) {
        if (index >= nums.length)
            return 0;
        if (dp[index] != -1)
            return dp[index];
        int res = 0;
        for (int i = index; i < nums.length; i++) {
            res = Math.max(res,nums[i] + tryRob(nums, i + 2));
        }
        dp[index] = res;
        return res;
    }
    //dp方法
    public int rob1(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;
        int[] dps = new int[n];
        for (int i = 0; i < n; i++)
            dps[i] = -1;
        dps[n-1] = nums[n-1];
        for (int i = n -2; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dps[i] = Math.max(dps[i], nums[j] + (j+2 < n ? dps [j+2] : 0));
            }
        }
        return dps[0];
    }
}

package leetcode.dp;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class HouseRobberII_213 {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
    private int rob(int[] nums, int lo, int hi) {
        int include = 0, exclude = 0;
        for (int j = lo; j <= hi; j++) {
            int i = include, e = exclude;
            include = e + nums[i];
            exclude = Math.max(e, i);
        }
        return Math.max(include, exclude);
    }
}

public class AllSort {
    private static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Permutation(str.toCharArray(), str.length(), 0);
        System.out.println(list.toString());
    }
    private static void Permutation(char[] chars, int strLen, int curIndex) {
        //如果到最后一个数，将排好的加入到list中
        if (curIndex == strLen - 1) {
            list.add(new String(chars));
        } else {
            for (int i = curIndex; i <= strLen - 1; i++) {
                //去重，避免相同数字的交换造成最终结果存在重复
                if (i == curIndex || chars[i] != chars[curIndex]) {
                    //依次交换开头字母与后面的进行递归
                    Swap(chars, i, curIndex);
                    Permutation(chars, strLen, curIndex + 1);
                    Swap(chars, i, curIndex);
                }
            }
        }
    }
    private static void Swap(char[] chars, int i, int curIndex) {
        char tmp = chars[i];
        chars[i] = chars[curIndex];
        chars[curIndex] = tmp;
    }
}

public class AllSort {
    private static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        PermutationWithDictionary(str.toCharArray(), str.length());
        System.out.println(list.toString());
    }
    private static void Swap(char[] chars, int i, int curIndex) {
        char tmp = chars[i];
        chars[i] = chars[curIndex];
        chars[curIndex] = tmp;
    }
    private static void PermutationWithDictionary(char[] chars, int strLen) {
        //对字符数组进行排序
        Arrays.sort(chars);
        while (true) {
            int j;
            int index = 0;
            //找到从右向左第一个不是非递增元素
            for (j = strLen - 2; j >= 0; j--) {
                if (chars[j] < chars[j+1]){
                    index = j;
                    break;
                } else if (j == 0){
                    return;
                }
            }
            //与从右向左第一个大于这个元素的元素交换
            for (j = strLen - 1; j >= 0; j--) {
                if (chars[j] > chars[index]) {
                    break;
                }
            }
            //交换这两个值
            Swap(chars, index, j);
            //对非递增元素位置后面的数组进行逆序排序
            Reverse(chars, index+1);
            list.add(new String(chars));
        }
    }
    private static void Reverse(char[] chars, int index) {
        int k = index, j = chars.length-1;
        while (k < j) {
            Swap(chars,k,j);
            k++;
            j--;
        }
    }
}

public class AllCombine {
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        combinetion(str.toCharArray(), str.length());
        System.out.println(list.toString());
    }
    private static void combinetion(char[] chars, int length) {
       if (chars == null || length == 0)
           return;
        List<Character> array = new ArrayList<>();
        //n中情况分别考虑
        for (int i = 1; i <= length; i++) {
            combine(chars, 0, i, array);
        }
    }
    /**
     * 从字符数组中index以后挑选number个数加入list
     * @param chars 输入的字符数组
     * @param index 开始字符下标
     * @param number
     * @param array
     */
    private static void combine(char[] chars, int index, int number, List<Character> array) {
        if (number == 0) {
            //递归终止条件，判断是为了去重
            if (!list.contains(array.toString())) {
                list.add(array.toString());
            }
            return;
        }
        if (index == chars.length) {
            return;
        }
        //取当前元素，并考察递归选取n-1个元素的情况
        array.add(chars[index]);
        combine(chars, index+1, number - 1, array);
        array.remove((Character) chars[index]);
        //不取当前元素，考察后面选取n个元素
        combine(chars, index+1, number, array);
    }
}

public class AllCombine1 {
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        combinetion(str.toCharArray());
        System.out.println(list.toString());
    }
    private static void combinetion(char[] chars) {
        if (chars == null || chars.length == 0)
            return;
        int len = chars.length;
        //n=2^len
        int n = 1<<len;
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < len; j++) {
                int temp = i;
                if ((temp & (1<<j)) != 0)
                    sb.append(chars[j]);
            }
            list.add(sb.toString());
        }
    }
}

public class PathSum_112 {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
            return sum == root.val;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

package leetcode.binaryTree;
import leetcode.linkedList.ListNode;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class PathSumII_113 {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        getPathSum(root, sum, res,list);
        return res;
    }
    /**
     *
     * @param root 跟节点
     * @param sum 和
     * @param res 返回的二维数组
     * @param list 单个路径
     */
    private void getPathSum(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
        if (root == null)
            return;
        list.add(root.val);
        //递归到叶子节点进行判断，决定是否将当前list添加到列表中，不是叶子节点则继续递归左子树和右子树。
        if (root.left == null && root.right == null && sum == root.val) {
            res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        } else {
            getPathSum(root.left, sum - root.val, res, list);
            getPathSum(root.right, sum - root.val, res, list);
        }
        //添加完记得删除，回溯上一个状态。
        list.remove(list.size() - 1);
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class PathSumIII_437 {
    public int pathSum(TreeNode root, int sum) {
        int res = 0;
        if (root == null)
            return res;
        res = findPath(root, sum);
        res += pathSum(root.left, sum);
        res += pathSum(root.right ,sum);
        return res;
    }
    private int findPath(TreeNode root, int sum) {
        if (root == null)
            return 0;
        int res = 0;
        if (root.val == sum)
            res++;
        return res + findPath(root.left, sum - root.val) + findPath(root.right, sum - root.val);
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class MaximunDepthOfBinaryTree_104 {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class MinimumDepthOfBinaryTree_111 {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null)
            return 1 + minDepth(root.right);
        if (root.right == null)
            return 1 + minDepth(root.left);
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
        return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null)
        return root;
    return left != null ? left : right;
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class LowestCommonAncestorOfABinarySearchTree_235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        else if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class KthSmallestElementInaBST_230 {
    //堆栈方法
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null) {
            stack .push(root);
            root = root.left;
        }
        while (k != 0) {
            TreeNode node = stack.pop();
            k--;
            if (k == 0)
                return node.val;
            TreeNode right = node.right;
            while (right != null) {
                stack.push(right);
                right = right.left;
            }
        }
        return -1;
    }
    //递归方法
    public int kthSmallest1(TreeNode root, int k) {
        int count = countNodes(root.left);
        if (k <= count)
            return kthSmallest(root.left, k);
        else if (k > count + 1)
            return kthSmallest(root.right, k - 1 -count);
        return root.val;
    }
    private int countNodes(TreeNode left) {
        if (left == null)
            return 0;
        return 1 + countNodes(left.left) + countNodes(left.right);
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class ValidateBST_98 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root, long minValue, long maxValue) {
        if (root == null)
            return true;
        if (root.val >= maxValue || root.val <= minValue)
            return false;
        return isValidBST(root.left,minValue, root.val) && isValidBST(root.right, root.val, maxValue);
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class DeleteNodeInABST_450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (key < root.val)
            root.left = deleteNode(root.left, key);
        else if (key > root.val)
            root.right = deleteNode(root.right, key);
        else {
            if (root.left == null) {
                return root.right;
            }else if (root.right == null) {
                return root.left;
            }
            TreeNode min = find(root.right);
            root.val = min.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    private TreeNode find(TreeNode root) {
        while (root.left != null)
            root = root.left;
        return root;
    }
}

package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class BalancedBinaryTree_110 {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.abs(right - left) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}