Sunday, February 21, 2021

Lintcode 676. Decode Ways II

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, now the encoded string can also contain the character *, which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character *, return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 10^9 + 7.

Example

Example 1

Input: "*"
Output: 9
Explanation: You can change it to "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 2

Input: "1*"
Output: 18

Notice

  1. The length of the input string will fit in range [1, 10^5].
  2. The input string will only contain the character * and digits 0 - 9.
Code (Java):


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Solution {
    /**
     * @param s: a message being encoded
     * @return: an integer
     */
    public int numDecodings(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }
         
        if (s.charAt(0) == '0') {
            return 0;
        }
         
        long MOD = (long)1e9 + 7;
         
        int n = s.length();
         
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '*' ? 9 : 1;
         
        for (int i = 2; i <= n; i++) {
            char c = s.charAt(i - 1);
             
            // regular case
            if (c != '*') {
                if (c != '0') {
                    dp[i] = dp[i - 1];
                }
                 
                int numCombinations = getNumberOfValidNumbers(s.charAt(i - 2), s.charAt(i - 1));
                dp[i] += dp[i - 2] * numCombinations % MOD;
            } else {
                dp[i] = dp[i - 1] * 9 % MOD; // * match 1-9
                int numCombinations = getNumberOfValidNumbers(s.charAt(i - 2), s.charAt(i - 1));
                dp[i] += dp[i - 2] * numCombinations % MOD;
                 
            }
        }
         
        return (int)(dp[n] % MOD);
    }
     
    private int getNumberOfValidNumbers(char a, char b) {
        // 4 cases:
        // * *
        // * num
        // num *
        // num num
         
        int ans = 0;
         
        if (a == '*' && b == '*') {
            ans = 15; // 11 -> 26, not 10, 20
        } else if (a == '*') {
            int nb = Character.getNumericValue(b);
            if (nb >= 0 && nb <= 6) {
                ans = 2; // 1* and 21->26
            } else {
                ans = 1; // 1*
            }
        } else if (b == '*') {
            int na = Character.getNumericValue(a);
            if (na == 1) {
                ans = 9; // 11-19
            } else if (na == 2) {
                ans = 6; // 21-26
            } else {
                ans = 0;
            }
        } else {
            int na = Character.getNumericValue(a);
            int nb = Character.getNumericValue(b);
            int num = na * 10 + nb;
             
            if (na == 0) {
                ans = 0;
            } else if (num >= 1 && num <= 26) {
                ans = 1;
            }
        }
         
        return ans;
    }
}
Posted by at 2 comments:

Tuesday, February 16, 2021

Lintcode 1208. Target Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Example 2:

Input: nums is [], S is 3. 
Output: 0
Explanation: 
There are 0 way to assign symbols to make the sum of nums be target 3.

Notice

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.


Solution:
Backpacking DP problem.

Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
    /**
     * @param nums: the given array
     * @param s: the given target
     * @return: the number of ways to assign symbols to make sum of integers equal to target S
     */
    public int findTargetSumWays(int[] nums, int s) {
        // Write your code here
         
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
         
        if (s > Math.abs(sum)) {
            return 0;
        }
         
        int[][] dp = new int[nums.length + 1][2 * sum + 1];
        dp[0][sum] = 1; // index = num + sum;
         
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < 2 * sum + 1; j++) {
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                }
                 
                if (j + nums[i - 1] < 2 * sum + 1) {
                    dp[i][j] += dp[i - 1][j + nums[i - 1]];
                }
            }
        }
         
        return dp[nums.length][s + sum];
    }
}
Posted by at 1 comment:
Labels:

Saturday, February 6, 2021

Leetcode Minimum Cost Tree From Leaf Values

Given an array arr of positive integers, consider all binary trees such that:

  • Each node has either 0 or 2 children;
  • The values of arr correspond to the values of each leaf in an in-order traversal of the tree.  (Recall that a node is a leaf if and only if it has 0 children.)
  • The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node.  It is guaranteed this sum fits into a 32-bit integer.

 

