一、引言
10点起床，等到10:30，刚想打周赛，力扣弹出：502 Bad Gateway Error
这是不是说明，最近程序员都在学习算法，人员太多把力扣网关搞崩溃了
后来，力扣恢复了正常，本来想着放弃这场周赛
后来想了想，还是打了算了
二、6012. 统计各位数字之和为偶数的整数个数
1、题目简介
2、题目解析
- 签到题目
- 直接暴力枚举
1 ~ num每个位置的数字是符合相加为偶数
3、题目代码
class Solution { public int countEven(int num) { int sum = 0; for(int i = 1; i <= num; i++){ if(f(i)){ sum++; } } return sum; } public boolean f(int n){ int sum = 0; while(n != 0){ sum = sum + n % 10; n = n / 10; } return sum % 2 == 0 ? true : false; } }
三、6013. 合并零之间的节点
1、题目简介
2、题目解析
- 链表模拟题目
- 我们需要遍历整个链表，将两个
ListNode.val == 0中间的数字进行相加
- 形成一个新的链表
3、题目代码
class Solution { public ListNode mergeNodes(ListNode head) { ListNode p1 = new ListNode(0); ListNode p2 = p1; ListNode newHead = head.next; int sum = 0; while(newHead != null){ if(newHead.val == 0){ ListNode next = new ListNode(sum); p2.next = next; p2 = p2.next; sum = 0; }else{ sum = sum + newHead.val; } newHead = newHead.next; } return p1.next; } }
四、6014. 构造限制重复的字符串
1、题目简介
2、题目解析
- 字符串贪心题目
- 我们最终形成的字符串需要满足字典序最大（
z > f > a），并且连续的字符不能超过repeatLimit - 我们整理出每一个字符出现的次数，将其放入优先队列中，优先队列按照
字符的大小排序
- 我们每一次贪心都去拿字典序最大的
- 如果字典序最大的字符的数量小于
repeatLimit，直接拿走最大的字符，队列中poll() - 如果字典序最大的字符的数量大于
repeatLimit，拿走repeatLimit个最大的字符，并且查看一下次大的字符，取一个
- 记得需要判断当前的字符是否连续出现过
repeatLimit次：if (stringBuffer.length() != 0 && val[0] + 'a' == stringBuffer.charAt(stringBuffer.length() - 1))
3、题目代码
class Solution { public String repeatLimitedString(String s, int repeatLimit) { PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o2[0] - o1[0]; } }); int[] arr = new int[26]; for (int i = 0; i < s.length(); i++) { arr[s.charAt(i) - 'a']++; } for (int i = 0; i < 26; i++) { if (arr[i] != 0) { priorityQueue.add(new int[]{i, arr[i]}); } } StringBuffer stringBuffer = new StringBuffer(); while (!priorityQueue.isEmpty()) { int[] val = priorityQueue.peek(); if (stringBuffer.length() != 0 && val[0] + 'a' == stringBuffer.charAt(stringBuffer.length() - 1)) { return stringBuffer.toString(); } if (val[1] <= repeatLimit) { stringBuffer.append(f(val[0], val[1])); priorityQueue.poll(); } else { stringBuffer.append(f(val[0], repeatLimit)); int[] first = priorityQueue.poll(); if (priorityQueue.isEmpty()) { return stringBuffer.toString(); } else { int[] sed = priorityQueue.peek(); if (sed[1] > 0) { stringBuffer.append(f(sed[0], 1)); priorityQueue.poll(); first[1] = first[1] - repeatLimit; sed[1] = sed[1] - 1; if (first[1] >= 1) { priorityQueue.add(first); } if (sed[1] >= 1) { priorityQueue.add(sed); } } } } } return stringBuffer.toString(); } public String f(int num, int value) { StringBuffer stringBuffer = new StringBuffer(); for (int i = 0; i < value; i++) { stringBuffer.append((char) (num + 'a')); } return stringBuffer.toString(); } }
五、6015. 统计可以被 K 整除的下标对数目
1、题目简介
2、题目解析
- 题面相对简介，题目十分困难本题考了数论，
如果 x * y % k == 0，那么 gcd(x, k) * gcd(y, k) % k == 0 - 解析证明见：证明地址
- 这样的话，我们可以把数组中每个值与
K的gcd求出来，放入Map中
for(Integer key1 : map.keySet()){ for(Integer key2 : map.keySet()){ // 这里需要注意:key1 * key2 会超越int的范围,需要转换为long if((long)key1 * (long)key2 % k == 0 && key1 <= key2){ // 逻辑处理 } } }
为了避免重复，我们这里只考虑 key1 <= key2
- 如果
key1 == key2，那么count = count + value1 * (value2 - 1) / 2;
- 如果
key1 < key2，那么count = count + value1 * value2;
- 最终返回
count即可
3、题目代码
class Solution { public long coutPairs(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); for(int num : nums){ int value = gcd(num, k); map.put(value, map.getOrDefault(value, 0) + 1); } long count = 0; for(Integer key1 : map.keySet()){ for(Integer key2 : map.keySet()){ // 这里需要注意:key1 * key2 会超越int的范围,需要转换为long if(key1 <= key2 && (long)key1 * (long)key2 % k == 0){ // 同样,value1 * value2 也会越int的界,需要转换为long long value1 = (long)map.get(key1); long value2 = (long)map.get(key2); if(key1 < key2){ count = count + value1 * value2; }else{ count = count + value1 * (value2 - 1) / 2; } } } } return count; } public int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
