(LeetCode 每日一题) 2311. 小于等于 K 的最长二进制子序列 (贪心+字符串)

题目：2311. 小于等于 K 的最长二进制子序列

思路：贪心+字符串，时间复杂度0(n)。

要想让子序列越长，那么1尽可能放在低位，也就是最右边。
得到k的二进制位数cnt，当字符串s的长度n，n<k时，n为答案；
当n>=k时，需要判断字符串s最右边长度为k的二进制对应的十进制数sum；
当sum<=k时，说明，右半段k个字符都可可选，而左半段只能选非0的字符，因为任何一个1都会造成大于k。
当sum<k时，不选右边开始的第k位元素，那么s[n-k-1,n）对应的十进制一定小于k。

C++版本：

class Solution {
public:
    int longestSubsequence(string s, int k) {
    	// k的二进制位数cnt
        int cnt=0;
        int copy_k=k;
        while(k){
            k>>=1;
            cnt++;
        }
        // 字符串s的长度n
        int n=s.size();
        // n<k时，n为答案
        if(n<cnt) return n;
        // 字符串s最右边长度为k的二进制对应的十进制数sum
        long long sum=0;
        for(int i=n-cnt;i<n;i++){
            sum=sum*2+s[i]-'0';
        }
        //左半段s[0,n-cnt-1]中0的个数
        int ans=0;
        for(int i=n-cnt-1;i>=0;i--){
            if(s[i]=='0') ans++;
        }
        //cout<<cnt<<" "<<sum<<" "<<ans;
        //右半段k个字符都可可选，而左半段只能选非0的字符
        if(sum<=copy_k) return ans+cnt;
        //不选右边开始的第k位元素
        return ans+cnt-1;
    }
};

JAVA版本：

class Solution {
    public int longestSubsequence(String s, int k) {
        int cnt=0;
        int copy_k=k;
        while(k>0){
            k>>=1;
            cnt++;
        }
        int n=s.length();
        if(n<cnt) return n;
        long  sum=0;
        for(int i=n-cnt;i<n;i++){
            sum=sum*2+s.charAt(i)-'0';
        }
        int ans=0;
        for(int i=n-cnt-1;i>=0;i--){
            if(s.charAt(i)=='0') ans++;
        }
        if(sum<=copy_k) return ans+cnt;
        return ans+cnt-1;
    }
    
}

Go版本：

func longestSubsequence(s string, k int) int {
    n:=len(s)
    cnt:=0
    copy_k:=k
    for k>0 {
        k>>=1
        cnt++
    } 
    if n<cnt {
        return n
    }
    var sum int64 = 0 
    for i:=n-cnt;i<n;i++ {
        sum=sum*2+int64(s[i]-'0')
    }
    ans:=0
    for i:=n-cnt-1;i>=0;i-- {
        if s[i]=='0' {
            ans++
        }
    }
    if sum<=int64(copy_k) {
        return ans+cnt
    }
    return ans+cnt-1
}