力扣第 334 场周赛题解 - 刷题题解

# T1. 后缀和，模拟

	class Solution {
	public int[] leftRigthDifference(int[] nums) {
	int n = nums.length;
	int[] rightSum = new int[n];
	int leftSum = 0;
	int[] ret = new int[n];

	for (int i = n - 2; i >= 0; --i) {
	rightSum[i] = rightSum[i + 1] + nums[i+1];
	}

	for (int i = 0; i < n; ++i) {
	ret[i] = Math.abs(leftSum - rightSum[i]);
	leftSum += nums[i];
	}

	return ret;
	}
	}

题目链接：https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/
解题思路
如果一个数 num 能被 m 整除，其除个位外的整数为 high = num / 10 ，个位为 low = num % 10 ；那么就会满足：
- 如果 high 能被 m 整除，则 low 也要能被 m 整除
- 如果 high 不能被 m 整除，则 high % m * 10 + low 要能被 m 整除
  综上： high % m * 10 + low 要能被 m 整除，需要注意的 int 溢出问题
代码

	class Solution {
	public int[] divisibilityArray(String word, int m) {
	char[] chs = word.toCharArray();
	int n = chs.length;
	int[] ret = new int[n];
	long mod = 0;

	for (int i = 0; i < n; ++i) {
	mod = (mod * 10 + chs[i] - '0') % m;
	ret[i] = mod == 0 ? 1 : 0;
	}

	return ret;
	}
	}

题目链接：https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/
解题思路
因为最多标记 nums.length / 2 对数；因此可以将数组进行排序，排完序后，则可以在左右半边各选一个数，如此可以找到尽可能多的数对。所以就是让左半边大的数与右半边大的数组队。
代码

	class Solution {
	public int maxNumOfMarkedIndices(int[] nums) {
	int n = nums.length;

	if (n < 2) return 0;

	Arrays.sort(nums);

	int ans = 0;
	int mid = n / 2;
	int l = mid - 1;
	int r = n - 1;

	while (l >= 0 && r >= mid) {
	if (2 * nums[l] <= nums[r]) {
	--l;
	--r;
	ans += 2;
	} else {
	// 不匹配时，l 减少
	// 如此才不会影响它左侧的数找 “伙伴”
	--l;
	}
	}

	return ans;
	}
	}

已有0条评论