Java | LeetCode
Задача: 247. Strobogrammatic Number II
Сложность: medium
Дано целое число n, верните все стробограмматические числа длины n. Ответ можно возвращать в любом порядке.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).
Пример:
Input: n = 2
Output: ["11","69","88","96"]
👨💻 Алгоритм:
1⃣Инициализируйте структуру данных reversiblePairs, которая содержит все пары обратимых цифр. Вызовите и верните результат рекурсивной функции generateStroboNumbers(n, finalLength), где первый аргумент указывает, что текущий вызов создаст все стробограмматические числа длиной n, а второй аргумент указывает длину конечных стробограмматических чисел, которые мы будем генерировать, и будет использоваться для проверки возможности добавления '0' в начало и конец числа.
2⃣Создайте функцию generateStroboNumbers(n, finalLength), которая вернет все стробограмматические числа длиной n:
Проверьте базовые случаи: если n == 0, верните массив с пустой строкой [""]; если n == 1, верните ["0", "1", "8"].
Вызовите generateStroboNumbers(n - 2, finalLength), чтобы получить все стробограмматические числа длиной (n-2), и сохраните их в subAns.
Инициализируйте пустой массив currStroboNums для хранения стробограмматических чисел длиной n.
3⃣Для каждого числа в subAns добавьте все reversiblePairs в начало и конец, за исключением случая, когда текущая пара '00' и n == finalLength (потому что нельзя добавить '0' в начало числа), и добавьте это новое число в currStroboNums. В конце функции верните все стробограмматические числа, т.е. currStroboNums.
😎 Решение:
import java.util.*;
class Solution {
List<List<Character>> reversiblePairs = Arrays.asList(
Arrays.asList('0', '0'), Arrays.asList('1', '1'),
Arrays.asList('6', '9'), Arrays.asList('8', '8'), Arrays.asList('9', '6')
);
public List<String> generateStroboNumbers(int n, int finalLength) {
if (n == 0) {
return Arrays.asList("");
}
if (n == 1) {
return Arrays.asList("0", "1", "8");
}
List<String> prevStroboNums = generateStroboNumbers(n - 2, finalLength);
List<String> currStroboNums = new ArrayList<>();
for (String prevStroboNum : prevStroboNums) {
for (List<Character> pair : reversiblePairs) {
if (pair.get(0) != '0' || n != finalLength) {
currStroboNums.add(pair.get(0) + prevStroboNum + pair.get(1));
}
}
}
return currStroboNums;
}
public List<String> findStrobogrammatic(int n) {
return generateStroboNumbers(n, n);
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 366 ·