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

上岸算法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]
查看完整版本: 上岸算法LeetCode Weekly Contest 281解题报告