首页 > 代码库 > 打卡2

打卡2

1.   155. Min Stack

https://leetcode.com/problems/min-stack/#/description

借助一个栈存储最小值, 当入栈值小于等于当前最小值时, 才加入中间站..当最小值被被pop出时, 中间栈才pop最小值

中间站初始的时候要加入一个第一个值

public class MinStack {

      private Stack<Integer> stack = new Stack<Integer>();

      private Stack<Integer> minStack = new Stack<Integer>();

     

    public MinStack() {

        // do initialize if necessary

         stack = new Stack<Integer>();

         minStack = new Stack<Integer>();*/

    }

 

    public void push(int number) {

        // write your code here

        stack.push(number);

        if (minStack.empty()) {

            minStack.push(number);

        } else if (number <= minStack.peek()) {

            minStack.push(number);

        }

       

    }

 

    public int pop() {

        // write your code here

        if (stack.peek().equals(minStack.peek())) {

            minStack.pop();

        }

        return stack.pop();

    }

 

    public int min() {

        // write your code here

        return minStack.peek();

    }

}

 

 

 

一个站, 一个动态的min

public class MinStack {

    Stack<Integer> stack;

    int min=Integer.MAX_VALUE;;

    /** initialize your data structure here. */

    public MinStack() {

        stack = new Stack<>();

    }

   

    public void push(int x) {

        if(x<=min)

        {

            stack.push(min);

            min = x;

        }

        stack.push(x);

    }

   

    public void pop() {

        if(stack.pop() == min)

            min = stack.pop();

    }

   

    public int top() {

        return stack.peek();

    }

   

    public int getMin() {

        return min;

    }

   

}

 

2.   514. Freedom Trail

 

 

 

3.   515. Find Largest Value in Each Tree Row

https://leetcode.com/submissions/detail/104030319/

public List<Integer> largestValues(TreeNode root) {

       

        List<Integer> ans = new ArrayList<>();

        if (root == null) return ans;

        Queue<TreeNode> q = new LinkedList<>();

       

        q.offer(root);

        while (!q.isEmpty()) {

            int size = q.size();

            int max = Integer.MIN_VALUE;

            while (size > 0) {

                 TreeNode cur = q.poll();

                 size--;

                 max = Math.max(cur.val, max);

                 if (cur.left != null) {

                    q.offer(cur.left);

                }

                if (cur.right != null) {

                    q.offer(cur.right);

                }

            }

            ans.add(max);

        }

        return ans;

}

4.   513. Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/#/description

http://www.cnblogs.com/grandyang/p/6405128.html

 

 

 

bfs

public int findBottomLeftValue(TreeNode root) {

        if (root == null) return -1;

        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);

        int ans = 1;

        while (!q.isEmpty()) {

            int size = q.size();

            for (int i = 0; i < size; i++) {

                TreeNode cur = q.poll();

                   

                    if (cur.left != null) {

                        q.offer(cur.left);

                    }

                    if (cur.right != null) {

                        q.offer(cur.right);

                    }

                if (i == 0) {

                    ans = cur.val;

                }

            }

        }

        return ans;

    }

 

Dfs

 

public class Solution {

int maxDeep = 0; 

     int ans = 0;

    public int findBottomLeftValue(TreeNode root) {

        if (root == null) return -1;

     

       helper(root, 0);

       return ans;

    }

    private void helper(TreeNode root, int deep) {

        if (root == null) {

            return;

        }

        if (deep >= maxDeep) {

            maxDeep++;

            ans =  root.val;

        }

        helper(root.left, deep + 1);

        helper(root.right, deep + 1);

}

}

5.   215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/#/solutions

 

https://leetcode.com/problems/kth-largest-element-in-an-array/#/solutions

数组能排序的先排序

public int findKthLargest(int[] nums, int k) {

        int n = nums.length;

        Arrays.sort(nums);

        return nums[n-k];

    }

快速排序

public int findKthLargest(int[] nums, int k) {

        if (nums == null || nums.length == 0) {

            return Integer.MAX_VALUE;

        }

       int ans = helper(nums, nums.length - k + 1, 0, nums.length - 1);

       return ans;

    }

    private int helper(int[] nums, int k, int beg, int end) {

        int pivot = nums[end];

        int i = beg, j = end;

        while (i < j) {

            if (nums[i] > pivot) {

                j--;

                swap( i, j,nums);

              

            } else {

                i++;

               

            }

           

        }

        swap(j, end, nums);

        if (i + 1 - beg == k) {

            return pivot;

        } else if (i + 1 - beg < k) {

            return helper(nums, k - i - 1 + beg, i + 1, end);

        } else {

            return helper(nums, k, beg, i - 1);

        }

    }

    private void swap (int a, int b, int[] nums) {

        int temp = nums[b];

        nums[b] = nums[a];

        nums[a] = temp;

    }

