2311.小于等于 K 的最长二进制子序列：贪心（先选0再选1）-好像还是比灵神写的清晰些

【LetMeFly】2311.小于等于 K 的最长二进制子序列：贪心（先选0再选1）-好像还是比灵神写的清晰些

力扣题目链接：https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k/

给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列，且该子序列对应的 二进制 数字小于等于 k 。

注意：

• 子序列可以有 前导 0 。
• 空字符串视为 0 。
• 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

 

示例 1：

输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。

示例 2：

输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。

 

提示：

• 1 <= s.length <= 1000
• s[i] 要么是 '0' ，要么是 '1' 。
• 1 <= k <= 109

解题方法：贪心

二话不说选中所有0，接着从右往左开始选1，全程保证所选元素不超过$k$。

Why?

选1可能导致没法选后面的0，选0不会影响后面的选择。如果选1导致无法选后面的0，那么不如舍弃这个1直接替换成0。综上先选0更优。

选1好说，当然是从低位往高位选1啦。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-06-26 22:16:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-26 22:43:01
 */
class Solution {
public:
    int longestSubsequence(string s, int k) {
        int ans = 0, val = 0, k_length = 32 - __builtin_clz(k), n = s.size();  // k=0时k_length=0计算错误也不受影响
        for (int i = 0; i < n; i++) {
            if (s[n - i - 1] == '0') {
                ans++;
                continue;
            }
            if (i < k_length && val + (1 << i) <= k) {
                val += 1 << i;
                ans++;
            }
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-06-26 22:16:30
LastEditors: LetMeFly.xyz
LastEditTime: 2025-06-26 22:38:54
'''
class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        ans, val, k_length = 0, 0, k.bit_length()
        for i, c in enumerate(s[::-1]):
            if c == '0':
                ans += 1
                continue
            if i < k_length and val + (1 << i) <= k:
                ans += 1
                val += 1 << i
        return ans

Python也可以理解为依次删除左边1直到int(s)<=k。

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-06-26 22:16:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-26 22:45:37
 */
class Solution {
    public int longestSubsequence(String s, int k) {
        int ans = 0, n = s.length(), lenK = 32 - Integer.numberOfLeadingZeros(k), val = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(n - i - 1) == '0') {
                ans++;
                continue;
            }
            if (i < lenK && val + (1 << i) <= k) {
                val += 1 << i;
                ans++;
            }
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-06-26 22:16:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-26 22:39:55
 */
package main

import "math/bits"

func longestSubsequence(s string, k int) (ans int) {
    val, n, lenK := 0, len(s), bits.Len(uint(k))
    for i := 0; i < n; i++ {
        if s[n - i - 1] == '0' {
            ans++
            continue
        }
        if i < lenK && val + (1 << i) <= k {
            ans++
            val += 1 << i
        }
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源