LeetCode第154场周赛（Java）

估计要刷很久才能突破三道题了。还是刷的太少。尽管对了前两题，但是我觉得写的不怎么样。还是将所有题目都写一下吧。

5189. “气球” 的最大数量

题目比较简单。就是找出一个字符串中，balloon 中每个字母出现的次数，次数最小的就是结果。注意，l 和 o 要除以 2。

定义一个数组统计每个字母的个数。

int[] count = new int[26];// 统计每个字母的个数

时间复杂度：只有一个循环，故为 O(n)O(n)O(n)。

空间复杂度：只有一个一维数组大小恒为 26，故为 O(1)O(1)O(1)。

代码如下：

class Solution {

    public int maxNumberOfBalloons(String text) {

        char[] arr = text.toCharArray();

        int[] count = new int[26];// 统计每个字母的个数

        for (char ch : arr) {

            ++count[ch - 'a'];// 字母ch个数加1

        }

        int ans = 10001;

        ans = Math.min(ans, count['b' - 'a']);

        ans = Math.min(ans, count['a' - 'a']);

        ans = Math.min(ans, count['l' - 'a'] >> 1);

        ans = Math.min(ans, count['o' - 'a'] >> 1);

        ans = Math.min(ans, count['n' - 'a']);

        return ans;

    }

}

提交结果：

5190. 反转每对括号间的子串

基本思路：找一对括号，将之间的字符串反转，再和括号外边的字符串重新组合成一个字符串赋给 s，如果找不到括号，说明结束，返回 s 即可。上述过程循环。

方法 int[] find(String s) 查找字符串 s 中的括号，返回左括号和右括号下标，如果未找到，则返回的数组的值为 -1。

找到括号，就将字符串分成三段，括号左边，括号之间，括号右边。将之间的反转后，重组成字符串赋给 s。直到未找到括号为止。

时间复杂度： Emmm，还不会算这个的时间复杂度。。。

空间复杂度： 与字符串长度无关，O(1)O(1)O(1)。

代码如下：

class Solution {

	public String reverseParentheses(String s) {

		int[] index = find(s);// 查找括号

		while (index[0] != -1) {// 若有括号，循环反转括号内字符串

			// 左括号左边的内容

			String outLeft = s.substring(0, index[0]);

			// 反转前括号之间的内容

			String inBefore = s.substring(index[0] + 1, index[1]);

			// 反转后括号之间的内容

			StringBuilder sb = new StringBuilder(inBefore);

			String inAfter = sb.reverse().toString();

			// 右括号右边的内容

			String outRight = s.substring(index[1] + 1, s.length());

			// 重组字符串s，由三部分组成

			s = outLeft + inAfter + outRight;

			index = find(s);// 查找括号

		}

		return s;// 返回结果

	}

	// 查找括号

	// 若未找到，数组的值为-1

	// 若找到，index[0]为左括号下标，index[1]为右括号下标

	private int[] find(String s) {

		char[] arr = s.toCharArray();

		int[] index = new int[2];

		index[0] = index[1] = -1;

		for (int i = 0; i < arr.length; ++i) {

			if (arr[i] == '(') {

				index[0] = i;

			} else if (arr[i] == ')') {

				index[1] = i;

				break;// 找到右括号，退出循环

			}

		}

		return index;

	}

}

提交结果：

1191. K 次串联后最大子数组之和

基本思路：k 次修改其实就是 k 个数组 arr 首尾相连，当 k 小于 2 的时候，我们只需要找到数组 arr 的最大子序列就行，当 k 大于等于 2 时，我们将两端的 arr 连起来，中间的是 k - 2 个数组 arr 的和是固定的为 (k - 2) × sumArr，其中 sumArr 表示数组 arr 的和。

因此问题就变成两组 arr 拼接起来的最大子序列问题。

第 1 个循环是计算从第 1 个数到第 i 个数的和。

第 2 个循环是计算从第 1 个数到第 i 个数的和的最大值。

第 3 个循环是计算从最后一个数到从后往前数的第 i 个数的和的最大值。（与第 2 个循环意思一样，只不过是从后往前而已）

第 4 个循环是计算数组 arr 的子序列的和的最大值。

然后取相应的最大值即可。

时间复杂度： 只有一层循环，O(n)O(n)O(n)。

空间复杂度： 一维数组，O(n)O(n)O(n)。

代码如下：

class Solution {

	public int kConcatenationMaxSum(int[] arr,

									int k) {

		int n = arr.length;

		int[] sumpi = new int[n + 1];// 前(pre)i个数的和(sum)

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

			sumpi[i + 1] = sumpi[i] + arr[i];

		}

		int maxsumpi = 0;// 前i个数的和的最大值，全为负数则最大值为0

		for (int i = 1; i <= n; ++i) {

			maxsumpi = Math.max(maxsumpi, sumpi[i]);

		}

		int maxsumri = 0;// 后(n-i)个数的和的最大值，全为负数则最大值为0

		for (int i = n; i >= 0; --i) {

			// sumpi[n]表示前n个数的和，即所有数的和

			maxsumri = Math.max(maxsumri, sumpi[n] - sumpi[i]);

		}

		// 后面j个数的最大值和前面i个数的最大值的和

		int maxsumpr = maxsumpi + maxsumri;

		int maxsubsum = 0;// 最大子序列的和

		int minsumpi = 0;// 前i个数的和的最小值

		for (int i = 1; i <= n; ++i) {

			maxsubsum = Math.max(maxsubsum, sumpi[i] - minsumpi);

			minsumpi = Math.min(minsumpi, sumpi[i]);

		}

		// 10^(5+5+4)=10^14，超过int(10^10)范围，但是未超过long(10^18)范围

		long maxsum = maxsubsum;

		if (k >= 2) {// 重复

			// 则取子序列最大值和拼接序列的最大值中的较大者

			maxsum = Math.max(maxsum, maxsumpr);

		}

		if (k >= 2) {

			// 取两组的最大值和全部的最大值中的较大者

			maxsum = Math.max(maxsum, maxsumpr + (long) (k - 2) * sumpi[n]);

		}

		return (int) (maxsum % 1000000007);// 取模

	}

}

巴特西

LeetCode第154场周赛（Java）

5189. “气球” 的最大数量

代码如下：

提交结果：

5190. 反转每对括号间的子串

代码如下：

提交结果：

1191. K 次串联后最大子数组之和

代码如下：

提交结果：

最新文章

热门文章