6.   116. Populating Next Right Pointers in Each Node ---- 空间一定

http://www.cnblogs.com/grandyang/p/4288151.html

http://www.cnblogs.com/EdwardLiu/p/3978458.html

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/#/description

 

层次遍历

public class Solution {

    public void connect(TreeLinkNode root) {

        TreeLinkNode pre = null;

        if (root == null) return;

        Queue<TreeLinkNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i=0; i<size; i++) {

                TreeLinkNode cur = queue.poll();

                if (pre == null) pre = cur;

                else {

                    pre.next = cur;

                    pre = cur;

                }

                if (cur.left != null) queue.offer(cur.left);

                if (cur.right != null) queue.offer(cur.right);

            }

            pre = null;

        }

    }

}

层次递进法—记住下一层, 下一层有才对其进行遍历, 内部循环操作本层的子节点

public class Solution {

    public void connect(TreeLinkNode root) {

        if(root==null) return;

                   root.next = null;

        TreeLinkNode cur = root;

        TreeLinkNode nextLeftmost = null;

 

      //递进while(cur.left!=null){

        //递进nextLeftmost = cur.left; // save the start of next level, 当作下次内循环的开始点并判断是否有下次循环

       //层次  while(cur!=null){

                cur.left.next=cur.right;

                cur.right.next = cur.next==null? null : cur.next.left;

                cur=cur.next;

            }

            cur=nextLeftmost;  // point to next level

        }

    }

}

7.   117. Populating Next Right Pointers in Each Node II  -----空间一定

 

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/#/description

http://www.cnblogs.com/EdwardLiu/p/3978460.html

 

bfs—同上---不可以

public class Solution {

    public void connect(TreeLinkNode root) {

        TreeLinkNode pre = null;

        if (root == null) return;

        Queue<TreeLinkNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i=0; i<size; i++) {

                TreeLinkNode cur = queue.poll();

                if (pre == null) pre = cur;

                else {

                    pre.next = cur;

                    pre = cur;

                }

                if (cur.left != null) queue.offer(cur.left);

                if (cur.right != null) queue.offer(cur.right);

            }

            pre = null;

        }

    }

}

层次递进法  ---需要记号: 记住本层 的头结点, 本层遍历的节点, 上一层遍历的节点

