1238. Circular Permutation in Binary Representation

LeetCode medium оригинал: C# #bit-manipulation #csharp #leetcode #medium

LeetCode Static

Даны 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]

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public IList<int> CircularPermutation(int n, int start) {
        var gray = GrayCode(n);
        int startIndex = gray.IndexOf(start);
        var result = new List<int>();
        result.AddRange(gray.Skip(startIndex));
        result.AddRange(gray.Take(startIndex));
        return result;
    }
    private List<int> GrayCode(int n) {
        var result = new List<int>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.Add(i ^ (i >> 1));
        }
        return result;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> CircularPermutation(int n, int start) {
        var gray = GrayCode(n);
        int startIndex = gray.IndexOf(start);
        var result = new List<int>();
        result.AddRange(gray.Skip(startIndex));
        result.AddRange(gray.Take(startIndex));
        return result;
    }
    private List<int> GrayCode(int n) {
        var result = new List<int>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.push_back(i ^ (i >> 1));
        }
        return result;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public List<int> CircularPermutation(int n, int start) {
        var gray = GrayCode(n);
        int startIndex = gray.IndexOf(start);
        var result = new List<int>();
        result.AddRange(gray.Skip(startIndex));
        result.AddRange(gray.Take(startIndex));
        return result;
    }
    private List<int> GrayCode(int n) {
        var result = new List<int>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}

Algorithm

Генерация Грей-кода:

Генерация Грей-кода для чисел от 0 до 2𝑛−1

Определение начальной позиции:

Находим индекс числа start в последовательности Грей-кода.

Построение перестановки:

Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.