class Solution {
public:
int longestSubsequence(string s, int k) {
}
};
2311. 小于等于 K 的最长二进制子序列
给你一个二进制字符串 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 <= 1000s[i] 要么是 '0' ，要么是 '1' 。1 <= k <= 109原站题解
php 解法, 执行用时: 8 ms, 内存消耗: 18.9 MB, 提交时间: 2023-10-08 15:09:33
class Solution {
/**
* @param String $s
* @param Integer $k
* @return Integer
*/
function longestSubsequence($s, $k) {
$ans = $cnt = 0;
for ($i = 0; $i < strlen($s); ++$i)
if ($s[$i] == 0) $cnt++;
for ($i = strlen($s) - 1; $i >= 0; --$i) {
if (bindec(substr($s, $i)) > $k) {
return $ans + $cnt;
}
if ($s[$i]) $ans++;
}
return $ans + $cnt;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 16 MB, 提交时间: 2023-10-08 15:08:35
class Solution:
def longestSubsequence(self, s: str, k: int) -> int:
while int(s, 2) > k:
s = s.replace('1', '', 1)
return len(s)
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-08 15:07:55
func longestSubsequence(s string, k int) int {
n, m := len(s), bits.Len(uint(k))
if n < m {
return n
}
ans := m
if v, _ := strconv.ParseInt(s[n-m:], 2, 0); int(v) > k {
ans--
}
return ans + strings.Count(s[:n-m], "0")
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.8 MB, 提交时间: 2023-10-08 15:07:38
class Solution {
public:
int longestSubsequence(string s, int k) {
int n = s.length(), m = 32 - __builtin_clz(k);
if (n < m) return n;
int ans = stoi(s.substr(n - m), nullptr, 2) <= k ? m : m - 1;
return ans + count(s.begin(), s.end() - m, '0');
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-08 15:06:57
class Solution {
public int longestSubsequence(String s, int k) {
//m 是 k 有几位，整数一共有32位，减掉2进制前导0的数目就是k代表数值的二进制长度
int n = s.length(), m = 32 - Integer.numberOfLeadingZeros(k);
//字符串总位数无法和k二进制位数相等，比它少，说明不可能超过k,直接返回全长
if (n < m) return n;
//刚好是一样位数的这一位，可能要也可能不要，如果加最高位超出最高位就不要，否则就要
//比如 k=110, 如果拿到字符串尾巴是 111，比k大，那只能要2位，如果是101，比k小就能都要
var ans = Integer.parseInt(s.substring(n - m), 2) <= k ? m : m - 1;
//然后看前面的0的数目，把0的数目加起来就是答案
return ans + (int) s.substring(0, n - m).chars().filter(c -> c == '0').count();
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-10-08 15:05:46
class Solution:
def longestSubsequence(self, s: str, k: int) -> int:
n, m = len(s), k.bit_length()
if n < m: return n
ans = m if int(s[-m:], 2) <= k else m - 1
return ans + s[:-m].count('0')