力扣 LeetCode-CN 第30场双周赛

华为云博客 技术博客 20378 36

最终成绩：

result

起因

最近一个多月自己有在坚持刷leetcode的每日一题，这次终于鼓起勇气参加了一场双周赛，用大佬的话说这场比赛就是手速赛，所以4道题都AK的人数很多。无聊刷起讨论区看到各位大佬都在讨论，想把第一次参赛的经历记录下来，因为Leetcode周赛和双周赛题目都比较新，所以能混个热搜什么的也挺好的嘤嘤嘤。

正文

5177. 转变日期格式 - E

题目内容: :https://leetcode-cn.com/problems/reformat-date/
思路:
典型的手速题，日期时间转换，很多cpp大佬在这道题上纷纷投向了js的怀抱。
解题代码：

public static String reformatDate(String date) { String[] s = date.split(" "); int day = processDay(s[0]); Map<String, Integer> monthMap = new HashMap<>(); monthMap.put("Jan", 1); monthMap.put("Feb", 2); monthMap.put("Mar", 3); monthMap.put("Apr", 4); monthMap.put("May", 5); monthMap.put("Jun", 6); monthMap.put("Jul", 7); monthMap.put("Aug", 8); monthMap.put("Sep", 9); monthMap.put("Oct", 10); monthMap.put("Nov", 11); monthMap.put("Dec", 12); int month = monthMap.get(s[1]); String ms = fillZero(month); int year = Integer.parseInt(s[2]); String ds = fillZero(day); return year + "-" + ms + "-" + ds;
  } private static String fillZero(int month) { if(month<10) { return "0" + month; } return String.valueOf(month);
  } private static int processDay(String s) { if (s.length() == 3) { return Integer.parseInt(s.substring(0, 1)); } else { return Integer.parseInt(s.substring(0, 2)); }
  }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

5445. 子数组和排序后的区间和 - M

题目内容: :https://leetcode-cn.com/problems/range-sum-of-sorted-subarray-sums/
思路:
我直接用暴力枚举+排序做出来的，没有超时但是也忘记了取模，后面有空会认真看一下其他大神的思路，毕竟刷题数量不是目的，掌握了优秀的思路才能更进一步。
解题代码：

public int rangeSum(int[] nums, int n, int left, int right) { int[] arr = new int[(n * (n + 1) / 2)]; int idx = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { arr[idx] = sum(nums, i, j); idx++; } } Arrays.sort(arr); return sum(arr, left-1, right-1);
  } private int sum(int[] nums, int start, int end) { int res = 0; for(int i=start; i<=end; i++) { res += nums[i]; } return res;
  }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

5446.三次操作后最大值与最小值的最小差 - M

题目内容: :https://leetcode-cn.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/
思路:
这道题思路比较好想，需要变化后差值最小，那么一定是要么把最大的值调整，要么是把最小的值调整，每次操作都操作一个最大值或最小值，很容易的我们想到需要先排序。至于每次操作的是最大值，还是最小值，其实取决于数组中其他数的分布情况，这里因为只需要操作三次，所以我们可以遍历各种情况，比如变动三个最小值，变动两个最小值一个最大值，变动一个最小值两个最大值，变动三个最大值。取其中最优化的结果即可。(我的代码后面的循环可以优化，进而拓展到N次操作的最大值最小值差值问题）
解题代码：

if (nums.length <= 4) { return 0; } Arrays.sort(nums); int a1 = nums[nums.length - 4] - nums[0]; int a2 = nums[nums.length - 3] - nums[1]; int a3 = nums[nums.length - 2] - nums[2]; int a4 = nums[nums.length - 1] - nums[3]; return Math.min(Math.min(a1, a2), Math.min(a3, a4));
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

5447. 石子游戏 IV - H

题目内容: :https://leetcode-cn.com/problems/stone-game-iv/
思路:
这道题可以说是非常有意思了，明显的可以用到递归或者动态规划或者记忆数组（i dont know how to call it）的思想，从只有一个石头开始，到两个石头，可以在纸上画一下前几次的结果分别是：
i=1 is true
i=2 is false
i=3 is true
i=4 is true
i=5 is false
i=6 is true
i=7 is false
i=8 is true
i=9 is true
i=10 is false
i=11 is true
i=12 is false
i=13 is true
i=14 is true
i=15 is false
i=16 is true
i=17 is false
那么我么来根据题目内容思考一下规律，以i = 17为例，Alice第一次可以拿走1, 4, 9, 16个石子，那么在拿走这些石子之后分别剩下：16, 13, 8, 1个石子，而根据计算我们已经知道了前16个石子的胜败情况，分别都是true，也就是说不管Alice怎么样拿石子，留给Bob的一定是获胜的石子，怎么样，计算i = 17的时候实际上是运用了i= 1, 8, 13, 16的结果，那么对1， 8 ，13， 16的计算也一定取决于更小的石子选择的结果。所以我们可以从1开始，只有1个石子，Alice获胜，很好，数组第一个元素已经初始化了，有2个石子，Alice只能拿1个，剩下1个给Bob，而查找之前的数组，dp[1]= true，所以Bob必胜。那么我们看i = 11的情况，i = 13的时候，Alice可以拿1, 4, 9个石子，分别留下12, 9, 4个石子给Bob，获胜情况是false, true, true，那么Alice可以选择只拿1个石子让Bob失败。也就是说，如果当前数字i是整数的平方数，那么Alice一次全拿走，必胜，否则查看Alice拿走所有平方数可能的结果，如果存在一次让Bob为false的结果，Alice就能获胜。接下来看代码：
解题代码：

public boolean winnerSquareGame(int n) { boolean[] dp = new boolean[n+1]; for(int i=1; i<=n; i++) { if(isPower(i)) { dp[i] = true; continue; } dp[i] = process(dp, i); } return dp[n];
  } private boolean process(boolean[] dp, int target) { boolean res = true; for(int i=1; i<=Math.sqrt(target)+1; i++) { // 遍历所有拿走石子的可能 if(target - i*i >0) { res = res && dp[target - i*i]; // 只要有一次为false， Alice就能获胜 } } return !res;
  } private boolean isPower(int i) { // 判断是否是平方数 for(int a =1; a<Math.sqrt(i)+1; a++) { if(a*a == i) { return true; } } return false;
  }```
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

文章来源: zclhit.blog.csdn.net，作者：zclhit_，版权归原作者所有，如需转载，请联系作者。

原文链接：zclhit.blog.csdn.net/article/details/107304395

（完）