You are given an integer R, and an
Constraints
2 ≤ N ≤ 10⁵(N is length of array)1 ≤ R ≤ 10⁵1 ≤ Ai ≤ 10⁵
Example 1
Input:
R = 10
A = [2, 3, 4]Output:
2Explanation: We can change the second element from 3 to 2. Then GCD of the array becomes gcd(2,2,4)=2, which is the maximum possible.
解法
允许把数组中至多一个元素改成不超过 R 的任意值，求最大可能 GCD。枚举候选 g(g 是答案，必整除剩余 n-1 个元素)，用前后缀 GCD 之差找出「跳过一个位置的 GCD」，对每个位置算 gcd(prefix[i-1], suffix[i+1])，要求这个值 g 也满足 g ≤ R(这样存在不超过 R 的值替换)。取最大即可。时间 O(n log V)，空间 O(n)。
from math import gcd
from typing import List
def findMaximumPossibleGCD(R: int, A: List[int]) -> int:
n = len(A)
pref = [0] * n
suf = [0] * n
pref[0] = A[0]
for i in range(1, n):
pref[i] = gcd(pref[i - 1], A[i])
suf[n - 1] = A[n - 1]
for i in range(n - 2, -1, -1):
suf[i] = gcd(suf[i + 1], A[i])
best = gcd(pref[n - 1], 0)
for i in range(n):
if i == 0:
g = suf[1]
elif i == n - 1:
g = pref[n - 2]
else:
g = gcd(pref[i - 1], suf[i + 1])
if g <= R:
best = max(best, g)
return bestclass Solution {
int findMaximumPossibleGCD(int R, int[] A) {
int n = A.length;
int[] pref = new int[n], suf = new int[n];
pref[0] = A[0];
for (int i = 1; i < n; i++) pref[i] = gcd(pref[i - 1], A[i]);
suf[n - 1] = A[n - 1];
for (int i = n - 2; i >= 0; i--) suf[i] = gcd(suf[i + 1], A[i]);
int best = 0;
for (int i = 0; i < n; i++) {
int g;
if (i == 0) g = suf[1];
else if (i == n - 1) g = pref[n - 2];
else g = gcd(pref[i - 1], suf[i + 1]);
if (g <= R) best = Math.max(best, g);
}
return best;
}
private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}#include <vector>
#include <numeric>
#include <algorithm>
class Solution {
public:
int findMaximumPossibleGCD(int R, std::vector<int>& A) {
int n = A.size();
std::vector<int> pref(n), suf(n);
pref[0] = A[0];
for (int i = 1; i < n; i++) pref[i] = std::gcd(pref[i - 1], A[i]);
suf[n - 1] = A[n - 1];
for (int i = n - 2; i >= 0; i--) suf[i] = std::gcd(suf[i + 1], A[i]);
int best = 0;
for (int i = 0; i < n; i++) {
int g;
if (i == 0) g = suf[1];
else if (i == n - 1) g = pref[n - 2];
else g = std::gcd(pref[i - 1], suf[i + 1]);
if (g <= R) best = std::max(best, g);
}
return best;
}
};Given two strings str1 and str2 containing only 0s and 1s, there are steps to change str1 to str2:
Find a substring of str1 of length 2 and reverse it, resulting in str1' (where str1' ≠ str1).
Find a substring of str1' of length 3, reverse it, resulting in str1'' (where str1'' ≠ str1').
Repeat similar steps.
String length ranges from 2 to 30.
Requirements:
Each step must be performed once, and you cannot skip previous steps to perform the next step.
If it's possible to change str1 to str2, output the minimum required steps. Otherwise, output -1.
Constraints
N/A
Example 1
Input:
str1 = "1010"
str2 = "0011"Output:
2Explanation: Steps:
- Choose substring in range [2, 3]: "1010" → "1001"
- Choose substring in the range [0, 2]: "1001" → "0011"
Example 2
Input:
str1 = "1001"
str2 = "0110"Output:
-1Explanation:
It's impossible to change str1 to str2.
Example 3
Input:
str1 = "10101010"
str2 = "00101011"Output:
7Explanation:
The minimum steps required to change str1 to str2 is 7.
解法
BFS 模拟：状态是当前字符串与已执行的步骤数 k(下一次要反转长度 k+2 的子串)。从 str1 出发，每次枚举所有长度为 k+2 的子串反转后形成的新状态，直到达到 str2 或步数超过合理上限(如 |s|+5)。注意「每一步反转后必须与上一步不同」。状态空间最坏 O(2^n)，n ≤ 30 但通常剪枝充分。
from collections import deque
def minimumStepsRequired(str1: str, str2: str) -> int:
if str1 == str2:
return 0
if sorted(str1) != sorted(str2):
return -1
n = len(str1)
# state: (s, step_idx) — next reverse length = step_idx + 2
visited: set[tuple[str, int]] = {(str1, 0)}
q: deque[tuple[str, int]] = deque([(str1, 0)])
max_steps = min(n * 2, 30)
while q:
s, step = q.popleft()
rev_len = step + 2
if rev_len > n:
continue
for start in range(n - rev_len + 1):
new_s = s[:start] + s[start:start + rev_len][::-1] + s[start + rev_len:]
if new_s == s:
continue
new_step = step + 1
if new_s == str2:
return new_step
if new_step >= max_steps:
continue
key = (new_s, new_step)
if key not in visited:
visited.add(key)
q.append(key)
return -1import java.util.*;
class Solution {
int minimumStepsRequired(String str1, String str2) {
if (str1.equals(str2)) return 0;
char[] a = str1.toCharArray(), b = str2.toCharArray();
Arrays.sort(a); Arrays.sort(b);
if (!Arrays.equals(a, b)) return -1;
int n = str1.length();
int maxSteps = Math.min(n * 2, 30);
Set<String> visited = new HashSet<>();
visited.add(str1 + "#0");
Queue<Object[]> q = new ArrayDeque<>();
q.offer(new Object[]{str1, 0});
while (!q.isEmpty()) {
Object[] cur = q.poll();
String s = (String) cur[0];
int step = (int) cur[1];
int revLen = step + 2;
if (revLen > n) continue;
for (int start = 0; start + revLen <= n; start++) {
StringBuilder sb = new StringBuilder(s);
sb.reverse();
String mid = new StringBuilder(s.substring(start, start + revLen)).reverse().toString();
String ns = s.substring(0, start) + mid + s.substring(start + revLen);
if (ns.equals(s)) continue;
int nStep = step + 1;
if (ns.equals(str2)) return nStep;
if (nStep >= maxSteps) continue;
String key = ns + "#" + nStep;
if (visited.add(key)) q.offer(new Object[]{ns, nStep});
}
}
return -1;
}
}#include <string>
#include <queue>
#include <unordered_set>
#include <algorithm>
class Solution {
public:
int minimumStepsRequired(std::string str1, std::string str2) {
if (str1 == str2) return 0;
std::string a = str1, b = str2;
std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end());
if (a != b) return -1;
int n = str1.size();
int maxSteps = std::min(n * 2, 30);
std::unordered_set<std::string> visited;
visited.insert(str1 + "#0");
std::queue<std::pair<std::string, int>> q;
q.push({str1, 0});
while (!q.empty()) {
auto [s, step] = q.front(); q.pop();
int revLen = step + 2;
if (revLen > n) continue;
for (int start = 0; start + revLen <= n; start++) {
std::string ns = s;
std::reverse(ns.begin() + start, ns.begin() + start + revLen);
if (ns == s) continue;
int nStep = step + 1;
if (ns == str2) return nStep;
if (nStep >= maxSteps) continue;
std::string key = ns + "#" + std::to_string(nStep);
if (visited.insert(key).second) q.push({ns, nStep});
}
}
return -1;
}
};