LeetCode刷题笔记 5月

Posted on By Guanzhou Song

2020-05-01

763. Partition Labels

Description

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1: Input: S = “ababcbacadefegdehijhklij” Output: [9,7,8] Explanation: The partition is “ababcbaca”, “defegde”, “hijhklij”. This is a partition so that each letter appears in at most one part. A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts. Note:

S will have length in range [1, 500]. S will consist of lowercase letters (‘a’ to ‘z’) only.

Solution

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        if (S == null || S.isEmpty()) {
            return res;
        }

        int[] idx = new int[26];
        //find last index of a char.
        for (int i = 0; i < S.length(); i++) {
            idx[S.charAt(i) - 'a'] = i;
        }

        int start = 0;
        int end = 0;
        for (int i = 0; i < S.length(); i++) {
            //end of the current partition so far.
            end = Math.max(end,idx[S.charAt(i)-'a']);
            //if it's already the end, cut as a partition and add length to res.
            if(end == i){
                res.add(end-start+1);
                start = i + 1;
            }
        }
        return res;
    }
}

55. Jump Game

Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 3 * 10^4 0 <= nums[i][j] <= 10^5

Solution

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

45. Jump Game II

Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:

You can assume that you can always reach the last index.

Solution

//This is an implicit bfs solution. i == curEnd means you visited all the items on the current level. Incrementing jumps++ is like incrementing the level you are on. And curEnd = curFarthest is like getting the queue size (level size) for the next level you are traversing.

class Solution {
    public int jump(int[] nums) {
        int jump = 0, curEnd = 0, farest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //get farest possible position this level's children can reach
            farest = Math.max(farest, i + nums[i]);
            //early stop;
            if (farest >= nums.length - 1) {
                jump++;
                    break;
            }
            //end of the level traveral, jump to next level, and curEnd will be the farest we can reach for all children.
            if (i == curEnd) {
                jump++;
                curEnd = farest;
                
            }
            
        }
        return jump;

    }
}

2020-05-02

135. Candy

Description

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Solution

//first check left neighbor then backwards to check right neighbor.
//It's due to the computation dependency. In the second scan, num[i-1]=max(num[i]+1,num[i-1]). In other words, num[i-1] depends on num[i]. So num[i] must be computed before num[i-1].
class Solution {
    public int candy(int[] ratings) {

        if(ratings == null || ratings.length == 0){
            return 0;
        }
        int len = ratings.length;
        int[] candies = new int[len];

        Arrays.fill(candies,1);

        for(int i = 1;i < len ;i++){
            if(ratings[i] > ratings[i-1]){
                candies[i] = candies[i-1] + 1;
            }
        }

        //candies[i] will not be changed after this itera so can sum it up.
        int sum = candies[len-1];
        for(int i = len-1;i>0;i--){
            if(ratings[i-1] > ratings[i]){
                candies[i-1] = Math.max(candies[i-1],candies[i] + 1);
            }
            sum += candies[i];
        }

  
        return sum;
    }
}

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

Description

A string is a valid parentheses string (denoted VPS) if and only if it consists of “(“ and “)” characters only, and:

It is the empty string, or It can be written as AB (A concatenated with B), where A and B are VPS’s, or It can be written as (A), where A is a VPS. We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth(“”) = 0 depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s depth(“(“ + A + “)”) = 1 + depth(A), where A is a VPS. For example, “”, “()()”, and “()(()())” are VPS’s (with nesting depths 0, 1, and 2), and “)(“ and “(()” are not VPS’s.

Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS’s (and A.length + B.length = seq.length).

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.

Example 1:

Input: seq = "(()())"
Output: [0,1,1,1,1,0]
Example 2:

Input: seq = "()(())()"
Output: [0,0,0,1,1,0,1,1]
 

Constraints:

1 <= seq.size <= 10000

Solution

//main idea is to split seq into two subarrays which has the Min(Max(A,B)) where "(" +1 and ")" -1. In order to minimize, try to evenly distribute into two.
class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int A = 0, B = 0;
        int[] res = new int[seq.length()];
        for(int i = 0;i<seq.length();i++){
            char c = seq.charAt(i);
            //will add 1, so pick the less one.
            if(c == '('){
                if(A > B){
                    B++;
                    res[i] = 1;
                }else{
                    //res[i] default to be 0, no need to set res[i].
                    A++;
                }
            }else{
                // will minius 1, pick the more one.
                if(A < B){
                    B--;
                    res[i] = 1;
                }else{
                    A--;
                }
            }
        }
        return res;
    }
}

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

//only if the char with max count exceed (len+1)/2 will return ""
//if not then fill the res from 0,2,4,... then fill the rest regardless of the order.
class Solution {
    public String reorganizeString(String S) {
        int[] map = new int[26];
        char max_key;
        for(char c: S.toCharArray()){
            map[c-'a']++;
        }

        int max = 0, letter = 0;
        for (int i = 0; i < map.length; i++) {
            if (map[i] > max) {
                max = map[i];
                letter = i;
            }
        }

        if(max > (S.length()+1)/2){
            return "";
        }

        char[] res = new char[S.length()];
        int idx = 0;
        while(map[letter]>0){
            res[idx] = (char)(letter+'a');
            map[letter]--;
            idx += 2;
        }

        for(int i = 0;i< map.length;i++){
            while(map[i]>0){
                if(idx>=res.length){
                    idx = 1;
                }
                res[idx] = (char)(i+'a');
            map[i]--;
            idx+=2;
            }
            
        }
        return String.valueOf(res);

    }
}

759. Employee Free Time

Description

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.
Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
 

Constraints:

1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10^8
Accepted

Solution

/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

//same idea as find intervals.
class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> res = new ArrayList();
        if(schedule == null || schedule.size() == 0){
            return res;
        }

        List<Interval> intervals = new ArrayList();
        for(List<Interval> list : schedule){
            intervals.addAll(list);
        }
        intervals.sort((a,b)->(a.start==b.start?a.end-b.end:a.start-b.start));

        int start = intervals.get(0).start;
        int end = intervals.get(0).end;

        for(int i = 1;i<intervals.size();i++){
            Interval interval = intervals.get(i);
            if(interval.start > end){
                Interval temp = new Interval(end,interval.start);
                res.add(temp);
                start =  interval.start;
                end = interval.end;
            }else{
                end = Math.max(end, interval.end);
            }
        }
        return res;
    }
}

714. Best Time to Buy and Sell Stock with Transaction Fee

Description

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Note:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

Solution

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int days = prices.length;
        int[] buy = new int[days];
        int[] sell = new int[days];
        buy[0] = -prices[0];
        for(int i = 1;i<days;i++){
            // keep the same as day i-1, or buy from sell status at day i-1
            buy[i] = Math.max(buy[i-1],sell[i-1]-prices[i]);

            // keep the same as day i-1, or sell from buy status at day i-1
            sell[i] = Math.max(sell[i-1],buy[i-1]+prices[i]-fee);
        }
        return sell[days-1];
    }
}

2020-05-04

861. Score After Flipping Matrix

Description

We have a two dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

Example 1:

Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
 

Note:

1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] is 0 or 1.

Solution

//main idea is to first toggle row so it start with 1 (change first idx to 1 will for sure larger the number)

//then count each column, the count for original or toggled will be either count or A.length-count, just max it, no need to change the array.

//then multiple the 1>>idx. 
class Solution {
    public int matrixScore(int[][] A) {
        if(A == null || A.length == 0 || A[0].length==0){
            return 0;
        }
        for(int i = 0;i<A.length;i++){
            if(A[i][0]!=1){
                toggle(A,i,true);
            }
        } 
        int res = 0;
        for(int i = 0;i<A[0].length;i++){
            int count = 0;
            for(int j = 0;j<A.length;j++){
                count += A[j][i];
            }
            res += Math.max(count,A.length-count) * (1<<(A[0].length-i-1));
        }
       
        return res;

    }



    private void toggle(int[][] A, int idx){
            for(int i = 0;i<A[idx].length;i++){
                if(A[idx][i]==1){
                    A[idx][i] = 0;
                }else{
                    A[idx][i] = 1;
                }
            }
       
    }

}

455. Assign Cookies

Description

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.

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

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Solution

//main idea is to go through all the cookies and assign the least size to the least child.
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int  i = 0;
        for(int j = 0;i<g.length && j<s.length;j++){
            if(g[i]<=s[j]) i++;
        }
        return i;
    }
}

1221. Split a String in Balanced Strings

Description

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.
Example 2:

Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.
Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".
Example 4:

Input: s = "RLRRRLLRLL"
Output: 2
Explanation: s can be split into "RL", "RRRLLRLL", since each substring contains an equal number of 'L' and 'R'
 

Constraints:

1 <= s.length <= 1000
s[i] = 'L' or 'R'

Solution

//once the sum reach 0, means it's balanced.
//"LRLR" is 0 but not balanced, because first LR already considered as one and second as other one.
class Solution {
    public int balancedStringSplit(String s) {
        int res = 0;
        int sum = 0;
        for(char c:s.toCharArray()){
            if(c == 'L'){
                sum++;
            }else{
                sum--;
            }
            if(sum == 0){
                res++;
            }
        }
        return res;
    }
}

452. Minimum Number of Arrows to Burst Balloons

Description

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Solution

//main idea is to find common lapse.
class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points== null || points.length == 0){
            return 0;
        }

        Arrays.sort(points,(a,b)->(a[0]-b[0]));
        
        int start = points[0][0];
        int end = points[0][1];
        int res = 1;
        for(int i = 1;i<points.length;i++){
            int[] point = points[i];
            //overlaped, find the min end
            if(point[0]<=end){
                start = point[0];
                end = Math.min(end,point[1]);
            }else{
                //not overlaped, start a new interval and count++.
                start = point[0];
                end = point[1];
                res++;
            }
            
        }
        return res;
    }
}

2020-05-05

279. Perfect Squares

Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution

//DP solution
//find the min step to go through i-j*j to j
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j*j<=i;j++){
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}
//BFS solution
//whenever try to find a min path, always for for BFS
//starting from 0, level 1 will reach all the perfect square number.
//then for each of the perfect square number, 
class Solution {
    public int numSquares(int n) {
        int[] cnt = new int[n+1];
        //store all the perfect square number
        List<Integer> perfectSq = new ArrayList();

        Queue<Integer> queue = new LinkedList();
        
   
        for(int i = 1;i*i<=n;i++){
            queue.offer(i*i);
            cnt[i*i] = 1;
            perfectSq.add(i*i);
        }
        
        //if n is already perfect
        if(perfectSq.get(perfectSq.size()-1) ==n){
            return 1;
        }

        int level = 1;

        while(!queue.isEmpty()){
            int queueSize = queue.size();
            level++;
            //go through all the numbers at this level.
            for(int j = 0;j<queueSize;j++){
                int cur = queue.poll();
                //from cur, jump perfSq and reach cur+perfSq
                for(int perfSq : perfectSq){
                    //we reached it.
                    if(cur + perfSq == n){
                        return level;
                    //not reach the end and this number has not been explored.(uncheck will lead to loop)
                    }else if(cur+perfSq <n && cnt[cur+perfSq] == 0){
                        cnt[cur+perfSq] = level;
                        queue.offer(cur+perfSq);
                    }else if(cur+perfSq>n){
                        break;
                    }
                }
            }

        }
        return cnt[n];
    }
}

