Java | LeetCode
Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium
Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.
Пример:
Input: n = 2, start = 3
Output: [3,2,0,1]
👨💻 Алгоритм:
1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1
2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.
3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.
😎 Решение:
import java.util.*;
public class Solution {
public List<Integer> circularPermutation(int n, int start) {
List<Integer> gray = grayCode(n);
int startIndex = gray.indexOf(start);
List<Integer> result = new ArrayList<>();
result.addAll(gray.subList(startIndex, gray.size()));
result.addAll(gray.subList(0, startIndex));
return result;
}
private List<Integer> grayCode(int n) {
List<Integer> result = new ArrayList<>();
int numElements = 1 << n;
for (int i = 0; i < numElements; i++) {
result.add(i ^ (i >> 1));
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 523 ·