public void connect(TreeLinkNode root) {

 

        public void connect(TreeLinkNode root) {

        if (root == null) return;

        TreeLinkNode temp = null;// 本层实现遍历的中介点

        TreeLinkNode head = null;// 记住本层的头节点, 下次作为是否开启内循环的判断和内循环的开始点

        TreeLinkNode cur = root;// 上一层的遍历点

        while (cur != null) {

           // 内循环遍历上一层的节点

            while (cur != null) {

                // 分情况看节点是否存在

                if (cur.left != null) {

                    // 本层节点的遍历节点是否存在

                    if (temp != null) { 

                        temp.next = cur.left;

                    } else {

                        //不存在的话先保存头结点

                        head = cur.left;

                    }

                    //遍历的传递

                    temp = cur.left;

                }

               

                if (cur.right != null) {

                    if (temp !=  null) {

                        temp.next = cur.right;

                    } else {

                        head = cur.right;

                    }

                    temp = cur.right;

                }

                // 上层遍历的传递

                cur = cur.next;

            }

            //开启下层循环, 重置下层的头结点和遍历节点

            cur = head;

            temp = null;

            head = null;

           

        }

}

 

8.   129. Sum Root to Leaf Numbers---

递归的题分为考察输入值(头到尾改变)、输出值(直到尾部才开始改变—多为先递归再操作然后作为返回值的 )二叉树常用分治

http://www.cnblogs.com/grandyang/p/4036961.html

https://leetcode.com/problems/sum-root-to-leaf-numbers/#/description

 

http://blog.csdn.net/linhuanmars/article/details/22913699

这是一道树的题目,一般使用递归来做,主要就是考虑递归条件和结束条件。这道题思路还是比较明确的,目标是把从根到叶子节点的所有路径得到的整数都累加起来,递归条件即是题目要求—是改动递归的输入值、返回值?: 把当前的sum乘以10并且加上当前节点传入下一函数,进行递归,最终把左右子树的总和相加。结束条件的话就是如果一个节点是叶子,那么我们应该累加到结果总和中,如果节点到了空节点,则不是叶子节点,不需要加入到结果中,直接返回0即可。算法的本质是一次先序遍历,所以时间是O(n),空间是栈大小,O(logn)。         

 

 

public int sumNumbers(TreeNode root) {

        int ans = helper(root, 0);

        return ans;

    }

    private int helper(TreeNode root, int sum) {

        // 处理空节点

        if (root == null) return 0;

        //处理叶结点

        if (root.left == null && root.right == null) {

            return sum * 10 + root.val;

        }

        // 在遍历的时候的操作, 只是改变输入值, 每一层都有返回, 画图! 回溯!

       int left = helper(root.left, sum * 10 + root.val);

       int right =  helper(root.right, sum * 10 + root.val);

       return left + right;

       

    }

9.   581. Shortest Unsorted Continuous Subarray

数组的题常用方法 :排序、最大值指针边走边找、最小值指针边走边找,数组的其他指针位置—顺序遍历, 逆序遍历,其他指针与最大值指针比较的后果或最小值指针

         https://leetcode.com/problems/shortest-unsorted-continuous-subarray/#/description

public int findUnsortedSubarray(int[] nums) {

        int n = nums.length;

        if (n == 0 || nums == null) {

            return 0;

        }

        int max = nums[0], min = nums[n - 1], beg = - 2, end = - 1;

        for (int i = 1; i < n; i++) {

            max = Math.max(max, nums[i]);

            min = Math.min(min, nums[n - 1 - i]);

            if (nums[i] < max) end = i;

            if (nums[n - 1 - i] > min) beg = n - 1- i;

        }

        return end - beg + 1;

}

10.         241. Different Ways to Add Parentheses

字符串的分治法,和递归一样,找递归条件-函数输入值和返回值,结束条件—叶节点和空节点的处理

http://www.cnblogs.com/EdwardLiu/p/5068637.html

https://leetcode.com/problems/different-ways-to-add-parentheses/#/description

 

public class Solution {

    public List<Integer> diffWaysToCompute(String input) {

        List<Integer> res = new ArrayList<Integer>();

        if (input==null || input.length()==0) return res;

       

        for (int i=0; i<input.length(); i++) { //结束条件 i  = input.length()

            char c = input.charAt(i);   

            if (!isOperator(c)) continue;  //递归条件

            List<Integer> left = diffWaysToCompute(input.substring(0, i));

            List<Integer> right = diffWaysToCompute(input.substring(i+1));

                            //递归条件---返回值

            for (int j=0; j<left.size(); j++) {

                for (int k=0; k<right.size(); k++) {

                    int a = left.get(j);

                    int b = right.get(k);

                    res.add(calc(a,b,c));

                }

            }

        }

        // 叶节点的处理

        if (res.size() == 0) { //input is not null or size==0, but res.size()==0, meaning input is just a number

            res.add(Integer.valueOf(input));

        }

        return res;

    }

   

    public boolean isOperator(char c) {

        if (c==‘+‘ || c==‘-‘ || c==‘*‘) return true;

        return false;

    }

   

    public int calc(int a, int b, char c) {

        int res = Integer.MAX_VALUE;

        switch(c) {

            case ‘+‘: res = a+b; break;

            case ‘-‘: res = a-b; break;

            case ‘*‘: res = a*b; break;

        }

        return res;

    }

}

11.         169. Majority Element

https://leetcode.com/submissions/detail/104321887/

分治法 数组的分治法: 返回值类型,变量类型, 出口, 分治, 题目要求--返回值,, 难点在与题目要求的理解和转换成结果类型,

public class Solution {

    public int majorityElement(int[] nums) {

        return helper(nums, 0, nums.length-1);

    }

//确定返回值类型(根据在下一次递归中的作用, 或者题目的返回值类型)

private int helper(int[] nums, int lo, int hi) {

//递归出口

        if (lo == hi) return nums[lo];

        int mid = lo + (hi - lo) / 2;

//分治

        int left = helper(nums, lo, mid);

        int right = helper(nums, mid+1, hi);

//开始对分治后的小分支进行操作: 根据题目要求用TC写一下, 准备进行返回了

// 优化的好啊, 如果相等不用判断了

        if (left == right) return left;

        else {

            int l = 0, r = 0;

            for (int i = lo; i <= hi; i++) {

                if (nums[i] == left)  l++;

                if (nums[i] == right) r++;

            }

            return l > r ? left : right;

        }

    }

}

 

根据majority 的特性---考点—提取成算法

public int majorityElement(int[] nums) {

        int majority = nums[0], count = 1;

        for (int i = 1; i < nums.length; i++) {

            if (count == 0) {

                majority = nums[i];

                count++;

            } else if (nums[i] == majority) {

                count++;

            } else {

                count--;

            }

        }

        return majority;

}

hashMap 法键值对

public class Solution {

    public int majorityElement(int[] num) {

        int n = num.length;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int elem : num) {

            if (map.containsKey(elem)) {

                map.put(elem, map.get(elem)+1);

            }

            else {

                map.put(elem, 1);

            }

        }

        for (int item : map.keySet()) {

            if (map.get(item) > n/2) {

                return item;

            }

        }

        return -1;

    }

}