107. Binary Tree Level Order Traversal II

Description

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

Solution


class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        levelBuilder(root,0,res);
        return res;
    }

    private void levelBuilder(TreeNode root, int level, List<List<Integer>> res){
        if(root == null) return;
        if(level >= res.size()){
            res.add(0,new ArrayList<Integer>());
        }

        //go deep first
        levelBuilder(root.left,level+1,res);
        levelBuilder(root.right,level+1,res);

        //add val to list.
        //like backtraversal.
        res.get(res.size()-level-1).add(root.val);
    }
}

2020-05-07

773. Sliding Puzzle

Description

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Input: board = [[3,2,4],[1,5,0]]
Output: 14
Note:

board will be a 2 x 3 array as described above.
board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].

Solution

//main idea is to use BFS to iterate through the possible next str.

class Solution {
    public int slidingPuzzle(int[][] board) {
        //depend on the zero index, all possible index to swap.
        int[][] dirs = new int[][][[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];

        String end = "123450";

        HashSet<String> visited = new HashSet();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();

        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);

        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            //go through all str at this level.
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                //end condition
                if (cur.equals(end)) {
                    return level;
                }
                int zero = cur.indexOf("0");
                //all possible swap index
                for (int dir : dirs[zero]) {
                    String nextStr = next(cur, zero, dir);
                    if (!visited.contains(nextStr)) {
                        queue.offer(nextStr);
                        visited.add(nextStr);
                    }
                }
            }
            level++;
        }
        return -1;

    }

    private String next(String str, int i, int j) {
        StringBuilder sb = new StringBuilder(str);
        sb.setCharAt(i, str.charAt(j));
        sb.setCharAt(j, str.charAt(i));
        return sb.toString();
    }
}

207. Course Schedule

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.
 

Constraints:

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.
1 <= numCourses <= 10^5

Solution

//main idea is to use topological sort to find out all reachable course.
class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] graph = new int[numCourses][numCourses];
        int[] degree = new int[numCourses];

        //build the graph and also degree.
        //with degree 0 means no prerequiest and ready to be taken.
        for(int[] edge : prerequisites){
            if(graph[edge[1]][edge[0]]==0){
                degree[edge[0]]++;
            }
            graph[edge[1]][edge[0]] = 1;

        }

        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        //find all course with no prerequisite
        for(int i = 0; i<degree.length;i++){
            if(degree[i]==0){
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()){
                int cur = queue.poll();
                count++;
                //for all of the course next
                for(int i = 0;i<numCourses;i++){
                    //if the course exist(graph[i][j]!=0) and also ready to be taken(--degree == 0)
                    if(graph[cur][i] != 0 && --degree[i]==0){
                        queue.offer(i);
                    }
                }
        }

        //count the number has been taken.
        return count == numCourses;

    }


}

2020-05-08

111. Minimum Depth of Binary Tree

Description

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

Solution

class Solution {
    
    public int minDepth(TreeNode root) {
        if(root == null) return 0;

        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        //if one of the children is null, then the null one will return 0 and use the other child's depth plus 1.
        //if both of the children are valid, then choose the min.
        return (root.left==null || root.right == null)? leftDepth+rightDepth+1 : Math.min(leftDepth,rightDepth)+1;
    }
}

529. Minesweeper

Description

Let’s play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over - change it to ‘X’. If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively. If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines. Return the board when no more squares will be revealed.

Example 1:

Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

![](https://assets.leetcode.com/uploads/2018/10/12/minesweeper_example_1.png)

Example 2:

Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Explanation:

![](https://assets.leetcode.com/uploads/2018/10/12/minesweeper_example_2.png)


Note:

The range of the input matrix’s height and width is [1,50]. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square. The input board won’t be a stage when game is over (some mines have been revealed). For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

Solution

//main idea is to iterate through the board and explore recursively.
class Solution {
    int[][] dirs = new int[][][[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

    public char[][] updateBoard(char[][] board, int[] click) {
    	//if it's a mine, boom!
        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }

        //if it's a 'B' or digit, nothing happen
        if (board[click[0]][click[1]] != 'E') {
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(click);

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int count = countMine(board, cur[0], cur[1]);
            //if no adjacent mine, go expore its adjacent recursivly.
            if (count == 0) {
                board[cur[0]][cur[1]] = 'B';
                for (int[] dir : dirs) {
                    int new_x = cur[0] + dir[0];
                    int new_y = cur[1] + dir[1];
                    if (new_x >= 0 && new_x < board.length && new_y >= 0 && new_y < board[new_x].length && board[new_x][new_y] == 'E') {
                        queue.offer(new int[]{new_x, new_y});
                        //very important so can avoid pushed into queue twice.
                        board[new_x][new_y] = 'B';
                    }
                }
            } else {
            	//have mine adjacent, change to digit.
                board[cur[0]][cur[1]] = (char) (count + '0');
            }
        }

        return board;


    }

    //helper function to count mines adjacent to certain point.
    private int countMine(char[][] board, int i, int j) {
        int count = 0;
        for (int[] dir : dirs) {
            int new_i = i + dir[0];
            int new_j = j + dir[1];

            if (new_i >= 0 && new_i < board.length && new_j >= 0 && new_j < board[new_i].length && board[new_i][new_j] == 'M') {
                count++;
            }
        }
        return count;
    }
}

2020-05-10

690. Employee Importance

Description

You are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.
 

Note:

One employee has at most one direct leader and may have several subordinates.
The maximum number of employees won't exceed 2000.

Solution

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        if(employees == null){
            return 0;
        }

        HashMap<Integer,Employee> map = new HashMap();
        for(Employee employee : employees){
            map.put(employee.id,employee);
        }
        Queue<Employee> queue = new LinkedList<>();
        queue.add(map.get(id));
        int res = 0;
        while(!queue.isEmpty()){
            Employee cur = queue.poll();
            res += cur.importance;
            if(cur.subordinates!=null){
                //since we have the restriction that one can only have one direct leader, no need to check cycle or dup.
                for(int nextId : cur.subordinates){
                    queue.offer(map.get(nextId));
                }
            }
        }
        return res;

    }
}

542. 01 Matrix

Description

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

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

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

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

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Solution

//main idea is to first go through all the 0, find adjacent and do BFS.
//like go through all the levels and mark as closet level.
class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length==0){
            return matrix;
        }

        int[][] dirs = new int[][][[0,-1],[0,1],[-1,0],[1,0]];
        
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0;i<matrix.length;i++){
            for(int j = 0; j< matrix[i].length;j++){
                if(matrix[i][j]==0){
                    queue.offer(new int[]{i,j});
                }else{
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            for(int[] dir : dirs){
                int new_i = cur[0] + dir[0];
                int new_j = cur[1] + dir[1];
                if(new_i < 0 || new_i >= matrix.length || new_j < 0 || new_j >= matrix[new_i].length || matrix[new_i][new_j] < matrix[cur[0]][cur[1]]+1){
                    continue;
                }
                matrix[new_i][new_j] = matrix[cur[0]][cur[1]]+1;
                queue.offer(new int[]{new_i,new_j});
            }
        }
        return matrix;
    }
}

2020-05-11

417. Pacific Atlantic Water Flow

Description

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Solution

//since water can only fall down, we can trace back from the ocean and find all adjacent point which is higher or even so the water can go. 
//find all points which can be reached fgrom P and A, then find the points can reach both P and A.
class Solution {

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        int iLen = matrix.length;
        int jLen = matrix[0].length;
        Queue<int[]> pQueue = new LinkedList<>();
        Queue<int[]> aQueue = new LinkedList<>();

        boolean[][] pVisited = new boolean[iLen][jLen];
        boolean[][] aVisited = new boolean[iLen][jLen];

        int[][] dirs = new int[][][[0, -1], [0, 1], [-1, 0], [1, 0]];

        //add all boarder to queue and visited.
        for (int i = 0; i < iLen; i++) {
            pQueue.offer(new int[]{i, 0});
            aQueue.offer(new int[]{i, jLen - 1});

            pVisited[i][0] = true;
            aVisited[i][jLen - 1] = true;
        }

        for (int j = 0; j < jLen; j++) {
            pQueue.offer(new int[]{0, j});
            aQueue.offer(new int[]{iLen - 1, j});

            pVisited[0][j] = true;
            aVisited[iLen - 1][j] = true;
        }

        //BFS from the boarder.
        BFS(matrix, pQueue, pVisited, dirs);
        BFS(matrix, aQueue, aVisited, dirs);

        //find all points can reach both P and A.
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < iLen; i++) {
            for (int j = 0; j < jLen; j++) {
                if (pVisited[i][j] && aVisited[i][j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }
        return res;
    }

    private void BFS(int[][] matrix, Queue<int[]> queue, boolean[][] visited, int[][] dirs) {
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int new_i = cur[0] + dir[0];
                int new_j = cur[1] + dir[1];
                //don't forget to check visited to avoid dup.
                if (new_i < 0 || new_i >= matrix.length || new_j < 0 || new_j >= matrix[new_i].length || visited[new_i][new_j] || matrix[new_i][new_j] < matrix[cur[0]][cur[1]]) {
                    continue;
                }
                queue.offer(new int[]{new_i, new_j});
                visited[new_i][new_j] = true;
            }
        }
    }
}

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

Using graph to BFS

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        if (root == null) return null;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        buildGraph(root, graph);

        HashSet<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(target.val);
        visited.add(target.val);
        for (int i = 0; i < K; i++) {
            if (queue.isEmpty()) {
                break;
            }
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                int cur = queue.poll();
                visited.add(cur);
                for (int neighbor : graph.getOrDefault(cur, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return new LinkedList<>(queue);


    }

    public void buildGraph(TreeNode root, Map<Integer, List<Integer>> graph) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            addNeighbor(root, root.left, graph);
            addNeighbor(root.left, root, graph);
            buildGraph(root.left, graph);
        }
        if (root.right != null) {
            addNeighbor(root, root.right, graph);
            addNeighbor(root.right, root, graph);
            buildGraph(root.right, graph);
        }
    }

    private void addNeighbor(TreeNode parent, TreeNode child, Map<Integer, List<Integer>> graph) {
        List<Integer> neighbors = graph.getOrDefault(parent.val, new ArrayList<Integer>());
        neighbors.add(child.val);
        graph.put(parent.val, neighbors);
    }
}

Use DFS

//first find the path from root to target and store distance to target.
//then use DFS to traverse all nodes
//1. in subtree of the target: will start with length = 0 then do deeper to its child K level.
//2. parent or sibiling of target: will start from any node on the way from root to target, then go deep, so the length will be target-node + node-
class Solution {
    
    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;
    }
    
    // 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);
    }
}

11. Container With Most Water

Description

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Solution

class Solution {
    public int maxArea(int[] height) {
        int res = Integer.MIN_VALUE;
        int i =0,j= height.length-1;
        while(i<j){
            int h = Math.min(height[i],height[j]);
            res = Math.max(res, h * (j-i));
            while(i<j && height[i]<=h) i++;
            while(i<j && height[j]<=h) j--;
        }
        return res;
    }
}

2020-05-12

16. 3Sum Closest

Description

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

   Example:
   
   Given array nums = [-1, 2, 1, -4], and target = 1.
   
   The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution

