当前位置：首页 > news >正文

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

news 2025/6/27 17:09:10

【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 <= 10⁹

解题方法：贪心

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

Why?

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

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

时间复杂度 $O (l e n (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 += 1continueif i < k_length and val + (1 << i) <= k:ans += 1val += 1 << ireturn 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 mainimport "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
}