LeetCode刷题笔记 10月

Posted on By Guanzhou Song

Go to Leetcode

2019-10-03

153. Find Minimum in Rotated Sorted Array

Description

Suppose an array sorted in ascending order 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]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2]
Output: 1
Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

Solution

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int min = Integer.MAX_VALUE;
        while(start<end){
            int mid = (start+end)/2;
            if(nums[mid]<nums[end]){
                end = mid;
            }else if(nums[mid]>nums[end]){
                //need to add one otherwise will loop forever.
                start = mid + 1;
            }
        }
        return nums[start];
    }
}

2019-10-06

207. Course Schedule

Description

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
             To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

Solution

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import javax.imageio.ImageTranscoder;

class Solution {
	//main idea is topological sort.
	public boolean canFinish(int numCourses, int[][] prerequisites) {
		int[][] graph = new int[numCourses][numCourses];
		int[] inDegree = new int[numCourses];

		for(int i=0;i<prerequisites.length;i++){
			int cur = prerequisites[i][0];
			int pre = prerequisites[i][1];
			//to prevent duplication.
			if(graph[pre][cur]==0){
				inDegree[cur]++;
			}
			graph[pre][cur] = 1;

		}

		int count = 0;
		Queue<Integer> queue = new LinkedList<>();
		for(int i =0;i<numCourses;i++){
			if(inDegree[i]==0){
				queue.offer(i);
			}
		}

		while (!queue.isEmpty()){
			int course = queue.poll();
			count++;
			for(int i = 0;i<numCourses;i++){
				if(graph[course][i]!=0){
					if(--inDegree[i]==0){
						queue.offer(i);
					}
				}
			}

		}
		return count == numCourses;
	}
}

430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.


Example:

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

SOlution

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {

	public Node flatten(Node head) {
		if(head == null){
			return head;
		}
		Node temp = head;
		while(temp!=null){
			if(temp.child == null){
				temp = temp.next;
				continue;
			}
			Node c = flatten(temp.child);
			Node tempNx = temp.next;
			temp.next = c;
			c.prev = temp;
			while(c.next!=null){
				c = c.next;
			}
			c.next = tempNx;
			if(tempNx!=null){
				tempNx.prev = c;
			}
            temp.child = null;
			temp = tempNx;
		}
		return head;
	}

75. Sort Colors

Description

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s. Could you come up with a one-pass algorithm using only constant space?

Solution

class Solution {
    public void sortColors(int[] nums) {
        int second = nums.length-1, zero = 0;
        for(int i = 0;i<=second;i++){
            while(nums[i]==2 && i<second) swap(i,second--,nums);
            while(nums[i] == 0 && i>zero) swap(i,zero++,nums);
        }

    }
    private void swap(int i, int j, int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

36. Valid Sudoku

Description

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true
Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules. The given board contain only digits 1-9 and the character ‘.’. The given board size is always 9x9.

Solution

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<String> seen = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]!='.'){
                    String temp = "(" + board[i][j] + ")";
                if(seen.contains(i+temp) || seen.contains(temp + j) || seen.contains(i/3+temp+j/3))return false;
                seen.add(i+temp) ;
                seen.add(temp+j) ;
                seen.add(i/3+temp+j/3);
                }
            }
        }
        return true;
    }
}

442. Find All Duplicates in an Array

Description

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Solution

public List<Integer> findDuplicates(int[] nums) {
    //use negative to store information.
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0){
                res.add(Math.abs(index+1));
                continue;
            }
            nums[index] = -nums[index];
        }
        return res;
}

2019-10-07

105. Construct Binary Tree from Preorder and Inorder Traversal

Description

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

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

For example, given

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree:

3    / \   9  20
/  \    15   7 ### Solution ```java class Solution {
//Preorder traversing implies that PRE[0] is the root node.
//Then we can find this PRE[0] in IN, say it's IN[5].
//Now we know that IN[5] is root, so we know that IN[0] - IN[4] is on the left side, IN[6] to the end is on the right side.
//Recursively doing this on subarrays, we can build a tree out of it :)
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(0,0,inorder.length-1,preorder,inorder);
}