//keep two variables, one gap and one sum. so compare gap and store the closet sum.
class Solution {

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int gap = Integer.MAX_VALUE;
        int res = target;
        for (int i = 0; i < len - 2; i++) {

            int left = i + 1, right = len - 1;

            while (left < right) {

                int sum = nums[i] + nums[left] + nums[right];

                if (sum == target) {
                    return target;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }

                if(Math.abs(sum-target) < gap){
                    gap = Math.abs(sum-target);
                    res = sum;
                }

            }
        }
        return res;
    }
}

2020-05-14

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

//restriction is: there's always one dup and array length n+1 and only contains 1->n inclusive.
//in that case the linkedlist will always be a loop and the start point is the dup number.
//[1,3,4,2,2] -> 1 -> 3 -> 2 -> 4 -> 2(cycle)
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int slow = 0,fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];

            if(slow == fast){
                break;
            }
        }

        slow = 0;
        while(slow!=fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;

    }
}

382. Linked List Random Node

Description

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

Solution

//蓄水池算法:
// Basic idea:
// Choose 1, 2, 3, ..., k first and put them into the reservoir.
// For k+1, pick it with a probability of k/(k+1), and randomly replace a number in the reservoir.
// Repeat until k+i reaches n

//example: for choosing  1 out of [1,2,3,4,5]:

