Posted Updated LeetCode / Hard / 复习6 minutes read (About 974 words)

2281. Sum of Total Strength of Wizards

Question

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the i<sup>th</sup> wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:

  • The strength of the weakest wizard in the group.
  • The total of all the individual strengths of the wizards in the group.

Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Solution

参考连接

根据题意，我们需要的结果是所有子数列乘以该子数列中最小值之和。

数组strength[]中的每一个元素，都充当一定范围内的子数列的最小值。因此我们需要**确定每个元素充当最小值的范围(left, right)**。然后计算这个元素可以组成的子数列的和与这个元素的乘积。

我们的问题相当于确定下一个更小元素，而单调栈专门处理这一类问题——“下一个更大/更小元素”
496. Next Greater Element I

通过单调栈，我们可以确定最小值为strength[i]的子数列的范围(left, right)，并将其保存在两个数组left[]与right[]中。

最后通过前缀和的计算，来确定(left, right)范围内的子数列之和。

单调栈

新建两个数组left[]， right[]保存以strength[i]为最小值的范围。

维护两个单调栈，保证下列关系：
strength[left] < strength[i]
strength[right] <= strength[i]

其中，left取小于号，而right可以等于是为了取值不重复。

注意，单调栈保存的是下标，这样使用起来更加灵活。

前缀和

为了得到范围（left, right）内的所有子数列之和。我们可以观察left, i, right之间的关系。

…left-1, left, left + 1, left + 2, … i-1, i, i+1, … right-1, right, right+1…

  • 开始于 left+1的子数列:
    sum(left+1, … i) = prefix[i + 1] - prefix[left + 1]
    sum(left+1, … i+1) = prefix[i + 2] - prefix[left + 1]
    …
    sum(left+1, … right-1) = prefix[right] - prefix[left + 1]
  • 开始于left+2的子数列:
    sum(left+2, … i) = prefix[i + 1] - prefix[left + 2]
    sum(left+2, … i+1) = prefix[i + 2] - prefix[left + 2]
    …
    sum(left+2, … right-1) = prefix[right] - prefix[left + 2]
    …
  • 开始于i的子数列:
    sum(i, … i) = prefix[i + 1] - prefix[i]
    sum(i, … i+1) = prefix[i + 2] - prefix[i]
    …
    sum(i, … right-1) = prefix[right] - prefix[i]

合并这些式子，我们可以得到：

  • 正数 部分:
    (prefix[i + 1] + prefix[i + 2] + ... + prefix[right]) * (i - left)
  • 负数 部分:
    (prefix[left + 1] + prefix[left + 2] + ... + prefix[i]) * (right - i)

最后我们可以提前计算前缀和的前缀和来优化计算步骤，注意计算时需要将各个部分模除以保证不超过范围。
正数部分模除后需要加上MOD以保证其减去负数部分的结果大于0。

