題目
給你一個二進制字符串 s 和一個正整數(shù) k 。
請你返回 s 的 最長 子序列，且該子序列對應的 二進制 數(shù)字小于等于 k 。
子序列 是指從一個字符串中刪除零個或者多個字符后，不改變順序得到的剩余字符序列。
示例 1：輸入：s = “1001010”, k = 5 輸出：5
解釋：s 中小于等于 5 的最長子序列是 “00010” ，對應的十進制數(shù)字是 2 。
注意 “00100” 和 “00101” 也是可行的最長子序列，十進制分別對應 4 和 5 。
最長子序列的長度為 5 ，所以返回 5 。
示例 2：輸入：s = “00101001”, k = 1 輸出：6
解釋：”000001″ 是 s 中小于等于 1 的最長子序列，對應的十進制數(shù)字是 1 。
最長子序列的長度為 6 ，所以返回 6 。
提示：1 <= s.length <= 1000
s[i] 要么是 ‘0’ ，要么是 ‘1’ 。
1 <= k <= 109
解題思路分析
1、貪心；時間復雜度O(n)，空間復雜度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、貪心；時間復雜度O(n)，空間復雜度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題目，使用貪心思想
