每日算法-250523

每日算法学习记录 - 250523

2748. 美丽下标对的数目

题目

思路

数组

解题过程

题目要求当 i < j 时，nums[i] 的第一个数字要和 nums[j] 的最后一个数字互质。
我们知道，nums[i] 的第一个数字必然落在 1-9 之间。因此，我们可以用一个大小为 10 的数组 map 来记录：当遍历到 nums[j] 时，在 j 之前（即 0 到 j-1 的索引）出现的数字中，其首位数字分别是 1-9 的各有几个。

遍历 nums 数组中的每个元素 x (代表 nums[j]):

1. 获取 x 的最后一位数字 cur = x % 10。
2. 遍历 map 数组的索引 k 从 1 到 9（k 代表之前某个 nums[i] 的首位数字）。
3. 如果 map[k] != 0 (即之前存在首位为 k 的数字) 并且 gcd(k, cur) == 1 (首位 k 与当前数字 x 的末位 cur 互质)，则将 map[k] 的值累加到结果 ret 中。这意味着之前所有首位为 k 的数字都与当前数字 x 构成了美丽下标对。
4. 获取当前数字 x 的首位数字 first = getFirstNum(x)。
5. 将 map[first] 的计数加 1，为后续的数字作准备。

复杂度

• 时间复杂度: $O(N\cdot \log M)$
  其中 $N$ 是数组 nums 的长度。对于 nums 中的每个元素，我们会执行一个常数次数（最多9次）的 gcd 运算。gcd(a, b) 的时间复杂度是 $O(\log (\min (a,b)))$，但在这里 a 和 b 都是个位数，所以 gcd 操作可以近似看作 $O(1)$。getFirstNum(x) 操作的时间复杂度是 $O({\log }_{10}x)$，即 $O(\log M)$，其中 $M$ 是 nums 中元素的最大值。因此，总体时间复杂度为 $O(N\cdot (\text{constant}+\log M))\approx O(N\log M)$。
• 辅助空间复杂度: $O(N)$

Code

class Solution {public int countBeautifulPairs(int[] nums) {int ret = 0;int[] map = new int[10]; // map[d] 存储已遍历过的数字中，首位是 d 的数字个数for (int x : nums) {int lastDigitOfX = x % 10;// 遍历所有可能的首位数字 (1-9)for (int firstDigitOfPrev = 1; firstDigitOfPrev < 10; firstDigitOfPrev++) {if (map[firstDigitOfPrev] != 0) { // 如果存在首位是 firstDigitOfPrev 的数字if (gcd(firstDigitOfPrev, lastDigitOfX) == 1) {ret += map[firstDigitOfPrev];}}}int firstDigitOfX = getFirstNum(x);map[firstDigitOfX]++;}return ret;}// 获取数字 x 的最高位private int getFirstNum(int x) {while (x >= 10) {x /= 10;}return x;}private int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}
}

---

881. 救生艇（复习）

题目

这是第二次写这道题，写的还不错，基本上掌握了，就不再多说了，详细题解见每日算法-250428

代码

class Solution {public int numRescueBoats(int[] people, int limit) {Arrays.sort(people);int ret = 0;int left = 0, right = people.length - 1; while (left <= right) {if (people[right] + people[left] <= limit) {left++;}ret++;right--;}return ret;}
}

---

20. 有效的括号（复习）

题目

很久之前的一道题目了，现在再写已经算是掌握了，也不再多说了，详细题解见每日算法-250329

代码

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else {if (stack.isEmpty()) { // 右括号多于左括号return false;}char topChar = stack.peek();if (c == ')' && topChar != '(') {return false;}if (c == ']' && topChar != '[') {return false;}if (c == '}' && topChar != '{') {return false;}stack.pop(); // 匹配成功，弹出栈顶左括号}}return stack.isEmpty(); // 如果栈为空，说明所有括号都匹配了}
}

---