T1: 分割圆的最少切割次数
思维题：
n 为偶数时，可以对半切割，切割 \(\frac{n}{2}\)次即可
n 为奇数时，不满足对称性，需要切割 n 次
n 为 1 时，不需要切割
public int numberOfCuts(int n) {
if (n == 1) {
return 0;
}
if (n % 2 == 0) {
return n / 2;
}
return n;
}
T2: 行和列中一和零的差值
思路：按要求模拟即可，第一次遍历统计，第二次遍历计算。
public int[][] onesMinusZeros(int[][] grid) {
// 第一遍遍历统计第 i 行 0 的数目和第 j 列 0 的数目
int m = grid.length;
int n = grid[0].length;
int[] zeroRow = new int[m];
int[] zeroCol = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
zeroRow[i] += 1;
zeroCol[j] += 1;
}
}
}
// 构建差值矩阵
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = (n - zeroRow[i]) + (m - zeroCol[j]) - (zeroRow[i]) - (zeroCol[j]);
}
}
return grid;
}
T3: 商店的最小代价
思路：前后缀统计
第一次遍历统计字符串中 Y 的个数，即在 0 小时关门的代价
第二次遍历计算在1~N 小时关门的代价
public int bestClosingTime(String customers) {
int pos = 0;
int cost = 0;
for (int i = 0; i < customers.length(); i++) {
if (customers.charAt(i) == 'Y') {
cost += 1;
}
}
if (cost == 0) {
return pos;
}
int min = cost;
for (int i = 1; i <= customers.length(); i++) {
if (customers.charAt(i - 1) == 'Y') {
cost -= 1;
}
else {
cost += 1;
}
if (cost < min) {
min = cost;
pos = i;
}
}
return pos;
}
T4: 统计回文子序列的数目
思路：动态规划 + 前缀/后缀和
回文子序列的长度固定为5，则其形式必须为xyzyx（x、y、z可以相等），即回文中心为单个字符，左右包括两个对称的双字符序列。
由于字符串只包含0~9的数字，所以 xy 一共只有100种
枚举所有回文中心 i，统计s[0, i - 1]中 xy 的个数，s[i + 1, s.length() - 1] 中 yx 的个数
\(ans = \sum_{i = 0}^{s.length() - 1} {\sum_{0}^{99} {count_{ab} * count_{ba}}}\)
如何高效统计 s[0, i-1] 以及 s[i + 1, s.length() - 1] 中各对字符的个数呢？
- 利用动态规划的思想，统计
s[0, i - 1] 中 xy 的个数，正向遍历字符串\(\begin{cases}dp[i][j][k] = dp[i - 1][j][k] + prefix[j] \quad (s[i] == k) \\dp[i][j][k] = dp[i - 1][j][k] \quad (s[i] != k)\end{cases}\)
上述公式中 prefix[j] 表示
s[0, i - 1] 中 j 的个数由于动态规划过程中当前状态只取决于上一状态，可以将其简化为 \(dp[j][k] += prefix[j] \quad (s[i] == k)\)
统计
s[i + 1, s.length() - 1] 中 yx 的个数也是类似的道理，需要逆向遍历字符串并维护一个后缀数组suffix/**
* 核心思路：回文串长度为5, 等价于回文中心是单个数字，且左右各有两个对称的数字, 即 12321
*
* 枚举所有的回文中心 i (0 <= i <= s.length() - 1)
* 统计 s[0 ... i - 1] 中 xy 的个数 count1, xy只有 100 种情况
* 统计 s[i + 1 ... s.length() - 1] 中 yx 的个数 count2
*
* ans = \sum_{0}^{s.length() - 1} {\sum_{0}^{99} {count1 * count2}}
* @param s
* @return
*/
public int countPalindromes(String s) {
char[] arr = s.toCharArray();
int[] prefix = new int[10];
int[] suffix = new int[10];
int[][] prefix2 = new int[10][10];
int[][] suffix2 = new int[10][10];
// 逆序遍历, 统计 xy 个数
// dp[pos][x][y] = dp[pos + 1][x][y] + suffix[y] if (cur == x)
// dp[pos][x][y] = dp[pos + 1][x][y] if (cur != x)
for (int i = arr.length - 1; i >= 0; i--) {
int cur = arr[i] - '0';
for (int j = 0; j <= 9; j++) {
suffix2[cur][j] += suffix[j];
}
suffix[cur] += 1;
}
int ans = 0;
for (int i = 0; i < arr.length; i++) {
int cur = arr[i] - '0';
suffix[cur] -= 1;
// 去除后序遍历计算的包括当前位置的xy个数
for (int j = 0; j <= 9; j++) {
suffix2[cur][j] -= suffix[j];
}
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
ans += (long) prefix2[k][j] * suffix2[j][k];
}
}
for (int j = 0; j <= 9; j++) {
prefix2[j][cur] += prefix[j];
}
prefix[cur] += 1;
}
return (int) (ans % MOD);
}
