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;

    }

}

二、反转每对括号间的子串(LeetCode-1190)

2.1 题目描述

2.2 解题思路

使用递归去解，每次只反转最里层括号的字符串，每次递归返回时将字符串外的括号去掉，终止条件为，字符串不存在括号。

2.3 解题代码



public class Solution {

    public String reverseParentheses(String s) {

        int len = s.length();

        int left = -1;

        int right = len + 1;

        //获取最靠右的左括号

        for (int i = 0; i < len; i++) {

            if (s.charAt(i) == '(') {

                left = Math.max(i, left);

            }

        }

        //获取最靠左的右括号

        for (int i = 0; i < len; i++) {

            //注意边界，right应该大于left

            if (s.charAt(i) == ')' && i>left) {

                right = Math.min(i, right);

            }

        }

       // 如果不存在括号，则返回字符串终止

        if (left == -1 && right == len + 1) {

            return s;

        }

        //对括号内的字符串进行反转

        String tmp = new StringBuilder(s.substring(left + 1, right)).reverse().toString();

        //去除括号，进行拼接

        tmp = s.substring(0,left) + tmp + s.substring(right+1,len);

        //进行递归

        return reverseParentheses(tmp);

    }

}

三、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 场周赛

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

1.1 题目描述

1.2 解题思路

1.3 解题代码

二、反转每对括号间的子串(LeetCode-1190)

2.1 题目描述

2.2 解题思路

2.3 解题代码

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

3.1 题目描述

3.2 解题思路

3.3 解题代码

最新文章

热门文章