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;}
}
}
}
}