No.1 较量中的配对次数
解题思路
模仿过程即可，较简略。
代码展现
class Solution {
public int numberOfMatches(int n) { int res = 0; while (n > 1) { res += n / 2; n = (n + 1) / 2; } return res;}}
No.2十-二进制数的起码数目
解题思路
取决于最大的数字是多少。
代码展现
class Solution { public int minPartitions(String n) { int res = 0; for (int i = 0; i < n.length(); i++) { res = Math.max(res, n.charAt(i) - '0'); } return res; }}No.3 石子游戏VII
解题思路
区间动静布局问题。
定义状态: dp[i][j] 示意区间 [i, j] 的得分差值
状态转移: 当一个人面临 [i, j] 的状况时，在拿右边和拿左边之间抉择本人取得分数更大的状况，详见代码。
定义 prefixSum 示意前缀和以辅助计算。
代码展现
class Solution {
public int stoneGameVII(int[] stones) { int n = stones.length; int[] prefixSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + stones[i]; } int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { if (i != j) { // 边界: dp[i][i] = 0 dp[i][j] = Math.max( // 拿了右边的 (prefixSum[j + 1] - prefixSum[i + 1]) - dp[i + 1][j], // 拿了左边的 (prefixSum[j] - prefixSum[i]) - dp[i][j - 1] ); } } } return dp[0][n - 1];}}
No.4 重叠长方体的最大高度
解题思路
该题目相似嵌套矩形的问题，而嵌套矩形问题又是最长回升子序列的变体，所以实质上和 LIS 问题没有太大区别。
定义状态: dp[i] 示意以 i 结尾的长方体上最高能重叠多高。
与解决二维一样地，先要对长方体进行排序，而后再递推求解。
留神最终答案是 max{ dp }
代码展现
class Solution {
public int maxHeight(int[][] cuboids) { // 排序 for (int[] c : cuboids) { Arrays.sort(c); } Arrays.sort(cuboids, (a, b) -> { if (a[0] != b[0]) return Integer.compare(a[0], b[0]); if (a[1] != b[1]) return Integer.compare(a[1], b[1]); return Integer.compare(a[2], b[2]); }); // dp[i] 示意以第 i 个长方体为开端时，能重叠的最大高度 int[] dp = new int[cuboids.length]; for (int i = 0; i < cuboids.length; i++) { dp[i] = cuboids[i][2]; for (int j = 0; j < i; j++) if (cuboids[j][0] <= cuboids[i][0] && cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) { dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]); } } return Arrays.stream(dp).max().getAsInt();}}