12.         229. Majority Element II

https://leetcode.com/problems/majority-element-ii/#/description

http://www.cnblogs.com/EdwardLiu/p/5060185.html

  public List<Integer> majorityElement(int[] nums) {

       List<Integer> list = new ArrayList<>();

       if (nums == null || nums.length == 0) {

           return list;

       }

       if (nums.length == 1) {

           list.add(nums[0]);

           return list;

       }

       int ans1 = 0, ans2 = 0;

       int count1 = 0, count2 = 0;

       for (int i = 0; i < nums.length; i++) {

           if (nums[i] != ans1 && nums[i] != ans2) {

               if (count1 == 0) {

                   ans1 = nums[i];

                   count1++;

               } else if (count2 == 0) {

                   ans2 = nums[i];

                   count2++;

               } else {

                   count1--;

                   count2--;

               }

           } else if (nums[i] == ans1) {

               count1++;

           } else {

               count2++;

           }

       }

       count1 = 0;

       count2 = 0;

      

       for (int i : nums) {

           if (i == ans1) {

               count1++;

           } else if (i == ans2) {

               count2++;

           }

       }

       if (count1 > nums.length / 3) {

           list.add(ans1);

       }

       if (count2 > nums.length / 3) {

           list.add(ans2);

       }

       return list;

}

 

13.         315. Count of Smaller Numbers After Self

 

https://leetcode.com/problems/count-of-smaller-numbers-after-self/#/description

 

BST

public class Solution {

    private class TreeNode {

        public int val;

        public int count = 1;

        public TreeNode left, right;

       

        public TreeNode(int val) {

            this.val = val;

        }

    }

   

    public List<Integer> countSmaller(int[] nums) {

        List<Integer> res = new ArrayList<>();

        if(nums == null || nums.length == 0) {

            return res;

        }

        TreeNode root = new TreeNode(nums[nums.length - 1]);

        res.add(0);

       

        for(int i = nums.length - 2; i >= 0; i--) {

            int count = addNode(root, nums[i]);

            res.add(count);

        }

       

        Collections.reverse(res);

        return res;

    }

   

    private int addNode(TreeNode root, int val) {

        int curCount = 0;

        while(true) {

            if(val <= root.val) {

                root.count++;                   // add the inversion count

                if(root.left == null) {

                    root.left = new TreeNode(val);

                    break;

                } else {

                    root = root.left;

                }

            } else {

                curCount += root.count;

                if(root.right == null) {

                    root.right = new TreeNode(val);

                    break;

                } else {

                    root = root.right;

                }

            }

        }

       

        return curCount;

    }

}

Merge sort

https://leetcode.com/problems/count-of-smaller-numbers-after-self/#/solutions

 

int[] count;

public List<Integer> countSmaller(int[] nums) {

    List<Integer> res = new ArrayList<Integer>();    

 

    count = new int[nums.length];

    int[] indexes = new int[nums.length];

    for(int i = 0; i < nums.length; i++){

             indexes[i] = i;

    }

    mergesort(nums, indexes, 0, nums.length - 1);

    for(int i = 0; i < count.length; i++){

             res.add(count[i]);

    }

    return res;

}

private void mergesort(int[] nums, int[] indexes, int start, int end){

         if(end <= start){

                   return;

         }

         int mid = (start + end) / 2;

         mergesort(nums, indexes, start, mid);

         mergesort(nums, indexes, mid + 1, end);

        

         merge(nums, indexes, start, end);

}

private void merge(int[] nums, int[] indexes, int start, int end){

         int mid = (start + end) / 2;

         int left_index = start;

         int right_index = mid+1;

         int rightcount = 0;       

         int[] new_indexes = new int[end - start + 1];

 

         int sort_index = 0;

         while(left_index <= mid && right_index <= end){

                   if(nums[indexes[right_index]] < nums[indexes[left_index]]){

                            new_indexes[sort_index] = indexes[right_index];

                            rightcount++;

                            right_index++;

                   }else{

                            new_indexes[sort_index] = indexes[left_index];

                            count[indexes[left_index]] += rightcount;

                            left_index++;

                   }

                   sort_index++;

         }

         while(left_index <= mid){

                   new_indexes[sort_index] = indexes[left_index];

                   count[indexes[left_index]] += rightcount;

                   left_index++;

                   sort_index++;

         }

         while(right_index <= end){

                   new_indexes[sort_index++] = indexes[right_index++];

         }

         for(int i = start; i <= end; i++){

                   indexes[i] = new_indexes[i - start];

         }

}

