【 NO.1 Excel 表中某个范围内的单元格】

解题思路

通过 char 类型的加减法进行坐标转换。

代码展示

class Solution {

   public List cellsInRange(String s) {

       int startX = s.charAt(1) - '1';

       int startY = s.charAt(0) - 'A';

       int endX = s.charAt(4) - '1';

       int endY = s.charAt(3) - 'A';

       List res = new ArrayList<>();

       for (int y = startY; y <= endY; y++) {

           for (int x = startX; x <= endX; x++) {

               res.add(String.valueOf(new char[]{(char) (y + 'A'), (char) (x + '1')}));

          }

      }

       return res;

  }

}

【 NO.2 向数组中追加 K 个整数】

解题思路

给原数组排序，然后向有缝隙的位置插入即可。

代码展示

class Solution {

   public long minimalKSum(int[] nums, int k) {

       Arrays.sort(nums);

       long res = 0;

       int last = 0;

       for (int num : nums) {

           // (last, num)

           if (last == num) {

               continue;

          }

           int cnt = Math.min(k, num - last - 1);

           k -= cnt;

           res += (long) (last + 1 + last + cnt) * cnt / 2;

           last = num;

           if (k == 0) {

               break;

          }

      }

       if (k > 0) {

           res += (long) (last + 1 + last + k) * k / 2;

      }

       return res;

  }

}

【 NO.3 根据描述创建二叉树】

解题思路

使用两个 Map, 一个记录节点值到节点的映射，一个记录节点到父节点的映射。

代码展示

class Solution {

   public TreeNode createBinaryTree(int[][] descriptions) {

       Map<Integer, Integer> parent = new HashMap<>();

       Map<Integer, TreeNode> valueToNode = new HashMap<>();

       for (var desc : descriptions) {

           for (int i = 0; i < 2; i++) {

               if (!valueToNode.containsKey(desc[i])) {

                   valueToNode.put(desc[i], new TreeNode(desc[i]));

              }

          }

           parent.put(desc[1], desc[0]);

           if (desc[2] == 1) {

               valueToNode.get(desc[0]).left = valueToNode.get(desc[1]);

          } else {

               valueToNode.get(desc[0]).right = valueToNode.get(desc[1]);

          }

      }

       int cur = descriptions[0][0];

       while (parent.containsKey(cur)) {

           cur = parent.get(cur);

      }

       return valueToNode.get(cur);

  }

}

【 NO.4 替换数组中的非互质数】

解题思路

正着遍历、反着遍历，直到无法再合并为止。详见注释。

代码展示

class Solution {

   public List replaceNonCoprimes(int[] nums) {

       List list = new ArrayList<>();

       for (int num : nums) {

           list.add(num);

      }

       while (true) {

           // 正着遍历，合并一次

           List merged = merge(list);

           if (list.size() == merged.size()) { // 合并前后长度一致，说明无法再合并，直接返回

               return merged;

          }

           // 反着遍历，合并一次

           list = reverse(merge(reverse(merged)));

      }

  }

   private List merge(List nums) {

       List res = new ArrayList<>();

       if (nums.size() == 1) {

           res.add(nums.get(0));

           return res;

      }

       // 一次合并中，令 i, j 表示相邻的两个元素

       // 当 nums[i], nums[j] 可合并时，nums[i] = lcm, j++ 即可

       // 最终将结果 add 到 res 中

       for (int i = 0, j = 1; j < nums.size(); j++) {

           int g = gcd(nums.get(i), nums.get(j));

           if (g > 1) {

               nums.set(i, nums.get(i) / g * nums.get(j));

               if (j == nums.size() - 1) {

                   res.add(nums.get(i));

              }

          } else {

               res.add(nums.get(i));

               i = j;

               if (j == nums.size() - 1) {

                   res.add(nums.get(j));

              }

          }

      }

       return res;

  }

   private List reverse(List list) {

       List rev = new ArrayList<>();

       for (int i = list.size() - 1; i >= 0; i--) {

           rev.add(list.get(i));

      }

       return rev;

  }

   private int gcd(int a, int b) {

       return b == 0 ? a : gcd(b, a % b);

  }

}