小记

本篇博客记录小黑第三次参加leetcode周赛（294场次）的成绩，以及对题目的总结，以便鞭策自己不断前进 。

这次周赛是我第三次参加，前两题比较简单，做起来也是非常顺利，只用了15分钟就完成解答，但是比较差劲的是，剩下的一个多小时也没有写出来第三题，给出的测试用可以正确输出，但是老是有超时用例。第四题的话也是有暴力解法的思路，但没有完成解答。以下是我这次的成绩：

这一部分主要是对题目进行总结，并且用ACM模式写出解决代码，也是为之后面试做准备。

题目一：字母在字符串中的百分比

思路： 这道题属实是简单。只考察两个Java的基础知识：1，循环；2，保留小数点后俩位。

遍历字符串s，统计字符串中letter的数量，然后用letter的数量除以字符串的长度。这里保留数点后俩位，可以先让被除数扩大100倍。

解决代码：

package leetcode_week_competition;
import java.util.Scanner;
public class week294 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String s2 = s.nextLine();
        char letter  =  s.next().charAt(0);
        int i = percentageLetter(s2, letter);
        System.out.println(i);

    }
    public static int percentageLetter(String s, char letter) {
        int n = s.length();
        int fenzi = 0;
        for (int i = 0; i <n ; i++) {
            if (s.charAt(i)==letter){
                fenzi++;
            }
        }
        int result = fenzi*100/n ;
        return result;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目二：6075. 装满石头的背包的最大数量

思路： 这道题目，我用的是暴力法。解题步骤为：

1，遍历一遍背包，用一个int数组arr保存每个背包还能放的石头数。

2，将arr从小到大排序，并用result表示满了的背包数。

3，遍历arr，如果为0，则说明该背包已经满了，满背包数result+1；

4，遍历arr，如果不为0，则看看背包还能放的石头数是否大于额外要放的石头数，如果大于则直接返回result，；否则满背包数result+1，额外要放的石头数=额外要放的石头数-该背包还能放的石头数。

解决代码：

package leetcode_week_competition;
import java.util.Arrays;
public class week294_2 {
    public static void main(String[] args) {
        int[] capacity = new int[]{10,2,2};
        int[] rock = new int[]{2,2,0};
        int add = 100;
        int i = maximumBags(capacity, rock, add);
        System.out.println(i);
    }
    public static int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int result = 0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = capacity[i]-rocks[i];
        }
        Arrays.sort(arr);
        for (int x:
             arr) {
            if (x==0){
                result++;
            }else {
                if (x>additionalRocks){
                    break;
                }else {
                    result++;
                    additionalRocks=additionalRocks-x;
                }
            }
        }
        return result;
    }
}
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

题目三： 6076. 表示一个折线图的最少线段数

思路： 本题的重点是如何判断A(x1，y1)，B(x2，y2)，C(x3，y3)三点在同一条直线上。见下面的公式
$$\frac{x3-x2}{y3-y2}==\frac{x2-x1}{y2-y1}$$

因为java中除法/会把小数点后数值归0，所以将上式转化为乘法运算。
$$（x3-x2）\ast （y2-y1）=（y3-y2）\ast （x2-x1）$$
1，将数值按day排序。

2，如果数组中只有一个点，那么构不成线段，返回0；如果数组只有两个点，那么只能构成一条线段，返回1。

3，从第三个点开始遍历，判断是否满足上式，不满足则线段数加一。

解决代码：

package leetcode_week_competition;

import java.util.Arrays;