14.         327. Count of Range Sum

https://leetcode.com/problems/count-of-range-sum/#/solutions

public int countRangeSum(int[] nums, int lower, int upper) {

    int n = nums.length;

    long[] sums = new long[n + 1];

    for (int i = 0; i < n; ++i)

        sums[i + 1] = sums[i] + nums[i];

    return countWhileMergeSort(sums, 0, n + 1, lower, upper);

}

 

private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {

    if (end - start <= 1) return 0;

    int mid = (start + end) / 2;

    int count = countWhileMergeSort(sums, start, mid, lower, upper)

              + countWhileMergeSort(sums, mid, end, lower, upper);

    int j = mid, k = mid, t = mid;

    long[] cache = new long[end - start];

    for (int i = start, r = 0; i < mid; ++i, ++r) {

        while (k < end && sums[k] - sums[i] < lower) k++;

        while (j < end && sums[j] - sums[i] <= upper) j++;

        while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];

        cache[r] = sums[i];

        count += j - k;

    }

    System.arraycopy(cache, 0, sums, start, t - start);

    return count;

}

 

15.         148. Sort List

https://leetcode.com/problems/sort-list/#/description

public ListNode sortList(ListNode head) { 

        // write your code here

        if (head == null || head.next == null) {

            return head;

        }

       

        ListNode mid = findMid(head);

       

        // 要从mid的下一个查找不然最后一次findmid会栈溢出

        ListNode right = sortList(mid.next);

        // 要让mid的下一个为空, 不然会死循环

        mid.next = null;

        ListNode left = sortList(head);

        return merge(left, right);

    }

    private ListNode merge(ListNode left, ListNode right) {

        ListNode dummy = new ListNode(0);

        ListNode tail = dummy;

        while (left != null && right != null) {

            if (left.val < right.val) {

                tail.next = left;

                left = left.next;

            } else {

                tail.next = right;

                right = right.next;

            }

            tail = tail.next;

        }

       

        if (left != null) {

            tail.next = left;

        } else {

            tail.next = right;

        }

       

        return dummy.next;

    }

    private ListNode findMid(ListNode head) {

        if (head.next == null || head == null) {

            return head;

        }

        ListNode slow = head;

        ListNode fast = head;

        // 先判断fast 不为空在判断fast.next不为空 不然容易空指针异常

        while  (fast.next != null && fast.next.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

       

        return slow;

    }

16.         92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/#/description\

 

public ListNode reverseBetween(ListNode head, int m, int n) {

        if (head == null || head.next == null) {

            return head;

        }

        int index = 1;

        ListNode tail = new ListNode(0);

        ListNode dummy = tail;

        tail.next = head;

        ListNode start =  head;

        while (index < m) {

            tail = start;

            start = head.next;

            head = head.next;

            index++;

        }

        head = head.next;

        ListNode midTail = start;

        while (index < n) {

            ListNode temp = head.next;

            head.next = start;

            start = head;

            head = temp;

            index++;

        }

        tail.next = start;

        midTail.next = head;

        return dummy.next;

}

17.         206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/#/solutions

 

public ListNode reverseList(ListNode head) {

    /* iterative solution */

    ListNode newHead = null;

    while (head != null) {

        ListNode next = head.next;

        head.next = newHead;

        newHead = head;

        head = next;

    }

    return newHead;

}

 

public ListNode reverseList(ListNode head) {

    /* recursive solution */

    return reverseListInt(head, null);

}

 

private ListNode reverseListInt(ListNode head, ListNode newHead) {

    if (head == null)

        return newHead;

    ListNode next = head.next;

    head.next = newHead;

    return reverseListInt(next, head);

}

18.         21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/#/description

http://www.cnblogs.com/EdwardLiu/p/3718025.html

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);

        ListNode cur = head;

        while (l1 != null && l2 != null) {

            if (l1.val < l2.val) {

                cur.next = l1;

                l1 = l1.next;

            }

            else {

                cur.next = l2;

                l2 = l2.next;

            }

            cur = cur.next;

        }

        cur.next = (l1 != null) ? l1 : l2;

        return head.next;

}

19.         331. Verify Preorder Serialization of a Binary Tree

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/#/description

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/#/solutions

出度入度