////probability: 1 * 1/2(for 1, there's a chance to be replaced) * 2/3(now the picked one will have 2/3 probability to be replaced) * 3/4 * 4/5
import java.util.Random;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    ListNode head;
    Random rnd;

    /** @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        this.head = head;
        rnd = new Random();
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int count = 0;
        ListNode res = null, cur = head;

        while(cur != null){
            if(rnd.nextInt(++count)==0){
                //replace the previous one.

                res = cur;
            }

            cur = cur.next;
        }
        return res.val;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

28. Implement strStr()

Description

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Solution

class Solution {

    public int strStr(String haystack, String needle) {
        int hLen = haystack.length();
        int nLen = needle.length();
        for (int i = 0; ; i++) {
            for (int j = 0; ; j++) {
                //j reached the end, all fit, return the start idx.
                if (j == nLen) {
                    return i;
                }
                //reached the end, means no fit, and no need to i++ 
                //since i+j is fit but j does not reached end -> there's no more chance to fit.
                if (i + j == hLen) {
                    return -1;
                }
                if (needle.charAt(j) != haystack.charAt(i + j)) {
                    break;
                }
            }
        }
    }
}

86. Partition List

Description

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode less = new ListNode(0);
        ListNode more = new ListNode(0);
        ListNode less_cur = less, more_cur = more;
        ListNode cur = head;
        
        while(cur!=null){
            if(cur.val<x){
                less_cur.next = cur;
                less_cur = less_cur.next;
                
            }else{
                more_cur.next = cur;
                more_cur = more_cur.next;
            }
            
            cur = cur.next;
        }
        
        more_cur.next = null;
        less_cur.next = more.next;
        
        return less.next;
        
    }
}

2020-05-15

72. Edit Distance

Description

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character Delete a character Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Solution

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];

        for(int i = 1;i<=len1;i++){
            dp[i][0] = i;
        }

        for(int j = 1; j<=len2;j++){
            dp[0][j] = j;
        }

        for(int i = 1; i<=len1;i++){
            for(int j = 1;j<=len2;j++){
            	//if the char are the same, nothing need to be done.
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                	//if not equal, then you may:
                	//modify -> dp[i-1][j-1] + 1
                	//insert/delete -> dp[i-1][j]+1 / dp[i][j-1]+1
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                }
            }
        }
        return dp[len1][len2];
    }
}

1140. Stone Game II

Description

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.


Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 
 

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

Solution

//main idea to to use memo and bottom up.
//for the current step, the optimal will be to let the opponent to have the minium values.
//for can iterate through steps, from 1 to 2M, and find out the min value opponent can get.
class Solution {

    int[] sums;
    int[][] memo;

    public int stoneGameII(int[] piles) {
        if (piles == null || piles.length == 0) {
            return 0;
        }
        int len = piles.length;
        sums = new int[len];
        memo = new int[len][len];
        //sums are for calc sum from i to end.
        sums[len - 1] = piles[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            sums[i] = sums[i + 1] + piles[i];
        }
        return dp(piles,0,1);
    }

    public int dp(int[] piles, int i, int M) {
    	//already reached the end.
        if (i >= piles.length) {
            return 0;
        }
        //the current step can already take all stones altogether.
        if (i + 2 * M >= piles.length) {
            return sums[i];
        }
        //searched already.
        if (memo[i][M] != 0) {
            return memo[i][M];
        }
        int min_val = Integer.MAX_VALUE;
        for (int x = 1; x <= 2 * M; x++) {
        	//to each gap x, find the min value the opponent can get.
            min_val = Math.min(min_val, dp(piles, i + x, Math.max(x, M)));
        }
        memo[i][M] = sums[i] - min_val;
        return memo[i][M];
    }
}

263. Ugly Number

Description

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3
Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2
Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.
Note:

1 is typically treated as an ugly number.
Input is within the 32-bit signed integer range: [−231,  231 − 1].

Solution

import java.util.HashMap;

//DP
class Solution {

    HashMap<Integer, Boolean> dp = new HashMap<>();
    int[] factors = new int[]{2, 3, 5};

    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        dp.put(1, true);
        return helper(num);

    }

    public boolean helper(int i) {
        if (dp.containsKey(i)) {
            return dp.get(i);
        }
        boolean res = false;
        for (int j : factors) {
            if (i % j == 0) {
                res |= helper(i / j);
            }
        }
        dp.put(i, res);
        return res;
    }
}


//Math
class Solution {

    int[] factors = new int[]{2, 3, 5};

    public boolean isUgly(int num) {
        if(num <= 0)return false;
        for(int factor : factors){
            while(num%factor==0){
                num /= factor;
            }
        }
        return num==1;

    }

    
}

375. Guess Number Higher or Lower II

Description

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution

//p[i][j] is the minimal cost to guess from range(i...j).
//When you choose an x where i <= x <= j, you may find the
//target number from left i...x-1, or you may find the target number from the x+1...j, //because you don't know which way should go, so to guarantee you have enough money to find //the target, you need to prepare the more, which is max(dp[i][x-1], dp[x+1][j]).
class Solution {

    int[][] dp;

    public int getMoneyAmount(int n) {
        dp = new int[n+1][n+1];
        return helper(1,n);
    }

    public int helper(int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int res = Integer.MAX_VALUE;
        for (int x = i; x <= j; x++) {
        	//since it's ganrantee, can be seens as AT LEAST, so find min of max.
        	//go left and right to search as next step, means less or more.
            res = Math.min(res, Math.max(helper(i, x -1), helper(x+1, j))+x);
        }
        dp[i][j] = res;
        return res;
    }
}

264. Ugly Number II

Description

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:  

1 is typically treated as an ugly number.
n does not exceed 1690.

Solution

class Solution {

    public int nthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[t2] * 2, Math.min(dp[t3] * 3, dp[t5] * 5));
            if (dp[i] == dp[t2] * 2) {
                t2++;
            }
            if (dp[i] == dp[t3] * 3) {
                t3++;
            }
            if (dp[i] == dp[t5] * 5) {
                t5++;
            }
        }
        return dp[n - 1];
    }
}

343. Integer Break

Description

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.

Solution

import java.util.Arrays;

class Solution {

    int[] dp;

    public int integerBreak(int n) {
        dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        int res =  helper(n);
        
        return res;
    }

    public int helper(int n) {
        
        if (n <= 2) {
            return 1;
        }
        if (dp[n] != 0) {
            return dp[n];
        }
        
        for(int i = 1; i<=n/2;i++){ 
            //use Max(helper(i),i) to support the case:
            //3 = 1+2, max = 1*2, while helper(2) will return 1, so maybe the number itself is larger.
            //i and n-i split or not will have 2 result.
            dp[n] = Math.max(dp[n],Math.max(helper(i),i)*Math.max(helper(n-i),n-i));
        }
        return dp[n];
    }
}

2020-05-16

746. Min Cost Climbing Stairs

Description

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Note:
cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

Solution

class Solution {

    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        if (len <= 2) {
            return 1;
        }
        int[] dp = new int[len+1];
        for (int i = 2; i<=len;i++){
            dp[i] = Math.min(dp[i-2]+cost[i-2],dp[i-1+cost[i-1]]);
        }
        return dp[len];
    }
}

And we can realize that only dp[i-2] and dp[i-1] involved, so no need to store all the info in dp.

class Solution {

    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        if (len <= 2) {
            return 1;
        }
        int pre_pre = 0,pre=0;
        for (int i = 2; i<=len;i++){
            int cur  = Math.min(pre_pre+cost[i-2],pre+cost[i-1]);
            pre_pre = pre;
            pre = cur;
        }
        return pre;
    }
}

516. Longest Palindromic Subsequence

Description

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"
Output:
2

One possible longest palindromic subsequence is "bb".

Solution

//dp[i][j]: the longest palindromic subsequence's length of substring(i, j), here i, j represent left, right indexes in the string
//State transition:
// dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
// otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
// Initialization: dp[i][i] = 1
class Solution {

    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int[][] dp = new int[len][len];

        //in order to get next step, we need to know: dp[i+1][j-1],dp[i+1][j], dp[i][j-1].
        //so we should iterate from tail to head for i, and i to tail for j.
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}

877. Stone Game

Description

Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.
 

Note:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.

Solution

// dp[i][j] means the biggest number of stones you can get more than opponent picking piles in piles[i] ~ piles[j].
// You can first pick piles[i] or piles[j].

// If you pick piles[i], your result will be piles[i] - dp[i + 1][j]
// If you pick piles[j], your result will be piles[j] - dp[i][j - 1]
// So we get:
// dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
class Solution {

    public boolean stoneGame(int[] piles) {
        if (piles == null || piles.length <= 2) {
            return true;
        }
        int len = piles.length;
        int[][] dp = new int[len][len];

        for (int i = len - 2; i >= 0; i--) {
            dp[i][i] = piles[i];
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][len - 1] > 0;
    }
}

Tricks:

Alex is first to pick pile.

piles.length is even, and this lead to an interesting fact:

Alex can always pick odd piles or always pick even piles!

For example,

If Alex wants to pick even indexed piles piles[0], piles[2], ….., piles[n-2],

he picks first piles[0], then Lee can pick either piles[1] or piles[n - 1].

Every turn, Alex can always pick even indexed piles and Lee can only pick odd indexed piles.

In the description, we know that sum(piles) is odd.

If sum(piles[even]) > sum(piles[odd]), Alex just picks all evens and wins.

If sum(piles[even]) < sum(piles[odd]), Alex just picks all odds and wins.

So, Alex always defeats Lee in this game.

return true;

718. Maximum Length of Repeated Subarray

Description

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].
 

Note:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Solution

class Solution {

    public int findLength(int[] A, int[] B) {
        int lenA = A.length;
        int lenB = B.length;

        //dp[i][j] is the length of longest common subarray ending with nums[i-1] and nums[j-1]
        //[a,b,c, F] [a,b,c, D] -> dp[3][3] = 3 dp[4][4] = 0
        int[][] dp = new int[lenA + 1][lenB + 1];

        int max = 0;
        for(int i = 1;i<=lenA;i++){
            for(int j = 1 ;j<=lenB;j++){
                if(A[i-1]==B[j-1]  ){
                    dp[i][j] = dp[i-1][j-1]+1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }

        return max;
    }
}

2020-05-17

10. Regular Expression Matching

Description

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

’.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input:
s = "aa"
p = "a\*"
Output: true
Explanation: '\*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:

Input:
s = "ab"
p = ".\*"
Output: true
Explanation: ".\*" means "zero or more (\*) of any character (.)".
Example 4:

Input:
s = "aab"
p = "c\*a\*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:

Input:
s = "mississippi"
p = "mis\*is\*p\*."
Output: false

Solution

详细解释

处理点号「.」通配符

点号可以匹配任意一个字符,万金油嘛,其实是最简单的,稍加改造即可:

def isMatch(text, pattern) -> bool:
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    return first_match and isMatch(text[1:], pattern[1:])

处理「*」通配符

星号通配符可以让前一个字符重复任意次数,包括零次。那到底是重复几次呢?这似乎有点困难,不过不要着急,我们起码可以把框架的搭建再进一步:

def isMatch(text, pattern) -> bool:
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    if len(pattern) >= 2 and pattern[1] == '*':
        # 发现 '*' 通配符
    else:
        return first_match and isMatch(text[1:], pattern[1:])

星号前面的那个字符到底要重复几次呢?这需要计算机暴力穷举来算,假设重复 N 次吧。前文多次强调过,写递归的技巧是管好当下,之后的事抛给递归。

具体到这里,不管 N 是多少,当前的选择只有两个:匹配 0 次、匹配 1 次。所以可以这样处理:

if len(pattern) >= 2 and pattern[1] == '*':
    return isMatch(text, pattern[2:]) or \
            first_match and isMatch(text[1:], pattern)
# 解释:如果发现有字符和 '*' 结合,
    # 或者匹配该字符 0 次,然后跳过该字符和 '*'
    # 或者当 pattern[0] 和 text[0] 匹配后,移动 text

可以看到,我们是通过保留 pattern 中的「*」,同时向后推移 text,来实现「」将字符重复匹配多次的功能。举个简单的例子就能理解这个逻辑了。假设 pattern = a,text = aaa,画个图看看匹配过程:

class Solution {

    String s;
    String p;
    HashMap<String, Boolean> map;

    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        map = new HashMap<>();
        return dp(0,0);
    }

    public boolean dp(int i, int j) {
        String pos = i + "," + j;
        if (map.containsKey(pos)) {
            return map.get(pos);
        }
        if(j==p.length()){
            return i == s.length();
        }

        boolean firstMatched = i<s.length() && (p.charAt(j)==s.charAt(i) || p.charAt(j)=='.');

        boolean res;
        if(j + 1 < p.length() && p.charAt(j+1)=='*') {
            res = dp(i,j+2) || (firstMatched && dp(i+1,j));
        }else{
            res = firstMatched && dp(i+1,j+1);
        }
        
        map.put(pos,res);
        return res;

    }
}

638. Shopping Offers

Description

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
Example 2:
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.
Note:
There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.
You are not allowed to buy more items than you want, even if that would lower the overall price.

Solution

class Solution {

    Map<String, Integer> map;
    List<Integer> price;
    List<List<Integer>> special;

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int size = price.size();
        this.price = price;
        this.special = special;
        map = new HashMap<>();

        return dp(needs, 0);


    }

    //use idx to prevent case like:
    //offer1->offer2 && offer2->offer1
    private int dp(List<Integer> cart, int idx) {

        String pos = cart.toString();
        //already compute, just return.
        if (map.containsKey(pos)) {
            return map.get(pos);
        }
        //base case, worst choice is to buy it without offers.
        int res = directPurchase(cart);
        
        //iterate through all the offers.
        for (int offerIdx = idx; offerIdx < special.size(); offerIdx++) {
            List<Integer> offer = special.get(offerIdx);
            List<Integer> temp = new ArrayList<>();
            //skip if the offer is invalid
            for (int i = 0; i < cart.size(); i++) {
                if (cart.get(i) - offer.get(i) < 0) {
                    temp = null;
                    break;
                }
                temp.add(cart.get(i) - offer.get(i));
            }
            if (temp == null) {
                continue;
            }
            //find min prices
            //use offerIdx to prevent idx: 1->2->1
            //you can still use the same offer for several times.
            res = Math.min(res, dp(temp, offerIdx) + offer.get(offer.size() - 1));
        }

        map.put(pos, res);
        return res;
    }

    private int directPurchase(List<Integer> needs) {
        int total = 0;
        for (int i = 0; i < needs.size(); i++) {
            total += price.get(i) * needs.get(i);
        }

        return total;
    }
}

983. Minimum Cost For Tickets

Description

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

a 1-day pass is sold for costs[0] dollars; a 7-day pass is sold for costs[1] dollars; a 30-day pass is sold for costs[2] dollars. The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.
Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.
 

Note:

1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000

Solution

//iterate through all the days, the min value for 1 -> today will be either dp[i-1] with 1-day, dp[i-7] plus a 7-day or dp[i-30] plus a 30-day
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[30];
        int travelIdx = 0;
        int val_cur = 0;
        for (int d = 1; d <= 365; d++) {
            //if today is not a travel day, the fae are the same as yesterday.
            if (d != days[travelIdx]) {
                dp[d % 30] = dp[(d - 1 + 30) % 30];
                continue;
            }

            travelIdx++;
            val_cur = Math
                .min(
                    dp[(d - 1 + 30) % 30] + costs[0], Math.min(
                        dp[(Math.max(d - 7, 0) + 30) % 30] + costs[1], 
                        dp[(Math.max(0, d - 30) + 30) % 30] + costs[2]
                    ));

            //early stop, already finish the travel.
            if (travelIdx == days.length) {
                break;
            }

            dp[d % 30] = val_cur;
        }
        
        return val_cur;
    }
}

2020-05-18

740. Delete and Earn

Description

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
 

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
 

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

Solution

//main idea is as Robbing House, take it or skip the current one will lead to diff res.
class Solution {
    public int deleteAndEarn(int[] nums) {
        HashMap<Integer, Integer> bucket = new HashMap<>();
        int len = 0;
        for (int num : nums) {
            bucket.put(num, bucket.getOrDefault(num, 0) + num);
            len = Math.max(len, num);
        }

        int take = 0;
        int skip = 0;

        for (int i = 1; i <= len; i++) {
            int pre_take = take;
            //if take it, then previous one should not be taken.
            take = skip + bucket.getOrDefault(i, 0);

            //if skip, find the max for taking or skipping the previous one.
            skip = Math.max(pre_take, skip);
        }
        return Math.max(take, skip);
    }
}

1048. Longest String Chain

Description

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, “abc” is a predecessor of “abac”.

A word chain is a sequence of words [word_1, word_2, …, word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".
 

Note:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.

Solution

//instead of adding from "", can try to delete every character from the longest one.
//go from the shorest one, calc it and store in the memo.
//so the next string can try to delete one of the char and get max length from the prev.
class Solution {

    public int longestStrChain(String[] words) {
        HashMap<String, Integer> map = new HashMap();
        int res = 1;
        Arrays.sort(words, (a, b) -> (a.length() - b.length()));
        for (String word : words) {
            int len = word.length();
            int localBest = -1;
            for (int i = 0; i < len; i++) {
                String prev = word.substring(0, i) + word.substring(i + 1);
                localBest = Math.max(localBest, map.getOrDefault(prev, 0) + 1);
            }
            map.put(word, localBest);
            res = Math.max(res, localBest);
        }
        return res;
    }
}

712. Minimum ASCII Delete Sum for Two Strings

Description

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
Example 2:
Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
Note:

0 < s1.length, s2.length <= 1000.
All elements of each string will have an ASCII value in [97, 122].

Solution

class Solution {

    public int minimumDeleteSum(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();

        int[][] dp = new int[len1 + 1][len2 + 1];

        //need to init the base base, "" and "xxx" will have cost sum(ACS(X)).
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }

        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + (int) s1.charAt(i - 1), dp[i][j - 1] + (int) s2.charAt(j - 1));
                }
            }
        }
        return dp[len1][len2];
    }
}

368. Largest Divisible Subset

Description

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: [1,2,3]
Output: [1,2] \(of course, [1,3] will also be ok\)
Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]

Solution

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums==null || nums.length==0){
            return res;
        }
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        //base case
        dp[0] = 0;

        int max_pos = 0;
        for(int i = 1;i<nums.length;i++){
            //iterate through all the prev and count the most subarray.
            for(int j = i-1;j>=0;j--){
                if(nums[i]%nums[j]==0){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            //if it's the largrest subarray so far.
            if(dp[i]>dp[max_pos]){
                max_pos = i;
            }
        }

        int prev = nums[max_pos];
        int cur_level = dp[max_pos];

        //go back from the largest number of the subarray.
        for(int i = max_pos;i>=0;i--){
            //need to check level to make sure it's the prev of the largest number.
            if(prev % nums[i]==0 && dp[i]==cur_level){
                res.add(nums[i]);
                prev = nums[i];
                cur_level--;
            }
        }

        return res;

    }
}

646. Maximum Length of Pair Chain

Description

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.

Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
The number of given pairs will be in the range [1, 1000].

Solution

DP solution

class Solution {
    public int findLongestChain(int[][] pairs) {
        if(pairs==null || pairs.length==0){
            return 0;
        }
        int len = pairs.length;
        Arrays.sort(pairs,(a,b)->(a[0]-b[0]));

        int[] dp = new int[len+1];
        int res = 0;
        for(int i = 1;i<=len;i++){
            dp[i] = 1;
            for(int j = i-1;j>=1;j--){
                if(pairs[i-1][0]>pairs[j-1][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

Greedy solution

class Solution {

    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) {
            return 0;
        }
        int len = pairs.length;
        Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));

        int[] cur = pairs[0];

        int res = 1;
        for (int i = 1; i < len; i++) {
            if (pairs[i][0] > cur[1]) {
                cur = pairs[i];
                res++;
            }

        }
        return res;
    }

}

2020-05-19

61. Rotate List

Description

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;

        int i;
        for (i = 0; fast.next != null; i++)//Get the total length 
        {
            fast = fast.next;
        }

        for (int j = i - n % i; j > 0; j--) //Get the i-n%i th node
        {
            slow = slow.next;
        }

        fast.next = dummy.next; //Do the rotation
        dummy.next = slow.next;
        slow.next = null;

        return dummy.next;
    }
}

632. Smallest Range Covering Elements from K Lists

Description

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
 

Note:

The given list may contain duplicates, so ascending order means >= here.
1 <= k <= 3500
-105 <= value of elements <= 105.

Solution

//4 -> 4 -> 10 -> 10 -> 10 -> 15 -> 15 -> 24 -> 24
//0 -> 9 ->  9 ->  9 -> 12 -> 12 -> 20 -> 20 -> 20
//5 -> 5 ->  5 -> 18 -> 18 -> 18 -> 18 -> 18 -> 22

//As merge K sort, use priorityQueue to find the next min value
//try to find the min range.
//until both of the array reach the end.
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        if (nums == null || nums.size() == 0) {
            return null;
        }

        int size = nums.size();
        //sort by value and min value at the top.
        PriorityQueue<Element> pq = new PriorityQueue<>(size, (a, b) -> (a.val - b.val));

        int cur_max = Integer.MIN_VALUE;
        int gap = Integer.MAX_VALUE;
        int[] res = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};

        //push first elements of all list.
        //find the cur_max of the heap.
        for (int row = 0; row < size; row++) {
            Element e = new Element(nums.get(row).get(0), row, 0);
            pq.offer(e);
            cur_max = Math.max(cur_max, e.val);
        }

        //if pq is smaller than size of the arrays, means at least one of the arrays will not be in the range.
        while (pq.size() == size) {
            Element cur_element = pq.poll();
            //if the range is smaller, update.
            if (cur_max - cur_element.val < gap) {
                res[0] = cur_element.val;
                res[1] = cur_max;
                gap = cur_max - cur_element.val;
            }

            //if it has next value.
            if (cur_element.idx + 1 < nums.get(cur_element.row).size()) {
                cur_element.idx++;
                cur_element.val = nums.get(cur_element.row).get(cur_element.idx);
                pq.offer(cur_element);
                //update the max of the heap.
                cur_max = Math.max(cur_max, cur_element.val);
            }
        }

        return res;
    }

    class Element {
        int val;
        int row;
        int idx;

        public Element(int val, int row, int idx) {
            this.val = val;
            this.row = row;
            this.idx = idx;
        }
    }
}

904. Fruit Into Baskets

Description

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop. Move to the next tree to the right of the current tree. If there is no tree to the right, stop. Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].
Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].
Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.
 

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Solution

class Solution {
    static final int busket = 2;

    public int totalFruit(int[] tree) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int i = 0, j = 0; j < tree.length; j++) {
            count.put(tree[j], count.getOrDefault(tree[j], 0) + 1);
            while (count.size() > 2) {
                //tree[i] must in the map since all nodes are iterate before the current one so the number will always >= 0.
                count.put(tree[i], count.get(tree[i]) - 1);
                if (count.get(tree[i]) == 0) {
                    count.remove(tree[i]);
                }
                i++;
            }
            res = Math.max(res, j - i + 1);
        }

        return res;
    }
}

977. Squares of a Sorted Array

Description

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
 

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Solution

class Solution {
    public int[] sortedSquares(int[] A) {
        int len = A.length;
        int i = 0, j = len - 1;
        int[] res = new int[len];
        for (int idx = len - 1; idx >= 0; idx--) {
            if (Math.abs(A[i]) > Math.abs(A[j])) {
                res[idx] = A[i] * A[i];
                i++;
            } else {
                res[idx] = A[j] * A[j];
                j--;
            }
        }
        return res;
    }
}

42. Trapping Rain Water

Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

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

Solution

//get the idea from histogram.
class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack();
        int i = 0;
        int count = 0;
        //keep stack non-ascending.
        while(i<height.length){
            //stack is empty or equal to prev.
            if(stack.isEmpty() || height[stack.peek()]>=height[i]){
                stack.push(i++);
            }else{
                //the bottom
                int bottom = height[stack.pop()];
                //if the stack is empty after pop, means reached the boarder, cannot contain water.
                //if the stack is not, find the min of either boarders, minus the bottom, 
                //multiple the length between two boarders.
                int vol = stack.isEmpty()?0:(
                        (Math.min(height[stack.peek()],height[i]) - bottom) * (i-stack.peek()-1)
                        );
                count += vol;
            }
        }
        
        return count;
    }
}

155. Min Stack

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2
 

Constraints:

Methods pop, top and getMin operations will always be called on non-empty stacks.

Solution

class MinStack {

    Node head;
    /** initialize your data structure here. */
    public MinStack() {
        head = null;
    }

    public void push(int x) {
        if(head == null){
            head = new Node(x,x);
        }else{
            //head will be the most current one.
            head = new Node(x,Math.min(x,head.min),head);
        }
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        if(head==null){
            throw new EmptyStackException();
        }else{
            return head.val;
        }
    }

    public int getMin() {
        if(head==null){
            throw new EmptyStackException();
        }else{
            return head.min;
        }
    }

    class Node{
        int val;
        int min;
        Node next;

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

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

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

2020-05-20

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

class Solution {

    public int[] dailyTemperatures(int[] T) {
        //keep stack descending
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            //while peek is lower than the current temp, means today is the first warmer day.
            while(!stack.isEmpty() && T[i]>T[stack.peek()]){
                int prev = stack.pop();
                //gap between two days.
                res[prev] = i - prev;
            }
            stack.push(i);
        }
        return res;
    }
}

