golang刷leetcode: 小于等于 K 的最長(zhǎng)二進(jìn)制子序列

給你一個(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，貪心思想：對(duì)于0都要保留，對(duì)于1，盡可能多保留

2，如果確定保留還是丟棄1，從最低位開(kāi)始，如果計(jì)算出來(lái)的10進(jìn)制數(shù)大于k需要丟棄

3，我們統(tǒng)計(jì)需要丟棄的1的個(gè)數(shù)，就可以得到最多保留長(zhǎng)度

4，這個(gè)題比較坑的地方在于字符串的長(zhǎng)度，因?yàn)樽畲笫?000，超過(guò)了整型的標(biāo)識(shí)范圍會(huì)溢出，也就是總有兩個(gè)用例不能通過(guò)的原因。

代碼實(shí)現(xiàn)：

func longestSubsequence(s string, k int) int {  sum:=0  removed:=0  for i:=0;i<len(s);i++{      if s[len(s)-1-i]=='1'{          if sum>=k{              removed++          }else if i>31{              removed++          }else{              sum+=1<<i              if sum >k{                  removed++              }          }      }  }  return len(s)-removed}

推薦閱讀

• Go 每日一庫(kù)之 hystrix-go