Example 1:

Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

 

Constraints:

  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
  • It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).


Solution: 
Use a descreasing monotonic stack. 
https://www.youtube.com/watch?v=xcYkzSrgOmY

Code (Java):


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int mctFromLeafValues(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
         
        Stack<Integer> stack = new Stack<>();
         
        int ans = 0;
        for (int num : arr) {
            while (!stack.isEmpty() && num > stack.peek()) {
                int drop = stack.pop();
                int left = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
                 
                ans += drop * Math.min(num, left);
            }
             
            stack.push(num);
        }
         
        while (stack.size() > 1) {
            ans += stack.pop() * stack.peek();
        }
         
        return ans;
    }
}
Posted by at No comments:

Thursday, February 4, 2021

Leetcode 739. Daily Temperatures

Given a list of daily temperatures, produce a list 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 temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Example

Example 1:
	Input:  temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
	Output:  [1, 1, 4, 2, 1, 1, 0, 0]
	
	Explanation:
	Just find the first day after it which has higher temperatures than it.

	
Example 2:
	Input: temperatures = [50, 40, 39, 30]
	Output:  [0,0,0,0]

Notice

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

Code (Java):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] dailyTemperatures(int[] T) {
        if (T == null || T.length == 0) {
            return new int[0];
        }
         
        int[] ans = new int[T.length];
         
        // monotonic descreasing stack
        Stack<Integer> stack = new Stack<>();
         
        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                stack.pop();
            }
             
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
             
            stack.push(i);
        }
         
        return ans;
    }
}
Posted by at No comments:

Lintcode 1491. Score of Parentheses

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

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Notice

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

Code (Java):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    /**
     * @param S: a string
     * @return: the score of the string
     */
    public int scoreOfParentheses(String S) {
        // Write your code here
        if (S == null || S.length() == 0) {
            return 0;
        }
         
        // stores the index of the left parathesis
        Stack<Integer> paraStack = new Stack<>();
         
        // store the pair of (res, left boundary), res is the current
        // result, left boundary is the left starting index of the result
        Stack<int[]> numStack = new Stack<>();
         
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
             
            if (c == '(') {
                paraStack.push(i);
            } else {
                int leftIdx = paraStack.pop();
                 
                // case 1: it's only ()
                if (i - leftIdx == 1) {
                    numStack.push(new int[]{1, leftIdx});
                } else {
                    // case 2: (())
                    int curAns = 0;
                    while (!numStack.isEmpty() && numStack.peek()[1] > leftIdx) {
                        curAns += numStack.pop()[0];
                    }
                     
                    curAns *= 2;
                     
                    numStack.push(new int[]{curAns, leftIdx});
                }
            }
        }
         
        int ans = 0;
        while (!numStack.isEmpty()) {
            ans += numStack.pop()[0];
        }
         
        return ans;
    }
}
Posted by at No comments:

Lintcode 1201. Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

Input: [1]
Output: [-1]
Explanation: 
The number 1 can't find next greater number.

Notice

The length of given array won't exceed 10000.


Solution:
monotonic descreasing stack. 

Code (Java):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    /**
     * @param nums: an array
     * @return: the Next Greater Number for every element
     */
    public int[] nextGreaterElements(int[] nums) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
         
        int[] ans = new int[nums.length];
         
        // init to -1
        for (int i = 0; i < nums.length; i++) {
            ans[i] = -1;
        }
         
        // stack is mono descreasing stack, and it stores the index
        Stack<Integer> stack = new Stack<>();
         
        for (int i = 0; i < nums.length * 2; i++) {
            int ii = i % nums.length;
            while (!stack.isEmpty() && nums[ii] > nums[stack.peek()]) {
                ans[stack.pop()] = nums[ii];
            }
             
            stack.push(ii);
        }
         
        return ans;
         
    }
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[nums.length];
         
        Stack<Integer> stack = new Stack<>();
         
        for (int i = nums.length * 2 - 1; i>= 0; i--) {
            int ii = i % nums.length;
             
            while (!stack.isEmpty() && nums[ii] >= nums[stack.peek()]) {
                stack.pop();
            }
             
            ans[ii] = stack.isEmpty() ? -1 : nums[stack.peek()];
             
            stack.push(ii);
        }
         
        return ans;
    }
}
Posted by at No comments:

