Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.
Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.
Пример:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.
C# решение
сопоставлено/оригиналpublic class Solution {
public int BinaryGap(int N) {
int[] A = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
A[t++] = i;
int ans = 0;
for (int i = 0; i < t - 1; ++i)
ans = Math.Max(ans, A[i + 1] - A[i]);
return ans;
}
}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 int BinaryGap(int N) {
vector<int>& A = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
A[t++] = i;
int ans = 0;
for (int i = 0; i < t - 1; ++i)
ans = max(ans, A[i + 1] - A[i]);
return ans;
}
}Java решение
сопоставлено/оригиналclass Solution {
public int binaryGap(int N) {
int[] A = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
A[t++] = i;
int ans = 0;
for (int i = 0; i < t - 1; ++i)
ans = Math.max(ans, A[i+1] - A[i]);
return ans;
}
}Python решение
сопоставлено/оригиналclass Solution:
def binaryGap(self, N: int) -> int:
A = [i for i in range(32) if (N >> i) & 1]
return max((A[i + 1] - A[i] for i in range(len(A) - 1)), default=0)Go решение
сопоставлено/оригиналfunc binaryGap(N int) int {
A, t := make([]int, 0, 32), 0
for i := 0; i < 32; i++ {
if (N>>i)&1 != 0 {
A = append(A, i)
t++
}
}
ans := 0
for i := 0; i < t-1; i++ {
if A[i+1]-A[i] > ans {
ans = A[i+1] - A[i]
}
}
return ans
}Algorithm
1⃣Создайте список A индексов i, таких что в двоичном представлении числа n i-й бит установлен в 1.
2⃣Используйте список A, чтобы найти максимальное расстояние между соседними значениями. Для этого пройдите по списку и вычислите разницу между каждым соседним элементом.
3⃣Верните найденное максимальное расстояние.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.