347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

//这道题目有两种解法，一种是桶排序(bucket sort)另外一种方法是PriorityQueue

//解法一，桶排序

public class Solution {
    public List topKFrequent(int[] nums, int k) {
        List[] bucket = new List[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            if (map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            } else {
                map.put(n, 1);
            }
        }
        for (int key : map.keySet()) {
            int frequency = map.get(key);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(key);
        }
        List res = new ArrayList<>();
        for (int pos = bucket.length - 1; pos >=0 && res.size() < k; pos--) {
            if (bucket[pos] != null) {
                res.addAll(bucket[pos]);
            }
        }
        return res;
    }
}

//解法二，优先队列

public class Solution {
    public List topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            if (map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            } else {
                map.put(n, 1);
            }
        }
        
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>(k, (o1, o2) -> o2.getValue() - o1.getValue());
        
        // PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
        //     k,
        //     new Comparator<Map.Entry<Integer, Integer>>(){
        //         @Override
        //         public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
        //             return e2.getValue() - e1.getValue();
        //             }
        //     }
        // );
        
        pq.addAll(map.entrySet());
        List res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(pq.poll().getKey());
        }
        return res;
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

/*思路
我们先考察先序遍历序列和中序遍历序列的特点。对于先序遍历序列，根在最前面，后面部分存在一个分割点，前半部分是根的左子树，后半部分是根的右子树。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。当我们从上向下构建树时，我们可以通过先序遍历序列知道根节点的值，但是如何知道两个序列是在哪里分割的呢？这就要依靠中序序列了。我们在中序序列中找到这个根的值，根据这个根的坐标，我们可以知道这个根左子树有多少个节点，右子树有多少个节点。然后我们根据这个将先序遍历序列分割，通过递归再次取每个部分的第一个作为根，同时为了下一次能准确的计算出左右子树各有多少节点，我们也要同时对中序遍历序列进行分割。*/
//O(n) O(n)

public class Solution {
    
    int preStart = 0;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(preorder, inorder, 0, inorder.length - 1, map);
    }
    
    public TreeNode helper(int[] preorder, int[] inorder, int start, int end, HashMap<Integer, Integer> map){
        if(start > end){
            return null;
        }
        int root_val = preorder[preStart];
        preStart++;
	int mid = map.get(root_val);
        TreeNode root = new TreeNode(root_val);
        root.left = helper(preorder, inorder, start, mid - 1, map);
        root.right = helper(preorder, inorder, mid + 1, end, map);
        return root;
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

 

public class Solution {
    int startpos;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        startpos = postorder.length - 1;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(0, postorder.length - 1, inorder, postorder, map);
    }
    public TreeNode helper(int start, int end, int[] inorder, int[] postorder, HashMap<Integer, Integer> map) {
        if (start > end || startpos < 0) {
            return null;
        }
        
        TreeNode root = new TreeNode(postorder[startpos]);
        startpos--;
        int mid = map.get(root.val);
        //这里是模板吗？
        root.right = helper(mid + 1, end, inorder, postorder, map);
        root.left = helper(start, mid - 1, inorder, postorder, map);
        return root;
    }
}

//也可以不用hashmap，每一次都直接扫一遍，相同值返回index

int inMid = 0;
   for (int i = inStart; i <= inEnd; i++) {
     if (inorder[i] == root.val) {
       inMid = i;
       break;
   }
 }

239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Hint:

1. How about using a data structure such as deque (double-ended queue)?
2. The queue size need not be the same as the window’s size.
3. Remove redundant elements and the queue should store only elements that need to be considered.

//时间负责度O(n) 空间复杂度 O(n)

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        LinkedList queue = new LinkedList();
        for (int i = 0; i < nums.length; i++) {
            //吧队列尾部所有比新数小的都扔掉，保证队列是降序数的index
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) { 
                queue.removeLast(); 
            } 
            queue.add(i); 
            //每当新数进来时，如果发现队列头部的数的下标，是窗口最左边数的下标，就扔掉             if (queue.peekFirst() == i - k) { 
                queue.removeFirst(); 
            } 
            //当i走的位置大于窗口宽度k的时候，开始将queue中最大的值放入结果中 
            if (i >= k - 1) {
                result[i - k + 1] = nums[queue.peekFirst()];
            }
        }
        return result;
    }
}

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

//这道题目还是用正统的方法hashmap比较好
//Time complexity O(n) space O(n)

 

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode last = dummy, newNode;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        while (head != null) {
            if (map.containsKey(head)) {
                newNode = map.get(head);
            } else {
                newNode = new RandomListNode(head.label);
                map.put(head, newNode);
            }
            last.next = newNode;
            if (head.random != null) {
                if (map.containsKey(head.random)) {
                    newNode = map.get(head.random);    
                } else {
                    newNode = new RandomListNode(head.random.label);
                    map.put(head.random, newNode);
                }
                last.next.random = newNode;
            }
            last = last.next;
            head = head.next;
        }
        return dummy.next;
    }
}

时间 O(N) 空间 O(1)

public calss Solution {
    if (head == null) return null;
    RandomListNode n1 = head;
    RandomListNode n2;
    //生成的新节点要接在旧节点的后面，穿插
    while (n1 != null) {
        n2 = new RandomListNode(n1.label);
        n2.next = n1.next;
        n1.next = n2;
        n1 = n1.next.next;
    }
    //给新节点的random字段赋值
        n1 = head;
        n2 = n1.next;
        while(n1!=null){
            n2.random = n1.random != null ? n1.random.next : null;
            n1 = n1.next.next;
            n2 = n1 != null ? n2.next.next : null;
        }
        n1 = head;
        n2 = n1.next;
        RandomListNode res = n2;
        // 将新旧节点分开
        while(n1!=null){
            n1.next = n1.next.next;
            n2.next = n2.next != null ? n2.next.next : null;
            n1 = n1.next;
            n2 = n2.next;
        }
        return res;
    }
}

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