Code

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
class Solution {
    public int totalStrength(int[] strength) {
        long MOD = 1_000_000_007;
        int n = strength.length;
        
        Deque<Integer> mono = new ArrayDeque<>();
        int[] left = new int[n], right = new int[n];
        
        for(int i = 0; i < strength.length; i++){   //单调栈，记录比当前元素strength[i]小的第一个左侧位置strength[left]
            while(!mono.isEmpty() && strength[mono.peek()] >= strength[i]){
                mono.pop();
            }
            left[i] = mono.isEmpty() ? -1 : mono.peek();
            mono.push(i);
        }
        mono.clear();
        for(int i = n-1; i >=0; i--){   //单调栈，记录比当前元素strength[i]小的第一个右侧位置strength[right]
            while(!mono.isEmpty() && strength[mono.peek()] > strength[i]){
                mono.pop();
            }
            right[i] = mono.isEmpty() ? n : mono.peek();
            mono.push(i);
        }
        
        long[] prefix = new long[n+1], prefix_sum = new long[n+2];
        
        for(int i = 1; i <= strength.length; i++){  //计算前缀和
            prefix[i] = (prefix[i-1] + strength[i-1]) % MOD;
        }
        
        for(int i = 2; i <= strength.length+1; i++){    //计算前缀和的前缀和
            prefix_sum[i] = (prefix_sum[i-1] + prefix[i-1]) % MOD;
        }
        
        long res = 0;
        
        for(int i = 0; i < n; i++){
            res += ((prefix_sum[right[i] + 1] - prefix_sum[i + 1]) * (i - left[i]) % MOD + MOD -    //这里加MOD是为了保证前项大于后项，防止出现负数
                    (prefix_sum[i + 1] - prefix_sum[left[i] + 1]) * (right[i] - i) % MOD ) * strength[i];
            res %= MOD;
        }
        
        return (int) res;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 271 words)

2280. Minimum Lines to Represent a Line Chart

Question

You are given a 2D integer array stockPrices where stockPrices[i] = [day<sub>i</sub>, price<sub>i</sub>] indicates the price of the stock on day day<sub>i</sub> is price<sub>i</sub>. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Solution

如果只有一个点，无法组成线段则返回0。否则至少可以组成1条线段。

首先将所有点根据x的位置排序，然后一次比较连续的各个向量的方向。
为了防止除法精度问题，计算两个向量（三个点组成两个向量）的叉乘，如果叉乘为0，则说明两个向量是平行的，此时不需要增加计数。
如果叉乘结果不等于0，则将计数+1。

最后返回计数的结果。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minimumLines(int[][] stockPrices) {
        if(stockPrices.length == 1) return 0;
        
        Arrays.sort(stockPrices, (a,b) -> a[0] - b[0]);
        int count = 1, lastX = 0, lastY = 0;
        
        for(int i = 1; i < stockPrices.length; i++){
            int x = stockPrices[i][0] - stockPrices[i-1][0];
            int y = stockPrices[i][1] - stockPrices[i-1][1];
            
            int k = lastX * y - lastY * x;
            if(k != 0) count++;
            lastX = x;
            lastY = y;
        }
        return count;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 226 words)

2279. Maximum Bags With Full Capacity of Rocks

Question

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The i<sup>th</sup> bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.

Return* the maximum number of bags that could have full capacity after placing the additional rocks in some bags.*

Solution

计算每个背包的剩余空间，然后进行排序。
按从小到大的顺序依次减少石头的总数。
设置i作为选取石头的计数。每次循环将i增加，直到剩余的石头数量小于0。
如果最后剩下的石头仍然大于等于0，则返回计数。
否则返回计数-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[] diff = new int[capacity.length];
        for(int i = 0 ; i < capacity.length; i++){
            diff[i] = capacity[i] - rocks[i];
        }
        
        Arrays.sort(diff);
        int i = 0;
        while(additionalRocks > 0 && i < diff.length){
            additionalRocks -= diff[i];
            i++;
        }
        return additionalRocks >= 0 ? i : i - 1;
    }
}
Posted Updated LeetCode / Easya few seconds read (About 90 words)

2278. Percentage of Letter in String

Question

Given a string s and a character letter, return* the percentage of characters in s that equal letter rounded down to the nearest whole percent.*

Solution

一次遍历，计算字符出现的次数。
返回字符出现的次数除以字符长度乘以100。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int percentageLetter(String s, char letter) {
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == letter){
                count++;
            }
        }
        return count * 100 / s.length();
    }
}
647. Palindromic Substrings
Posted Updated LeetCode / Medium3 minutes read (About 404 words)

647. Palindromic Substrings

Question

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Solution

Manacher算法，与5. Longest Palindromic Substring的实现方法相同。

首先处理字符串。
然后采用中心拓展计算各个位置的拓展长度，并维护c与r。
每次遍历时计算结果，将当前可扩展长度加一然后除以二后加入结果。

Code

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
class Solution {
    int n;
    int[] p;
    String newString;
    public int countSubstrings(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        
        return manacher();
    }
    
    private int manacher(){
        int res = 0, c = 0, r = 0;
        for(int i = 1; i < newString.length()-1; i++){
            int m = 2 * c - i;
            if(i < r) p[i] = Math.min(r-i, p[m]);
            
            while(newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)){    //中心拓展
                p[i]++;
            }
            
            if(i+p[i] > r){ //更新c与r
                c = i;
                r = i + p[i];
            }
            res += (p[i]+1)/2;  //向上取整
        }
        return res;
    }
}

Solution 2

中心拓展，辅助方法count()用来计算每个字符可以组成的最大回文数。

注意每次需要计算奇数长度回文和偶数长度回文两种情况。
遍历所有字符并加和，返回总数。

Code

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
class Solution {
    String word;
    public int countSubstrings(String s) {
        word = s;
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            ret+=count(i);
        }
        return ret;
    }
    
    private int count(int i){
        int count = 1, left = i-1, right = i+1;

        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        
        left = i;
        right = i+1;
        
        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        return count;
    }
}
Follow

Recents

Archives

Links

×