共计 2559 个字符，预计需要花费 7 分钟才能阅读完成。
【NO.1 值相等的最小索引】
解题思路
签到题。
代码展现
class Solution {
public int smallestEqual(int[] nums) {
for (int i = 0; i < nums.length; i++) {if (i % 10 == nums[i]) {return i;}
}
return -1;}
}
【NO.2 找出临界点之间的最小和最大间隔】
解题思路
遍历链表即可。
代码展现
class Solution {
public int[] nodesBetweenCriticalPoints(ListNode head) {
if (head.next == null) {return new int[]{-1, -1};
}
List<Integer> pos = new ArrayList<>();
int last = head.val;
int p = 1;
for (ListNode i = head.next; i.next != null; i = i.next) {if (last < i.val && i.next.val < i.val) {pos.add(p);
} else if (i.val < last && i.val < i.next.val) {pos.add(p);
}
last = i.val;
p++;
}
if (pos.size() < 2) {return new int[]{-1, -1};
}
int[] res = new int[]{pos.get(1) - pos.get(0), pos.get(pos.size() - 1) - pos.get(0)};
for (int i = 2; i < pos.size(); i++) {int dis = pos.get(i) - pos.get(i - 1);
res[0] = Math.min(res[0], dis);
}
return res;}
}
【NO.3 转化数字的最小运算数】
解题思路
相当于 BFS 求最短路，为了进步运算速度，应用一个长度为 2001 的数组贮存 [-1000, 1000] 范畴内的数字，从 start 达到它们的最小步数。
因为题目规定，绝对值超过 1000 的数字不能持续运算，所以无需贮存达到这些数字的最小步数。
代码展现
class Solution {
public int minimumOperations(int[] nums, int start, int goal) {
int[] min = new int[2001];
Arrays.fill(min, 0x7fffffff);
min[start + 1000] = 0;
LinkedList<Integer> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {int cur = queue.poll();
int dis = min[cur + 1000] + 1;
for (int i : nums) {
int nxt = cur + i;
if (nxt == goal) {return dis;} else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {min[nxt + 1000] = dis;
queue.add(nxt);
}
}
for (int i : nums) {
int nxt = cur - i;
if (nxt == goal) {return dis;} else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {min[nxt + 1000] = dis;
queue.add(nxt);
}
}
for (int i : nums) {
int nxt = cur ^ i;
if (nxt == goal) {return dis;} else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {min[nxt + 1000] = dis;
queue.add(nxt);
}
}
}
return -1;}
}
【NO.4 同源字符串检测】
解题思路
动静布局，细节见正文。
代码展现
class Solution {
public boolean possiblyEquals(String s1, String s2) {
// f[i][j] 示意 s1 的前 i 个字符和 s2 的前 j 个字符匹配时可能的长度差
Set<Integer>[][] f = new Set[41][41];
for (int i = 0; i <= 40; i++) {for (int j = 0; j <= 40; j++) {f[i][j] = new HashSet<>();}
}
int n = s1.length();
int m = s2.length();
f[0][0].add(0); // 初始化 f[0][0] = {0}
for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {for (Integer diff : f[i][j]) {// 当 s1[i] 为字母，且目前 s2 比 s1 长的时候，该字母能够间接被 s2 中的数字消化掉
if (i < n && !Character.isDigit(s1.charAt(i)) && diff < 0) {f[i + 1][j].add(diff + 1);
}
// 当 s2[j] 为字母，且目前 s1 比 s2 长的时候，该字母能够间接被 s1 中的数字消化掉
if (j < m && !Character.isDigit(s2.charAt(j)) && diff > 0) {f[i][j + 1].add(diff - 1);
}
// 当 s1[i] == s2[j] 且都为字母时，必须齐全匹配（即要求 diff == 0）if (i < n && j < m && s1.charAt(i) == s2.charAt(j) && !Character.isDigit(s1.charAt(i)) && diff == 0) {f[i + 1][j + 1].add(0);
}
// 枚举 s1[i:] 的数字，退出到汇合中
for (int o = i, p = 0; o < n && Character.isDigit(s1.charAt(o)); o++) {p = p * 10 + (s1.charAt(o) - '0');
f[o + 1][j].add(diff + p);
}
// 枚举 s2[j:] 的数字，退出到汇合中
for (int o = j, p = 0; o < m && Character.isDigit(s2.charAt(o)); o++) {p = p * 10 + (s2.charAt(o) - '0');
f[i][o + 1].add(diff - p);
}
}
}
}
return f[n][m].contains(0);}
}
正文完