欢迎大家加QQ群：623375442。今天还是两道hard，最后一题也不难，连续写错，麻了。
100670. Minimum Deletions for At Most K Distinct Characters
给你一个字符串 s（由小写英文字母组成）和一个整数 k。
你的任务是删除字符串中的一些字符（可以不删除任何字符），使得结果字符串中的 不同字符数量 最多为 k。
返回为达到上述目标所需删除的 最小 字符数量。
测试样例：
输入：s = "abc", k = 2
输出：1
解释：s 有三个不同的字符：'a'、'b' 和 'c'，每个字符的出现频率为 1。由于最多只能有 k = 2 个不同字符，需要删除某一个字符的所有出现。例如，删除所有 'c' 后，结果字符串中的不同字符数最多为 k。因此，答案是 1。
解答：
- 首先统计字符串中每个字符的出现次数，存入一个大小为 26 的数组 count，对应字符 a 到 z。
- 对 count 数组进行排序，从大到小的顺序。排序的目的是让频次较高的字符优先保留，这样删除字符时可以尽量减少删除的字符数量。
- 遍历排序后的数组，如果当前字符数量超过了 k，则需要删除一些字符。我们通过逐个减少频次，直到字符串中不同字符的数量为 k 为止，记录删除的字符数量。
- 最后返回删除的字符数量。
class Solution {
public int minDeletion(String s, int k) {
int[] count = new int[26]; // 用于记录每个字符的出现次数
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - 'a'] += 1; // 统计每个字符的出现频次
}
Arrays.sort(count); // 对频次数组排序，优先考虑高频字符
int res = 0; // 删除的字符数量
for (int i = 0, j = 26; i < 26 && j > k; ++i, --j) {
res += count[i]; // 如果不同字符数超出了k，删除低频字符
}
return res; // 返回最少删除的字符数量
}
}100647. Maximum Sum of Edge Values in a Graph
给你一个包含 n 个节点的 无向图，节点按从 0 到 n - 1 编号。每个节点 最多 与其他两个节点相连。
图中包含 m 条边，使用一个二维数组 edges 表示，其中 edges[i] = [ai, bi] 表示节点 ai 和节点 bi 之间有一条边。
你需要为每个节点分配一个从 1 到 n 的 唯一 值。边的值定义为其两端节点值的 乘积 。
你的得分是图中所有边值的总和。
返回你可以获得的 最大 得分。
测试样例：
输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6]]
输出：130
解释: 上图展示了一个最优的节点值分配方式。边值的总和为：(7 6) + (7 5) + (6 5) + (1 3) + (3 4) + (4 2) = 130。
由于 0 < 1 < 2 < 3，该网格满足给定的约束条件。
解答：
- 题目要求最大化边值的总和，我们需要分配节点的值以使得边值最大。
- 对于每一条边，其值为连接的两个节点值的乘积。为了让总和最大，应该尽量让连接的节点的值较大。
- 我们可以将节点按照其度数（与其他节点连接的数量）进行分配，度数较高的节点分配较大的值，度数较低的节点分配较小的值。
- 通过深度优先搜索（DFS）找到无环的节点集和有环的节点集，并分别计算它们的最大得分。
class Solution {
public long maxScore(int n, int[][] edges) {
List<Integer>[] graph = new List[n]; // 用于存储图的邻接表
for (int i = 0; i < n; ++i) {
graph[i] = new ArrayList<>();
}
for (int[] e : edges) {
graph[e[0]].add(e[1]); // 双向图
graph[e[1]].add(e[0]);
}
List<Integer> cycle = new ArrayList<>(), noCycle = new ArrayList<>();
boolean[] isVisit = new boolean[n];
for (int i = 0; i < n; ++i) {
if (graph[i].size() == 1 && !isVisit[i]) {
noCycle.add(dfs(i, -1, graph, isVisit)); // 非环节点处理
}
}
for (int i = 0; i < n; ++i) {
if (graph[i].size() == 2 && !isVisit[i]) {
cycle.add(dfs(i, -1, graph, isVisit)); // 环节点处理
}
}
Collections.sort(cycle); // 对环节点进行排序
Collections.sort(noCycle, (a, b) -> (b.compareTo(a))); // 对非环节点排序
int[] max = {n}; // 最大值从n开始
long res = 0; // 最终结果
for (int c : cycle) {
res += cycleCal(c, max); // 计算环节点得分
}
for (int c : noCycle) {
res += noCycleCal(c, max); // 计算非环节点得分
}
return res; // 返回最大得分
}
// 辅助函数：深度优先搜索，计算当前节点的子树大小
private int dfs(int cur, int pre, List<Integer>[] graph, boolean[] isVisit) {
if (isVisit[cur]) {
return 0;
}
isVisit[cur] = true;
int res = 1;
for (int n : graph[cur]) {
if (n != pre) {
res += dfs(n, cur, graph, isVisit); // 递归计算子树
break;
}
}
return res;
}
// 辅助函数：计算环节点的得分
private long cycleCal(int c, int[] max) {
// 计算环节点得分
long st = max[0];
max[0] -= c;
c -= 1;
long res = 0;
long[] tmp = {st, -1};
while (c > 1) {
if (tmp[1] == -1) {
res += st * (st - 1);
res += st * (st - 2);
tmp[0] = st - 1;
tmp[1] = st - 2;
} else {
res += tmp[0] * (tmp[1] - 1);
res += tmp[1] * (tmp[1] - 2);
tmp[0] = tmp[1] - 1;
tmp[1] = tmp[1] - 2;
}
c -= 2;
}
if (c == 0) {
res += tmp[0] * tmp[1];
} else {
res += tmp[0] * (tmp[1] - 1);
res += tmp[1] * (tmp[1] - 1);
}
return res;
}
// 辅助函数：计算非环节点的得分
private long noCycleCal(int c, int[] max) {
// 计算非环节点得分
long st = max[0];
max[0] -= c;
c -= 2;
long res = st * (st - 1);
long[] tmp = {st, st - 1};
while (c > 1) {
res += tmp[0] * (tmp[1] - 1);
res += tmp[1] * (tmp[1] - 2);
tmp[0] = tmp[1] - 1;
tmp[1] = tmp[1] - 2;
c -= 2;
}
if (c == 1) {
res += tmp[0] * (tmp[1] - 1);
}
return res;
}
}100651. Equal Sum Grid Partition II
给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：
- 分割后形成的每个部分都是 非空 的。
- 两个部分中所有元素的和 相等 ，或者总共 最多移除一个单元格 （从其中一个部分中）的情况下可以使它们相等。
- 如果移除某个单元格，剩余部分必须保持 连通 。
如果存在这样的分割，返回 true；否则，返回 false。
注意： 如果一个部分中的每个单元格都可以通过向上、向下、向左或向右移动到达同一部分中的其他单元格，则认为这一部分是 连通 的。
测试样例：
输入：grid = [[1,4],[2,3]]
输出：true
解释: 在第 0 行和第 1 行之间进行水平分割，结果两部分的元素和为 1 + 4 = 5 和 2 + 3 = 5，相等。因此答案是 true。
解答：
- 计算矩阵中所有元素的总和，如果矩阵只有一行或一列，直接计算分割后两部分的和是否相等，或者通过移除一个单元格来使两部分和相等。
- 对于更一般的情况，分别考虑水平和垂直分割：
- 水平分割：从上到下逐行累加，判断分割点两侧的和是否相等。
- 垂直分割：从左到右逐列累加，判断分割点两侧的和是否相等。
- 如果在某一个分割点，两部分和相等或移除一个单元格后可以使其相等，则返回 true，否则返回 false。
class Solution {
private class MySet {
boolean[][] isAdd;
int[][] grid;
HashMap<Integer, Integer> map;
public MySet(int[][] grid) {
this.grid = grid;
isAdd = new boolean[grid.length][grid[0].length];
map = new HashMap<>();
}
public void add(int m, int n) {
if (!isAdd[m][n]) {
isAdd[m][n] = true;
int key = grid[m][n];
map.put(key, map.getOrDefault(key, 0) + 1);
}
}
public void remove(int m, int n) {
if (isAdd[m][n]) {
isAdd[m][n] = false;
int key = grid[m][n];
map.put(key, map.getOrDefault(key, 0) + 1);
}
}
public boolean contains(int key) {
return map.getOrDefault(key, 0) >= 1;
}
}
public boolean canPartitionGrid(int[][] grid) {
long sum = 0;
int m = grid.length, n = grid[0].length;
for (int[] ints : grid) {
for (int t : ints) {
sum += t;
}
}
if (m == 1) {
long leftSum = 0;
for (int i = 0; i < n - 1; ++i) {
leftSum += grid[0][i];
long rightSum = sum - leftSum;
if (leftSum == rightSum) {
return true;
}
long diff = leftSum - rightSum;
if (diff == grid[0][0] || diff == grid[0][i]) {
return true;
} else if (-diff == grid[0][i + 1] || -diff == grid[0][n - 1]) {
return true;
}
}
} else if (n == 1) {
long topSum = 0;
for (int i = 0; i < m - 1; ++i) {
topSum += grid[i][0];
long downSum = sum - topSum;
if (topSum == downSum) {
return true;
}
long diff = topSum - downSum;
if (diff == grid[0][0] || diff == grid[i][0]) {
return true;
} else if (-diff == grid[i + 1][0] || -diff == grid[m - 1][0]) {
return true;
}
}
} else {
// 水平分割
{
long topSum = 0;
MySet top = new MySet(grid), down = new MySet(grid);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
down.add(i, j);
}
}
for (int i = 0; i < m - 1; ++i) {
for (int j = 0; j < n; ++j) {
down.remove(i, j);
topSum += grid[i][j];
if (i == m - 2) {
down = new MySet(grid);
down.add(m - 1, 0);
down.add(m - 1, n - 1);
}
if (i == 0) {
top.add(0, 0);
top.add(0, n - 1);
} else {
top.add(i, j);
if (i == 1) {
top.add(0, j);
}
}
}
long bottomSum = sum - topSum;
if (topSum == bottomSum) {
return true;
}
long diff = topSum - bottomSum;
if (Math.abs(diff) > 1_000_000) continue;
if (diff > 0 && top.contains((int) diff)) {
return true;
} else if (diff < 0 && down.contains((int) -diff)) {
return true;
}
}
}
// 垂直分割
{
long leftSum = 0;
MySet left = new MySet(grid), right = new MySet(grid);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
right.add(i, j);
}
}
for (int j = 0; j < n - 1; ++j) {
for (int i = 0; i < m; ++i) {
leftSum += grid[i][j];
right.remove(i, j);
if (j == n - 2) {
right = new MySet(grid);
right.add(0, n - 1);
right.add(m - 1, n - 1);
}
if (j == 0) {
left.add(0, 0);
left.add(m - 1, 0);
} else {
left.add(i, j);
if (j == 1) {
left.add(i, 0);
}
}
}
long rightSum = sum - leftSum;
if (leftSum == rightSum) {
return true;
}
long diff = leftSum - rightSum;
if (Math.abs(diff) > 1_000_000) continue;
if (diff > 0 && left.contains((int) diff)) {
return true;
} else if (diff < 0 && right.contains((int) -diff)) {
return true;
}
}
}
}
return false;
}
}