上岸算法LeetCode Weekly Contest 289解题报告

上岸算法 · 发表于 2022-4-17 17:19:24

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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] 表示完成 i 个任务完成所需的最少轮数，于是有 dp[i] = min(dp[i-2], dp[i-3]) + 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[100001];
   mem[2] = mem[3] = 1;
   mem[4] = mem[5] = 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[cnt] > 0) {
         return mem[cnt];
   }
   mem[cnt] = Math.min(dp(cnt - 3, mem) + 1, dp(cnt - 2, mem) + 1);
   return mem[cnt];
  }
}

【 NO.3 转角路径的乘积中最多能有几个尾随零】

解题思路
尾随 0 的个数其实就是 MIN(因数 2 的个数, 因数 5 的个数)

代码虽然很长，但大部分是重复的逻辑，详见注释。

代码展示

class Solution {
public int maxTrailingZeros(int[][] grid) {
   // up2 表示 grid[i][j] 开始连续往上走最多能累计到因数 2 的个数
   // up5 表示 grid[i][j] 开始连续往上走最多能累计到因数 5 的个数
   int[][] up2 = new int[grid.length][grid[0].length];
   int[][] up5 = new int[grid.length][grid[0].length];
   for (int i = 0; i < grid.length; i++) {
         for (int j = 0; j < grid[0].length; j++) {
            up2[i][j] = num(grid[i][j], 2);
            up5[i][j] = num(grid[i][j], 5);
            if (i > 0) {
               up2[i][j] += up2[i - 1][j];
               up5[i][j] += up5[i - 1][j];
            }
      }
   }
   // left2 表示 grid[i][j] 开始连续往左走最多能累计到因数 2 的个数
   // left5 表示 grid[i][j] 开始连续往左走最多能累计到因数 5 的个数
   int[][] left2 = new int[grid.length][grid[0].length];
   int[][] left5 = new int[grid.length][grid[0].length];
   for (int i = 0; i < grid.length; i++) {
         for (int j = 0; j < grid[0].length; j++) {
            left2[i][j] = num(grid[i][j], 2);
            left5[i][j] = num(grid[i][j], 5);
            if (j > 0) {
               left2[i][j] += left2[i][j - 1];
               left5[i][j] += left5[i][j - 1];
            }
      }
   }
   // down2 表示 grid[i][j] 开始连续往下走最多能累计到因数 2 的个数
   // down5 表示 grid[i][j] 开始连续往下走最多能累计到因数 5 的个数
   int[][] down2 = new int[grid.length][grid[0].length];
   int[][] down5 = new int[grid.length][grid[0].length];
   for (int i = grid.length - 1; i >= 0; i--) {
         for (int j = grid[0].length - 1; j >= 0; j--) {
            down2[i][j] = num(grid[i][j], 2);
            down5[i][j] = num(grid[i][j], 5);
            if (i < grid.length - 1) {
               down2[i][j] += down2[i + 1][j];
               down5[i][j] += down5[i + 1][j];
            }
      }
   }
   // right2 表示 grid[i][j] 开始连续往右走最多能累计到因数 2 的个数
   // right5 表示 grid[i][j] 开始连续往右走最多能累计到因数 5 的个数
   int[][] right2 = new int[grid.length][grid[0].length];
   int[][] right5 = new int[grid.length][grid[0].length];
   for (int i = grid.length - 1; i >= 0; i--) {
         for (int j = grid[0].length - 1; j >= 0; j--) {
            right2[i][j] = num(grid[i][j], 2);
            right5[i][j] = num(grid[i][j], 5);
            if (j < grid[0].length - 1) {
               right2[i][j] += right2[i][j + 1];
               right5[i][j] += right5[i][j + 1];
            }
      }
   }

   int res = 0;
   for (int i = 0; i < grid.length; i++) {
         for (int j = 0; j < grid[0].length; j++) {
            // 有四种转角形态
            // 1. up + left
            if (i > 0) {
               res = Math.max(res, Math.min(up2[i - 1][j] + left2[i][j], up5[i - 1][j] + left5[i][j]));
            }
            // 2. up + right
            if (i > 0) {
               res = Math.max(res, Math.min(up2[i - 1][j] + right2[i][j], up5[i - 1][j] + right5[i][j]));
            }
            // 3. down + left
            if (i < grid.length - 1) {
               res = Math.max(res, Math.min(down2[i + 1][j] + left2[i][j], down5[i + 1][j] + left5[i][j]));
            }
            // 4. down + right
            if (i < grid.length - 1) {
               res = Math.max(res, Math.min(down2[i + 1][j] + right2[i][j], down5[i + 1][j] + right5[i][j]));
            }
            // 不转角
            // 5. up/down/left/right
            res = Math.max(res, Math.min(up2[i][j], up5[i][j]));
            res = Math.max(res, Math.min(down2[i][j], down5[i][j]));
            res = Math.max(res, Math.min(left2[i][j], left5[i][j]));
            res = Math.max(res, Math.min(right2[i][j], right5[i][j]));
      }
   }
   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[i] != -1) {
            if (!children.containsKey(parent[i])) {
               children.put(parent[i], new ArrayList<>());
            }
            children.get(parent[i]).add(i);
      }
   }

   int[] maxLength = new int[parent.length];
   res = 1;
   dfs(0, children, maxLength, s);
   return res;
  }

private void dfs(int cur, Map<Integer, List<Integer>> children, int[] maxLength, String s) {
   maxLength[cur] = 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[cur] = Math.max(maxLength[cur], maxLength[child] + 1);
            if (maxLength[child] >= first) {
               second = first;
               first = maxLength[child];
            } else if (maxLength[child] > second) {
               second = maxLength[child];
            }
      }
   }
   res = Math.max(res, maxLength[cur]);
   res = Math.max(res, first + second + 1);
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 289解题报告

登录后可回复主题