LeetCode 第 154 场周赛

一、“气球” 的最大数量(LeetCode-5189)

1.1 题目描述

1.2 解题思路

统计各个字母的出现的次数，然后根据“木桶最短板”返回就好。

1.3 解题代码

public class Solution {

    public int maxNumberOfBalloons(String text) {

        int[] arr = new int[5];
        char[] charArray = text.toCharArray();
        for(char ch:charArray){
            if(ch == 'a'){
                arr[0]++;
            }
            if(ch == 'b'){
                arr[1]++;
            }
            if(ch == 'l'){
                arr[2]++;
            }
            if(ch == 'o'){
                arr[3]++;
            }
            if(ch == 'n'){
                arr[4]++;
            }
        }
        int res = -1;
        for(int i = 0;i<5;i++){
            if(i == 2 || i == 3){
                res = arr[i]/2 > res && res != -1 ? res:arr[i]/2;
            }else{
                res = arr[i] > res && res != -1? res:arr[i];
            }
        }
        return res;
    }

}

三、K 次串联后最大子数组之和(LeetCode-5191)

3.1 题目描述

3.2 解题思路

考虑好所有的情况。

• 如果k = 1，则取最大子字符串之和

• 如果数组是{1，1，16，-15，10，1，3},则需要找到leftMax、rightMax，然后加上单个数组全部元素之和 *（k-2）。

• 如果数组是{1,1,16,-15},则需要找到Math.max(leftMax、rightMax),然后加上单个数组全部元素之和 *（k-1）。

• 如果数组是{1，2，3，4}，则结果是单个数组全部元素之和 * k。

3.3 解题代码

public class Solution {

    public static int MOD = (int) (1e9 + 7);

    public int kConcatenationMaxSum(int[] arr, int k) {
        long sum = 0;
        long res = 0;
        int len = arr.length;
        int leftMax = 0;
        int rightMax = 0;
        // 统计固定左端点，从左往右最大和
        for (int i = 0, cur = 0; i < len; i++) {
            cur += arr[i];
            leftMax = Math.max(leftMax, cur);
        }
        // 统计固定右端点，从右往左最大和
        for (int i = len - 1, cur = 0; i >= 0; i--) {
            cur += arr[i];
            rightMax = Math.max(rightMax, cur);
        }
        // 最大的子数组
        for (int i = 0, cur = 0; i < len; i++) {
            cur += arr[i];
            if (cur < 0) {
                cur = 0;
            }
            res = Math.max(res, cur);
        }
        //获取数组之和
        for (int t : arr) {
            sum += t;
        }
        if (k == 1) {
            return (int) res % MOD;
        }

        //1.取所有sum
        res = Math.max(res, sum * k);
        //2.只拼接一边之和
        res = Math.max(res, sum * (k - 1) + Math.max(leftMax, rightMax));
        //3.左右最大子串之和
        res = Math.max(res, sum * (k - 2) + leftMax + rightMax);
        //4.sum < 0
        res = Math.max(res, leftMax + rightMax);
        res = res % MOD;
        return (int) res;

    }
}

LeetCode 第 154 场周赛

原文：https://www.cnblogs.com/fonxian/p/11521592.html