No.1设计Goal解析器
解题思路
详情见下方代码注解。
代码展现
class Solution { public String interpret(String command) { command = command.replaceAll("\\(\\)", "o"); command = command.replaceAll("\\(al\\)", "al"); return command; }}No.2 K和数对的最大数目
解题思路
应用 Map 统计每个数值的呈现次数, 而后匹配即可. 为了防止反复, Map 中贮存大于 k/2 的, 而之后枚举的是小于 k/2 的.
代码展现
class Solution { public int maxOperations(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); int halfk = 0; for (int num : nums) { if (num * 2 > k) { count.put(num, count.getOrDefault(num, 0) + 1); } else if (num * 2 == k) { halfk++; } } Arrays.sort(nums); int res = halfk / 2; for (int num : nums) { if (num * 2 > k) { break; } if (count.getOrDefault(k - num, 0) > 0) { res++; count.put(k - num, count.get(k - num) - 1); } } return res; }}No.3 连贯间断二进制数字
解题思路
从 n 到 1 一一拼接计算加和即可. 往一个数字 i 的二进制前拼接一个 0 不影响大小, 拼接一个 1 相当于加上一个 2 的幂.
代码展现
class Solution { final int mod = 1000000007; public int concatenatedBinary(int n) { int res = 0; int pow2 = 1; for (int i = n; i >= 1; i--) { for (int j = i; j > 0; j >>= 1) { if ((j & 1) == 1) { res = (res + pow2) % mod; } pow2 = (pow2 << 1) % mod; } } return res; }}No.4最小不兼容性
解题思路
解决该题目的通用办法就是深度优先搜寻. 别离枚举每个数字要放到哪个组中.
然而须要加一些优化, 否则会超时.
代码展现
class Solution { int res, k, cnt; int[] idx, latest, first, nums; public int minimumIncompatibility(int[] nums, int k) { if (nums.length == k) { return 0; } // 判断无解 int[] numCnt = new int[17]; for (int num : nums) { if ((++numCnt[num]) > k) { return -1; } } Arrays.sort(nums); this.k = k; this.nums = nums; cnt = nums.length / k; res = Integer.MAX_VALUE; idx = new int[k]; latest = new int[k]; first = new int[k]; dfs(0, 0); return res; } private void dfs(int used, int sum) { if (used == nums.length) { res = Math.min(res, sum); return; } // 优化点 if (sum >= res) { return; } // 枚举 nums[used] 放到哪一组中 for (int i = 0; i < k; i++) { if (idx[i] < cnt && (idx[i] == 0 || latest[i] != nums[used])) { int newSum = sum; if (idx[i] == 0) { first[i] = nums[used]; } else { newSum -= latest[i] - first[i]; newSum += nums[used] - first[i]; } idx[i]++; int bak = latest[i]; latest[i] = nums[used]; dfs(used + 1, newSum); idx[i]--; latest[i] = bak; // 优化点: 第一个数值, 没有必要持续枚举 if (idx[i] == 0) { break; } } } }}