public boolean isValidSerialization(String preorder) {

    String[] nodes = preorder.split(",");

    int diff = 1;

    for (String node: nodes) {

        if (--diff < 0) return false;

        if (!node.equals("#")) diff += 2;

    }

    return diff == 0;

}

 

 

用栈

public boolean isValidSerialization(String preorder) {

        // using a stack, scan left to right

        // case 1: we see a number, just push it to the stack

        // case 2: we see #, check if the top of stack is also #

        // if so, pop #, pop the number in a while loop, until top of stack is not #

        // if not, push it to stack

        // in the end, check if stack size is 1, and stack top is #

        if (preorder == null) {

            return false;

        }

        Stack<String> st = new Stack<>();

        String[] strs = preorder.split(",");

        for (int pos = 0; pos < strs.length; pos++) {

            String curr = strs[pos];

            while (curr.equals("#") && !st.isEmpty() && st.peek().equals(curr)) {

                st.pop();

                if (st.isEmpty()) {

                    return false;

                }

                st.pop();

            }

            st.push(curr);

        }

        return st.size() == 1 && st.peek().equals("#");

}

20.         449. Serialize and Deserialize BST

https://leetcode.com/problems/serialize-and-deserialize-bst/#/description

https://leetcode.com/problems/serialize-and-deserialize-bst/#/solutions

public class Codec {

private static final String SEP = ",";

    private static final String NULL = "null";

    // Encodes a tree to a single string.

    public String serialize(TreeNode root) {

        StringBuilder sb = new StringBuilder();

        if (root == null) return NULL;

        //traverse it recursively if you want to, I am doing it iteratively here

        Stack<TreeNode> st = new Stack<>();

        st.push(root);

        while (!st.empty()) {

            root = st.pop();

            sb.append(root.val).append(SEP);

            if (root.right != null) st.push(root.right);

            if (root.left != null) st.push(root.left);

        }

        return sb.toString();

    }

 

    // Decodes your encoded data to tree.

    // pre-order traversal

    public TreeNode deserialize(String data) {

        if (data.equals(NULL)) return null;

        String[] strs = data.split(SEP);

        Queue<Integer> q = new LinkedList<>();

        for (String e : strs) {

            q.offer(Integer.parseInt(e));

        }

        return getNode(q);

    }

   

    // some notes:

    //   5

    //  3 6

    // 2   7

    private TreeNode getNode(Queue<Integer> q) { //q: 5,3,2,6,7

        if (q.isEmpty()) return null;

        TreeNode root = new TreeNode(q.poll());//root (5)

        Queue<Integer> samllerQueue = new LinkedList<>();

        while (!q.isEmpty() && q.peek() < root.val) {

            samllerQueue.offer(q.poll());

        }

        //smallerQueue : 3,2   storing elements smaller than 5 (root)

        root.left = getNode(samllerQueue);

        //q: 6,7   storing elements bigger than 5 (root)

        root.right = getNode(q);

        return root;

}

 

21.         491. Increasing Subsequences

https://leetcode.com/problems/increasing-subsequences/#/solutions

 

public List<List<Integer>> findSubsequences(int[] nums) {

         Set<List<Integer>> res= new HashSet<List<Integer>>();

         List<Integer> holder = new ArrayList<Integer>();

         findSequence(res, holder, 0, nums);

         List result = new ArrayList(res);

         return result;

     }

 

    public void findSequence(Set<List<Integer>> res, List<Integer> holder, int index, int[] nums) {

        if (holder.size() >= 2) {

            res.add(new ArrayList(holder));

        }

        for (int i = index; i < nums.length; i++) {

            if(holder.size() == 0 || holder.get(holder.size() - 1) <= nums[i]) {

                holder.add(nums[i]);

                findSequence(res, holder, i + 1, nums);

                holder.remove(holder.size() - 1);

            }

        }

}

 

22.         547. Friend Circles

https://leetcode.com/problems/friend-circles/#/solutions

相似的题: http://www.cnblogs.com/grandyang/p/5166356.html

 

dfs

public void dfs(int[][] M, int[] visited, int i) {

        for (int j = 0; j < M.length; j++) {

            if (M[i][j] == 1 && visited[j] == 0) {

                visited[j] = 1;

                dfs(M, visited, j);

            }

        }

    }

