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

上岸算法 · 发表于 2022-3-8 17:55:18

登录后可回复主题

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

x

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

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

代码展示

class Solution {
public List<String> 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<String> 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<Integer> replaceNonCoprimes(int[] nums) {
   List<Integer> list = new ArrayList<>();
   for (int num : nums) {
         list.add(num);
   }
   while (true) {
         // 正着遍历，合并一次
         List<Integer> merged = merge(list);
         if (list.size() == merged.size()) { // 合并前后长度一致，说明无法再合并，直接返回
            return merged;
      }
         // 反着遍历，合并一次
         list = reverse(merge(reverse(merged)));
   }
  }

private List<Integer> merge(List<Integer> nums) {
   List<Integer> 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<Integer> reverse(List<Integer> list) {
   List<Integer> 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);
  }
}

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

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

登录后可回复主题