Сложность: medium
Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.
Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.
Пример:
Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.
👨💻 Алгоритм:
1⃣Переберите все возможные начальные элементы первой и второй части последовательности, проверяя, чтобы не было ведущих нулей.
2⃣Для каждой пары начальных элементов проверяйте, можно ли продолжить последовательность Фибоначчи, создавая следующую часть, которая должна быть суммой двух предыдущих частей.
3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.
😎 Решение:
class Solution {
public:
vector<int> splitIntoFibonacci(string S) {
int N = S.length();
for (int i = 0; i < min(10, N); ++i) {
if (S[0] == '0' && i > 0) break;
long a = stol(S.substr(0, i + 1));
if (a >= INT_MAX) break;
for (int j = i + 1; j < min(i + 10, N); ++j) {
if (S[i + 1] == '0' && j > i + 1) break;
long b = stol(S.substr(i + 1, j - i));
if (b >= INT_MAX) break;
vector<int> fib = {(int)a, (int)b};
int k = j + 1;
while (k < N) {
long nxt = (long)fib[fib.size() - 2] + fib[fib.size() - 1];
if (nxt > INT_MAX) break;
string nxtS = to_string(nxt);
if (S.substr(k).find(nxtS) == 0) {
k += nxtS.length();
fib.push_back((int)nxt);
} else {
break;
}
}
if (fib.size() >= 3) return fib;
}
}
return {};
}
};Ставь 👍 и забирай 📚 Базу знаний