316. Remove Duplicate Letters

Description

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"
Output: "abc"
Example 2:

Input: "cbacdcbc"
Output: "acdb"

Solution

// Given the string s, the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i], s.t.
// the suffix s[i .. ] contains all the unique letters. (Note that, when there are more than one smallest s[i]'s
//we choose the leftmost one. Why? Simply consider the example: "abcacb".)

// After determining the greedy choice s[i], we get a new string s' from s by

// removing all letters to the left of s[i],
// removing all s[i]'s from s.
class Solution {
    public String removeDuplicateLetters(String s) {
        if(s==null || s.isEmpty()){
            return "";
        }
        int[] count = new int[26];
        for(char c : s.toCharArray()){
            count[c-'a']++;
        }

        int pos = 0;
        for(int i = 0;i<s.length();i++){
            if(s.charAt(pos)>s.charAt(i)){
                pos = i;
            }
            if(--count[s.charAt(i)-'a']==0){
                break;
            }
        }

        String next = s.substring(pos+1);
        next = next.replaceAll(""+s.charAt(pos),"");
        return "" + s.charAt(pos) + removeDuplicateLetters(next);
    }
}

341. Flatten Nested List Iterator

Description

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].
Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,4,6].

Solution


/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    Stack<NestedInteger> stack = new Stack();

    public NestedIterator(List<NestedInteger> nestedList) {
        pushNext(nestedList);
    }

    private void pushNext(List<NestedInteger> nestedList){
        //push to stack backward so can iterate forward.
        for(int i = nestedList.size()-1;i>=0;i--){
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        //run hasNext() will come to two result:
        //1. stack.peek() is an Integer
        //2. stack is empty
        if(!hasNext()){
            return null;
        }
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        //will go deep until reach an integer.
       while(!stack.isEmpty() && !stack.peek().isInteger()){
           List<NestedInteger> list = stack.pop().getList();
           pushNext(list);
       }
       return !stack.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

94. Binary Tree Inorder Traversal

Description

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        
        while(cur != null || !stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

144. Binary Tree Preorder Traversal

Description

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3] 1 \ 2 / 3

Output: [1,2,3]

Solution

Recursive method with List as returning value:

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> pre = new LinkedList<Integer>();
        if(root==null) return pre;
        pre.add(root.val);
        pre.addAll(preorderTraversal(root.left));
        pre.addAll(preorderTraversal(root.right));
        return pre;
    }

Recursive method with Helper method to have a List as paramater, so we can modify the parameter and don’t have to instantiate a new List at each recursive call:

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> pre = new LinkedList<Integer>();
        preHelper(root,pre);
        return pre;
    }
    public void preHelper(TreeNode root, List<Integer> pre) {
        if(root==null) return;
        pre.add(root.val);
        preHelper(root.left,pre);
        preHelper(root.right,pre);
    }

Iterative method with Stack:

class Solution {
    public List<Integer> preorderIt(TreeNode root) {
        List<Integer> pre = new LinkedList<Integer>();
        if(root==null) return pre;
        Stack<TreeNode> tovisit = new Stack<TreeNode>();
        tovisit.push(root);
        while(!tovisit.empty()) {
            TreeNode visiting = tovisit.pop();
            pre.add(visiting.val);
            if(visiting.right!=null) tovisit.push(visiting.right);
            if(visiting.left!=null) tovisit.push(visiting.left);
        }
        return pre;
    }
}

Tree Iterative Traverse

Description

Iterative implementation for preorder, inorder, and postorder traverse.

Solution

Pre Order

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;   
        }
    }
    return result;
}

In Order

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;   
        }
    }
    return result;
}

Post Order

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

856. Score of Parentheses

Description

Given a balanced parentheses string S, compute the score of the string based on the following rule:

() has score 1 AB has score A + B, where A and B are balanced parentheses strings. (A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1
Example 2:

Input: "(())"
Output: 2
Example 3:

Input: "()()"
Output: 2
Example 4:

Input: "(()(()))"
Output: 6
 

Note:

S is a balanced parentheses string, containing only ( and ).
2 <= S.length <= 50

Solution

class Solution {
    public int scoreOfParentheses(String S) {
        Deque<Integer> stack  = new ArrayDeque();
        int res = 0;
        for(char par : S.toCharArray()){
            if(par == '('){
                stack.push(res);
                res = 0;
            }else{
                res = res==0?1:2*res;
                res += stack.pop();
            }
        }
        return res;
    }
}

907. Sum of Subarray Minimums

Description

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.
 

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

Solution

class Solution {
    public int sumSubarrayMins(int[] A) {
      // initialize previous less element and next less element of 
      // each element in the array
        
        Stack<int[]> previousLess = new Stack<>();
        Stack<int[]> nextLess = new Stack<>();
        int[] leftDistance = new int[A.length];
        int[] rightDistance = new int[A.length];
        
        for(int i=0; i<A.length; i++)
        {
            // use ">=" to deal with duplicate elements
            while(!previousLess.isEmpty() && previousLess.peek()[0] >= A[i])
            {
                previousLess.pop();
            }
            
            leftDistance[i] = previousLess.isEmpty() ? i+1 : i - previousLess.peek()[1];
            previousLess.push(new int[]{A[i], i});
            
        }
        
        for(int i=A.length-1; i>=0; i--)
        {
            while(!nextLess.isEmpty() && nextLess.peek()[0] > A[i])
            {
                nextLess.pop();
            }
            
            rightDistance[i] = nextLess.isEmpty() ? A.length - i : nextLess.peek()[1] - i;
            nextLess.push(new int[]{A[i], i});
        } 
        
        int ans = 0;
        int mod = 1000000007;
        for(int i=0; i<A.length; i++)
        {
            ans = (ans + A[i] * leftDistance[i] * rightDistance[i]) % mod;
        }
        return ans;
    }
}

Main Idea

Before diving into the solution, we first introduce a very important stack type, which is called monotone stack .

What is monotonous increase stack?

Roughly speaking, the elements in the an monotonous increase stack keeps an increasing order.

The typical paradigm for monotonous increase stack:

for(int i = 0; i < A.size(); i++){
  while(!in_stk.empty() && in_stk.top() > A[i]){
    in_stk.pop();
  }
  in_stk.push(A[i]);
}

What can monotonous increase stack do?

(1) find the previous less element of each element in a vector with O(n) time:

What is the previous less element of an element?

For example:

[3, 7, 8, 4]
The previous less element of 7 is 3.
The previous less element of 8 is 7.
The previous less element of 4 is 3.
There is no previous less element for 3.
For simplicity of notation, we use abbreviation PLE to denote Previous Less Element.

C++ code (by slitghly modifying the paradigm):
Instead of directly pushing the element itself, here for simplicity, we push the index.
We do some record when the index is pushed into the stack.

// previous_less[i] = j means A[j] is the previous less element of A[i].
// previous_less[i] = -1 means there is no previous less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
  while(!in_stk.empty() && A[in_stk.top()] > A[i]){
    in_stk.pop();
  }
  previous_less[i] = in_stk.empty()? -1: in_stk.top();
  in_stk.push(i);
}