Leetcode 496. Next Greater Element I

You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.

Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.

 

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

 

Constraints:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

 

Follow up: Could you find an O(nums1.length + nums2.length) solution? 

Code (Java)


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
         
        int[] ans = new int[nums1.length];
         
        Stack<Integer> monoDescStack = new Stack<>();
        // key is the elements in nums2, value is the next greater element
        Map<Integer, Integer> map = new HashMap<>();
         
        for (int num : nums2) {
            while (!monoDescStack.isEmpty() && num > monoDescStack.peek()) {
                int top = monoDescStack.pop();
                map.put(top, num);
            }
             
            monoDescStack.push(num);
        }
         
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                ans[i] = map.get(nums1[i]);
            } else {
                ans[i] = -1;
            }
        }
         
        return ans;
    }
}
Posted by at No comments:

Wednesday, February 3, 2021

Lintcode 1740. Online Stock Span

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example

Example 1:

Input: prices = [100,80,60,70,60,75,85]
Output: [1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

Example 2:

Input: prices = [50,80,80,70,90,75,85]
Output: [1,2,3,1,5,1,2]
Explanation: ：
First, S = StockSpanner() is initialized.  Then:
S.next(50) is called and returns 1,
S.next(80) is called and returns 3
S.next(70) is called and returns 1
S.next(90) is called and returns 5
S.next(75) is called and returns 1
S.next(85) is called and returns 2

Notice

  • Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
  • There will be at most 10000 calls to StockSpanner.next per test case.
  • There will be at most 150000 calls to StockSpanner.next across all test cases.
  • The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

 



Solution:
Monotone stack

Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class StockSpanner {
    Stack<int[]> stack;
    public StockSpanner() {
        stack = new Stack<>();
    }
    /**
     * @param price:
     * @return: int
     */
    public int next(int price) {
        // Write your code here.
        int ans = 1;
         
        while (!stack.isEmpty() && price >= stack.peek()[0]) {
            ans += stack.pop()[1];
        }
         
        stack.push(new int[]{price, ans});
         
        return ans;
    }
}
Posted by at No comments:

Lintcode 1817. Divide Chocolate

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your K friends so you start cutting the chocolate bar into K+1 pieces using K cuts, each piece consists of some consecutive chunks.

Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Example

Example 1:

Input: sweetness = [1,2,3,4,5,6,7,8,9], K = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]

Example 2:

Input: sweetness = [5,6,7,8,9,1,2,3,4], K = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.

Example 3:

Input: sweetness = [1,2,2,1,2,2,1,2,2], K = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

Notice

  • 0 <= K < sweetness.length <= 10^4
  • 1 <= sweetness[i] <= 10^5

 

Solution:
Binary search on answer. 
The idea is if we give a larger sweetness to each person, they tend to have more pieces each one, so the number of people we can distribute tend to be less. The same to the other. If a person gets less sweetness, we can distribute to more people.

So the idea is, given a sweetness level, we can find out the number of people we can distribute to. If it's less than the K + 1, that means the sweentess we choose was too high; otherwise, if the number of people is greater or equal to the K + 1, we can try a bigger sweetness.

