LeetCode刷题笔记 5月(下)

Posted on By Guanzhou Song

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-05-26

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;
    }
}