【 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);

  }

}