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

上岸算法 · 发表于 2022-2-20 16:59:15

登录后可回复主题

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

x

【 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[26];
   for (char c : s.toCharArray()) {
         cnt[c - 'a']++;
   }

   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[i] > 0 && not != (char) (i + 'a')) {
            cnt[i]--;
            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[i] = gcd(nums[i], k);
   }
   long res = 0;
   int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
   for (int num : nums) {
         // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数
         res += cnt[k / num];

         // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++
         for (int j = 1; j * j <= num; j++) {
            if (num % j == 0) {
               cnt[j]++;
               if (j * j != num) {
                     cnt[num / j]++;
               }
            }
      }
   }
   return res;
  }

int gcd(int a, int b) {
   return a % b == 0 ? b : gcd(b, a % b);
  }
}

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

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

登录后可回复主题