上岸算法LeetCode Weekly Contest 281解题报告
【 NO.1 Count Integers With Even Digit Sum】解题思路
签到题,枚举计算即可。
代码展示
class Solution {
public int countEven(int num) {
int res = 0;
for (int i = 1; i <= num; i++) {
if (digitsSum(i) % 2 == 0) {
res++;
}
}
return res;
}
private int digitsSum(int num) {
int res = 0;
for (; num > 0; num /= 10) {
res += num % 10;
}
return res;
}
}
【 NO.2 Merge Nodes in Between Zeros】
解题思路
遍历链表即可。
代码展示
class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode res = new ListNode(0);
ListNode tail = res;
int sum = 0;
for (ListNode cur = head.next; cur != null; cur = cur.next) {
sum += cur.val;
if (cur.val == 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
}
}
return res.next;
}
}
【 NO.3 Merge Nodes in Between Zeros】
解题思路
注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。
代码展示
class Solution {
public String repeatLimitedString(String s, int repeatLimit) {
int[] cnt = new int;
for (char c : s.toCharArray()) {
cnt++;
}
StringBuilder sb = new StringBuilder();
int repeat = 0;
char cur = 0;
for (int i = 0; i < s.length(); i++) {
char c;
if (repeat == repeatLimit) {
repeat = 1;
c = poll(cnt, cur);
cur = c;
} else {
c = poll(cnt, (char) 0);
if (c == cur) {
repeat++;
} else {
repeat = 1;
cur = c;
}
}
if (c == 0) {
break;
}
sb.append(c);
}
return sb.toString();
}
private char poll(int[] cnt, char not) {
for (int i = 25; i >= 0; i--) {
if (cnt > 0 && not != (char) (i + 'a')) {
cnt--;
return (char) (i + 'a');
}
}
return 0;
}
}
【 NO.4 Count Array Pairs Divisible by K】
解题思路
预处理转换成最大公因数,详见注释。
代码展示
class Solution {
public long coutPairs(int[] nums, int k) {
// 将 nums 转换成与 k 的最大公约数
// 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)
for (int i = 0; i < nums.length; i++) {
nums = gcd(nums, k);
}
long res = 0;
int[] cnt = new int; // cnt 表示因数 i 的出现次数
for (int num : nums) {
// 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数
res += cnt;
// 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt++
for (int j = 1; j * j <= num; j++) {
if (num % j == 0) {
cnt++;
if (j * j != num) {
cnt++;
}
}
}
}
return res;
}
int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
}
页:
[1]