力扣第 99 场双周赛题解 - 刷题题解

题目链接：https://leetcode.cn/contest/biweekly-contest-99/

# 第一题：排序 + 奇偶分组

	class Solution {
	public int splitNum(int num) {
	int[] d = new int[10];
	int n = 0;

	while (num > 0) {
	++d[num % 10];
	num /= 10;
	}

	// 从小到大排序后，【奇数下标表示的数 + 偶数下标表示的数】就是最小的和
	int odd = 0;
	int even = 0;
	boolean isOdd = false;
	int i = 1;
	while (i < d.length) {
	if (d[i] < 1) {
	++i;
	continue;
	}

	if (isOdd) odd = odd * 10 + i;
	else even = even * 10 + i;
	isOdd = !isOdd;
	--d[i];
	}

	return even + odd;
	}
	}

规律为：
- 1：1
- 2：1 + 3 + 1
- 3：1 + 3 + 5 + 3 + 1
- 4：1 + 3 + 5 + 7 + 5 + 3 + 1
- ......
于是，两个等差数列求和： (1 + 2 * n - 1) * n / 2 * 2 - 2 * n + 1 = n*n + (n - 1) * (n - 1)

	class Solution {
	public long coloredCells(int n) {
	long nn = n;
	return nnnn + (nn - 1) (nn - 1);
	}
	}

	class Solution {
	public int countWays(int[][] ranges) {
	int n = ranges.length;
	final int MOD = (int) (1e9 + 7);
	// 统计无交集区间的组数
	int group = 0;
	int r = Integer.MIN_VALUE;
	// 对于每个独立的区间组，都可以选择放入 a 组或 b 组，故答案就是 2^group
	long res = 1L;

	Arrays.sort(ranges, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);

	for (int i = 0; i < n; ++i) {
	if (ranges[i][0] > r) {
	++group;
	res = (res * 2) % MOD;
	r = ranges[i][1];
	continue;
	}
	r = Math.max(r, ranges[i][1]);
	}

	return (int) res;
	}
	}