(2) find the next less element of each element in a vector with O(n) time: What is the next less element of an element?

For example:
[3, 7, 8, 4]
The next less element of 8 is 4.
The next less element of 7 is 4.
There is no next less element for 3 and 4.
For simplicity of notation, we use abbreviation NLE to denote Next Less Element.

C++ code (by slighly modifying the paradigm):

We do some record when the index is poped out from the stack.

// next_less[i] = j means A[j] is the next less element of A[i].
// next_less[i] = -1 means there is no next less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
  while(!in_stk.empty() && A[in_stk.top()] > A[i]){
    auto x = in_stk.top(); in_stk.pop();
    next_less[x] = i;
  }
  in_stk.push(i);
}

How can the monotonous increase stack be applied to this problem?

For example:

Consider the element 3 in the following vector:


                            [2, 9, 7, 8, 3, 4, 6, 1]
			     |                    |
	             the previous less       the next less 
	                element of 3          element of 3

After finding both NLE and PLE of 3, we can determine the distance between 3 and 2(previous less) , and the distance between 3 and 1(next less). In this example, the distance is 4 and 3 respectively.

How many subarrays with 3 being its minimum value?

The answer is 4*3.

682. Baseball Game

Description

You’re now a baseball game point recorder.

Given a list of strings, each string can be one of the 4 following types:

Integer (one round’s score): Directly represents the number of points you get in this round. “+” (one round’s score): Represents that the points you get in this round are the sum of the last two valid round’s points. “D” (one round’s score): Represents that the points you get in this round are the doubled data of the last valid round’s points. “C” (an operation, which isn’t a round’s score): Represents the last valid round’s points you get were invalid and should be removed. Each round’s operation is permanent and could have an impact on the round before and the round after.

You need to return the sum of the points you could get in all the rounds.

Example 1:
Input: ["5","2","C","D","+"]
Output: 30
Explanation: 
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get 2 points. The sum is: 7.
Operation 1: The round 2's data was invalid. The sum is: 5.  
Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.
Round 4: You could get 5 + 10 = 15 points. The sum is: 30.
Example 2:
Input: ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation: 
Round 1: You could get 5 points. The sum is: 5.
Round 2: You could get -2 points. The sum is: 3.
Round 3: You could get 4 points. The sum is: 7.
Operation 1: The round 3's data is invalid. The sum is: 3.  
Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.
Round 5: You could get 9 points. The sum is: 8.
Round 6: You could get -4 + 9 = 5 points. The sum is 13.
Round 7: You could get 9 + 5 = 14 points. The sum is 27.
Note:
The size of the input list will be between 1 and 1000.
Every integer represented in the list will be between -30000 and 30000.

Solution

class Solution {
    public int calPoints(String[] ops) {
        int sum = 0;
        Deque<Integer> stack = new ArrayDeque();
        
        for(String score : ops){
            if("+".equals(score)){
                int pre = stack.pop();
                int localSum = pre+ stack.peek();
                stack.push(pre);
                stack.push(localSum);
                sum += localSum;
            }else if("D".equals(score)){
                sum += 2 * stack.peek();
                stack.push(2*stack.peek());
            }else if("C".equals(score)){
                sum -= stack.peek();
                stack.pop();
            }else{
                int num = Integer.parseInt(score);
                sum += num;
                stack.push(num);
            }
                
        }
        return sum;
    }
}

225. Implement Stack using Queues

Description

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false
Notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Solution

import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        
        if(queue1.isEmpty()){
            queue1.offer(x);
            while(!queue2.isEmpty()){
                queue1.offer(queue2.poll());
            }
        }else{
            queue2.offer(x);
            while(!queue1.isEmpty()){
                queue2.offer(queue1.poll());
            }
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if(!queue1.isEmpty()){
            return queue1.poll();
        }else{
            return queue2.poll();
        }
    }

    /**
     * Get the top element.
     */
    public int top() {
        if(!queue1.isEmpty()){
            return queue1.peek();
        }else{
            return queue2.peek();
        }
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such: MyStack obj = new MyStack(); obj.push(x); int param_2 = obj.pop(); int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

2020-05-23

22. Generate Parentheses

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(res,"",0,0,n);
        return res;
    }

    public void helper(List<String> res, String temp, int open, int close, int n){
        if(temp.length() == 2*n){
            res.add(temp);
            return;
        }
        if(open < n){
            helper(res,temp+"(",open+1,close,n);
        }
        //close can not exceed open or will be invalid.
        if(close < open){
            helper(res,temp+")",open,close+1,n);
        }
    }
}

46. Permutations

Description

Given a collection of distinct integers, return all possible permutations.

Example:

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

Solution

class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        helper(new ArrayList<>(), nums, res);
        return res;
    }

    private void helper(List<Integer> temp, int[] nums, List<List<Integer>> res) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (temp.contains(nums[i])) {
                continue;
            }

            temp.add(nums[i]);
            helper(temp, nums, res);
            temp.remove(temp.size() - 1);
        }
    }
}

39. Combination Sum

Description

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Solution

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

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        helper(candidates,target,0,0,new ArrayList<>(),res);
        return res;
    }

    private void helper(int[] candidates, int target, int idx, int tempSum,List<Integer> temp, List<List<Integer>> res){

        if(tempSum >= target){
            if(tempSum == target){
            	//DEEP CLONE! otherwise will be removed and be empty.
                res.add(new ArrayList<>(temp));
            }
            return;
        }

        //start from idx, so i itself can be duplicated, but will not track backward.
        //prevent case like [2,2,3] and [2,3,2]
        for(int i = idx;i<candidates.length;i++){
            temp.add(candidates[i]);
            helper(candidates,target,i,tempSum+candidates[i],temp,res);
            temp.remove(temp.size()-1);
        }
    }

}

Description

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.

Example:

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution

public class Solution {

    public boolean exist(char[][] board, String word) {
    	//loop over to pick every possible start.
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (exist(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean exist(char[][] board, int i, int j, String word, int ind) {
        if (ind == word.length()) {
            return true;
        }
        //if the current idx is not the same, just go bacl, no need to go further.
        if (i > board.length - 1 || i < 0 || j < 0 || j > board[0].length - 1 || board[i][j] != word.charAt(ind)) {
            return false;
        }

        //remove the current board[i][j] to prevent duplicate backward.
        board[i][j] = '*';

        boolean result =
            exist(board, i - 1, j, word, ind + 1) ||
            exist(board, i, j - 1, word, ind + 1) ||
            exist(board, i, j + 1, word, ind + 1) ||
            exist(board, i + 1, j, word, ind + 1);

        //revert it for others to visit.
        board[i][j] = word.charAt(ind);
        return result;
    }
}

78. Subsets

Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        res.add(temp);
        helper(res,temp,nums,0);
        return res;
    }

    public void helper(List<List<Integer>> res, List<Integer> temp,int[] nums, int idx){
        if(idx >= nums.length){
            return;
        }
        for(int i = idx;i<nums.length;i++){
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            helper(res,temp,nums,i+1);
            temp.remove(temp.size()-1);
        }
    }
}

93. Restore IP Addresses

Description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution

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

class Solution {

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        helper(s,0,res,"");
        return res;
    }

    public void helper(String s,  int count, List<String> res, String temp) {
        if (count == 4 || s.length()==0) {
            if(count == 4 && s.length()==0){
            	//first '.' will be removed.
                res.add(temp.substring(1));
            }
            return;
        }

        for (int i = 1; i <= s.length() && i <= (s.charAt(0) == '0'?1:3); i++) {
            int val = Integer.parseInt(s.substring(0,i));
            if (val <= 255) {
            	//use substring to prevent use idx.
                 helper(s.substring(i),count+1,res,temp+"."+val);

            }
        }
    }
}

131. Palindrome Partitioning

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution

class Solution {

    public List<List<String>> partition(String s) {
        List<String> temp = new ArrayList<>();
        List<List<String>> res = new ArrayList<>();
        helper(s,res,temp,0);
        return res;
    }

    public void helper(String s, List<List<String>> res, List<String> temp, int left) {
        if (left >= s.length() && temp.size() != 0) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for (int i = left; i < s.length(); i++) {
            if(isPalindrome(s,left,i)){
                if(i==left){
                    temp.add(""+s.charAt(i));
                }else{
                    temp.add(s.substring(left,i+1));
                }
                helper(s,res,temp,i+1);
                temp.remove(temp.size()-1);
            }
            
        }

    }

    private boolean isPalindrome(String str, int l, int r) {
        if (l == r) {
            return true;
        }
        while (l < r) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

77. Combinations

Description

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution

class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        helper(res,1,temp,n,k);
        return res;
    }

    public void helper(List<List<Integer>> res, int idx, List<Integer> temp, int n, int k) {
        if (k == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }

        //pruning, stop beforehead.
        //since there's k item to be added, there's no point to start after n-k+1 which will never satisitied.
        for (int i = idx; i <= n-k+1 ;i++) {
            temp.add(i);
            helper(res,i+1,temp,n,k-1);
            temp.remove(temp.size()-1);
        }
    }
}

2020-05-24

401. Binary Watch

Description

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
Note:
The order of output does not matter.
The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

Solution

class Solution {

    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for(int h = 0;h<12;h++){
            for(int m = 0;m<60;m++){
                if(Integer.bitCount(h)+Integer.bitCount(m)==num){
                    String time = h + ":" + ((m<10)?"0"+m:m);
                    res.add(time);
                }
            }
        }
        return res;
    }

}

47. Permutations II

Description

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

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

Description

class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        helper(nums, temp, res, visited);
        return res;
    }

    private void helper(int[] nums, List<Integer> temp, List<List<Integer>> res, boolean[] visited) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
        	//to prevent dup use
        	//!visited[i-1] means the previous one is not used on the previous level and must be used 
        	//at this level, so it will be a dup.
        	//if visited[i-1], means it's been used for last level.
        	//take [1,1',2] for example: 1 is used, then  1' will not be used as it's a dup. -> [1]==[1']
        	//But next level, [1] will add 1' into it as 1 is visited previously.
            if (i != 0 && nums[i - 1] == nums[i] && !visited[i-1]) {
                continue;
            }
            if (!visited[i]) {
                visited[i] = true;
                temp.add(nums[i]);
                helper(nums, temp, res, visited);
                temp.remove(temp.size() - 1);
                visited[i] = false;
            }
        }

    }
}

126. Word Ladder II

