一、“气球” 的最大数量(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; }
}