1323.Maximum 69 Number

解题思路比较简单:

若给定的数字包含 6, 则把最高位的 6 替换成 9

若给定的数字不包含 6, 则直接返回

至于实现, 可以转换成字符串进行查找替换, 然后再转换回整型.

不过更高效的则是利用 % 10 和 / 10 运算依次检查每一个数位, 记录最高的是 6 的数位. 最后用加法完成替换.

代码展示部分：

class Solution {
   public int maximum69Number (int num) {
       // (num >= 0) 找到最高位的 6, 把它换成 9
       int base = 1;   // 表示 10 的幂
       int target = 0;  // 最高位的 6 的 base
       for (int t = num; t > 0; t /= 10) {
           if (t % 10 == 6) {
               target = base;
           }
           base *= 10;
       }
       return num + target * 3;  // 将对应数位的 6 换成 9
   }
}

1324.Print Words Vertically

解题思路：依次构造每一个垂直字符即可.

注意细节：在构造第 col 列对应的垂直字符串时，若原字符串长度不足col，按照题意应该填入空格，并且最终需要将尾部的空格删去

至于实现, 可以转换成字符串进行查找替换, 然后再转换回整型.

代码展示部分：

class Solution {
   public List<String> printVertically(String s) {
       // 先将原字符串以空格分割
       String[] strs = s.split(" ");
       List<String> res = new ArrayList<String>();
       // 依次构造每一列对应的垂直字符串
       for (int col = 0; ; col++) {
           StringBuilder sb = new StringBuilder();
           // 将每个字符串的 col 位置的字符添加到 StringBuilder 中
           for (String str : strs) {
               if (str.length() > col) {
                   sb.append(str.charAt(col));
               } else {
                   sb.append(' ');
               }
           }
           // 若 StringBuilder 中只有空格, 则可以 break
           if ("".equals(sb.toString().stripTrailing())) {
               break;  // 如果
           }
           // stripTrailing() 消除末端空格 (前端的空格不可以消除)
           res.add(sb.toString().stripTrailing());
       }
       return res;
   }
}

1325.Delete Leaves With a Given Value

先递归进入左右子树, 递归出来之后再判断当前节点是否叶子节点, 如果是叶子节点, 进而判断值是否 target, 如果是 target, 说明该节点需要删除, 那么应该返回 null

代码展示部分：

class Solution {
   public TreeNode removeLeafNodes(TreeNode root, int target) {
       if (root == null) {
           return null;
       }
       // 递归
       root.left = removeLeafNodes(root.left, target);
       root.right = removeLeafNodes(root.right, target);
       // 判断当前节点是否需要删除
       if (root.left == null && root.right == null && root.val == target) {
           return null;
       } else {
           return root;
       }
   }
}

1326.Minimum Number of Taps to Water a Garden

首先说明，这个题目的解法之一是贪心.

然后注意一个题目理解问题：需要覆盖的是线段而不是水龙头

举个例子, 对于 n = 3, ranges = [1, 0, 0, 1] 这组数据, 如果你是根据 "覆盖水龙头" 来判断的, 那么选择首尾两个水龙头, 就可以覆盖这 4 个点, 但是实际上 1 号点和 2 号点之间的这一段空间并没有被覆盖. 所以这个例子的正确输出是 0, 而不是 2.

接着我们再详细说明贪心的思路. 假如我们从左到右考虑每个点, 如果当前点 (包含当前点到下一个点之间的这一段区间) 还没有被覆盖, 问题就是选择哪一个水龙头来覆盖这个点. 从贪心的角度思考: 因为左边的已经被覆盖了, 所以我们选择的水龙头是能覆盖右侧最多的那个.

所以我们维护一个 maxR 数组, 根据该数组计算最终答案. 时空复杂度均为 $o(n)$

代码展示部分：

class Solution {
   public int minTaps(int n, int[] ranges) {
       // 把每个水龙头的位置以及它的范围看作一个区间 [l, r]
       // 那么 maxR[l] 表示以 l 为起点的区间的终点最大是多少
       int[] maxR = new int[n + 1];
       for (int i = 0; i <= n; i++) {
           int l = Math.max(0, i - ranges[i]);
           int r = Math.min(n, i + ranges[i]);
           maxR[l] = Math.max(maxR[l], r);
       }
       int res = 0;
       for (int start = 0, end = 0; end < n; ) {
           res++;
           int prevEnd = end;
           // 现在需要覆盖的点是 end, 枚举 [start, end] 之间的区间, 选择终点最大的那个
           for (int i = start; i <= prevEnd; i++) {
               end = Math.max(end, maxR[i]);
           }
           // 如果没有区间能够覆盖 end, 则返回 -1
           if (prevEnd == end) {
               return -1;
           }
           // start 表示下一次枚举的起点
           // [start, prevEnd] 已经枚举过了, 无需再枚举, 可以将 start 设置为 prevEnd + 1
           // 因为 start 和 end 都是只增不减的, 所以时间复杂度很容易分析出来是 o(n)
           start = prevEnd + 1;
       }
       return res;
   }
}

想要了解最新的最新的周赛题解信息，可以入群与大佬们交流~