    public int findCircleNum(int[][] M) {

        int[] visited = new int[M.length];

        int count = 0;

        for (int i = 0; i < M.length; i++) {

            if (visited[i] == 0) {

                dfs(M, visited, i);

                count++;

            }

        }

        return count;

}

Bfs

public int findCircleNum(int[][] M) {

    int count = 0;

    for (int i=0; i<M.length; i++)

        if (M[i][i] == 1) { count++; BFS(i, M); }

    return count;

}

 

public void BFS(int student, int[][] M) {

    Queue<Integer> queue = new LinkedList<>();

    queue.add(student);

    while (queue.size() > 0) {

        int queueSize = queue.size();

        for (int i=0;i<queueSize;i++) {

            int j = queue.poll();

            M[j][j] = 2; // marks as visited

            for (int k=0;k<M[0].length;k++)

                if (M[j][k] == 1 && M[k][k] == 1) queue.add(k);

        }

    }

}

Union find

public class Solution {

  

        class UF {

            private int[] id;

            private int count;

            public UF(int N) {

                count = N;

                id = new int[N];

                for (int i = 0; i < N; i++) {

                    id[i] = i;

                }

            }

            public int count() {

                return count;

            }

            public int find(int p) {

                while (p != id[p]) p  = id[p];

                return p;

            }

            public void union(int p, int q) {

                int pRoot = find(p);

                int qRoot = find(q);

                if (pRoot == qRoot) return;

                id[pRoot] = qRoot;

                count--;

            }

        }

       

    public int findCircleNum(int[][] M) {

        int n = M.length;

        UF uf = new UF(n);

        for (int i = 0; i < n - 1; i++) {

            for (int j = i + 1; j < n; j++) {

                if (M[i][j] == 1) uf.union(i, j);

            }

        }

        return uf.count();

    }

}

23.         297. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/#/description

http://www.cnblogs.com/EdwardLiu/p/5084538.html

public class Codec {

    private static final String spliter = ",";

    private static final String NN = "X";

 

    // Encodes a tree to a single string.

    public String serialize(TreeNode root) {

        StringBuilder sb = new StringBuilder();

        buildString(root, sb);

        return sb.toString();

    }

 

    private void buildString(TreeNode node, StringBuilder sb) {

        if (node == null) {

            sb.append(NN).append(spliter);

        } else {

            sb.append(node.val).append(spliter);

            buildString(node.left, sb);

            buildString(node.right,sb);

        }

    }

    // Decodes your encoded data to tree.

    public TreeNode deserialize(String data) {

        Deque<String> nodes = new LinkedList<>();

        nodes.addAll(Arrays.asList(data.split(spliter)));

        return buildTree(nodes);

    }

   

    private TreeNode buildTree(Deque<String> nodes) {

        String val = nodes.remove();

        if (val.equals(NN)) return null;

        else {

            TreeNode node = new TreeNode(Integer.valueOf(val));

            node.left = buildTree(nodes);

            node.right = buildTree(nodes);

            return node;

        }

    }

}

24.         39. Combination Sum

https://leetcode.com/problems/combination-sum/#/solutions

 

排序后用的if (i != pos && candidates[i] == candidates[i - 1]) { continue; }                         

public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> ans = new ArrayList<>();

        List<Integer> list = new ArrayList<>();

        Arrays.sort(candidates);

        helper(ans, list, candidates, target, 0);

        return ans;

       

    }

    private void helper(List<List<Integer>> ans, List<Integer> list, int[] candidates, int target, int pos) {

        if (target == 0) {

            ans.add(new ArrayList(list));

        }

        for (int i = pos; i < candidates.length; i++) {

            if (candidates[i] > target) return;

            if (i != pos && candidates[i] == candidates[i - 1]) {

                continue;

            }

            list.add(candidates[i]);

            helper(ans, list, candidates, target - candidates[i], i);

            list.remove(list.size() - 1);

        }

}

用hashSet

public List<List<Integer>> combinationSum(int[] candidates, int target) {

        Set<List<Integer>> ans = new HashSet<>();

        List<Integer> list = new ArrayList<>();

        Arrays.sort(candidates);

        helper(ans, list, candidates, target, 0);

        List<List<Integer>> res = new ArrayList(ans);

        return res;

       

    }

    private void helper(Set<List<Integer>> ans, List<Integer> list, int[] candidates, int target, int pos) {

        if (target == 0) {

            ans.add(new ArrayList(list));

        }

        for (int i = pos; i < candidates.length; i++) {

            if (candidates[i] > target) return;

            list.add(candidates[i]);

            helper(ans, list, candidates, target - candidates[i], i);

            list.remove(list.size() - 1);

        }

}

 

25.         40. Combination Sum II

 

