我的 Binary Gap 代码解决方案是否正确？在这方面我应该改进什么？
Is my code solution for Binary Gap is correct or not? What should I improved in that?
正整数N中的二进制间隙是N的二进制表示中两端被1包围的连续零的任何最大序列。
例如，数字 9 的二进制表示为 1001，包含长度为 2 的二进制间隙。数字 529 的二进制表示为 1000010001，包含两个二进制间隙：一个长度为 4，一个长度为 3。数字 20 有二进制表示 10100，包含一个长度为 1 的二进制间隙。数字 15 的二进制表示为 1111，没有二进制间隙。
写一个函数：
int 解决方案（int N）；
也就是说，给定一个正整数 N，returns 是其最长二进制间隙的长度。如果 N 不包含二进制间隙，则函数应 return 0。
例如，给定 N = 1041，函数应 return 5，因为 N 的二进制表示形式为 10000010001，因此其最长的二进制间隙长度为 5。
public int solution(int n) {
// write your code in Java SE 8
String binaryRep = Integer.toBinaryString(n);
System.out.println("Binary Representation of " + n + " = " + binaryRep);
List<String> strList = new ArrayList<String>();
int count = 0;
for (int i = 0; i < binaryRep.length(); i++) { // Loop through the each number
String str = binaryRep.charAt(i) + ""; // getting one by one number
if(str.equals("0")){
for(int j = i;j<binaryRep.length();j++){ //Get each next element
String str1 = binaryRep.charAt(j) + "";
if(!str.equals("1") && str.equals(str1)){
if(!strList.isEmpty() && count >= strList.size()){
strList.add(str1);
}else if(strList.isEmpty()){
strList.add(str1);
}
count ++;
}else{
count = 0;
break;
}
}
}
}
return strList.size();
}
不需要将二进制字符串的内容放入数组中（当然除非这是一个要求），只需遍历字符串本身并使用 String.substring() 方法检索字符串表示每个二进制数字的值，如：
String digit = binaryString.substring(i, i+1);
这一切都归结为计算 0 的数量 在 任何一组 1 之间，并通过使用整数数据类型变量跟踪那些 0，每次 0 时递增遇到了。每次遇到 1 时，相同的变量都会重置为 0，但在重置之前，您可以将它与另一个预定义的整数变量进行比较，该变量将保存遇到的 0 中最长的 运行，例如：
if(binaryString.substring(i, i+1).equals("1")) {
if (zeroHit > longest) { longest = zeroHit; }
zeroHit = 0;
}
else { zeroHit++; }
整个方法可能看起来像这样：
private static int solution(int intValue) {
String binaryString = Integer.toBinaryString(intValue);
int zeroHit = 0;
int longest = 0;
for (int i = 0; i < binaryString.length(); i++) {
if(binaryString.substring(i, i+1).equals("1")) {
if (zeroHit > longest) { longest = zeroHit; }
zeroHit = 0;
}
else { zeroHit++; }
}
return longest;
}
我还没有测试你的代码，但如果你的目标只是计算最长的时间，那么效率似乎很低'binary gap'。
您的代码中的问题：
- 当它可以是
char 时，就变成了 java.lang.String。制作对象比制作基本类型慢得多。
- 当它能够简单地数数时，就列一个清单。只要你只需要列表的大小，你就可以把它算在一个整数变量中。
- 愚蠢的算法。字符串的子字符串不能比原始字符串长。我说的是第二个
for 循环。例如，假设您正在计算 1001 的二进制间隙。然后你的算法计算 001 和 01 的二进制间隙。你根本不需要数第二个。它正在发生，因为你有两个 for 循环。
最大的问题是，根本不用把int转换成java.lang.String就可以解决这个问题。如果您从教科书上遇到了这个问题，我相信这就是 'correct' 答案：使用按位运算符。
public static int solution(int num) {
int ptr; //Used for bitwise operation.
for(ptr=1; ptr>0; ptr<<=1) //Find the lowest bit 1
if((num&ptr) != 0)
break;
int cnt=0; //Count the (possible) gap
int ret=0; //Keep the longest gap.
for(; ptr>0; ptr<<=1) {
if((num&ptr) != 0) { //If it's bit 1
ret = cnt < ret ? ret : cnt; //Get the bigger one between cnt and ret
cnt=-1; //Exclude this bit
}
cnt++; //Increment the count. If this bit is 1, then cnt would become 0 beause we set the cnt as -1 instead of 0.
}
return ret;
}
这是我的适度解决方案。现在我看到它看起来像是修改
魔鬼的答案。我测试了
public int countZeros(int n) {
String binaryRep = Integer.toBinaryString(n);
char[] nChars = binaryRep.toCharArray();
int nElemLength = Math.min(binaryRep.lastIndexOf('1') + 1, nChars.length);
if (nElemLength <= 2) {
return 0;
}
String[] elementsParts = binaryRep.substring(0, nElemLength).split("1");
int zeroLength = 0;
for (String elementsPart : elementsParts) {
if (elementsPart.length() > zeroLength) {
zeroLength = elementsPart.length();
}
}
return zeroLength;
}
我觉得你的代码有点混乱，检查这个。
public int solution(int n) {
if (n <= 0) return 0;
char[] chars = Integer.toBinaryString(n).toCharArray();
ArrayList<Integer> arrayList = new ArrayList<>();
int maxCount = 0;
for (int i = 0; i < chars.length; i++) {
while (chars[i] == '0' && i + 1 < chars.length) {
maxCount++;
i++;
if (i + 1 == chars.length && chars[i] == '0')
maxCount = 0;
}
if (maxCount != 0)
arrayList.add(maxCount);
maxCount = 0;
}
return arrayList.isEmpty() ? 0 : Collections.max(arrayList);
}
这个算法呢。对时间表现是好是坏？
int count = 0, prevCount = 0;
while (a > 1) {
if (a % 2 == 0) {
count++;
if (count > prevCount)
prevCount++;
} else {
count = 0;
}
a = a/2;
}
if(a % 2 == 0)
prevCount++;
您好，这是我针对此任务的解决方案。
我有任务
分数：100%
正确性：100%
public int solution(int N) {
String binary = Integer.toBinaryString(N);
int[] table = new int[binary.length()];
for (int i=0;i<binary.length();i++){
int number = Integer.parseInt(binary.substring(i,i+1));
table[i] = number;
}
int resu = 0;
int res = 0;
for (int i=0;i<table.length;i++){
if (table[i] == 1){
if (resu > res){
res = resu;
}
resu = 0;
}else {
resu++;
}
}
return res;
}
为了大家的利益，这里是我的二元差距解决方案，它让我在任务分数和任务正确性方面都达到了 100%：
class Solution {
public int solution(int N) {
String nStr = Integer.toBinaryString(N);
boolean isCounting = false;
int j=0;
int[] seqs = new int[32];
for (int i=0; i<nStr.length(); i++)
{
if ( nStr.charAt(i) == '1')
{
if (!isCounting)
{
isCounting = true;
seqs[j] = 0;
}
else // isCounting, turn it off
{
isCounting = false;
j++;
}
}
else // nStr.charAt(i) == '0'
{
if (!isCounting)
isCounting = true;
seqs[j]++;
}
}
if (isCounting == true)
seqs[j] = 0;
int maxGap = 0;
for (int k=0; k<seqs.length; k++)
if (seqs[k] > maxGap)
maxGap = seqs[k];
return maxGap;
}
}
OBJECTIVE-C 解 O(n)
Codility给出的结果
任务分数：100%
正确率：100%
性能：未评估
时间复杂度
最坏情况的时间复杂度是O(n)
算法解释
事实
每个有效间隙都以“1”开头并以另一个“1”结束，它们之间至少有一个 'zero'。
- 1001 - 是有效间隙
- 00100 - 不是有效间隙
- 10100 - 是有效间隙
- 11111 - 不是有效间隙
第 1 步
从右向左逐个获取位表示。
这意味着，对于 n=4，我将首先得到一个零，然后是另一个零，然后是一个，最后是一个零。 [0,1,0,0]
4 -> 0100
第 2 步
开始寻找第一个 '1' - 因为我们的标志 'hasStartPattern' 在第一次迭代中为假，我们将寻找第一次出现的 '1'，这意味着我们有一个有效的开始模式，我们在下一次迭代中将标志 'hasStartPattern' 更改为 true 我们应该验证当前位是否为“0”并使用计数器，在本例中为 'candidates'.
只有当传入的位中有另一个'1'时，我们确定我们有一个有效的二进制间隙，然后我们将我们之前的'candidates'与我们当前的'gapCounter'为了保持最高的。
如果没有另一个 '1' 来缩小差距，我们永远不会更改 'gapCounter' 的值并且我们 return 0
-(int)solutionOne:(int)n {
BOOL hasStartPattern = NO;
int candidates = 0;
int gapCounter = 0;
while(n){
// STEP 1
NSString *bit = (n & 1) ? @"1": @"0";
n /= 2;
// STEP 2
if ( hasStartPattern && [bit isEqualToString:@"0"]) {
candidates++;
}
else if ( hasStartPattern && [bit isEqualToString:@"1"]) {
// At least one '1' exist as a close pattern
if (candidates > gapCounter) {
gapCounter = candidates;
}
candidates = 0;
}
else if ([bit isEqualToString:@"1"]) {
hasStartPattern = YES; // At least one '1' exist as an open pattern
}
}
return gapCounter;
}
OBJECTIVE-C 解 O(2n)
Codility给出的结果
任务分数：100%
正确率：100%
性能：未评估
时间复杂度
最坏情况的时间复杂度是O(2n)
算法解释
事实
每个有效间隙都以“1”开头并以另一个“1”结束，它们之间至少有一个 'zero'。
- 1001 - 是有效间隙
- 00100 - 不是有效间隙
- 10100 - 是有效间隙
- 11111 - 不是有效间隙
第 1 步
- 使用复杂度为 O(n) 的辅助方法获取 n 的位
第 2 步
- 迭代我们在第一步中得到的每一位
- 开始寻找第一个 '1' - 因为我们的标志 'hasStartPattern' 在第一次迭代中为假，我们将寻找第一次出现的 '1'，这意味着我们有一个有效的开始模式然后我们将标志 'hasStartPattern' 更改为 true
对于下一次迭代，我们应该验证当前位是否为“0”并使用计数器，在本例中为 'candidates'.
- 只有当传入的位中有另一个'1'时，我们才能确定我们有一个有效的二进制间隙，然后我们将之前的'candidates'与当前的'gapCounter'按顺序进行比较保持最高的。
- 如果没有另一个 '1' 来缩小差距，我们永远不会更改 'gapCounter' 的值并且我们 return 0.
+(int)solutionTwo:(int)n {
// STEP 1
// O(n)
NSString *bits = [self getBitsForNumber:n];
BOOL hasStartPattern = NO;
int candidates = 0;
int gapCounter = 0;
// STEP 2
// O(n)
for (int i=0; i < bits.length; i++) {
char currentBit = [bits characterAtIndex:i];
if ( hasStartPattern && currentBit == '0' ) {
candidates++;
}
else if ( hasStartPattern && currentBit == '1' ) {
// At least one '1' exist as a close pattern
if (candidates > gapCounter) {
gapCounter = candidates;
}
candidates = 0;
}
else if (currentBit == '1') {
hasStartPattern = YES; // At least one '1' exist as an open pattern
}
}
return gapCounter;
}
/*
Time Complexity:
- The worst case time complexity for this auxiliary method is O(n)
*/
+(NSString*)getBitsForNumber:(int)n {
NSMutableString *bits = [NSMutableString string];
while(n) {
[bits insertString:((n&1)? @"1" : @"0") atIndex:0];
n /= 2;
}
return bits;
}
这是我的解决方案。
是100/100。
不过我觉得还是可以打磨的
class Solution {
public int solution(int N) {
String s = Integer.toBinaryString(N);
int ctr = 0;
for (int x = 0; x < s.length(); x++){
if (s.substring(x,x+1).equals("1")){
ctr++;
}
}
int result[] = new int[ctr];
boolean flag = false;
int fCtr = 0;
for(int y = 0; y < s.length(); y++){
if(s.substring(y,y+1).equals("1")){
flag = true;
if(flag == true){
fCtr++;
}
}
else if (s.substring(y,y+1).equals("0") && flag == true && fCtr < ctr){
result[fCtr]++;
}
}
int ans = 0;
for (int d = 0; d < result.length; d++){
if (ans <= result[d]){
ans = result[d];
}
}
return ans;
}
}
我认为这是一个非常小的代码
public int solution(int N)
{
string binary = Convert.ToString(N, 2);
binary = binary.TrimEnd(new Char[] { '0' });
var gaps = binary.Split('1');
int max = 0;
foreach (var item in gaps)
{
if (!string.IsNullOrEmpty(item))
if(item.Length > max)
max = item.Length;
}
return max ;
}
这是我的
public int solution(int N) {
String binary = Integer.toBinaryString(N);
LinkedList<Integer> gaps = new LinkedList<>();
int countGap = 0;
int j = 0;
for (int i = 1; i < binary.length() - 1; i++) {
if (binary.charAt(i) == '0') {
countGap++;
} else {
gaps.add(j, countGap);
j++;
countGap = 0;
}
}
gaps.add(j, countGap);
if (binary.charAt(binary.length() - 1) == '0') {
gaps.set(gaps.size() - 1, 0);
}
Collections.sort(gaps);
return gaps.getLast();
}
这是我的解决方案。 （斯卡拉）
是100/100。
object Solution {
def solution(n: Int): Int = {
val regex = raw"(?=(10*1))".r
val result = regex.findAllMatchIn(n.toBinaryString).map(_.group(1)) match {
case re:Iterator[String] if !re.isEmpty => (re.toList.map(Integer.parseInt(_, 2)).sorted.last.toBinaryString.length - 2)
case _ => 0
}
result
}
}
我的解决方案使用 JavaScript，100% 测试。
function solution(N) {
N = N.toString(2);
let numberOfOnes = 0;
let binaryGap = 0;
let binaryZeros = 0;
for(let i=0; i<N.length; i++) {
if(N[i] > 0) {
numberOfOnes++;
}
}
if(numberOfOnes) {
for(let j=0; j<N.length; j++) {
if(N[j] > 0) {
if(binaryZeros) {
if(binaryZeros > binaryGap) {
binaryGap = binaryZeros;
}
}
binaryZeros = 0;
}
if(N[j] < 1) {
binaryZeros++;
}
}
} else {
binaryGap = 0;
}
return binaryGap;
}
我用 PHP 调整了@minary 解决方案并且它起作用了。
function maxZeros($N){
$ptr = 0; //Used for bitwise operation.
for($ptr = 1; $ptr > 0; $ptr <<= 1) //Find the lowest bit 1
if(($N & $ptr) != 0)
break;
$cnt = 0; //Count the (possible) gap
$ret = 0; //Keep the longest gap.
for(; $ptr > 0; $ptr <<= 1) {
if(($N & $ptr) != 0) { //If it's bit 1
$ret = $cnt < $ret ? $ret : $cnt; //Get the bigger one between cnt and ret
$cnt = -1; //Exclude this bit
}
$cnt++; //Increment the count. If this bit is 1, then cnt would become 0 because we set the cnt as -1 instead of 0.
}
return $ret;
}
//Run the function below, for example N = 32
$N = 32;
echo (maxZeros($N));
这是等效的 C# 代码
public int solution(int N) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int m;
for (m=1;m>0;m<<=1){
if((m&N) !=0){
break;
}
}
int i = 0;
int j = 0;
for (; m>0;m<<=1){
if((m&N) !=0){
j=i<j ? j:i;
i=-1;
}
i++;
}
return j;
}
}
public static int solution(int N) {
int longestBinaryGap = 0;
String binary= Integer.toBinaryString(N);
if(!binary.contains("01")){
return 0;
}
binary = binary.replaceAll("0*$", "");
String[] gaps = binary.split("1");
for (String g:gaps) {
if(g.length()>longestBinaryGap){
longestBinaryGap = g.length();
}
}
return longestBinaryGap;
}
这是我在 Javascript 中写的，有人可以批评一下吗，虽然在 Codility 上它得分 100%。
const binaryGap = (intN)=>{
const binary = Array.from(intN.toString(2)).map(item=>parseInt(item))
const newArrayGroup = []
const arrLength = binary.length
let zeroGroup = []
for (let index = 0; index < arrLength; index++) {
const parsedInt = binary[index]
if ( parsedInt == 0 ) {
zeroGroup.push(parsedInt)
}else{
if (zeroGroup.length>0) {
newArrayGroup.push(zeroGroup.length)
}
zeroGroup = []
}
}
return newArrayGroup.length == 0 ? 0 : Math.max(...newArrayGroup)
}
这是我在 C# 中的回答：
</p>
<pre><code>class Solution {
public int solution(int N) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
string Nbin = Convert.ToString(N, 2);
string[] arr = Nbin.Split('1');
int maxZ = 0;
if (arr.Length > 2 && arr[arr.Length - 1] == " ")
{
foreach (var item in arr)
{
if (item.Length > maxZ)
{
maxZ = item.Length;
}
}
}
else
{
for (int i = 0; i < arr.Length - 1; i++)
{
if (arr[i].Length > maxZ)
{
maxZ = arr[i].Length;
}
}
}
return maxZ;
}
}
这是我的简单解决方案
class Solution {
public int solution(int N) {
// write your code in Java SE 8
String b = Integer.toBinaryString(N);
char[] binaryArr = b.toCharArray();
int max = 0;
int internalCount = 0;
for(int index=1; index< binaryArr.length; index++){
if(binaryArr[index] =='0')
internalCount++;
else{
if (max<internalCount) max = internalCount;
internalCount =0;
}
}
return max;
}
}
这是我在 PHP 中的简短解决方案（任务分数：100%，正确性：100%）
function solution($N) {
$gaps = array();
$s = explode('1', trim(decbin($N),'0'));
foreach($s as $g){
$gaps[] = strlen($g);
}
return max($gaps);
}
对于 Javascript 这是我的解决方案。
function solution(N){
N = N.toString(2);
var totalOnes = 0;
var binaryGap = 0;
var binaryZero = 0;
const foundBinaryZero = []
for(let i=0; i<N.length; i++) {
if(N[i] > 0) {
totalOnes++;
foundBinaryZero.push(binaryZero);
binaryZero = 0;
}else{
binaryGap = 0;
binaryZero = binaryZero + 1;
}
}
foundBinaryZero.sort();
return (foundBinaryZero[foundBinaryZero.length - 1]);
}
此解决方案不会将数字转换为二进制字符串，因为这是不必要的。它从第一个设置位 (1) 左侧的第一个位开始，从右到左查看每个位。
n & -n returns 只设置了 n 最右边位的掩码。将其乘以 2 得到左边的下一位，这是开始计数的合适位置。
对于每个位检查（即循环的每次迭代），它会递增或重置 current 计数器，并使用它来跟踪迄今为止找到的最大连续部分。
public int solution(int n) {
int max = 0;
for (int mask = (n & -n) * 2, current = 0; mask < n; mask <<= 1)
max = Math.max(max, (n & mask) == 0 ? ++current : (current = 0));
return max;
}
以上所有代码中最简单的代码，Codility 100% 正确性和得分，已验证！
Javascript中的解决方案：
function solution(N) {
let binaryValue = (N >>> 0).toString(2);
let lengthArr = [];
let length = 1;
for(let i = 0; i < binaryValue.length; i++){
if(binaryValue[i] == 0){
// Check if 1 is ending then push the lenght to array and reset the length
if(binaryValue[i + 1] == 1){
lengthArr.push(length);
length = 0;
}
length++;
}
}
return lengthArr.length ? Math.max(...lengthArr) : 0;
}
A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
大家好，我刚刚解决了这个问题，希望对大家有所帮助。
public int solution(int N) {
String toBinary = Integer.toBinaryString(N);
char[] ch = toBinary.toCharArray();
int maxCount = 0;
int count = 0;
boolean flag = false;
for(int i=0; i < ch.length; i++){
if(ch[i] == '1'){
if(count > maxCount){
maxCount = count;
}
count = 0;
} else
count ++;
}
return maxCount;
}
}
我添加了这个解决方案，Codility 得分为 100%。
public int solution(int N) {
String s = Integer.toBinaryString(N);
s = removeTrailingZeros(s);
System.out.println(s);
String arrayBinary[] = s.split("1");
int x = 0;
for (String abc : arrayBinary) {
if (abc.length() > x)
x = abc.length();
}
return x;
}
private String removeTrailingZeros(String s) {
if (s.endsWith("0")) {
s = s.substring(0, s.length() - 1);
return removeTrailingZeros(s);
}
return s;
}
Executed test sets
Python中的一行：
任务得分 100%，正确性 100%
def solution(N):
b=bin(N)[2:]
return len(max(b.strip('0').split('1')))
# here strip will remove all trailing 0's and split will create a list with splitting 1's and combining 0's which are together.
如果二进制数以0结尾，则number % 2 == 0否则number % 2 == 1，利用这个规则我们可以很容易地解决它。
def solution(N: int):
prev = 0
current = 0
# remove leading zeros
while N % 2 == 0:
N >>= 1
# shift to right until its reaches 1
while N != 1:
if N % 2 == 0:
current += 1
else:
prev = max(current, prev)
current = 0
N >>= 1
return max(prev , current)
这是 Java 11 中二进制缺口的可能解决方案（可调节性测试）
class Solution {
public int solution(int N) {
// write your code in Java SE 11
String binN= Integer.toBinaryString(N);
int counter=0;
int maxCount=0;
boolean enableCounter=false;
char prevChar= binN.charAt(0);
for(int i=1 ; i < binN.length()-1; i++){
if(prevChar=='1'){
enableCounter=true;
}
if (binN.charAt(i)=='0' && enableCounter){
counter++;
if (binN.charAt(i+1)=='1'){
if(counter>maxCount){
maxCount=counter;
}
counter=0;
}
}
prevChar=binN.charAt(i);
}
return maxCount;
}
}
这是 swift 中 100% 的工作代码 :)
public func solution(_ N : Int) -> Int {
let str = String(N, radix: 2)
if str.contains("1") && str.contains("0") {
if str.split(separator: "0").count != 1 {
if str.last == "0" {
return str.split(separator: "1").dropLast().max()!.count
}
return str.split(separator: "1").max()!.count
}
}
return 0
}
在PHP
function solution($N) {
$bin = decbin($N);
$gap = [];
$len = strlen($bin);
$startCount = 0;
$endCount = 0;
$startCount = strpos($bin,'0');
if(! $startCount)
return 0;
while($startCount){
$endCount = strpos($bin,'1',$startCount);
if(! $endCount)
break;
$sub = substr($bin,$startCount,$endCount - $startCount);
array_push($gap,strlen($sub));
$startCount = strpos($bin,'0',$endCount);
}
$sum = 0;
if(count($gap)>0)
return max($gap);
else
return 0;
}
正整数N中的二进制间隙是N的二进制表示中两端被1包围的连续零的任何最大序列。
例如，数字 9 的二进制表示为 1001，包含长度为 2 的二进制间隙。数字 529 的二进制表示为 1000010001，包含两个二进制间隙：一个长度为 4，一个长度为 3。数字 20 有二进制表示 10100，包含一个长度为 1 的二进制间隙。数字 15 的二进制表示为 1111，没有二进制间隙。
写一个函数：
int 解决方案（int N）； 也就是说，给定一个正整数 N，returns 是其最长二进制间隙的长度。如果 N 不包含二进制间隙，则函数应 return 0。
例如，给定 N = 1041，函数应 return 5，因为 N 的二进制表示形式为 10000010001，因此其最长的二进制间隙长度为 5。
public int solution(int n) {
// write your code in Java SE 8
String binaryRep = Integer.toBinaryString(n);
System.out.println("Binary Representation of " + n + " = " + binaryRep);
List<String> strList = new ArrayList<String>();
int count = 0;
for (int i = 0; i < binaryRep.length(); i++) { // Loop through the each number
String str = binaryRep.charAt(i) + ""; // getting one by one number
if(str.equals("0")){
for(int j = i;j<binaryRep.length();j++){ //Get each next element
String str1 = binaryRep.charAt(j) + "";
if(!str.equals("1") && str.equals(str1)){
if(!strList.isEmpty() && count >= strList.size()){
strList.add(str1);
}else if(strList.isEmpty()){
strList.add(str1);
}
count ++;
}else{
count = 0;
break;
}
}
}
}
return strList.size();
}
不需要将二进制字符串的内容放入数组中（当然除非这是一个要求），只需遍历字符串本身并使用 String.substring() 方法检索字符串表示每个二进制数字的值，如：
String digit = binaryString.substring(i, i+1);
这一切都归结为计算 0 的数量 在 任何一组 1 之间，并通过使用整数数据类型变量跟踪那些 0，每次 0 时递增遇到了。每次遇到 1 时，相同的变量都会重置为 0，但在重置之前，您可以将它与另一个预定义的整数变量进行比较，该变量将保存遇到的 0 中最长的 运行，例如：
if(binaryString.substring(i, i+1).equals("1")) {
if (zeroHit > longest) { longest = zeroHit; }
zeroHit = 0;
}
else { zeroHit++; }
整个方法可能看起来像这样：
private static int solution(int intValue) {
String binaryString = Integer.toBinaryString(intValue);
int zeroHit = 0;
int longest = 0;
for (int i = 0; i < binaryString.length(); i++) {
if(binaryString.substring(i, i+1).equals("1")) {
if (zeroHit > longest) { longest = zeroHit; }
zeroHit = 0;
}
else { zeroHit++; }
}
return longest;
}
我还没有测试你的代码，但如果你的目标只是计算最长的时间，那么效率似乎很低'binary gap'。
您的代码中的问题：
- 当它可以是
char时，就变成了java.lang.String。制作对象比制作基本类型慢得多。 - 当它能够简单地数数时，就列一个清单。只要你只需要列表的大小，你就可以把它算在一个整数变量中。
- 愚蠢的算法。字符串的子字符串不能比原始字符串长。我说的是第二个
for循环。例如，假设您正在计算1001的二进制间隙。然后你的算法计算001和01的二进制间隙。你根本不需要数第二个。它正在发生，因为你有两个 for 循环。
最大的问题是，根本不用把int转换成java.lang.String就可以解决这个问题。如果您从教科书上遇到了这个问题，我相信这就是 'correct' 答案：使用按位运算符。
public static int solution(int num) {
int ptr; //Used for bitwise operation.
for(ptr=1; ptr>0; ptr<<=1) //Find the lowest bit 1
if((num&ptr) != 0)
break;
int cnt=0; //Count the (possible) gap
int ret=0; //Keep the longest gap.
for(; ptr>0; ptr<<=1) {
if((num&ptr) != 0) { //If it's bit 1
ret = cnt < ret ? ret : cnt; //Get the bigger one between cnt and ret
cnt=-1; //Exclude this bit
}
cnt++; //Increment the count. If this bit is 1, then cnt would become 0 beause we set the cnt as -1 instead of 0.
}
return ret;
}
这是我的适度解决方案。现在我看到它看起来像是修改 魔鬼的答案。我测试了
public int countZeros(int n) {
String binaryRep = Integer.toBinaryString(n);
char[] nChars = binaryRep.toCharArray();
int nElemLength = Math.min(binaryRep.lastIndexOf('1') + 1, nChars.length);
if (nElemLength <= 2) {
return 0;
}
String[] elementsParts = binaryRep.substring(0, nElemLength).split("1");
int zeroLength = 0;
for (String elementsPart : elementsParts) {
if (elementsPart.length() > zeroLength) {
zeroLength = elementsPart.length();
}
}
return zeroLength;
}
我觉得你的代码有点混乱，检查这个。
public int solution(int n) {
if (n <= 0) return 0;
char[] chars = Integer.toBinaryString(n).toCharArray();
ArrayList<Integer> arrayList = new ArrayList<>();
int maxCount = 0;
for (int i = 0; i < chars.length; i++) {
while (chars[i] == '0' && i + 1 < chars.length) {
maxCount++;
i++;
if (i + 1 == chars.length && chars[i] == '0')
maxCount = 0;
}
if (maxCount != 0)
arrayList.add(maxCount);
maxCount = 0;
}
return arrayList.isEmpty() ? 0 : Collections.max(arrayList);
}
这个算法呢。对时间表现是好是坏？
int count = 0, prevCount = 0;
while (a > 1) {
if (a % 2 == 0) {
count++;
if (count > prevCount)
prevCount++;
} else {
count = 0;
}
a = a/2;
}
if(a % 2 == 0)
prevCount++;
您好，这是我针对此任务的解决方案。 我有任务 分数：100% 正确性：100%
public int solution(int N) {
String binary = Integer.toBinaryString(N);
int[] table = new int[binary.length()];
for (int i=0;i<binary.length();i++){
int number = Integer.parseInt(binary.substring(i,i+1));
table[i] = number;
}
int resu = 0;
int res = 0;
for (int i=0;i<table.length;i++){
if (table[i] == 1){
if (resu > res){
res = resu;
}
resu = 0;
}else {
resu++;
}
}
return res;
}
为了大家的利益，这里是我的二元差距解决方案，它让我在任务分数和任务正确性方面都达到了 100%：
class Solution {
public int solution(int N) {
String nStr = Integer.toBinaryString(N);
boolean isCounting = false;
int j=0;
int[] seqs = new int[32];
for (int i=0; i<nStr.length(); i++)
{
if ( nStr.charAt(i) == '1')
{
if (!isCounting)
{
isCounting = true;
seqs[j] = 0;
}
else // isCounting, turn it off
{
isCounting = false;
j++;
}
}
else // nStr.charAt(i) == '0'
{
if (!isCounting)
isCounting = true;
seqs[j]++;
}
}
if (isCounting == true)
seqs[j] = 0;
int maxGap = 0;
for (int k=0; k<seqs.length; k++)
if (seqs[k] > maxGap)
maxGap = seqs[k];
return maxGap;
}
}
OBJECTIVE-C 解 O(n)
Codility给出的结果
任务分数：100%
正确率：100%
性能：未评估
时间复杂度
最坏情况的时间复杂度是O(n)
算法解释
事实
每个有效间隙都以“1”开头并以另一个“1”结束，它们之间至少有一个 'zero'。
- 1001 - 是有效间隙
- 00100 - 不是有效间隙
- 10100 - 是有效间隙
- 11111 - 不是有效间隙
第 1 步
从右向左逐个获取位表示。
这意味着，对于 n=4，我将首先得到一个零，然后是另一个零，然后是一个，最后是一个零。 [0,1,0,0]
4 -> 0100
第 2 步
开始寻找第一个 '1' - 因为我们的标志 'hasStartPattern' 在第一次迭代中为假，我们将寻找第一次出现的 '1'，这意味着我们有一个有效的开始模式，我们在下一次迭代中将标志 'hasStartPattern' 更改为 true 我们应该验证当前位是否为“0”并使用计数器，在本例中为 'candidates'.
只有当传入的位中有另一个'1'时，我们确定我们有一个有效的二进制间隙，然后我们将我们之前的'candidates'与我们当前的'gapCounter'为了保持最高的。
如果没有另一个 '1' 来缩小差距，我们永远不会更改 'gapCounter' 的值并且我们 return 0
-(int)solutionOne:(int)n {
BOOL hasStartPattern = NO;
int candidates = 0;
int gapCounter = 0;
while(n){
// STEP 1
NSString *bit = (n & 1) ? @"1": @"0";
n /= 2;
// STEP 2
if ( hasStartPattern && [bit isEqualToString:@"0"]) {
candidates++;
}
else if ( hasStartPattern && [bit isEqualToString:@"1"]) {
// At least one '1' exist as a close pattern
if (candidates > gapCounter) {
gapCounter = candidates;
}
candidates = 0;
}
else if ([bit isEqualToString:@"1"]) {
hasStartPattern = YES; // At least one '1' exist as an open pattern
}
}
return gapCounter;
}
OBJECTIVE-C 解 O(2n)
Codility给出的结果
任务分数：100%
正确率：100%
性能：未评估
时间复杂度
最坏情况的时间复杂度是O(2n)
算法解释
事实
每个有效间隙都以“1”开头并以另一个“1”结束，它们之间至少有一个 'zero'。
- 1001 - 是有效间隙
- 00100 - 不是有效间隙
- 10100 - 是有效间隙
- 11111 - 不是有效间隙
第 1 步
- 使用复杂度为 O(n) 的辅助方法获取 n 的位
第 2 步
- 迭代我们在第一步中得到的每一位
- 开始寻找第一个 '1' - 因为我们的标志 'hasStartPattern' 在第一次迭代中为假，我们将寻找第一次出现的 '1'，这意味着我们有一个有效的开始模式然后我们将标志 'hasStartPattern' 更改为 true 对于下一次迭代，我们应该验证当前位是否为“0”并使用计数器，在本例中为 'candidates'.
- 只有当传入的位中有另一个'1'时，我们才能确定我们有一个有效的二进制间隙，然后我们将之前的'candidates'与当前的'gapCounter'按顺序进行比较保持最高的。
- 如果没有另一个 '1' 来缩小差距，我们永远不会更改 'gapCounter' 的值并且我们 return 0.
+(int)solutionTwo:(int)n {
// STEP 1
// O(n)
NSString *bits = [self getBitsForNumber:n];
BOOL hasStartPattern = NO;
int candidates = 0;
int gapCounter = 0;
// STEP 2
// O(n)
for (int i=0; i < bits.length; i++) {
char currentBit = [bits characterAtIndex:i];
if ( hasStartPattern && currentBit == '0' ) {
candidates++;
}
else if ( hasStartPattern && currentBit == '1' ) {
// At least one '1' exist as a close pattern
if (candidates > gapCounter) {
gapCounter = candidates;
}
candidates = 0;
}
else if (currentBit == '1') {
hasStartPattern = YES; // At least one '1' exist as an open pattern
}
}
return gapCounter;
}
/*
Time Complexity:
- The worst case time complexity for this auxiliary method is O(n)
*/
+(NSString*)getBitsForNumber:(int)n {
NSMutableString *bits = [NSMutableString string];
while(n) {
[bits insertString:((n&1)? @"1" : @"0") atIndex:0];
n /= 2;
}
return bits;
}
这是我的解决方案。
是100/100。
不过我觉得还是可以打磨的
class Solution {
public int solution(int N) {
String s = Integer.toBinaryString(N);
int ctr = 0;
for (int x = 0; x < s.length(); x++){
if (s.substring(x,x+1).equals("1")){
ctr++;
}
}
int result[] = new int[ctr];
boolean flag = false;
int fCtr = 0;
for(int y = 0; y < s.length(); y++){
if(s.substring(y,y+1).equals("1")){
flag = true;
if(flag == true){
fCtr++;
}
}
else if (s.substring(y,y+1).equals("0") && flag == true && fCtr < ctr){
result[fCtr]++;
}
}
int ans = 0;
for (int d = 0; d < result.length; d++){
if (ans <= result[d]){
ans = result[d];
}
}
return ans;
}
}
我认为这是一个非常小的代码
public int solution(int N)
{
string binary = Convert.ToString(N, 2);
binary = binary.TrimEnd(new Char[] { '0' });
var gaps = binary.Split('1');
int max = 0;
foreach (var item in gaps)
{
if (!string.IsNullOrEmpty(item))
if(item.Length > max)
max = item.Length;
}
return max ;
}
这是我的
public int solution(int N) {
String binary = Integer.toBinaryString(N);
LinkedList<Integer> gaps = new LinkedList<>();
int countGap = 0;
int j = 0;
for (int i = 1; i < binary.length() - 1; i++) {
if (binary.charAt(i) == '0') {
countGap++;
} else {
gaps.add(j, countGap);
j++;
countGap = 0;
}
}
gaps.add(j, countGap);
if (binary.charAt(binary.length() - 1) == '0') {
gaps.set(gaps.size() - 1, 0);
}
Collections.sort(gaps);
return gaps.getLast();
}
这是我的解决方案。 （斯卡拉）
是100/100。
object Solution {
def solution(n: Int): Int = {
val regex = raw"(?=(10*1))".r
val result = regex.findAllMatchIn(n.toBinaryString).map(_.group(1)) match {
case re:Iterator[String] if !re.isEmpty => (re.toList.map(Integer.parseInt(_, 2)).sorted.last.toBinaryString.length - 2)
case _ => 0
}
result
}
}
我的解决方案使用 JavaScript，100% 测试。
function solution(N) {
N = N.toString(2);
let numberOfOnes = 0;
let binaryGap = 0;
let binaryZeros = 0;
for(let i=0; i<N.length; i++) {
if(N[i] > 0) {
numberOfOnes++;
}
}
if(numberOfOnes) {
for(let j=0; j<N.length; j++) {
if(N[j] > 0) {
if(binaryZeros) {
if(binaryZeros > binaryGap) {
binaryGap = binaryZeros;
}
}
binaryZeros = 0;
}
if(N[j] < 1) {
binaryZeros++;
}
}
} else {
binaryGap = 0;
}
return binaryGap;
}
我用 PHP 调整了@minary 解决方案并且它起作用了。
function maxZeros($N){
$ptr = 0; //Used for bitwise operation.
for($ptr = 1; $ptr > 0; $ptr <<= 1) //Find the lowest bit 1
if(($N & $ptr) != 0)
break;
$cnt = 0; //Count the (possible) gap
$ret = 0; //Keep the longest gap.
for(; $ptr > 0; $ptr <<= 1) {
if(($N & $ptr) != 0) { //If it's bit 1
$ret = $cnt < $ret ? $ret : $cnt; //Get the bigger one between cnt and ret
$cnt = -1; //Exclude this bit
}
$cnt++; //Increment the count. If this bit is 1, then cnt would become 0 because we set the cnt as -1 instead of 0.
}
return $ret;
}
//Run the function below, for example N = 32
$N = 32;
echo (maxZeros($N));
这是等效的 C# 代码
public int solution(int N) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int m;
for (m=1;m>0;m<<=1){
if((m&N) !=0){
break;
}
}
int i = 0;
int j = 0;
for (; m>0;m<<=1){
if((m&N) !=0){
j=i<j ? j:i;
i=-1;
}
i++;
}
return j;
}
}
public static int solution(int N) {
int longestBinaryGap = 0;
String binary= Integer.toBinaryString(N);
if(!binary.contains("01")){
return 0;
}
binary = binary.replaceAll("0*$", "");
String[] gaps = binary.split("1");
for (String g:gaps) {
if(g.length()>longestBinaryGap){
longestBinaryGap = g.length();
}
}
return longestBinaryGap;
}
这是我在 Javascript 中写的，有人可以批评一下吗，虽然在 Codility 上它得分 100%。
const binaryGap = (intN)=>{
const binary = Array.from(intN.toString(2)).map(item=>parseInt(item))
const newArrayGroup = []
const arrLength = binary.length
let zeroGroup = []
for (let index = 0; index < arrLength; index++) {
const parsedInt = binary[index]
if ( parsedInt == 0 ) {
zeroGroup.push(parsedInt)
}else{
if (zeroGroup.length>0) {
newArrayGroup.push(zeroGroup.length)
}
zeroGroup = []
}
}
return newArrayGroup.length == 0 ? 0 : Math.max(...newArrayGroup)
}
这是我在 C# 中的回答：
</p>
<pre><code>class Solution {
public int solution(int N) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
string Nbin = Convert.ToString(N, 2);
string[] arr = Nbin.Split('1');
int maxZ = 0;
if (arr.Length > 2 && arr[arr.Length - 1] == " ")
{
foreach (var item in arr)
{
if (item.Length > maxZ)
{
maxZ = item.Length;
}
}
}
else
{
for (int i = 0; i < arr.Length - 1; i++)
{
if (arr[i].Length > maxZ)
{
maxZ = arr[i].Length;
}
}
}
return maxZ;
}
}
这是我的简单解决方案
class Solution {
public int solution(int N) {
// write your code in Java SE 8
String b = Integer.toBinaryString(N);
char[] binaryArr = b.toCharArray();
int max = 0;
int internalCount = 0;
for(int index=1; index< binaryArr.length; index++){
if(binaryArr[index] =='0')
internalCount++;
else{
if (max<internalCount) max = internalCount;
internalCount =0;
}
}
return max;
}
}
这是我在 PHP 中的简短解决方案（任务分数：100%，正确性：100%）
function solution($N) {
$gaps = array();
$s = explode('1', trim(decbin($N),'0'));
foreach($s as $g){
$gaps[] = strlen($g);
}
return max($gaps);
}
对于 Javascript 这是我的解决方案。
function solution(N){
N = N.toString(2);
var totalOnes = 0;
var binaryGap = 0;
var binaryZero = 0;
const foundBinaryZero = []
for(let i=0; i<N.length; i++) {
if(N[i] > 0) {
totalOnes++;
foundBinaryZero.push(binaryZero);
binaryZero = 0;
}else{
binaryGap = 0;
binaryZero = binaryZero + 1;
}
}
foundBinaryZero.sort();
return (foundBinaryZero[foundBinaryZero.length - 1]);
}
此解决方案不会将数字转换为二进制字符串，因为这是不必要的。它从第一个设置位 (1) 左侧的第一个位开始，从右到左查看每个位。
n & -n returns 只设置了 n 最右边位的掩码。将其乘以 2 得到左边的下一位，这是开始计数的合适位置。
对于每个位检查（即循环的每次迭代），它会递增或重置 current 计数器，并使用它来跟踪迄今为止找到的最大连续部分。
public int solution(int n) {
int max = 0;
for (int mask = (n & -n) * 2, current = 0; mask < n; mask <<= 1)
max = Math.max(max, (n & mask) == 0 ? ++current : (current = 0));
return max;
}
以上所有代码中最简单的代码，Codility 100% 正确性和得分，已验证！
Javascript中的解决方案：
function solution(N) {
let binaryValue = (N >>> 0).toString(2);
let lengthArr = [];
let length = 1;
for(let i = 0; i < binaryValue.length; i++){
if(binaryValue[i] == 0){
// Check if 1 is ending then push the lenght to array and reset the length
if(binaryValue[i + 1] == 1){
lengthArr.push(length);
length = 0;
}
length++;
}
}
return lengthArr.length ? Math.max(...lengthArr) : 0;
}
A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
大家好，我刚刚解决了这个问题，希望对大家有所帮助。
public int solution(int N) {
String toBinary = Integer.toBinaryString(N);
char[] ch = toBinary.toCharArray();
int maxCount = 0;
int count = 0;
boolean flag = false;
for(int i=0; i < ch.length; i++){
if(ch[i] == '1'){
if(count > maxCount){
maxCount = count;
}
count = 0;
} else
count ++;
}
return maxCount;
}
}
我添加了这个解决方案，Codility 得分为 100%。
public int solution(int N) {
String s = Integer.toBinaryString(N);
s = removeTrailingZeros(s);
System.out.println(s);
String arrayBinary[] = s.split("1");
int x = 0;
for (String abc : arrayBinary) {
if (abc.length() > x)
x = abc.length();
}
return x;
}
private String removeTrailingZeros(String s) {
if (s.endsWith("0")) {
s = s.substring(0, s.length() - 1);
return removeTrailingZeros(s);
}
return s;
}
Executed test sets
Python中的一行： 任务得分 100%，正确性 100%
def solution(N):
b=bin(N)[2:]
return len(max(b.strip('0').split('1')))
# here strip will remove all trailing 0's and split will create a list with splitting 1's and combining 0's which are together.
如果二进制数以0结尾，则number % 2 == 0否则number % 2 == 1，利用这个规则我们可以很容易地解决它。
def solution(N: int):
prev = 0
current = 0
# remove leading zeros
while N % 2 == 0:
N >>= 1
# shift to right until its reaches 1
while N != 1:
if N % 2 == 0:
current += 1
else:
prev = max(current, prev)
current = 0
N >>= 1
return max(prev , current)
这是 Java 11 中二进制缺口的可能解决方案（可调节性测试）
class Solution {
public int solution(int N) {
// write your code in Java SE 11
String binN= Integer.toBinaryString(N);
int counter=0;
int maxCount=0;
boolean enableCounter=false;
char prevChar= binN.charAt(0);
for(int i=1 ; i < binN.length()-1; i++){
if(prevChar=='1'){
enableCounter=true;
}
if (binN.charAt(i)=='0' && enableCounter){
counter++;
if (binN.charAt(i+1)=='1'){
if(counter>maxCount){
maxCount=counter;
}
counter=0;
}
}
prevChar=binN.charAt(i);
}
return maxCount;
}
}
这是 swift 中 100% 的工作代码 :)
public func solution(_ N : Int) -> Int {
let str = String(N, radix: 2)
if str.contains("1") && str.contains("0") {
if str.split(separator: "0").count != 1 {
if str.last == "0" {
return str.split(separator: "1").dropLast().max()!.count
}
return str.split(separator: "1").max()!.count
}
}
return 0
}
在PHP
function solution($N) {
$bin = decbin($N);
$gap = [];
$len = strlen($bin);
$startCount = 0;
$endCount = 0;
$startCount = strpos($bin,'0');
if(! $startCount)
return 0;
while($startCount){
$endCount = strpos($bin,'1',$startCount);
if(! $endCount)
break;
$sub = substr($bin,$startCount,$endCount - $startCount);
array_push($gap,strlen($sub));
$startCount = strpos($bin,'0',$endCount);
}
$sum = 0;
if(count($gap)>0)
return max($gap);
else
return 0;
}