private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder){
    if(preStart > preorder.length-1 || inStart>inEnd){
        return null;
    }
    TreeNode root = new TreeNode(preorder[preStart]);
    int inIndex = 0;
    for(int i = 0;i<inorder.length;i++){
        if(preorder[preStart]==inorder[i]){
            inIndex = i;
            break;
        }
    }
    root.left = helper(preStart+1,inStart,inIndex-1,preorder,inorder);
    root.right = helper(preStart+inIndex-inStart+1,inIndex+1,inEnd,preorder,inorder);
    return root;
} } ```

974. Subarray Sums Divisible by K

Description

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1 <= A.length <= 30000 -10000 <= A[i] <= 10000 2 <= K <= 10000

Solution

//count[prefix] means how many sequences that sum%K = prefix.
//so by sum[0,j] - sum[0,i] will count sum[i,j].
public int subarraysDivByK(int[] A, int K) {
        int[] count = new int[K];
        int res = 0, prefix = 0;
        count[0] = 1;
        for (int a : A) {
            prefix = (prefix + a % K + K) % K;
            res += count[prefix];
            count[prefix]++;
        }
        return res;
    }

647. Palindromic Substrings

Description

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".


Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Solution


class Solution {

    public int countSubstrings(String s) {
        int count = 0;
        for(int i = 0; i<s.length();i++){
            count += extendPalindrome(s,i,i);
            count += extendPalindrome(s,i,i+1);
        }
        return count;
    }

    private Integer extendPalindrome(String s, int left, int right) {
        int count = 0;
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++; left--; right++;
        }
        return count;
    }

}

2019-10-13

222. Count Complete Tree Nodes

Description

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input: 1 / \ 2 3 / \ / 4 5 6

Output: 6

Solution


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = countDeptLeft(root);
        int r = countDeptRight(root);
        //if it's a balanced tree, can simply calc by 2^n-1.
        if(l==r){
            return (1<<l) -1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    private int countDeptLeft(TreeNode root) {
        int dep = 0;
        while (root != null) {
            root = root.left;
            dep++;
        }
        return dep;
    }

    private int countDeptRight(TreeNode root) {
        int dep = 0;
        while (root != null) {
            root = root.right;
            dep++;
        }
        return dep;
    }

}

2019-10-14

525. Contiguous Array

Description

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

Solution

import java.util.HashMap;

class Solution {
    public int findMaxLength(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==0){
                nums[i] = -1;
            }
        }
        //store the earlist position of a sum.
        //if the sum is equal, then means the difference is 0.
        HashMap<Integer,Integer> sumAtIndex = new HashMap<>();
        int sum = 0, max = 0;
        sumAtIndex.put(0,-1);
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            if(sumAtIndex.containsKey(sum)){
                max = Math.max(max,i-sumAtIndex.get(sum));
            }else{
                sumAtIndex.put(sum,i);
            }

        }
        return max;
    }
}

2019-10-15

739. Daily Temperatures

Description

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution


import java.util.Stack;

class Solution {

    //use stack to store previous information.
    public int[] dailyTemperatures(int[] temperatures) {
    Stack<Integer> stack = new Stack<>();
    int[] ret = new int[temperatures.length];
    for(int i = 0; i < temperatures.length; i++) {
        //go back to see if the current one is a relative warmer day to previous day.
        //if the previous day is higher, than stop cause the previous day is a closer warmer day.
        while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ret[idx] = i - idx;
        }
        //put into stack for future use.
        //all number will pushed once, so O(N).
        stack.push(i);
    }
    return ret;
}


    //same idea but use array and only cost 5 ms which stack consume 50ms.
    public int[] dailyTemperatures(int[] T) {
        int[] stack = new int[T.length];
        int[] res = new int[T.length];
        int top = -1;
        for(int i = 0;i<T.length;i++){
            while(top>-1 && T[i]>T[stack[top]]){
                int index = stack[top--];
                res[index] = i - index;
            }
            stack[++top] = i;
        }
        return res;
    }
}

228. Summary Ranges

Description

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.
Example 2:

Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

Solution

import java.util.ArrayList;
import java.util.List;

class Solution {

    public List<String> summaryRanges(int[] nums) {
        String arrow = "->";
        List<String> res = new ArrayList<>();
        if(nums.length==1){
            res.add(nums[0]+"");
            return res;
        }

        for(int i = 0;i<nums.length;i++){
            int pre = nums[i];
            //use while will save lots of work
            while(i+1<nums.length && nums[i+1]==nums[i]+1)i++;
            if(pre!=nums[i]){
                res.add(pre+arrow+nums[i]);
            }else{
                res.add(pre+"");
            }
        }
        return res;
    }
}

498. Diagonal Traverse

Description

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output:  [1,2,4,7,5,3,6,8,9]

Solution

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int row = 0, col = 0, d = 1;
        int[] res = new int[rowLen * colLen];
        for (int i = 0; i < res.length; i++) {
            res[i] = matrix[row][col];
            row -= d;
            col += d;
            //order is important
            //if reverse: row<0 && col>len => row=0 then row = 2
            if (row >= rowLen) {
                row = rowLen - 1;
                col += 2;
                d = -d;
            }
            if (col >= colLen) {
                col = colLen - 1;
                row += 2;
                d = -d;
            }
            if (row < 0) {
                row = 0;
                d = -d;
            }
            if (col < 0) {
                col = 0;
                d = -d;
            }

        }
        return res;
    }
}

2019-10-16

863. All Nodes Distance K in Binary Tree

Description

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.



Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

The given tree is non-empty. Each node in the tree has unique values 0 <= node.val <= 500. The target node is a node in the tree. 0 <= K <= 1000.

Solution


//solution 1 : build a map and BFS.
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, List<TreeNode>> map = new HashMap<>();
        buildGraph(root, null, map);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(target);
        Set<TreeNode> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            if (K-- == 0) {
                return queue.stream().map(e -> e.val).collect(Collectors.toList());
            }
            Queue<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                visited.add(cur);
                //temp.addAll(map.getOrDefault(cur,new ArrayList<>()).stream().filter(e->!visited.contains(e)).collect(Collectors.toList()));
                if (map.containsKey(cur)) {
                    List<TreeNode> neighbor = map.get(cur);
                    for (TreeNode treeNode : neighbor) {
                        if (!visited.contains(treeNode)) temp.add(treeNode);
                    }
                }
            }
            queue = temp;
        }
        return new ArrayList<Integer>();
    }

    private void buildGraph(TreeNode root, TreeNode parent, Map<TreeNode, List<TreeNode>> map) {
        if (null == root) {
            return;
        }
        if (parent != null) {
            List<TreeNode> p = map.getOrDefault(parent, new ArrayList<TreeNode>());
            p.add(root);
            map.put(parent, p);
            List<TreeNode> t = map.getOrDefault(root, new ArrayList<TreeNode>());
            t.add(parent);
            map.put(root, t);
        }
        buildGraph(root.left, root, map);
        buildGraph(root.right, root, map);
    }


//solution 2: DFS
    Map<TreeNode, Integer> map = new HashMap<>();
        
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> res = new LinkedList<>();
        find(root, target);
        dfs(root, target, K, map.get(root), res);
        return res;
    }
    
    //store distance on every node from root to target, and it's enough!
    //cause the dfs will take care the rest to calculate the distance.
    //As we know, if the distance from a node to target node is k, the distance from its child to the target node is k + 1.
    //unless the child node is closer to the target node which means the target node is in it's subtree.
    // find target node first and store the distance in that path that we could use it later directly
    private int find(TreeNode root, TreeNode target) {
        if (root == null) return -1;
        if (root == target) {
            map.put(root, 0);
            return 0;
        }
        int left = find(root.left, target);
        if (left >= 0) {
            map.put(root, left + 1);
            return left + 1;
        }
        int right = find(root.right, target);
        if (right >= 0) {
            map.put(root, right + 1);
            return right + 1;
        }
        return -1;
    }
    
    private void dfs(TreeNode root, TreeNode target, int K, int length, List<Integer> res) {
        if (root == null) return;
        if (map.containsKey(root)) length = map.get(root);
        if (length == K) res.add(root.val);
        dfs(root.left, target, K, length + 1, res);
        dfs(root.right, target, K, length + 1, res);
    }

1031. Maximum Sum of Two Non-Overlapping Subarrays

Description

Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M. (For clarification, the L-length subarray could occur before or after the M-length subarray.)

Formally, return the largest V for which V = (A[i] + A[i+1] + … + A[i+L-1]) + (A[j] + A[j+1] + … + A[j+M-1]) and either:

0 <= i < i + L - 1 < j < j + M - 1 < A.length, or 0 <= j < j + M - 1 < i < i + L - 1 < A.length.

Example 1:

Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.
Example 2:

Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.
Example 3:

Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

Note:

L >= 1 M >= 1 L + M <= A.length <= 1000 0 <= A[i] <= 1000

Solution


//Lsum, sum of the last L elements
//Msum, sum of the last M elements
//Lmax, max sum of contiguous L elements before the last M elements.
//Mmax, max sum of contiguous M elements before the last L elements/
class Solution {
    public int maxSumTwoNoOverlap(int[] A, int L, int M) {
        for (int i = 1; i < A.length; i++) {
            A[i] += A[i - 1];
        }
        int Lmax = A[L - 1], Mmax = A[M - 1], res = A[L + M - 1];
        for (int i = L + M ; i < A.length; i++) {
            Lmax = Math.max(Lmax,A[i-M]-A[i-M-L]);
            Mmax = Math.max(Mmax, A[i-L] - A[i-M-L]);
            res = Math.max(res,Math.max(Lmax+(A[i]-A[i-M]),Mmax+(A[i]-A[i-L])));
        }
        return res;

    }
}

2019-10-19

109. Convert Sorted List to Binary Search Tree

Description

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

  0
 / \    -3   9    /   /  -10  5

### Solution

//cut into half.
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while(fast.next!=null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null;
        TreeNode res = new TreeNode(slow.val);
        res.left = sortedListToBST(head);
        res.right = sortedListToBST(slow.next);
        return res;
    }

}

209. Minimum Size Subarray Sum

Description

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution

class Solution {
    public int minSubArrayLen_N(int s, int[] nums) {
        int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right++];
            while (sum >= s) {
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE? 0: min;
    }

    public int minSubArrayLen_NLOGN(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] sums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int min = Integer.MAX_VALUE;
        //see more detail about Arrays.binarySearch().
        //https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int,%20int,%20int)
        for (int i = 0; i < nums.length; i++) {
            int end = Arrays.binarySearch(sums, i + 1, len + 1, sums[i] + s);
            if (end < 0) end = -end - 1;
            if (end == len + 1) break;
            min = Math.min(min, end - i);
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

406. Queue Reconstruction by Height

Description

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Solution

class Solution {
    //let the tallest insert first.
    //then if the height is same, let small k goes first.
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0]? (o1[1]-o2[1]): -(o1[0]-o2[0]);
            }
        });
        List<int[]> res = new LinkedList<>();
        for(int[] pair : people){
            res.add(pair[1],pair);
        }
        return res.toArray(new int[people.length][]);
    }
}

2019-10-20

210. Course Schedule II

Descriotion

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .
Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

Solution


class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int len = prerequisites.length;
        int[] indegree = new int[numCourses];
        for(int[] pair : prerequisites){
            indegree[pair[0]] ++;
        }
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        //indegree is 0 means no prerequisite course needed, just added into res.
        for(int i = 0;i<indegree.length;i++){
            if(indegree[i]==0){
                res.add(i);
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()){
            //get a course that has been taken.
            int pre = queue.poll();
            for(int i = 0;i<len;i++){
                //if this course been taken, means the relative course may start being taken.
                if(prerequisites[i][1] == pre){
                    //if indegree is o means able to take this course, otherwise,
                    // there still remains prerequisite need to be taken.
                    indegree[prerequisites[i][0]]--;
                    //able to take the course.
                    if(indegree[prerequisites[i][0]]==0){
                        res.add(prerequisites[i][0]);
                        queue.offer(prerequisites[i][0]);
                    }
                }
            }
        }
        return res.size()==numCourses? res.stream().mapToInt(i->i).toArray():new int[0];
    }
}

355. Design Twitter

Description

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. follow(followerId, followeeId): Follower follows a followee. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Solution

class Twitter {

	//for global use.
	private static int timestamp;
	private Map<Integer, User> userMap;

	//internal class.
	private class Tweet {

		public int id;
		public int time;
		//to store in User class as linked List.
		public Tweet next;

		public Tweet(int id) {
			this.id = id;
			time = timestamp++;
			next = null;
		}
	}

	private class User {

		public int id;
		public Set<Integer> followed;
		//use linkedlist to store sorted by time.
		public Tweet head;

		public User(int id) {
			this.id = id;
			followed = new HashSet<Integer>();
			followed.add(this.id);
			head = null;
		}

		public void follow(int id) {
			followed.add(id);
		}

		public void unfollow(int id) {
			followed.remove(id);
		}

		public void post(int id) {
			Tweet t = new Tweet(id);
			t.next = head;
			head = t;
		}
	}

	/**
	 * Initialize your data structure here.
	 */
	public Twitter() {
		userMap = new HashMap<Integer, User>();
	}

	/**
	 * Compose a new tweet.
	 */
	public void postTweet(int userId, int tweetId) {
		if (!userMap.containsKey(userId)) {
			User u = new User(userId);
			userMap.put(userId, u);
		}
		User u = userMap.get(userId);
		u.post(tweetId);
	}

	/**
	 * Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed
	 * must be posted by users who the user followed or by the user herself. Tweets must be ordered
	 * from most recent to least recent.
	 */
	public List<Integer> getNewsFeed(int userId) {
		List<Integer> res = new LinkedList<>();
		if (!userMap.containsKey(userId)) {
			return res;
		}

		Set<Integer> users = userMap.get(userId).followed;
		PriorityQueue<Tweet> q = new PriorityQueue<>((a, b) -> (b.time - a.time));
		for (int user : users) {
			Tweet t = userMap.get(user).head;
			if (t != null) {
				q.add(t);
			}
		}
		int n = 0;
		//to receive most up-to-date tweet and put next to queue.
		while (!q.isEmpty() && n < 10) {
			Tweet t = q.poll();
			res.add(t.id);
			n++;
			if(t.next != null){
				q.offer(t.next);
			}
		}
		return res;

	}

	/**
	 * Follower follows a followee. If the operation is invalid, it should be a no-op.
	 */
	public void follow(int followerId, int followeeId) {
		if (!userMap.containsKey(followerId)) {
			User u = new User(followerId);
			userMap.put(followerId, u);
		}
		if (!userMap.containsKey(followeeId)) {
			User u = new User(followeeId);
			userMap.put(followeeId, u);
		}
		userMap.get(followerId).follow(followeeId);
	}

	/**
	 * Follower unfollows a followee. If the operation is invalid, it should be a no-op.
	 */
	public void unfollow(int followerId, int followeeId) {
		if (!userMap.containsKey(followerId) || followeeId == followerId) {
			return;
		}
		userMap.get(followerId).unfollow(followeeId);
	}
}


2019-10-21

635. Design Log Storage System

Description

You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Design a log storage system to implement the following functions:

void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system.

int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.

Example 1:
put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note: There will be at most 300 operations of Put or Retrieve. Year ranges from [2000,2017]. Hour ranges from [00,23]. Output for Retrieve has no order required.

Solution

import java.util.*;

class LogSystem {
    private String min, max;
    private SortedMap<String, List<Integer>> map;
    private Map<String, Integer> index;

    public LogSystem() {
        min = "2000:01:01:00:00:00";
        max = "2017:12:31:23:59:59";
        map = new TreeMap<>();
        //use index map to store the index where you only need to consider.
        //ex. Year, only consider first 4 letter and the rest will be filled by min and max.
        index = new HashMap<>();
        index.put("Year", 4);
        index.put("Month", 7);
        index.put("Day", 10);
        index.put("Hour", 13);
        index.put("Minute", 16);
        index.put("Second", 19);
    }

    public void put(int id, String timestamp) {
        if (!map.containsKey(timestamp)) map.put(timestamp, new ArrayList<Integer>());
        map.get(timestamp).add(id);
    }

    public List<Integer> retrieve(String s, String e, String gra) {
        int idx = index.get(gra);
        String start = s.substring(0, idx) + min.substring(idx);
        //sortedmap.submap will exclude end, so add a tail "1" will result the returned submap
        //include the actual end but not larger than the last timestamp.
        String end = e.substring(0, idx) + max.substring(idx) + "1";
        SortedMap<String, List<Integer>> subMap = map.subMap(start, end);
        List<Integer> res = new ArrayList<>();
        for (List<Integer> l : subMap.values()) {
            res.addAll(l);
        }
        return res;
    }
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * List<Integer> param_2 = obj.retrieve(s,e,gra);
 */

723. Candy Crush

Description

This question is about implementing a basic elimination algorithm for Candy Crush.

Given a 2D integer array board representing the grid of candy, different positive integers board[i][j] represent different types of candies. A value of board[i][j] = 0 represents that the cell at position (i, j) is empty. The given board represents the state of the game following the player’s move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:

If three or more candies of the same type are adjacent vertically or horizontally, “crush” them all at the same time - these positions become empty. After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. (No new candies will drop outside the top boundary.) After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps. If there does not exist more candies that can be crushed (ie. the board is stable), then return the current board. You need to perform the above rules until the board becomes stable, then return the current board.

Example:

Input:
board =
[[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]

Output:
[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

Note:

The length of board will be in the range [3, 50]. The length of board[i] will be in the range [3, 50]. Each board[i][j] will initially start as an integer in the range [1, 2000].

Solution

import java.lang.reflect.Array;
import java.util.Arrays;

class Solution {
    public int[][] candyCrush(int[][] board) {
        boolean found = true;
        while (found) {
            found = step(board);
            if (found) move(board);
        }
        return board;
    }

    private boolean step(int[][] b) {
        boolean found = false;
        int Y = b.length;
        int X = b[0].length;
        for (int y = 0; y < Y; y++) {
            for (int x = 0; x < X; x++) {
                //have to check one by one but not skip the negative one.
                int val = Math.abs(b[y][x]);
                if (val == 0) continue;
                //looking rightside and set eliminated item as negative.
                if (x < X - 2 && Math.abs(b[y][x + 1]) == val && Math.abs(b[y][x + 2]) == val) {
                    found = true;
                    int idx = x;
                    while (idx < X && Math.abs(b[y][idx]) == val) {
                        b[y][idx++] = -val;
                    }
                }
                //looking downside and set eliminated item as negative.
                if (y < Y - 2 && Math.abs(b[y + 1][x]) == val && Math.abs(b[y + 2][x]) == val) {
                    found = true;
                    int idx = y;
                    while (idx < Y && Math.abs(b[idx][x]) == val) {
                        b[idx++][x] = -val;
                    }
                }
            }
        }
        return found;
    }

    private void move(int[][] b) {
        int Y = b.length;
        int X = b[0].length;
        //from bottom to top, only store positive number.
        for (int x = 0; x < X; x++) {
            int idx = Y - 1;
            for (int y = Y - 1; y >= 0; y--) {
                if (b[y][x] > 0) {
                    b[idx--][x] = b[y][x];
                }
            }
            //set rest as 0.
            for (int k = idx; k >= 0; k--) {
                b[k][x] = 0;
            }
        }
    }

}


2019-10-22

208. Implement Trie (Prefix Tree)

Description

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert(“apple”); trie.search(“apple”); // returns true trie.search(“app”); // returns false trie.startsWith(“app”); // returns true trie.insert(“app”);
trie.search(“app”); // returns true Note:

You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings.

Solution

class Trie {

    private class Node {

        Node[] alpha;
        boolean isEnd;

        public Node() {
            alpha = new Node[26];
            isEnd = false;
        }

        public boolean isEmpty() {
            for (int i = 0; i < 26; i++) {
                if (alpha[i] != null) {
                    return false;
                }
            }
            return true;
        }
    }

    Node root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new Node();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        char[] charArray = word.toCharArray();
        Node cur = root;
        for (char c : charArray) {
            if (cur.alpha[c - 'a'] == null) {
                cur.alpha[c - 'a'] = new Node();
            }
            cur = cur.alpha[c - 'a'];
        }
        cur.isEnd = true;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        char[] charArray = word.toCharArray();
        Node cur = root;
        for (char c : charArray) {
            if (cur.alpha[c - 'a'] == null) {
                return false;
            }
            cur = cur.alpha[c - 'a'];
        }
        return cur.isEnd;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        char[] charArray = prefix.toCharArray();
        Node cur = root;
        for (char c : charArray) {
            if (cur.alpha[c - 'a'] == null) {
                return false;
            }
            cur = cur.alpha[c - 'a'];
        }
        return cur.isEnd || !cur.isEmpty();
    }
}

/**
 * Your Trie object will be instantiated and called as such: Trie obj = new Trie();
 * obj.insert(word); boolean param_2 = obj.search(word); boolean param_3 = obj.startsWith(prefix);
 */

767. Reorganize String

Description

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = “aab” Output: “aba” Example 2:

Input: S = “aaab” Output: “” Note:

S will consist of lowercase letters and have length in range [1, 500].

Solution

import java.util.PriorityQueue;

class Solution {

    public String reorganizeString(String S) {
        int[] count = new int[26];
        int len = S.length();
        for (char c : S.toCharArray()) {
            count[c - 'a']++;
            if(count[c-'a']>(len+1)/2) return "";
        }
        //Greedy to fill the largest count letter first.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
        //do not add 0 count letter or will add every letter into res.
        for(int i =0;i<26;i++){
            if(count[i]!=0)pq.offer(new int[]{i+'a',count[i]});
        }
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            int[] first = pq.poll();
            if(sb.length()==0 || sb.charAt(sb.length()-1)!=first[0]){
                sb.append((char)first[0]);
                if(--first[1] >0){
                    pq.add(first);
                }
            }else if(!pq.isEmpty()) {
                //if dup, go find second large letter.
                int[] sec = pq.poll();
                sb.append((char)sec[0]);
                if(--sec[1]>0){
                    pq.add(sec);
                }
                pq.add(first);
            }

        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.reorganizeString("aab"));
    }
}

2019-10-23

713. Subarray Product Less Than K

Description

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

0 < nums.length <= 50000. 0 < nums[i] < 1000. 0 <= k < 10^6.

Solution

class Solution {

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int count = 0;
        if (nums == null || nums.length == 0) {
            return count;
        }
        int pro = 1;
        for (int i = 0, j = 0; j < nums.length; j++) {
            //count the pre product.
            pro *= nums[j];
            //move i by one and find the max subarray that product < k;
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            count += (j - i + 1);
        }
        return count;
    }
}

2019-10-27

146. LRU Cache

Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache(2);

cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4

Solution

Main idea is that store head and tail of a double linked list in order to store Least. and use hashmap to store all the information.

class LRUCache {

  Node head;
  Node tail;
  Map<Integer,Node> nodeMap;
  int size;
  int capacity;


  public LRUCache(int capacity) {
    size= 0;
    this.capacity = capacity;
    this.nodeMap = new HashMap<>();

  }

//to get node from map and move to head.
  public int get(int key) {
    if(!nodeMap.containsKey(key)){
      return -1;
    }else{
      Node node = nodeMap.get(key);
      moveToStart(node);
      return node.val;
    }
  }

//put into map and evict least one.
  public void put(int key, int value) {
    if(nodeMap.containsKey(key)){
      Node node = nodeMap.get(key);
      node.val = value;
      moveToStart(node);
    }else{
      Node node = new Node(key,value);
      addStart(node);
      nodeMap.put(key,node);
      size++;
      while(size>capacity){
        int tailKey = tail.key;
        tail = tail.prev;
        tail.next = null;
        nodeMap.remove(tailKey);
        size--;
      }
    }
  }

  private class Node{
    int key;
    int val;
    Node prev;
    Node next;

    public Node(int key, int val){
      this.key = key;
      this.val = val;
    }
  }

  private void addStart(Node node){
    if(head==null){
      head = node;
      tail = node;
    }else{
      node.next = head;
      head.prev = node;
      head = node;
    }
  }

  private void moveToStart(Node node){
    if(node == head) return;
    if(node == tail){
      tail = tail.prev;
      tail.next = null;
      addStart(node);
    }else{
      node.prev.next = node.next;
      node.next.prev = node.prev;
      addStart(node);
    }
  }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

721. Accounts Merge

Description

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1: Input: accounts = [[“John”, “johnsmith@mail.com”, “john00@mail.com”], [“John”, “johnnybravo@mail.com”], [“John”, “johnsmith@mail.com”, “john_newyork@mail.com”], [“Mary”, “mary@mail.com”]] Output: [[“John”, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’], [“John”, “johnnybravo@mail.com”], [“Mary”, “mary@mail.com”]] Explanation: The first and third John’s are the same person as they have the common email “johnsmith@mail.com”. The second John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’], [‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted. Note:

The length of accounts will be in the range [1, 1000]. The length of accounts[i] will be in the range [1, 10]. The length of accounts[i][j] will be in the range [1, 30].

Solution

class Solution {

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Set<String>> neighbor = new HashMap<>();
        Map<String, String> names = new HashMap<>();
        Set<String> emails = new HashSet<>();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for(int i=1; i<account.size(); i++){
                String email = account.get(i);
                emails.add( email );
                names.put( email, name );
                neighbor.putIfAbsent( email, new HashSet<String>() );

                if(i==1) continue;

                //build the "edge" between two adjacent email-nodes
                neighbor.get( account.get(i-1) ).add( email );
                neighbor.get( email ).add( account.get(i-1) );
            }
        }
        List<List<String>> result = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        //search all email and use visited to prevent duplication.
        for(String s : emails)
            if( !visited.contains(s) ){
                visited.add(s);
                List<String> buffer = new ArrayList<String>();
                buffer.add(s);
                helper(s, neighbor, visited, buffer);
                Collections.sort(buffer);
                buffer.add(0, names.get(s));
                result.add(buffer);
            }
        return result;
    }

    //visited from one of the node, and get all it's related neighbors. that's accounted as one user.
    private void helper(String s, Map<String, Set<String>> map, Set<String> visited, List<String> buffer){
        for(String node : map.get(s))
            if( !visited.contains(node) ){
                visited.add(node);
                buffer.add(node);
                helper(node, map, visited, buffer);
            }
    }

}

518. Coin Change 2

Description

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 Example 2:

Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2. Example 3:

Input: amount = 10, coins = [10] Output: 1

Note:

You can assume that

0 <= amount <= 5000 1 <= coin <= 5000 the number of coins is less than 500 the answer is guaranteed to fit into signed 32-bit integer

Solution

class Solution {

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount+1];
        dp[0][0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= amount; j++) {
                //互斥事件:
                //1. use zero coins[i].
                //2. use at least one coins[i].
                dp[i][j] = dp[i-1][j] + (j - coins[i - 1] >= 0 ? dp[i][j - coins[i - 1]] : 0);
            }
        }
        return dp[coins.length][amount];
    }
}

2019-10-28

162. Find Peak Element

Description

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2. Example 2:

Input: nums = [1,2,1,3,5,6,4] Output: 1 or 5 Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6. Note:

Your solution should be in logarithmic complexity.

Solution

class Solution {
        public int findPeakElement(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            if (start == end) {
                return start;
            }
            int mid1 = (start + end) / 2;
            int mid2 = mid1 + 1;
            if(nums[mid1]<nums[mid2]){
                start = mid2;
            }else{
                end = mid1;
            }
        }
        return start;
    }
}

287. Find the Duplicate Number

Description

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2] Output: 2 Example 2:

Input: [3,1,3,4,2] Output: 3 Note:

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

Solution

If there is no duplicate in the array, we can map each indexes to each numbers in this array. In other words, we can have a mapping function f(index) = number For example, let’s assume nums = [2,1,3], then the mapping function is 0->2, 1->1, 2->3. If we start from index = 0, we can get a value according to this mapping function, and then we use this value as a new index and, again, we can get the other new value according to this new index. We repeat this process until the index exceeds the array. Actually, by doing so, we can get a sequence. Using the above example again, the sequence we get is 0->2->3. (Because index=3 exceeds the array’s size, the sequence terminates!)

However, if there is duplicate in the array, the mapping function is many-to-one. For example, let’s assume nums = [2,1,3,1], then the mapping function is 0->2, {1,3}->1, 2->3. Then the sequence we get definitely has a cycle. 0->2->3->1->1->1->1->1->…….. The starting point of this cycle is the duplicate number. We can use Floyd’s Tortoise and Hare Algorithm to find the starting point.

class Solution {

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

2019-10-30

19. Remove Nth Node From End of List

Description

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5. Note:

Given n will always be valid. Could you do this in one pass?

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //use dummy to avoid nullpointerexception.
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy.next,slow = dummy.next,pre_slow = dummy;
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        while(fast!=null){
            pre_slow = slow;
            slow = slow.next;
            fast = fast.next;
        }
        pre_slow.next = slow.next;
        return dummy.next;
    }
}

1007. Minimum Domino Rotations For Equal Row

Description

In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the i-th domino, so that A[i] and B[i] swap values.

Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.

If it cannot be done, return -1.

Example 1:



Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:

Input: A = [3,5,1,2,3], B = [3,6,3,3,4]
Output: -1
Explanation: 
In this case, it is not possible to rotate the dominoes to make one row of values equal.

Note:

1 <= A[i], B[i] <= 6 2 <= A.length == B.length <= 20000

Solution


class Solution {

    public int minDominoRotations(int[] A, int[] B) {
        //use same array to remove dup so it will sum up to len.
        int[] countA = new int[7], countB = new int[7], same = new int[7];
        int len = A.length;
        for (int i = 0; i < len; i++) {
            countA[A[i]]++;
            countB[B[i]]++;
            if (A[i] == B[i]) {
                same[A[i]]++;
            }
        }

        for (int i = 1; i < 7; i++) {
            if(countA[i]+countB[i]-same[i]==len){
                return len - Math.max(countA[i],countB[i]);
            }
        }
        return -1;
    }
}