https://leetcode.com/problems/combination-sum-ii/#/description

 

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> res = new ArrayList<>();

        //List<Integer> list = new ArrayList<Integer>();

        

        if (candidates.length == 0) {

            return res;

        }

        Arrays.sort(candidates);

        helper(res, new ArrayList<Integer>(), candidates, target, 0);

        return res;

    }

   

    private void helper(List<List<Integer>> res, List<Integer> list,

                        int[] num, int target, int pos) {

        if (target == 0) {

            res.add(new ArrayList<Integer>(list));

            return;

        }

        for (int i = pos; i < num.length; i++) {

            if (num[i] > target) return;

            if (i != pos && num[i] == num[i - 1]) {

                continue;

            }

            list.add(num[i]);

            helper(res, list, num, target - num[i], i + 1);

            list.remove(list.size() - 1);

           

        }

}

26.         46. Permutations

https://leetcode.com/problems/permutations/#/description

public List<List<Integer>> permute(int[] nums) {

   List<List<Integer>> list = new ArrayList<>();

   // Arrays.sort(nums); // not necessary

   backtrack(list, new ArrayList<>(), nums);

   return list;

}

 

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){

   if(tempList.size() == nums.length){

      list.add(new ArrayList<>(tempList));

   } else{

      for(int i = 0; i < nums.length; i++){

         if(tempList.contains(nums[i])) continue; // element already exists, skip

         tempList.add(nums[i]);

         backtrack(list, tempList, nums);

         tempList.remove(tempList.size() - 1);

      }

   }

}

 

27.         47. Permutations II

https://leetcode.com/problems/permutations-ii/#/description

public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        if(nums==null || nums.length==0) return res;

        boolean[] used = new boolean[nums.length];

        List<Integer> list = new ArrayList<Integer>();

        Arrays.sort(nums);

        dfs(nums, used, list, res);

        return res;

    }

 

    public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){

        if(list.size()==nums.length){

            res.add(new ArrayList<Integer>(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(nums,used,list,res);

            used[i]=false;

            list.remove(list.size()-1);

        }

    }

}

28.         216. Combination Sum III

https://leetcode.com/problems/combination-sum-iii/#/solutions

public List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> ans = new ArrayList<>();

        List<Integer> list = new ArrayList<>();

        if (n < k || n >= k * 9 || k < 1) {

            //ans.add(list);

            return ans;

        }

        helper(k, n, ans, list, 1);

        return ans;

       

    }

    private void helper(int k, int n, List<List<Integer>> ans, List<Integer> list, int pos) {

        if (list.size() == k && n == 0) {

            ans.add(new ArrayList(list));

        }

        for (int i = pos; i <= 9; i++) {

            if (i > n) {

                return;

            }

            list.add(i);

            helper(k, n - i, ans, list, i + 1);

            list.remove(list.size() - 1);

        }

}

 

29.         377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/#/solutions

思路值得借鉴!!!

https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation

 

暴力法

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;

}

暴力法转化为动归---top down:

private int[] dp;

 

public int combinationSum4(int[] nums, int target) {

    dp = new int[target + 1];

    Arrays.fill(dp, -1);

    dp[0] = 1;

    return helper(nums, target);

}

 

暴力法转化为动归的关键所在—用数组保存重复递归的函数所以节省了再次递归的时间效率, 先写暴力法、画图、在想着怎么优化时间复杂度, 在重复计算的基础上优化画图—top  down

 

private int helper(int[] nums, int target) {

    if (dp[target] != -1) {

        return dp[target];           //

    }

    int res = 0;

    for (int i = 0; i < nums.length; i++) {

        if (target >= nums[i]) {

            res += helper(nums, target - nums[i]);

        }

    }

    dp[target] = res;

    return res;

}

用一个for 循环和数组加入了所有的可能因素—是因为第一个for 控制了是的内循环的if 得以展开因此省去重复计算时间bottom up…

动归----bottom up

public int combinationSum4(int[] nums, int target) {

    int[] comb = new int[target + 1];

    comb[0] = 1;

    for (int i = 1; i < comb.length; i++) {

        for (int j = 0; j < nums.length; j++) {

            if (i - nums[j] >= 0) {

                comb[i] += comb[i - nums[j]];

            }

        }

    }

    return comb[target];

}

 

30.         17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/#/solutions

 

public class Solution {

             private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

   

             public List<String> letterCombinations(String digits) {

                       List<String> ret = new LinkedList<String>();

                       combination("", digits, 0, ret);

                       return ret;

             }

   

             private void combination(String prefix, String digits, int offset, List<String> ret) {

                       if (offset >= digits.length()) {

                                ret.add(prefix);

                                return;

                       }

                       String letters = KEYS[(digits.charAt(offset) - ‘0‘)];  //不断变化的, charAt() – ‘0’表示数组的位置

                       for (int i = 0; i < letters.length(); i++) {

                                combination(prefix + letters.charAt(i), digits, offset + 1, ret);

                       }

             }

    }

打卡2