首页 > 试题广场 >

小红的二进制删数字

[编程题]小红的二进制删数字
  • 热度指数：2933 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一个二进制字符串 s，她可以删掉其中的一些字符，使得最终该字符串为一个2的幂（即可以表示为 形式的数）。小红想知道，自己最少删几个字符可以达成？请你编写一个函数返回这个答案。
示例1

输入

"111"

输出

2

说明

删掉前两个 '1'，字符串变成"1"，1=2^0 为2的幂。
示例2

输入

"1010"

输出

1

说明

删掉第三个字符 '1'，字符串变成"100"，代表的数是 4=2^2
算法知识视频讲解
添加回答
Yin_同学头像 Yin_同学
找到二进制的规律就行
object Solution {
    def minCnt(s: String): Int = {
    var sum:Int = 0
    for (i <- s){
      if (i != '0'){
        sum = sum + 1
      }
    }
    sum - 1
    }
}

发表于 2022-06-22 10:06:31 回复(0)
C/C++
牛客719237317号头像 牛客719237317号
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int minCnt(string s) {
        // write code here
        int iCount = count(s.begin(), s.end(), '1');// 仅需获取字符串中1的个数，对于任意二进制字符串，只有形如1...000的字符串为2的幂。
        return iCount-1;
    }
};

发表于 2022-06-14 14:13:27 回复(3)
牛客834091834号头像 牛客834091834号 
class Solution:
    def minCnt(self,s):
      if s == '1':
          return False
      s = s[1:]
          return s.count('1')
         

发表于 2022-08-27 09:41:58 回复(0)
気にしない头像 気にしない
importjava.util.*;
 
 
publicclassSolution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    publicintminCnt (String s) {
        // write code here
         
        //观察并分析s可能出现的情况，可得出以下结论：删除的个数等于s字符串中出现1的次数-1
        //所以只需着力计算出s中1出现的个数即可
        intcount = 0; //记录s中1出现的个数
        intlen = s.length(); //s的长度
        for(inti = 0; i < len; i++) {
            if(s.charAt(i)== '1') {
                count++;
            }
        }
 
        //如果s中没有1，全部为0，则抛出不支持操作异常
        if(count == 0) {
            thrownewUnsupportedOperationException("ths s is not actionable");
        }

        returncount - 1;
    }
}
发表于 2023-04-13 23:41:25 回复(0)
善良的强盗头像 善良的强盗 
import java.util.*;


public class Solution {
    public int minCnt (String s) {
        int res = -1;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '1')
                res++;
        }
        return res;
    }
}
这道题很好理解 就是将多余的1删掉就会是2的幂
发表于 2022-09-08 00:57:26 回复(0)
牛客691022087号头像 牛客691022087号
classSolution:
    defminCnt(self, s: str) -> int:
        return s.count('1')-1
发表于 2022-09-07 21:37:29 回复(0)
Snowya头像 Snowya 
# pyhton 寻找规律
class Solution:
    def minCnt(self , s: str) -> int:
        # write code here
        if int(s)==1:
            return 0
        count = 0

        for i in range(len(s)):
            if s[i]!='0':
                count = count+1
        return count-1
             

发表于 2022-09-05 14:29:15 回复(0)
蒜头王八的种子头像 蒜头王八的种子 
function minCnt( s ) {
    let a=s.split("");
    let num=0;
    for(i=1;i<a.length;i++){
        if(a[i]==1) num++;
    }
    return num
}
module.exports = {
    minCnt : minCnt
};

发表于 2022-09-04 16:54:32 回复(0)
远道.头像 远道.
1的个数减一
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int minCnt (String s) {
        return s.length()-s.replace("1","").length()-1;
    }
}
发表于 2022-08-16 00:20:38 回复(0)
打水漂头像 打水漂 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int minCnt (String s) {
        // write code here
        int sum = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '1') {
                sum++;
            }
        }
        return sum - 1;
    }
}

发表于 2022-08-14 16:08:35 回复(0)
紫川风流头像 紫川风流 
 /* @param s string字符串
 * @return int整型
 */
function minCnt(s) {
  // write code here
  let str = s
  let myRe = /[0]/g;
  return (str.replace(myRe,"")).length-1
}
module.exports = {
  minCnt: minCnt,
};

发表于 2022-08-08 22:16:58 回复(0)
苏觅云头像 苏觅云 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int minCnt(string s) {
        // write code here
        int ans = 0;
        for(int i = 1; i < s.length(); i++) {
            if(s[i] == '1') {
                ans++;
            }
        }
        return ans;
    }
};

发表于 2022-08-01 15:13:20 回复(0)
牛客416168164号头像 牛客416168164号 
classSolution:
    defminCnt(self, s: str) -> int:
        # write code here
        returns.count("1") -1 #计算1的个数并保留一个1


发表于 2022-07-23 15:38:56 回复(1)
多多尝试多多努力头像 多多尝试多多努力
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int minCnt(string s) {
        // write code here
        // 只允许字符串中出现一个1 ，其他 1 都要删除，尽量从字符串后面删除1
        // 遇到 字符 ‘1’ 进栈，最后统计栈的大小,-1 为删除的结果
        stack<char> st;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '1')
                st.push('1');
        }
        return st.size()-1;
    }
};
发表于 2022-07-22 11:08:36 回复(0)
在吵架的王者很精致头像 在吵架的王者很精致 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int minCnt (String s) {
        // write code here
        // 创建一个数组记录每一个位置 其右边 包含 "1" 的个数
        int len = s.length();
        int[] rightOneCount = new int[len];
        int count = 0;
        for (int i = len - 1; i >= 0; i--){
            rightOneCount[i] = count;
            if (s.charAt(i) == '1') count++;
        }
        int index = 0;
        int minCount = len;
        while (index < len){
            if (s.charAt(index) != '1'){
                index++;
            } else {// 找到左端的 1 开始更新最小操作数
                minCount = Math.min(minCount, index + rightOneCount[index]);
            }
            index++;
        }
        return minCount;
    }
}

发表于 2022-07-17 14:31:25 回复(0)
Python
leyex头像 leyex

2的n次方用二进制表示 规律 就是 首位为1，后面位只有0 

def main(src):
    return len(src.replace('0', '')) - 1
发表于 2022-07-05 15:02:14 回复(0)
Java
8102925636号头像 8102925636号
    public int minCnt (String s) {
        int icount = 0;
        for(int i = 0 ; i < s.length();i++){
            if(s.charAt(i) == '1'){
                icount++;
            }
        }
        return icount-1;
    }
按照楼上大神的思路写的
编辑于 2022-07-03 17:14:47 回复(0)
拼搏拼搏！！！头像 拼搏拼搏！！！
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int minCnt (String s) {
        StringBuilder sb=new StringBuilder();
        StringBuilder sb1=new StringBuilder();
        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='1'){
                sb.append(s.charAt(i));
                for (int j=i+1;j<s.length();j++){
                    sb.append(s.charAt(j));
                }
                i=s.length();
            }
        }
        sb1.append(1);
        for (int i=1;i<sb.length();i++){
            if (sb.charAt(i)=='0'){
                sb1.append(sb.charAt(i));
            }
        }

        int minCnt=s.length()-sb1.length();
        return minCnt;
    }
}
发表于 2022-06-08 14:50:50 回复(0)
提交观点

问题信息

上传者：小小
难度：
18条回答 3317浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号