上岸算法LeetCode Weekly Contest 289解题报告
【 NO.1 计算字符串的数字和】解题思路
签到题，循环处理即可。
代码展示
class Solution {
public String digitSum(String s, int k) {
while (s.length() > k) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < s.length(); i += k) {
int sum = 0;
for (int j = i; j < i + k && j < s.length(); j++) {
sum += s.charAt(j) - '0';
}
builder.append(sum);
}
s = builder.toString();
}
return s;
}
}
【 NO.2 完成所有任务需要的最少轮数】
解题思路
使用 Map 维护每种任务的数量，然后使用 dp 求解。
dp 表示完成 i 个任务完成所需的最少轮数，于是有 dp = min(dp, dp) + 1。
代码展示
class Solution {
public int minimumRounds(int[] tasks) {
Map<Integer, Integer> count = new HashMap<>();
for (int task : tasks) {
count.put(task, count.getOrDefault(task, 0) + 1);
}
int res = 0;
int[] mem = new int;
mem = mem = 1;
mem = mem = 2;
for (var entry : count.entrySet()) {
int cnt = entry.getValue();
if (cnt == 1) {
return -1;
}
res += dp(cnt, mem);
}
return res;
}
private int dp(int cnt, int[] mem) {
if (mem > 0) {
return mem;
}
mem = Math.min(dp(cnt - 3, mem) + 1, dp(cnt - 2, mem) + 1);
return mem;
}
}
【 NO.3 转角路径的乘积中最多能有几个尾随零】
解题思路
尾随 0 的个数其实就是 MIN(因数 2 的个数, 因数 5 的个数)
代码虽然很长，但大部分是重复的逻辑，详见注释。
代码展示
class Solution {
public int maxTrailingZeros(int[][] grid) {
// up2 表示 grid 开始连续往上走最多能累计到因数 2 的个数
// up5 表示 grid 开始连续往上走最多能累计到因数 5 的个数
int[][] up2 = new int.length];
int[][] up5 = new int.length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
up2 = num(grid, 2);
up5 = num(grid, 5);
if (i > 0) {
up2 += up2;
up5 += up5;
}
}
}
// left2 表示 grid 开始连续往左走最多能累计到因数 2 的个数
// left5 表示 grid 开始连续往左走最多能累计到因数 5 的个数
int[][] left2 = new int.length];
int[][] left5 = new int.length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
left2 = num(grid, 2);
left5 = num(grid, 5);
if (j > 0) {
left2 += left2;
left5 += left5;
}
}
}
// down2 表示 grid 开始连续往下走最多能累计到因数 2 的个数
// down5 表示 grid 开始连续往下走最多能累计到因数 5 的个数
int[][] down2 = new int.length];
int[][] down5 = new int.length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid.length - 1; j >= 0; j--) {
down2 = num(grid, 2);
down5 = num(grid, 5);
if (i < grid.length - 1) {
down2 += down2;
down5 += down5;
}
}
}
// right2 表示 grid 开始连续往右走最多能累计到因数 2 的个数
// right5 表示 grid 开始连续往右走最多能累计到因数 5 的个数
int[][] right2 = new int.length];
int[][] right5 = new int.length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid.length - 1; j >= 0; j--) {
right2 = num(grid, 2);
right5 = num(grid, 5);
if (j < grid.length - 1) {
right2 += right2;
right5 += right5;
}
}
}
int res = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
// 有四种转角形态
// 1. up + left
if (i > 0) {
res = Math.max(res, Math.min(up2 + left2, up5 + left5));
}
// 2. up + right
if (i > 0) {
res = Math.max(res, Math.min(up2 + right2, up5 + right5));
}
// 3. down + left
if (i < grid.length - 1) {
res = Math.max(res, Math.min(down2 + left2, down5 + left5));
}
// 4. down + right
if (i < grid.length - 1) {
res = Math.max(res, Math.min(down2 + right2, down5 + right5));
}
// 不转角
// 5. up/down/left/right
res = Math.max(res, Math.min(up2, up5));
res = Math.max(res, Math.min(down2, down5));
res = Math.max(res, Math.min(left2, left5));
res = Math.max(res, Math.min(right2, right5));
}
}
return res;
}
private int num(int x, int y) {
int res = 0;
while (x % y == 0) {
res++;
x /= y;
}
return res;
}
}
【 NO.4 相邻字符不同的最长路径】
解题思路
求出每个节点向下走能得到的最长路径，在每个节点的所有子节点中，挑出最长的和次长的连接，可以得到经过当前节点的最长路径。
代码展示
class Solution {
int res;
public int longestPath(int[] parent, String s) {
Map<Integer, List<Integer>> children = new HashMap<>();
for (int i = 0; i < parent.length; i++) {
if (parent != -1) {
if (!children.containsKey(parent)) {
children.put(parent, new ArrayList<>());
}
children.get(parent).add(i);
}
}
int[] maxLength = new int;
res = 1;
dfs(0, children, maxLength, s);
return res;
}
private void dfs(int cur, Map<Integer, List<Integer>> children, int[] maxLength, String s) {
maxLength = 1;
if (!children.containsKey(cur)) {
return;
}
var curChildren = children.get(cur);
int first = 0, second = 0;
for (int child : curChildren) {
dfs(child, children, maxLength, s);
if (s.charAt(child) != s.charAt(cur)) {
maxLength = Math.max(maxLength, maxLength + 1);
if (maxLength >= first) {
second = first;
first = maxLength;
} else if (maxLength > second) {
second = maxLength;
}
}
}
res = Math.max(res, maxLength);
res = Math.max(res, first + second + 1);
}
}
页:
[1]