/*建立helper函数，当board[i][j]和word的第一个字符相等，将board[i][j]置为非字母的其它字符，防止这个元素再一次被调用，然后递归调用helper函数判断board[i][j]的上下左右相邻的字符是否和word的下一个字符相等并将结果存入res，再把board[i][j]置回原来的字符（可能和word.charAt(0)相同的字符在board[][]中有多种情况，而此解并非正解，故还原数组在main函数里继续循环），然后递归返回res到上一层helper函数。
当递归到第word.length次时，helper被调用了word.length+1次。说明整个word已经被找到，返回true。
回到main函数，遍历整个board数组，当helper函数返回true时，才返回true；否则在循环结束之后返回false。*/

 

 

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) { 
                if (board[i][j] == word.charAt(0) && helper(board, word, i, j, 0)) { 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
    public boolean helper(char[][] board, String word, int i, int j, int start) { 
        if (start == word.length()) return true; 
        if (i >= 0 && i < board.length && j >= 0 && j < board[0].length && board[i][j] == word.charAt(start)) {
            board[i][j] = '$';
            boolean res = helper(board, word, i + 1, j, start + 1) ||
                          helper(board, word, i - 1, j, start + 1) ||
                          helper(board, word, i, j + 1, start + 1) ||
                          helper(board, word, i, j - 1, start + 1);
            board[i][j] = word.charAt(start);
            return res;
        }
        return false;
    }
}

33. Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

//这里的等号感觉很烦。有多种写法，最终目的就是为了不miss掉边界的值的比较

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        while (start <= end) { 
            int mid = start + (end - start) / 2; 
            if (nums[mid] == target) { 
                return mid; 
            } else if (nums[mid] >= nums[start]) {
                if (target >= nums[start] && target < nums[mid]) { 
                    end = mid - 1; 
                } else { 
                    start = mid + 1; 
                } 
            } else { 
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}

50. Pow(x, n)

Implement pow(x, n).

/*复杂度
时间 O(logN) 空间 O(logN)

思路
通过一点点数学推导我们可以知道，如果n是偶数
xnxn=x2n

如果n是奇数
xnxnx=x2n+1

根据这几条原则递归，我们就不用将x相乘n次，而只要logN次就行了

注意
在递归函数中处理n的奇偶问题，在主函数中处理n的正负问题
*/

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0){
        // n为负返回倒数
            return 1/pow(x, -n);
        } else {
        // n为正直接返回结果
            return pow(x, n);
        }
    }
    
    private double pow(double x, int n){
        // 递归终止条件
        if(n == 0){
            return 1.0;
        } 
        if(n == 1){
            return x;
        }
        double val = pow(x, n/2);
        // 根据奇数还是偶数返回不同的值
        if(n % 2 == 0){
            return val * val;
        } else {
            return val * val * x;
        }
    }
}

49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

1. For the return value, each inner list’s elements must follow the lexicographic order.
2. All inputs will be in lower-case.

// 一种新的办法来拿出map里面的所有key，但是是无序的
// 分辨两种排序的方法，一种是Arrays.sort可以直接sort数组里面的单词
// 另外一种是Collections.sort(List list)可以排序里面的String(将每个列表按照内部的词排序一下。)

public class Solution {
    public List<List> groupAnagrams(String[] strs) {
        Map<String, List> map = new HashMap<String, List>();
        for (String str : strs) {
            char[] temp = str.toCharArray();
            Arrays.sort(temp);
            String key = new String(temp);
            List list = map.get(key);
            if (list == null) list = new ArrayList();
            list.add(str);
            map.put(key, list);
        }
        List<List> res = new ArrayList<List>();
        for (String key : map.keySet()) {
            List temp = map.get(key);
            Collections.sort(temp);
            res.add(temp);
        }
        return res;
    }
}

29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

/*首先，分析溢出条件，设置符号位，然后取绝对值运算。
原理如下，被除数a，除数b，设c等于b。
在b<=a时，令除数c每次乘以2，增大到小于等于被除数a的时候，c乘了几次，商里就会有一个2的几次方。如25 / 4，4 * 4 < 25，4 * 8 > 25，所以商里必定有一个4（2的2次方）存入temp，然后res += temp。
然后被除数a减去c，继续check。a = 25 – 4 * 4 = 9，c = 4 * 2 = 8，所以商里必定有一个8 / 4 = 2（2的1次方）存入temp。此时a = 9 – 8 = 1，a < b，循环结束。res = 4 + 2 = 6，为所求。

再举一个例子:

13 / 3, a = 13, b = 3, c = 3:
c = 3, temp = 1; c = 6, temp = 2; c = 12; temp = 4;
c = 3, res = 4, a = 1, a < b, return res = 4.*/

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) return Integer.MAX_VALUE;
        boolean isPos = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0); 
        long a = Math.abs((long)dividend); 
        long b = Math.abs((long)divisor); 
        long res = 0; 
        while (a >= b) {
            long temp = 0;
            long c = b;
            while (c <= a) {
                temp = temp == 0 ? 1 : temp << 1;
                c = c << 1; 
            } 
            c = c >> 1;
            a = a - c;
            res += temp;
        }
        if (res >= Integer.MAX_VALUE) {
            res = isPos ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        else if (!isPos) res = -res;
        return (int)res;
    }
}