Code (Java):


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
    /**
     * @param sweetness: an integer array
     * @param K: an integer
     * @return:  return the maximum total sweetness of the piece
     */
    public int maximizeSweetness(int[] sweetness, int K) {
        // write your code here
        if (sweetness == null || sweetness.length == 0) {
            return 0;
        }
         
        int lo = 0;
        int hi = 0;
         
        for (int s : sweetness) {
            lo = Math.min(lo, s);
            hi += s;
        }
         
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
             
            if (getNumFriends(sweetness, mid) >= K + 1) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
         
        if (getNumFriends(sweetness, hi) >= K + 1) {
            return hi;
        }
         
        return lo;
    }
     
    private int getNumFriends(int[] sweetness, int s) {
        int count = 0;
        int curr = 0;
         
        for (int sweet : sweetness) {
            curr += sweet;
            if (curr >= s) {
                count++;
                curr = 0;
            }
        }
         
        return count;
    }
}
Posted by at No comments:
Labels:

Tuesday, February 2, 2021

Lintcode 285. Tall Building

At the weekend, Xiao Q and his friends came to the big city for shopping. There are many tall buildings.There are n tall buildings in a row, whose height is indicated by arr.
Xiao Q has walked from the first building to the last one. Xiao Q has never seen so many buildings, so he wants to know how many buildings can he see at the location of each building? (When the height of the front building is greater than or equal to the back building, the back building will be blocked)

Example

Example 1:

Input:[5,3,8,3,2,5]
Output:[3,3,5,4,4,4]
Explanation:
When Xiao Q is at position 0, he can see 3 tall buildings at positions 0, 1, and 2.
When Xiao Q is at position 1, he can see  3 tall buildings at positions 0, 1, and 2.
When Xiao Q is at position 2, he can see the building at position 0, 1 forward, and the building at position 3, 5 backward, plus the third building, a total of 5 buildings can be seen.
When Xiao Q is at position 3, he can see 4 tall buildings in positions 2, 3, 4, and 5.
When Xiao Q is at position 4, he can see 4 tall buildings in positions 2, 3, 4, and 5.
When Xiao Q is at position 5, he can see 4 tall buildings in positions 2, 3, 4, and 5.

Notice

1 \leq n \leq 100000
1 \leq arr[i] \leq 100000

1≤arr[i]≤100000 



Solution:
Mono stack. Stack elements are monotonously decreasing. For each arr[i], the max number of buildings to its left is the number of elements in the stack. The same to the right. 

Code (Java):


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    /**
     * @param arr: the height of all buildings
     * @return: how many buildings can he see at the location of each building
     */
    public int[] tallBuilding(int[] arr) {
        // Write your code here.
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
         
        int[] ans = new int[arr.length];
         
        // mono descreasing stack
        Stack<Integer> stack = new Stack<>();
         
        // left to right
        for (int i = 0; i < arr.length; i++) {
            ans[i] = stack.size();
             
            while (!stack.isEmpty() && arr[i] >= stack.peek()) {
                stack.pop();
            }
             
            stack.push(arr[i]);
        }
         
        // right to left
        stack.clear();
         
        for (int i = arr.length - 1; i >= 0; i--) {
            ans[i] += stack.size() + 1; // +1 count itself
             
            while (!stack.isEmpty() && arr[i] >= stack.peek()) {
                stack.pop();
            }
             
            stack.push(arr[i]);
        }
         
        return ans;
    }
}
Posted by at No comments:

Friday, January 29, 2021

Lintcode 1379. The Longest Scene

A string, each character representing a scene. Between two identical characters is considered to be a continuous scene. For example: abcda, you can think of these five characters as the same scene. Or acafghbeb can think of two aca and beb scenes. If there is a coincidence between the scenes, then the scenes are combined. For example, abcab, where abca and bcab are coincident, then the five characters are considered to be the same scene. Give a string to find the longest scene.

Example

Example 1

Input: "abcda"
Output: 5
Explanation:
The longest scene is "abcda".

Example 2

Input: "abcab"
Output: 5
Explanation:
The longest scene is "abcab".

Notice

  • 1 <= |str| <=1e5
  • str contains only lowercase letters
