6016. Excel 表中某个范围内的单元格
Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示，其中：
- 即单元格的列号`c`用英文字母表中的字母标识。 - 例如，第 `1` 列用 `'A'` 表示，第 `2` 列用 `'B'` 表示，第 `3` 列用 `'C'` 表示，以此类推。
<row>即单元格的行号r。第r行就用 整数r标识。
给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，其中 <col1> 表示 c1 列，<row1> 表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足 r1 <= r2 且 c1 <= c2 。
找出所有满足 r1 <= x <= r2 且 c1 <= y <= c2 的单元格，并以列表形式返回。单元格应该按前面描述的格式用 字符串 表示，并以 非递减 顺序排列（先按列排，再按行排）。
示例 1：
输入：s = "K1:L2" 输出：["K1","K2","L1","L2"] 解释： 上图显示了列表中应该出现的单元格。 红色箭头指示单元格的出现顺序。
示例 2：
输入：s = "A1:F1" 输出：["A1","B1","C1","D1","E1","F1"] 解释： 上图显示了列表中应该出现的单元格。 红色箭头指示单元格的出现顺序。
提示：
s.length == 5'A' <= s[0] <= s[3] <= 'Z''1' <= s[1] <= s[4] <= '9's由大写英文字母、数字、和':'组成
解题思路：
直接模拟，注意数字字符转成数字要减去′ 0 ′ '0'′0′
class Solution { public List<String> cellsInRange(String s) { int n = s.length(); String[] str = s.split(":"); int r1 = str[0].charAt(1) - '0'; int r2 = str[1].charAt(1) - '0'; int c = (str[1].charAt(0) - str[0].charAt(0)); List<String> res = new ArrayList<>(); for (int i = 0; i <= c; i++) { char c1 = (char) (str[0].charAt(0) + i); for (int j = 0; j <= r2 - r1; j++) { int num = (int) (str[0].charAt(1) - '0') + j; String ss = new String("" + c1 + num); res.add(ss); } } return res; } }
6017. 向数组中追加 K 个整数
给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
返回追加到 nums 中的 k 个整数之和。
示例 1：
输入：nums = [1,4,25,10,25], k = 2 输出：5 解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。 nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。 所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
示例 2：
输入：nums = [5,6], k = 6 输出：25 解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。 nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。 所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。
提示：
1 <= nums.length <= 10^51 <= nums[i], k <= 10^9
解题思路：由于这个题目要求的是互 不 相 同 且 未 出 现 的 正 整 数 的 和 互不相同且未出现的正整数的和互不相同且未出现的正整数的和，因此连续正整数的和可以用到高斯求和公式，就不需要去模拟每次插入的是哪几个数字了，可以直接求连续数字的和。
class Solution { public long minimalKSum(int[] nums, int k) { long res = 0; int n = nums.length; int pre = 0; Arrays.sort(nums); for (int i = 0; i < n; i++) { if (nums[i] - pre > k) { res += (long) ((pre + 1) + (pre + k)) * k / 2; return res; } else if (nums[i] - pre <= 1) { pre = nums[i]; } else { res += (long) ((pre + 1) + (nums[i] - 1)) * (nums[i] - pre - 1) / 2; k -= (nums[i] - pre - 1); pre = nums[i]; } } if (k > 0) { res += (long) (nums[n - 1] + 1 + nums[n - 1] + k) * k / 2; } return res; } }
6018. 根据描述创建二叉树
给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
- 如果
isLefti == 1，那么childi就是parenti的左子节点。 - 如果
isLefti == 0，那么childi就是parenti的右子节点。
请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
测试用例会保证可以构造出 有效 的二叉树。
示例 1：
输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] 输出：[50,20,80,15,17,19] 解释：根节点是值为 50 的节点，因为它没有父节点。 结果二叉树如上图所示。
示例 2：
输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]] 输出：[1,2,null,null,3,4] 解释：根节点是值为 1 的节点，因为它没有父节点。 结果二叉树如上图所示。
提示：
1 <= descriptions.length <= 104descriptions[i].length == 31 <= parenti, childi <= 10^50 <= isLefti <= 1descriptions所描述的二叉树是一棵有效二叉树
这个题也可以用并查集去做，主要是把对应的结点关联起来
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode createBinaryTree(int[][] descriptions) { Map<Integer, TreeNode> map = new HashMap<>(); for (int[] num : descriptions) { if (num[2] == 0) { map.computeIfAbsent(num[0], t -> new TreeNode(num[0])).right = map.computeIfAbsent(num[1], t -> new TreeNode(num[1])); } else { map.computeIfAbsent(num[0], t -> new TreeNode(num[0])).left = map.computeIfAbsent(num[1], t -> new TreeNode(num[1])); } } // 把computeIfAbsent过程中额外引入的num[1]的映射关系去掉 for (int[] num : descriptions) { map.remove(num[1]); } // values集合中迭代器的第一个 return map.values().iterator().next(); } }
* Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode createBinaryTree(int[][] descriptions) { // 缓存TreeNode节点 Map<Integer, TreeNode> map = new HashMap<>(); DSU dsu = new DSU(100001); for (int[] d : descriptions) { TreeNode node1 = map.compute(d[0], (key, value) -> value == null ? new TreeNode(d[0]) : value); TreeNode node2 = map.compute(d[1], (key, value) -> value == null ? new TreeNode(d[1]) : value); if (d[2] ==1) { node1.left = node2; } else { node1.right = node2; } dsu.union(d[1], d[0]); } // 随便找一个节点即可，因为全部处理之后，所有节点的parent都是根节点 return map.get(dsu.find(descriptions[0][0])); } class DSU { int[] parent; public DSU(int N) { parent = new int[N]; for (int i = 0; i < N; ++i) { parent[i] = i; } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } public void union(int x, int y) { parent[find(x)] = find(y); } } }
6019.替换数组中的非互质数
给你一个整数数组 nums 。请你对数组执行下述操作：
- 从
nums中找出 任意 两个 相邻 的 非互质 数。 - 如果不存在这样的数，终止 这一过程。
- 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
- 只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于108 。
两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。
示例 1 ：
输入：nums = [6,4,3,2,7,6,2] 输出：[12,7,6] 解释： - (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。 - (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。 - (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。 - (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。 现在，nums 中不存在相邻的非互质数。 因此，修改后得到的最终数组是 [12,7,6] 。 注意，存在其他方法可以获得相同的最终数组。
示例 2 ：
输入：nums = [2,2,1,1,3,3,3] 输出：[2,1,1,3] 解释： - (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。 - (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。 - (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。 现在，nums 中不存在相邻的非互质数。 因此，修改后得到的最终数组是 [2,1,1,3] 。 注意，存在其他方法可以获得相同的最终数组。
提示：
1 <= nums.length <= 10^1 <= nums[i] <= 10^5- 生成的测试用例可以保证最终数组中的值 小于或者等于
10^8
思路：
直接用栈模拟题目的操作步骤。
注意gcd函数即可
class Solution { public List<Integer> replaceNonCoprimes(int[] nums) { Stack<Integer> stack = new Stack<>(); for (int num : nums) { int cur = num; while (!stack.isEmpty()) { int p = stack.peek(); long x = gcd(cur, p); // 非互质 if (x > 1) { stack.pop(); cur = (int) (p / x * cur); } else { break; } } stack.push(cur); } List<Integer> res = new ArrayList<>(); for (int num : stack) { res.add(num); } return res; } public long gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