Description

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:

Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Solution

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList();
        if (wordList == null || wordList.size() == 0) return res;
        Set<String> wordDict = new HashSet(wordList);
        if (!wordDict.contains(endWord)) return res;
        
        Map<String, List<String>> graph = new HashMap();
        Set<String> curLevel = new HashSet();
        
        curLevel.add(beginWord);
        boolean foundEnd = false;
        
        while (!curLevel.isEmpty() && !foundEnd) {
        	//this is important for minimizing the graph size, and avoid backtrack of the path
            wordDict.removeAll(curLevel); 

            //traverse by level.
            Set<String> nextLevel = new HashSet();
            for (String s : curLevel) {
                graph.put(s, new ArrayList<String>());
                char[] cur = s.toCharArray();
                for (int j = 0; j < cur.length; j++) {
                    char c = cur[j];
                    for (char r = 'a'; r <= 'z'; r++) {
                        if (r == c) continue;
                        cur[j] = r;
                        String temp = new String(cur);
                        //find if the temp is in the dict
                        if (!wordDict.contains(temp)) continue;
                        graph.get(s).add(temp);

                        //since it's a set, can dup.
                        nextLevel.add(temp);

                        //early stop, only contains the closet path.
                        //since now it's reached the end, the path will not shorter than the current one.
                        if (temp.equals(endWord)) {
                            foundEnd = true;
                        };
                    }
                    cur[j] = c;
                }
            }
            curLevel = nextLevel;
        }
        //maybe impossible to find a path.
        if (!foundEnd) return res;
        
        List<String> list = new ArrayList();
        list.add(beginWord);
        addPath(beginWord, endWord, res, graph, list);
        return res;
    }
    
    private void addPath(String from, String to,  List<List<String>> res, 
                         Map<String, List<String>> graph, List<String> list) {
        if (from.equals(to)) {
            res.add(new ArrayList(list));
            return;
        }
        if (!graph.containsKey(from)) return;
        for (String next : graph.get(from)) {
            list.add(next);
            addPath(next, to, res, graph, list);
            list.remove(list.size() - 1);
        }
    }
}

2020-05-25

216. Combination Sum III

Description

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers. The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Solution

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

class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        helper(1,0,temp,res,k,n);
        return res;
    }

    public void helper(int idx, int sum, List<Integer> temp, List<List<Integer>> res, int k,int target) {
        //end condition
        if (idx > 9 || k<=0 || sum >= target) {
            if (sum == target && k==0) {
                res.add(new ArrayList<>(temp));
            }
            return;
        }

        for (int i = idx; i <= 9; i++) {
            temp.add(i);
            //i+1 will prevent i being used again.
            helper(i + 1, sum + i, temp, res, k-1,target);
            temp.remove(temp.size() - 1);
        }
    }
}

60. Permutation Sequence

Description

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"
Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution

//find index for each position, update/remove from the candidate numbers and go for next position.
class Solution {

    public String getPermutation(int n, int k) {
        int pos = 0;
        List<Integer> nums = new ArrayList<>();
        int[] factorial = new int[n + 1];
        StringBuilder sb = new StringBuilder();

        int sum = 1;
        factorial[0] = sum;
        for (int i = 1; i <= n; i++) {
            sum *= i;
            factorial[i] = sum;
            nums.add(i);
        }

        k--;
        for (int i = 1; i <= n; i++) {
            //fac[n-i] is the total number that start with i;
            //2xx have 2 in total, third one,  will be 3 / 2 = 1.
            //so the third one should start with num[1] which is 2 in this case.
            int idx = k / factorial[n - i];
            sb.append(nums.get(idx));
            //remove the current number
            nums.remove(idx);
            k -= idx * factorial[n - i];
        }
        
        return sb.toString();

    }

}

980. Unique Paths III

Description

On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square. There is exactly one starting square. 2 represents the ending square. There is exactly one ending square. 0 represents empty squares we can walk over. -1 represents obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
 

Note:

1 <= grid.length * grid[0].length <= 20

Solution

class Solution {

    int count = 0;
    int total;
    int[][] dirs = new int[][][[0, 1], [0, -1], [1, 0], [-1, 0]];

    public int uniquePathsIII(int[][] grid) {
        int rLen = grid.length;
        int cLen = grid[0].length;
        total = 0;
        int[] start = new int[2];
        for (int i = 0; i < rLen; i++) {
            for (int j = 0; j < cLen; j++) {
                if (grid[i][j] != -1) {
                    total++;
                }
                if (grid[i][j] == 1) {
                    start = new int[]{i, j};
                }
            }
        }

        helper(grid, 1, start[0], start[1]);
        return count;
    }

    public void helper(int[][] grid, int steps, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[row].length || grid[row][col] == Integer.MIN_VALUE || grid[row][col] == -1) {
            return;
        }

        //reached the end and steps are exactly the same as total so it go every possible place.
        if (grid[row][col] == 2) {
            if (steps == total) {
                count++;
            }
            return;
        }

        int original = grid[row][col];
        grid[row][col] = Integer.MIN_VALUE;
        for (int[] dir : dirs) {
            int new_row = row + dir[0];
            int new_col = col + dir[1];
            if (new_row < 0 || new_row >= grid.length || new_col < 0 || new_col >= grid[row].length || grid[new_row][new_col] == Integer.MIN_VALUE
                || grid[new_row][new_col] == -1) {
                continue;
            }
            helper(grid, steps + 1, new_row, new_col);
        }

        grid[row][col] = original;


    }
}

44. Wildcard Matching

Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.

’?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        //to handle the case where s reached the end and p only have * left in the end.
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!='*')
                break;
            else
                match[s.length()][i]=true;
        }

        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                //p is char or ?, mathch one char.
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
                        match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=='*')
                    //(i+1,j) -> match one char in s, and \* continue to match.
                    //(i, j+1) -> match nothing and just go for next position.
                        match[i][j]=match[i+1][j]||match[i][j+1];
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
    }
}

52. N-Queens II

Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.


Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution

import java.util.HashSet;
import java.util.Set;

class Solution {

    private final Set<Integer> occupiedCols = new HashSet<>();
    private final Set<Integer> occupiedDiag1 = new HashSet<>();
    private final Set<Integer> occupiedDiag2 = new HashSet<>();

    public int totalNQueens(int n) {
        return helper(0, 0, n);
    }

    private int helper(int row, int count, int n) {
        for (int col = 0; col < n; col++) {
            //if the current position is invalid.
            if (occupiedCols.contains(col) || occupiedDiag1.contains(row + col) || occupiedDiag2.contains(row - col)) {
                continue;
            }
            //if it's already end of the grid, then count all valid positions.
            if (row == n - 1) {
                count++;
            } else {
                //if not, then set current position a queen and go deeper to find all possible solutions.
                occupiedCols.add(col);
                occupiedDiag1.add(row + col);
                occupiedDiag2.add(row - col);
                count = helper(row + 1, count, n);
                //remove the current queen.
                occupiedCols.remove(col);
                occupiedDiag1.remove(row + col);
                occupiedDiag2.remove(row - col);
            }
        }
        return count;
    }
}

784. Letter Case Permutation

Description

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]
Note:

S will be a string with length between 1 and 12.
S will consist only of letters or digits.

Solution

class Solution {

    public List<String> letterCasePermutation(String S) {
        List<String> set = new ArrayList<>();
        helper(set, S.toCharArray(),0);
        return new ArrayList<>(set);
    }

    public void helper(List<String> res, char[] cur, int idx) {
        //reach the end.
        if(idx == cur.length){
            res.add(String.valueOf(cur));
            return;
        }

        //if cur position is a digit, do nothing and go for next.
        if(Character.isDigit(cur[idx])){
            helper(res,cur,idx+1);
            return;
        }
        
        //try lower case and go next.
        cur[idx] = Character.toLowerCase(cur[idx]);
        helper(res,cur,idx+1);

        //change to upper case and go next.
        cur[idx] = Character.toUpperCase(cur[idx]);
        helper(res,cur,idx+1);
    }
}

2020-05026

526. Beautiful Arrangement

Description

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

The number at the ith position is divisible by i. i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
 

Note:

N is a positive integer and will not exceed 15.

Solution

//one trick is that start from N and go backward, as large number are more likely to fail divided itself.
//So it can failed earier and save more time.
class Solution {

    int N;

    public int countArrangement(int N) {
        this.N = N;
        boolean[] used = new boolean[N + 1];
        return helper(used, N);
    }

    public int helper(boolean[] used, int idx) {
    	//end condition.
        if (idx == 0) {
            return 1;
        }
        
        int count = 0;
        for (int i = used.length-1; i >=1; i--) {
        	//for each of the unused number, try to use it in the current position.
            if (!used[i] && (i % idx == 0 || idx % i == 0)) {
                used[i] = true;
                count += helper(used, idx - 1);
                used[i] = false;
            }
        }
        return count;
    }
}

1079. Letter Tile Possibilities

Description

You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Example 1:

Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Example 2:

Input: "AAABBC"
Output: 188
 

Note:

1 <= tiles.length <= 7
tiles consists of uppercase English letters.

Solution

class Solution {

    char[] list;

    public int numTilePossibilities(String tiles) {
        int[] arr = new int[26];
        for(char c:tiles.toCharArray()){
            arr[c-'A']++;
        }
        return dfs(arr);
    }

    public int dfs(int[] arr) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (arr[i] == 0) {
                continue;
            }
            //with these current tiles (not necessarily all the tiles given) we already have a valid combination.
            sum++;

            //using the i-th tile ('A'+i) as the current tile because there are still remaining ones.
            arr[i]--;

            //if we still want to add more tiles to the existing combination, we simply do recursion with the tiles left;
            sum += dfs(arr);

            //is backtracking because we have finished exploring the possibilities of using the i-th tile and need to restore it and continue to explore other possibilities.
            arr[i]++;
        }
        return sum;
    }
}

320. Generalized Abbreviation

Description

Write a function to generate the generalized abbreviations of a word.

Note: The order of the output does not matter.

Example:

Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Solution

//main idea is to concate the current char with all possible result generated by the rest of the string.
//f(word) = ("w"+f(ord)) + ("1"+f(ord));
//special case is when 1 + 1rd, should merge two number -> 2rd.

class Solution {

    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        if (word == null || word.isEmpty()) {
            res.add("");
            return res;
        }
        res.add("1");
        res.add("" + word.charAt(word.length() - 1));
        //start from the tail and go backward.
        for (int i = word.length() - 2; i >= 0; i--) {
            List<String> temp = new ArrayList<>();

            char c = word.charAt(i);
            for (String str : res) {
                temp.add(concate('1', str));
                temp.add(concate(c, str));
            }
            res = new ArrayList<>(temp);
        }
        return res;

    }

    private String concate(char prefix, String str) {
        if (str == null || str.isEmpty()) {
            return "" + prefix;
        }
        //special case when 1 + 1rd, should merge two number -> 2rd.
        if (Character.isDigit(str.charAt(0)) && Character.isDigit(prefix)) {
            int sum = 0;
            int idx = 0;
            while (idx < str.length() && Character.isDigit(str.charAt(idx))) {
                sum *= 10;
                sum += str.charAt(idx++) - '0';
            }
            sum += prefix - '0';
            return sum + str.substring(idx);
        } else {
            return prefix + str;
        }
    }
}


class Solution {

    public List<String> generateAbbreviations(String word){
        List<String> res = new ArrayList<String>();
        backtrack(res, word, 0, "", 0);

        return res;
    }

    private void backtrack(List<String> res, String word, int pos, String cur, int count){
        if(pos==word.length()){
            if(count > 0) cur += count;
            res.add(cur);
        }
        else{
            //consider the current position as a number.
            backtrack(res, word, pos + 1, cur, count + 1);
            
            //consider the current position as a char and set count to 0.
            backtrack(res, word, pos + 1, cur + (count>0 ? count : "") + word.charAt(pos), 0);
        }
    }
}

148. Sort List

Description

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution

//Main idea: Merge sort, since linkedlist are nature for merging.
class Solution {

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode fast = head, slow = head,prev = null;
        while (fast != null && fast.next != null) {
            prev  =slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        prev.next=null;

        ListNode node1 = sortList(head);
        ListNode node2 = sortList(slow);
        return merge(node1, node2);
    }