Solution:
First of all, for each character, we note down the position of the rightmost same character it can reach. E.g. abcdad. For character a, the position of the rightmost is 4. 

After that, we can form a list of intervals with start and end position of each character. Then the problem is to merge the intervals. 

Code (Java):

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class Solution {
    /**
     * @param str: The scene string
     * @return: Return the length longest scene
     */
    public int getLongestScene(String str) {
        // Write your code here
        if (str == null || str.length() == 0) {
            return 0;
        }
         
        if (str.length() == 1) {
            return 1;
        }
         
        // pos saves the rightmost position of each character
        int[] pos = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            pos[c - 'a'] = i;
        }
         
        // store the intervals into the list. Note that it's already sorted by the start time
        List<Interval> intervals = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (pos[c - 'a'] != i) {
                intervals.add(new Interval(i, pos[c - 'a']));
            }
        }
         
        // now it's time to merge and get the longest interval
        Interval prev = null;
        int ans = 1;
         
        for (int i = 0; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev == null || prev.end < curr.start) {
                prev = curr;
            } else { // overlap
                prev.start = Math.min(prev.start, curr.start);
                prev.end = Math.max(prev.end, curr.end);
            }
             
            if (prev.end - prev.start + 1 > ans) {
                ans = prev.end - prev.start + 1;
            }
        }
         
        if (prev != null) {
            ans = Math.max(ans, prev.end - prev.start + 1);
        }
         
        return ans;
         
    }
}
 
class Interval {
    int start;
    int end;
     
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
Posted by at No comments:
Labels:

Lintcode 1397. Digital Coverage

Description

Given some intervals, ask how many are covered most, if there are multiple, output the smallest number.

  • the number of the interval is not more than 10^5.
  • the left and right endpoints of the interval are greater than 0 not more than 10^5.

Example

Example 1:

 Input:intervals = [(1,7),(2,8)]
 Output:2
Explanation:2 is covered 2 times, and is the number of 2 times the smallest number.

Example 2:

Input:intervals = [(1,3),(2,3),(3,4)]
Output:3 

Explanation:3 is covered 3 times. 



Solution 1:
Split the interval into events and sort by start time. Time complexity O(nlogn)

Code (Java):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
         
        List<Event> events = new ArrayList<>();
        for (Interval interval : intervals) {
            events.add(new Event(interval.start, 0));
            events.add(new Event(interval.end, 1));
        }
         
        Collections.sort(events, new MyEventComparator());
         
        int count = 0;
        int ans = 0;
        int maxCount = 0;
         
        for (Event event : events) {
            if (event.flag == 0) {
                count++;
            } else {
                count--;
            }
             
            if (count > maxCount) {
                maxCount = count;
                ans = event.time;
            }
        }
         
        return ans;
    }
}
 
class Event {
    int time;
    int flag; // 0 start, 1 end
     
    public Event(int time, int flag) {
        this.time = time;
        this.flag = flag;
    }
}
 
class MyEventComparator implements Comparator<Event> {
    @Override
    public int compare(Event a, Event b) {
        if (a.time != b.time) {
            return a.time - b.time;
        }
         
        return a.flag - b.flag;
    }
}
Solution 2: prefix sum
Allocate an array with size of data range (10^5 for this problem). for each interval, if it's start, count + 1, otherwise count - 1. In the end, we sum up the counts and get the max number.

Time complexity is O(data range)

Code (Java):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
         
        int[] counts = new int[1000001];
         
        for (Interval interval : intervals) {
            counts[interval.start] += 1;
            counts[interval.end + 1] -= 1;
        }
         
        int maxCount = 0;
        int count = 0;
        int ans = -1;
         
        for (int i = 0; i < counts.length; i++) {
            count += counts[i];
            if (count > maxCount) {
                maxCount = count;
                ans = i;
            }
        }
         
        return ans;
    }
}
Posted by at No comments:
Subscribe to: Posts (Atom)