T1: 温度转换
思路：模拟
public double[] convertTemperature(double celsius) {
return new double[]{celsius + 273.15, celsius * 1.80 + 32.00};
}
T2: 最小公倍数为 K 的子数组数目
思路：暴力枚举
- 关键在于如何高效求得两个数字的最小公倍数
最小公倍数 = a × b ÷ 最大公约数
使用辗转相除法求最大公约数
// 辗转相除法求最大公约数
public int gcd(int a, int b) {
if (a == 0) {
return b;
}
return gcd(b % a, a);
}
public int lcm(int a, int b) {
return a * b / (gcd(a, b));
}
public int subarrayLCM(int[] nums, int k) {
int res = 0;
// 暴力枚举所有子数组
for (int i = 0; i < nums.length; i++) {
if (nums[i] > k) {
continue;
}
int temp = 1;
for (int j = i; j < nums.length; j++) {
temp = lcm(temp, nums[j]);
// 剪枝条件
if (k % temp != 0) {
break;
}
if (temp == k) {
res += 1;
}
}
}
return res;
}
T3: 逐层排序二叉树所需的最少操作数目
本题解答参考学习 灵茶山艾府 大佬的题解。
思路：宽度优先搜索 + 置换环
本题抽象出来就是使得每一层数组元素有序的最小交换次数，该问题的做法是置换环。
如何寻找置换环：将这个数字当成下标去访问数组中的元素，不断循环直到回到这个数本身。对于每个置换环，需要的交换次数是 size - 1
public int minimumOperations(TreeNode root) {
//BFS
int res = 0;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
arr[i] = node.val;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res += exchangeTimes(arr);
}
return res;
}
public int exchangeTimes(int[] arr) {
int count = 0;
// key: arr 元素值
// value: 对应元素应该放置的下标
Map<Integer, Integer> map = new HashMap<>();
int[] copy = Arrays.copyOf(arr, arr.length);
Arrays.sort(copy);
for (int i = 0; i < copy.length; i++) {
map.put(copy[i], i);
}
// 标记数组，表示下标为 i 的元素是否已被访问过
boolean[] flags = new boolean[arr.length];
for (int i = 0; i < arr.length; i++) {
if (!flags[i]) {
int j = i;
while (!flags[j]) {
flags[j] = true;
j = map.get(arr[j]);
}
count += 1;
}
}
return arr.length - count;
}
T4: 不重叠回文子字符串的最大数目
思路：中心拓展 + 动态规划
中心拓展方法枚举回文子串的中心位置
若子串 s[left, right] 是回文串，则 \(dp[right + 1] = Max(dp[right + 1], dp[left] + 1)\)
中心拓展枚举回文中心方法介绍
长度为 n 的字符串会生成 2n - 1 组回文中心 \([left_i, right_i]\)，其中 \(left_i = i / 2, right_i = i / 2 + i \% 2\)
所以，在 0 ~ 2n-2 范围内遍历，即可得到所有可能的回文中心
public int maxPalindromes(String s, int k) {
char[] arr = s.toCharArray();
int n = arr.length;
int[] dp = new int[n + 1];
// 中心拓展枚举回文子串
for (int i = 0; i < 2 * n - 1; i++) {
int left = i / 2;
int right = i / 2 + i % 2;
dp[left + 1] = Math.max(dp[left + 1], dp[left]);
while (left >= 0 && right < n && arr[left] == arr[right]) {
if (right - left + 1 >= k) {
dp[right + 1] = Math.max(dp[right + 1], dp[left] + 1);
}
left -= 1;
right += 1;
}
}
return dp[n];
