題目
給你一個(gè)二進(jìn)制字符串 s 和一個(gè)正整數(shù) k 。
請(qǐng)你返回 s 的 最長(zhǎng) 子序列，且該子序列對(duì)應(yīng)的 二進(jìn)制 數(shù)字小于等于 k 。
注意：子序列可以有 前導(dǎo) 0 。 空字符串視為 0 。
子序列 是指從一個(gè)字符串中刪除零個(gè)或者多個(gè)字符后，不改變順序得到的剩余字符序列。
示例 1：輸入：s = “1001010”, k = 5 輸出：5
解釋：s 中小于等于 5 的最長(zhǎng)子序列是 “00010” ，對(duì)應(yīng)的十進(jìn)制數(shù)字是 2 。
注意 “00100” 和 “00101” 也是可行的最長(zhǎng)子序列，十進(jìn)制分別對(duì)應(yīng) 4 和 5 。
最長(zhǎng)子序列的長(zhǎng)度為 5 ，所以返回 5 。
示例 2：輸入：s = “00101001”, k = 1 輸出：6
解釋：”000001″ 是 s 中小于等于 1 的最長(zhǎng)子序列，對(duì)應(yīng)的十進(jìn)制數(shù)字是 1 。
最長(zhǎng)子序列的長(zhǎng)度為 6 ，所以返回 6 。
提示：1 <= s.length <= 1000
s[i] 要么是 ‘0’ ，要么是 ‘1’ 。
1 <= k <= 109
解題思路分析
1、貪心；時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)
func longestSubsequence(s string, k int) int { res := 0 sum, bitValue := int64(0), int64(1) target := int64(k) for i := len(s) – 1; i >= 0; i– { if s[i] == ‘0’ { // 0全部加上 res++ } else if sum <= target { sum = sum + bitValue if sum <= target { // 小于<=k加上 res++ } } if sum <= target && bitValue <= target { bitValue = bitValue * 2 } } return res}
2、貪心；時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)
func longestSubsequence(s string, k int) int { res := 0 sum, bitValue := 0, 1 for i := len(s) – 1; i >= 0; i– { if s[i] == ‘0’ { // 0全部加上 res++ } else { if sum+bitValue <= k { res++ sum = sum + bitValue } } if bitValue <= k { bitValue = bitValue * 2 } } return res}
總結(jié)
Medium題目，使用貪心思想