    public ListNode merge(ListNode node1, ListNode node2) {

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }

        if (node1 != null) {
            cur.next = node1;
        }
        if (node2 != null) {
            cur.next = node2;
        }

        return dummy.next;

    }
}

147. Insertion Sort List

Description

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5[]

Solution


class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        
        ListNode cur = head;
        ListNode pre = dummy;
        ListNode next = null;

        while(cur!=null){
            next = cur.next;
            //trick is not move pre to head every time.
            //only when the last item is larger than the current one
            //shall it means the current one will be inserted in the middle
            //otherise it definitly go for the tail so no need to reset to head.
            if (pre.val >= cur.val) pre = dummy;

            //find the right position to insert.
            while(pre.next!=null && pre.next.val<cur.val){
                pre = pre.next;
            }

            //insert cur between pre and pre.next
            //pre -> cur -> pre.next
            cur.next = pre.next;
            pre.next = cur;
            cur = next;
        }

        return dummy.next;

    }

}

2020-05-27

179. Largest Number

Description

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"
Example 2:

Input: [3,30,34,5,9]
Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.

Solution

class Solution {

    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        //convert to string, cause int are hard to compare using comparator.
        String[] s_nums = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            s_nums[i] = String.valueOf(nums[i]);
        }
        
        //main idea, compare two possible outcome with different order.
        Arrays.sort(s_nums, (s1,s2)->((s2+s1).compareTo(s1+s2)));

        //no number should start with 0 except 0.
        if (s_nums[0].charAt(0) == '0') {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for (String s : s_nums) {
            sb.append(s);
        }
        return sb.toString();

    }

}

164. Maximum Gap

Description

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.
Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
Note:

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Try to solve it in linear time/space.

Solution

//For example, we set the bucket size to be 10, those numbers can be put into above buckets. 
//If we set the bucket size clever(relatively small), we can ensure that the max gap cannot be in same bucket. 
//In worst case each successive numbers have same gap. 
//For example, we have 1, 3, 5 the gap and max gap is (5 - 1) / 2. Largest - Smallest, two gaps.

Based on this, we only need to compare max number in this bucket and min number in next bucket to get the relatively large gap and find out which two bucket have the largest gap.
class Solution {

    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        int min = nums[0];
        int max = nums[0];
        for (int n : nums) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
        if (min == max) {
            return 0;
        }

        int n = nums.length;

        int gap = (int) Math.ceil((double) (max - min) / (n - 1));
        int bucketMin[] = new int[n];
        int bucketMax[] = new int[n];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

        for (int num : nums) {
            int i = (num - min) / gap;
            bucketMin[i] = Math.min(bucketMin[i], num);
            bucketMax[i] = Math.max(bucketMax[i], num);
        }

        for (int i = 0; i < bucketMin.length; ++i) {
            if (bucketMin[i] != Integer.MAX_VALUE) {
                gap = Math.max(gap, bucketMin[i] - min);
                min = bucketMax[i];
            }
        }

        return gap;
    }
}

2020-05-28

296. Best Meeting Point

Description

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

Input: 

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6 

Explanation: Given three people living at (0,0), (0,4), and (2,2):
             The point (0,2) is an ideal meeting point, as the total travel distance 
             of 2+2+2=6 is minimal. So return 6.

Solution

//mian idea: median point will be the point where min the sum.
class Solution {

    public int minTotalDistance(int[][] grid) {
        int sum_i = 0;
        int sum_j = 0;
        List<Integer> list_i = new ArrayList<>();
        List<Integer> list_j = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    list_i.add(i);
                    list_j.add(j);

                }
            }
        }

        return sum_dist(list_i) + sum_dist(list_j);
    }

    private int sum_dist(List<Integer> list) {
        Collections.sort(list);
        int i = 0;
        int j = list.size() - 1;
        int sum = 0;
        while (i < j) {
            sum += list.get(j--) - list.get(i++);
        }
        return sum;
    }
}

969. Pancake Sorting

Description

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted. 
Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.
 

Note:

1 <= A.length <= 100
A[i] is a permutation of [1, 2, ..., A.length]

Solution

//Find the index i of the next maximum number x.
//Reverse i + 1 numbers, so that the x will be at A[0]
//Reverse x numbers, so that x will be at A[x - 1].
//Repeat this process N times.
class Solution {
    public List<Integer> pancakeSort(int[] A) {
        List<Integer> res = new ArrayList<>();
        for (int x = A.length, i; x > 0; --x) {
            for (i = 0; A[i] != x; ++i);
            reverse(A, i + 1);
            res.add(i + 1);
            reverse(A, x);
            res.add(x);
        }
        return res;
    }

    public void reverse(int[] A, int k) {
        for (int i = 0, j = k - 1; i < j; i++, j--) {
            int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
}

1329. Sort the Matrix Diagonally

Description

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.


Example 1:


Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
 

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution

class Solution {

    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;

        HashMap<Integer, PriorityQueue<Integer>> d = new HashMap<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                d.putIfAbsent(i-j,new PriorityQueue<>());
                d.get(i-j).offer(mat[i][j]);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = d.get(i-j).poll();
            }
        }
        
        return mat;
    }
}

252. Meeting Rooms

Description

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

Example 1:

Input: [[0,30],[5,10],[15,20]]
Output: false
Example 2:

Input: [[7,10],[2,4]]
Output: true
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        if(intervals.length==0){
            return true;
        }
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        int end = intervals[0][1];
        for(int i = 1;i<intervals.length;i++){
            if(intervals[i][0] < end){
                return false;
            }
            end = Math.max(end, intervals[i][1]);
        }
        return true;
    }
}

1122. Relative Sort Array

Description

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don’t appear in arr2 should be placed at the end of arr1 in ascending order.


Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
 

Constraints:

arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
Each arr2[i] is distinct.
Each arr2[i] is in arr1.

Solution

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for (int n : arr1) {
            count[n]++;
        }

        int[] res = new int[arr1.length];
        int idx = 0;

        for (int num : arr2) {
            while (count[num] > 0) {
                res[idx++] = num;
                count[num]--;
            }
        }
    
        for(int i = 0;i<count.length;i++){
            while(count[i]>0){
                res[idx++] = i;
                count[i]--;
            }
            
        }

        return res;
    }
}

1086. High Five

Description

Given a list of scores of different students, return the average score of each student’s top five scores in the order of each student’s id.

Each entry items[i] has items[i][0] the student’s id, and items[i][1] the student’s score. The average score is calculated using integer division.

Example 1:

Input: [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: [[1,87],[2,88]]
Explanation: 
The average of the student with id = 1 is 87.
The average of the student with id = 2 is 88.6. But with integer division their average converts to 88.
 

Note:

1 <= items.length <= 1000
items[i].length == 2
The IDs of the students is between 1 to 1000
The score of the students is between 1 to 100
For each student, there are at least 5 scores

Solution

class Solution {
    public int[][] highFive(int[][] items) {
        HashMap<Integer, PriorityQueue<Integer>> scores = new HashMap<>();
        if(items == null || items.length==0){
            return new int[0][0];
        }

        for(int[] item :items){
            scores.putIfAbsent(item[0],new PriorityQueue<Integer>((a,b)->(b-a)));
            scores.get(item[0]).offer(item[1]);
        }

        int[][] res = new int[scores.size()][2];
        int idx = 0;
        for(Map.Entry<Integer,PriorityQueue<Integer>> e : scores.entrySet()){
            PriorityQueue<Integer> pq = e.getValue();
            int sum = 0;
            int count = 0;
            while(count < 5 && !pq.isEmpty()){
                sum += pq.poll();
                count++;
            }
            res[idx++] = new int[]{e.getKey(),sum/count};

        }
        return res;
    }
}

2020-05-31

922. Sort Array By Parity II

Description

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
 

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

Solution

class Solution {

    public int[] sortArrayByParityII(int[] A) {
        int odd = 1, even = 0;
        int len = A.length;
        while (odd < len && even < len) {
        	//& 0x1 -> find the last value of the bi value
        	//== has higher proority than &, so need to wrap it up.
            while (odd < len && (A[odd] & 0x1) != 0) {
                odd += 2;
            }
            while (even < len && (A[even] & 0x1) == 0) {
                even += 2;
            }

            if (odd < len && even < len) {
                swap(A, odd, even);
            }
        }
        return A;
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

1235. Maximum Profit in Job Scheduling

Description

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:



Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solution

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int[][] items = new int[startTime.length][3];
        for (int i = 0; i < startTime.length; i++) {
            items[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(items, (a, b) -> (a[1] - b[1]));
        List<Integer> dpEndTime = new ArrayList<>();
        List<Integer> dpProfit = new ArrayList<>();

        //base case
        dpEndTime.add(0);
        dpProfit.add(0);

        for (int[] item : items) {
            int s = item[0], e = item[1], p = item[2];

            //find the last previous one that's not overlaped.
            //s+1 so can fit into two case:
            //1. prev.end == cur.start
            //2. prev.end < cur.start
            int prevIdx = Collections.binarySearch(dpEndTime, s + 1);
            if (prevIdx < 0) {
                prevIdx = -prevIdx - 1;
            }
            //the result from binary search is the insertion position.
            //prevIdx-- so can find the previous interval.
            prevIdx--;
            int curProfit = dpProfit.get(prevIdx) + p;
            int maxProfit = dpProfit.get(dpProfit.size()-1);
            
            //only add to dp list when it's ;arger so keep the list ascending.
            //so no need to find previous largest interval but the last one in the list.
            if(curProfit > maxProfit){
                dpProfit.add(curProfit);
                dpEndTime.add(e);
            }
        }
        
        return dpProfit.get(dpProfit.size()-1);
    }
}

461. Hamming Distance

Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Solution

class Solution {
    public int hammingDistance(int x, int y) {
        int XOR = x ^ y;
        int count = 0;
        while(XOR != 0){
            if((XOR & 0x1)!=0){
                count++;
            }
            XOR = XOR>>1;
        }
        return count;
    }
}

169. Majority Element

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

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

Solution

//count the total number of 1 for each position across 0-31(len for binary int)
//if the current position's 1 
class Solution {

    public int majorityElement(int[] nums) {
        int[] count = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                count[i]+=(num >> (31 - i) & 1);
              
            }
        }

        int ret = 0;
        int len = nums.length;
        for (int i = 0; i < 32; i++) {
            ret += (count[i] > len / 2) ? (1 << (31 - i)) : 0;
        }

        return ret;
    }
}
//voting algo
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = nums[0];
        for(int i : nums){
            if(count == 0){
                major = i;
                count+=1;
            }else if(i != major){
                count--;
            }else{
                count++;
            }
        }
        return major;
    }
}

229. Majority Element II

Description

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

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

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

Solution

class Solution {

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int count1 = 0, count2 = 0;
        int num1 = 0, num2 = 1;
        for (int num : nums) {
            if (num1 == num) {
                count1++;
            }else if (num2 == num) {
                count2++;
            }else if (count1 == 0) {
                num1 = num;
                count1 = 1;
            }else if(count2 == 0){
                num2 = num;
                count2 = 1;
            }else{
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        
        for(int num:nums){
            if(num==num1){
                count1++;
            }
            if(num==num2){
                count2++;
            }
        }
        if(count1>nums.length/3){
            res.add(num1);
        }
        if(count2>nums.length/3){
            res.add(num2);
        }
        return res;
    }
}