6303. Separate the Digits in an Array
给你一个正整数数组 nums ，请你返回一个数组 answer ，你需要将 nums 中每个整数进行数位分割后，按照 nums 中出现的 相同顺序 放入答案数组中。
对一个整数进行数位分割，指的是将整数各个数位按原本出现的顺序排列成数组。
- 比方说，整数 10921 ，分割它的各个数位得到 [1,0,9,2,1] 。
测试样例
输入：nums = [13,25,83,77]
输出：[1,3,2,5,8,3,7,7]
解释：
- 分割 13 得到 [1,3] 。
- 分割 25 得到 [2,5] 。
- 分割 83 得到 [8,3] 。
- 分割 77 得到 [7,7] 。
answer = [1,3,2,5,8,3,7,7] 。answer 中的数字分割结果按照原数字在数组中的相同顺序排列。
解答：硬编码
class Solution {
public int[] separateDigits(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int i : nums) {
List<Integer> tmp = de(i);
for (int j = tmp.size() - 1; j >= 0; --j) {
list.add(tmp.get(j));
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); ++i) {
res[i] = list.get(i);
}
return res;
}
private List<Integer> de(int n) {
List<Integer> tmp = new ArrayList<>();
while (n != 0) {
tmp.add(n % 10);
n /= 10;
}
return tmp;
}
}6304. Maximum Number of Integers to Choose From a Range I
给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：
- 被选择整数的范围是 [1, n] 。
- 每个整数 至多 选择 一次 。
- 被选择整数不能在数组 banned 中。
- 被选择整数的和不超过 maxSum 。
请你返回按照上述规则 最多 可以选择的整数数目。
测试样例：
输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：
你可以选择整数 2 和 4 。2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
解答: 利用HashSet去除banned的数组，并暴力枚举。
class Solution {
public int maxCount(int[] banned, int n, int maxSum) {
Set<Integer> bannedSet = new HashSet<>();
for (int i : banned) {
bannedSet.add(i);
}
int sum = 0, res = 0;
for (int i = 1; i <= n; ++i) {
if (!bannedSet.contains(i)) {
if (sum + i > maxSum) {
break;
}
sum += i;
++res;
}
}
return res;
}
}6331. Maximize Win From Two Segments
在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。
你可以选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。
- 比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。
请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。
测试样例
输入：prizePositions = [1,1,2,2,3,3,5], k = 2
输出：7
解答：双指针配合动态规划。
- 计算从当前位置开始，k范围内最大可以获取多少的奖品数（双指针动态规划）。
- 计算从当前位置开始，k范围内的覆盖奖品数，并且加上之后位置k范围的最大奖品数
- 不断取max即可得到答案
class Solution {
public int maximizeWin(int[] prizePositions, int k) {
int len = prizePositions.length;
int[] dp = new int[len];
int left = prizePositions.length - 1, right = prizePositions.length - 1;
while (left >= 0) {
while (prizePositions[right] - prizePositions[left] > k) {
--right;
}
dp[left] = Math.max(right - left + 1, left + 1 < prizePositions.length ? dp[left + 1] : 0);
--left;
}
int max = 0;
left = 0; right = 0;
while (left < prizePositions.length) {
while (right < prizePositions.length && prizePositions[right] - prizePositions[left] <= k) {
++right;
}
int cur = (right - left) + (right < prizePositions.length ? dp[right] : 0);
max = Math.max(cur, max);
++left;
}
return max;
}
}6305. Disconnect Path in a Binary Matrix by at Most One Flip
给你一个下标从 0 开始的 m x n 二进制 矩阵 grid 。你可以从一个格子 (row, col) 移动到格子 (row + 1, col) 或者 (row, col + 1) ，前提是前往的格子值为 1 。如果从 (0, 0) 到 (m - 1, n - 1) 没有任何路径，我们称该矩阵是 不连通 的。
你可以翻转 最多一个 格子的值（也可以不翻转）。你 不能翻转 格子 (0, 0) 和 (m - 1, n - 1) 。
如果可以使矩阵不连通，请你返回 true ，否则返回 false 。
注意 ，翻转一个格子的值，可以使它的值从 0 变 1 ，或从 1 变 0 。
测试样例
输入：grid = [[1,1,1],[1,0,0],[1,1,1]]
输出：true
解答：又是一道脑筋急转弯的题目。在最多去掉一个格子的情况下，查找是否存在连通性。其实从另一种思维就是，首先寻找到一条路径，并且把路径上的所有格子标志为0。然后再次寻找路径，如果此时仍然联通，那么第一条路径上的点不存在割点。否则存在割点。
class Solution {
public boolean isPossibleToCutPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
if (isConnect(grid, 0, 0, new boolean[m][n])) {
if (isConnect(grid, 0, 0, new boolean[m][n])) {
return false;
}
}
return true;
}
private boolean isConnect(int[][] grid, int x, int y, boolean[][] isVisit) {
if (x == grid.length - 1 && y == grid[0].length - 1) {
return true;
}
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
if (isVisit[x][y]) {
return false;
}
isVisit[x][y] = true;
if (!((x == 0 && y == 0) || (x == grid.length - 1 && y == grid[0].length - 1))) {
grid[x][y] = 0;
}
if (isConnect(grid, x + 1, y, isVisit) || isConnect(grid, x, y + 1, isVisit)) {
return true;
}
grid[x][y] = 1;
}
return false;
}
}