public class week294_3 {
    public static void main(String[] args) {
        int[][]  stockPrices =new int[][]{{83,35},{79,51},{61,48},{54,87}};
        int i = minimumLines(stockPrices);
        System.out.println(i);
    }
    public  int minimumLines(int[][] stockPrices) {
        //用到了Lambda表达式
        Arrays.sort(stockPrices,(o, p)->o[0]-p[0]);
        if(stockPrices.length==1) return 0;
        int result = 1;
        for (int i = 2; i <stockPrices.length ; i++) {
            if ((long)(stockPrices[i][0]-stockPrices[i-1][0])*(stockPrices[i-1][1]-stockPrices[i-2][1])!=
                    (long)(stockPrices[i-1][0]-stockPrices[i-2][0])*(stockPrices[i][1]-stockPrices[i-1][1])){
                result++;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目四：6077. 巫师的总力量和

思路： 本题考查单调栈。解题步骤：将题目转变为对数组中的每个数进行计数，求以它为最小值的巫师的总能量。

1. 首先求以这个数为最小值的数组 左边界、右边界分别可以到什么位置，这里求左边界的时候注意它的左边可能存在和它相同的数，由于左边这个数已经被算过了，所以此时左边界不应该超过这个数。

2. 假设左边界有leftCnt个数，右边界有rightCnt个数，所有区间的总和 = leftCnt*(sum右) - rightCnt*(sum左)， sum左右表示左右边界上区间和。

3. 由于每个数的 左边界、右边界cnt都可能很大，所以必须找到一种办法快速将某个区间的前缀和的总和快速求出来，所以用前缀和的前缀和来快速求出区间的前缀和的总和。

4. 举个列子：a1 a2 a3 a4, 假设a3的时候，左边界可以到a1, 右边界可以到a4, 此时leftCnt = 3, rightCnt = 2
   此时我们计数的是a3, 所以子数组必须包含a3，以a3为结尾的子数组，有3个：

   子数组	a1,a2,a3	a2,a3	a3
   总和	s3 - s0	s3 - s1	s3 - s2

   总和 = 3s3- (s2+s1+s0)
   以a4为结尾的子数组，有3个：

   子数组	a1,a2,a3,a4	a2,a3,a4	a3,a4
   总和	s4 - s0	s4- s1	s4 - s2

   总和 = 3s4 - (s2+s1+s0)
   总计： 3*(s3+s4) - 2*(s2+s1+s0), 其中s表示的是前缀和

本题思路参考Leetcode大神ctysss，详情可见大神Leetcode主页。

解决代码：

package leetcode_week_competition;
import java.util.ArrayDeque;
import java.util.Deque;

public class week_294_4 {
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,1,2};
        int i = totalStrength(arr);
        System.out.println(i);
    }
    public static int totalStrength(int[] s) {
        int len = s.length;
        long[] sum = new long[len];
        // sum2表示前缀和的前缀和
        long[] sum2 = new long[len+1];
        int mod = 1000000007;
        for(int i = 0 ; i < len ; i++){
            sum[i] = (i > 0 ? sum[i-1] : 0) + s[i];
            sum2[i+1] = (sum2[i] + sum[i])%mod;
        }
        // t[i][0]表示左边界， t[i][1]表示右边界
        int[][] t = new int[len][2];
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 0 ; i < len ; i++){
            //求左边界的时候，这里是 ‘>’
            while(!q.isEmpty() && s[q.peek()] > s[i]){
                q.pop();
            }
            t[i][0] = q.isEmpty()?-1:q.peek();
            q.push(i);
        }
        q = new ArrayDeque<>();
        for(int i = len-1 ; i >= 0 ; i--){
            // 求右边界的时候，这里是 ‘>=’
            while(!q.isEmpty() && s[q.peek()] >= s[i]){
                q.pop();
            }
            t[i][1] = q.isEmpty()?len:q.peek();
            q.push(i);
        }
        long ret = 0;
        for(int i = 0 ; i < len ; i++){
            int leftCnt = i - t[i][0];
            int rightCnt = t[i][1] - i;
            long rSum = 1L*leftCnt *(sum2[t[i][1]] - sum2[i] + mod)%mod;
            long lSum = 1L*rightCnt*(sum2[i] - sum2[t[i][0] >= 0 ? t[i][0] : 0] + mod)%mod;
            ret += 1L*s[i]*((rSum - lSum + mod)%mod);
            ret %= mod;
        }
        return (int)ret;
    }
}
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

总结：以上就是LeetCode第294场周赛题目，这次又是只做出了两道题；第三道题思路很简单易懂，也写出了代码，但是由于卡在数值单位上导致浪费太多时间，最终也没能成功AC；而第四道题是有着暴力解法的思路，但是无法完全通过全部案例，看LeetCode大神才知道这题主要是考查单调栈，对单调栈一窍不通的我，一脸懵。还是要继续加油，保二争三（四）。