上岸算法LeetCode Weekly Contest 283解题报告
【 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)) {
valueToNode.put(desc, new TreeNode(desc));
}
}
parent.put(desc, desc);
if (desc == 1) {
valueToNode.get(desc).left = valueToNode.get(desc);
} else {
valueToNode.get(desc).right = valueToNode.get(desc);
}
}
int cur = descriptions;
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, nums 可合并时，nums = 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);
}
}
页:
[1]