Medium

题目描述

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

请你返回 s 中能够组成小于等于 k 的二进制数的最长子序列的长度。

注意：

  • 子序列可以有前导零。
  • 空字符串视为等于 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 <= 10^9

解题思路

解题思路

这道题需要找到最长的子序列，使得其二进制值不超过 k。关键观察是：

  1. 贪心策略：优先选择 ‘0’，因为 ‘0’ 不会增加数值但能增加长度
  2. 从右到左处理 ‘1’：当遇到 ‘1’ 时，从右到左考虑是否加入，这样能保持数值最小
  3. 动态维护当前值：维护当前选择的子序列对应的数值

算法步骤：

  • 首先统计所有的 ‘0’，它们都可以包含在结果中
  • 从右到左扫描字符串，遇到 ‘1’ 时：
    • 计算如果包含这个 ‘1’，当前数值会变成多少
    • 如果新数值仍然 ≤ k，则包含这个 ‘1’
    • 否则跳过这个 ‘1’

这个贪心策略是正确的，因为：

  • ‘0’ 永远不会让数值变大，所以全部包含
  • 对于 ‘1’，位置越靠右权重越小，优先选择权重小的 ‘1’ 能获得更长的序列

时间复杂度 O(n)，空间复杂度 O(1)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    int longestSubsequence(string s, int k) {
        int n = s.length();
        int zeros = 0;
        int ones = 0;
        long long value = 0;
        long long power = 1;
        
        // 统计0的个数
        for (char c : s) {
            if (c == '0') zeros++;
        }
        
        // 从右到左处理1
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '1') {
                if (value + power <= k) {
                    value += power;
                    ones++;
                }
                power *= 2;
                if (power > k) break; // 优化：后续的1权重太大，直接跳出
            }
        }
        
        return zeros + ones;
    }
};

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        zeros = s.count('0')
        ones = 0
        value = 0
        power = 1
        
        # 从右到左处理1
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '1':
                if value + power <= k:
                    value += power
                    ones += 1
                power *= 2
                if power > k:  # 优化：后续的1权重太大，直接跳出
                    break
        
        return zeros + ones

public class Solution {
    public int LongestSubsequence(string s, int k) {
        int zeros = 0;
        int ones = 0;
        long value = 0;
        long power = 1;
        
        // 统计0的个数
        foreach (char c in s) {
            if (c == '0') zeros++;
        }
        
        // 从右到左处理1
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '1') {
                if (value + power <= k) {
                    value += power;
                    ones++;
                }
                power *= 2;
                if (power > k) break; // 优化：后续的1权重太大，直接跳出
            }
        }
        
        return zeros + ones;
    }
}

var longestSubsequence = function(s, k) {
    const zeros = (s.match(/0/g) || []).length;
    let ones = 0;
    let value = 0;
    let power = 1;
    
    // 从右到左处理1
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，其中 n 为字符串长度
空间复杂度O(1)只使用了常数级别的额外空间

相关题目