欢迎大家加QQ群：623375442，可以方便群里面交流。
100422. Convert Date to Binary
给你一个字符串 date，它的格式为 yyyy-mm-dd，表示一个公历日期。
date 可以重写为二进制表示，只需要将年、月、日分别转换为对应的二进制表示（不带前导零）并遵循 year-month-day 的格式。
返回 date 的 二进制 表示。
测试样例：
输入：date = "2080-02-29"
输出："100000100000-10-11101"
解释：100000100000, 10 和 11101 分别是 2080, 02 和 29 的二进制表示。
解答：暴力拆分，然后转成二进制。Java的API还是挺全的。
class Solution {
public String convertDateToBinary(String date) {
String[] split = date.split("-");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; ++i) {
if (sb.length() > 0) {
sb.append('-');
}
sb.append(Integer.toBinaryString(Integer.parseInt(split[i])));
}
return sb.toString();
}
}100353. Maximize Score of Numbers in Ranges
给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。
你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的 得分 定义为所选整数两两之间的 最小 绝对差。
返回所选整数的 最大可能得分 。
测试样例：
输入：start = [6,0,3], d = 2
输出：4
解释：可以选择整数 8, 0 和 4 获得最大可能得分，得分为 min(|8 - 0|, |8 - 4|, |0 - 4|)，等于 4。
解答：利用折半搜索寻找最大值。这题需要想到，最小绝对差越大，则越不容易实现。
class Solution {
public int maxPossibleScore(int[] start, int d) {
Arrays.sort(start);
int st = 0, ed = start[start.length - 1] + d - start[0];
while (st < ed) {
int mid = st + (ed - st + 1) / 2;
if (isValid(start, d, mid)) {
st = mid;
} else {
ed = mid - 1;
}
}
return st;
}
private boolean isValid(int[] start, int d, int mid) {
long pos = start[0];
// 贪婪的寻找下一个最优数，越小越好。
for (int i = 1; i < start.length; ++i) {
pos += mid;
if (pos > start[i] + d) {
return false;
}
pos = Math.max(start[i], pos);
}
return true;
}
}100389. Reach End of Array With Max Score
给你一个长度为 n 的整数数组 nums 。
你的目标是从下标 0 出发，到达下标 n - 1 处。每次你只能移动到 更大 的下标处。
从下标 i 跳到下标 j 的得分为 (j - i) * nums[i] 。
请你返回你到达最后一个下标处能得到的 最大总得分 。
测试样例：
输入：nums = [1,3,1,5]
输出：7
解释：一开始跳到下标 1 处，然后跳到最后一个下标处。总得分为 1 1 + 2 3 = 7 。
解答：重点是贪婪，得分是(j - i) * nums[i]，所以每次碰到一个比当前大的数值，就立刻停下，然后完成一次跳跃。
class Solution {
public long findMaximumScore(List<Integer> _nums) {
int[] nums = new int[_nums.size()];
int p = 0;
for (int n : _nums) {
nums[p++] = n;
}
long[] dp = new long[nums.length];
Stack<Integer> stack = new Stack<>();
for (int i = nums.length - 1; i >= 0; --i) {
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
stack.pop();
}
if (stack.isEmpty()) {
dp[i] = (nums.length - 1L - i) * nums[i];
} else {
dp[i] = ((long) stack.peek() - i) * nums[i] + dp[stack.peek()];
}
stack.push(i);
}
return dp[0];
}
}补一个群友的，更好的解答。没必要用单调栈
class Solution {
public long findMaximumScore(List<Integer> nums) {
int n = nums.size();
if(n == 1) return 0;
int mx = nums.get(0);
long ans = mx;
for(int i = 1; i < n - 1; i++){
if(mx < nums.get(i))
mx = nums.get(i);
ans += mx;
}
return ans;
}
}100416. Maximum Number of Moves to Kill All Pawns
给你一个 50 x 50 的国际象棋棋盘，棋盘上有 一个 马和一些兵。给你两个整数 kx 和 ky ，其中 (kx, ky) 表示马所在的位置，同时还有一个二维数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个兵在棋盘上的位置。
Alice 和 Bob 玩一个回合制游戏，Alice 先手。玩家的一次操作中，可以执行以下操作：
- 玩家选择一个仍然在棋盘上的兵，然后移动马，通过 最少 的 步数 吃掉这个兵。注意 ，玩家可以选择 任意 一个兵，不一定 要选择从马的位置出发 最少 移动步数的兵。
- 在马吃兵的过程中，马 可能 会经过一些其他兵的位置，但这些兵 不会 被吃掉。只有 选中的兵在这个回合中被吃掉。
Alice 的目标是 最大化 两名玩家的 总 移动次数，直到棋盘上不再存在兵，而 Bob 的目标是 最小化 总移动次数。
假设两名玩家都采用 最优 策略，请你返回 Alice 可以达到的 最大 总移动次数。
在一次 移动 中，如下图所示，马有 8 个可以移动到的位置，每个移动位置都是沿着坐标轴的一个方向前进 2 格，然后沿着垂直的方向前进 1 格。
测试样例：
输入：kx = 1, ky = 1, positions = [[0,0]]
输出：4
解释：马需要移动 4 步吃掉 (0, 0) 处的兵。
解答：这题总体分成2步：
- 利用BFS搜索出每一个兵到棋盘上各个位置的最小跳数
- 利用动态规划，在Alice轮寻找最大跳数，Bob轮寻找最小跳数
class Solution {
private static final int[][] moves = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
private class Data {
public int[][][] dis;
public int[][] positions;
public Integer[][] dp;
public int kx, ky;
public Data(int[][] positions, int kx, int ky) {
this.positions = positions;
this.dis = new int[positions.length][][];
for (int i = 0; i < positions.length; ++i) {
int[] pos = positions[i];
dis[i] = findLeastDis(pos);
}
dp = new Integer[positions.length][1 << positions.length];
this.kx = kx;
this.ky = ky;
}
private int[][] findLeastDis(int[] pos) {
int[][] distance = new int[50][50];
for (int i = 0; i < 50; ++i) {
for (int j = 0; j < 50; ++j) {
distance[i][j] = Integer.MAX_VALUE;
}
}
distance[pos[0]][pos[1]] = 0;
// 利用BFS寻找到每个兵，最小的跳数
Queue<int[]> queue = new LinkedList<>();
queue.add(pos);
while (!queue.isEmpty()) {
int[] first = queue.poll();
int oldDis = distance[first[0]][first[1]];
for (int[] mv : moves) {
int xt = first[0] + mv[0], yt = first[1] + mv[1];
if (xt >= 0 && xt < 50 && yt >= 0 && yt < 50 && distance[xt][yt] == Integer.MAX_VALUE) {
queue.add(new int[]{xt, yt});
distance[xt][yt] = oldDis + 1;
}
}
}
return distance;
}
}
public int maxMoves(int kx, int ky, int[][] positions) {
Data data = new Data(positions, kx, ky);
return dfs(-1, 0, 0, data);
}
// 使用了带记忆DFS，模拟动态规划，正向有点想不到怎么做
private int dfs(int offset, int mark, int count, Data data) {
// 所有兵都吃完了，这个时候跳出计算
if (mark == (1 << data.positions.length) - 1) {
return 0;
}
if (offset == -1 || data.dp[offset][mark] == null) {
int x, y;
if (offset == -1) {
x = data.kx;
y = data.ky;
} else {
x = data.positions[offset][0];
y = data.positions[offset][1];
}
int res = count == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
for (int i = 0; i < data.positions.length; ++i) {
if (!isUsed(mark, i)) {
if (count == 0) {
// Alice轮寻找最大跳数
res = Math.max(res, dfs(i, mark + (1 << i),1, data) + data.dis[i][x][y]);
} else {
// Bob轮寻找最大跳数
res = Math.min(res, dfs(i, mark + (1 << i),0, data) + data.dis[i][x][y]);
}
}
}
if (offset != -1) {
data.dp[offset][mark] = res;
}
return res;
}
return data.dp[offset][mark];
}
private boolean isUsed(int mark, int offset) {
int tmp = (mark >> offset) & 1;
return tmp == 1;
}
}