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.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理