leetcode 2311. Longest Binary Subsequence Less Than or Equal to K(python)
持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第31天,點選檢視活動詳情
描述
You are given a binary string s and a positive integer k. Return the length of the longest subsequence of s that makes up a binary number less than or equal to k.
Note:
- The subsequence can contain leading zeroes.
- The empty string is considered to be equal to 0.
- A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Example 1:
Input: s = "1001010", k = 5
Output: 5
Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.
Example 2:
Input: s = "00101001", k = 1
Output: 6
Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.
Note:
1 <= s.length <= 1000
s[i] is either '0' or '1'.
1 <= k <= 10^9
解析
根據題意,給定一個二進位制字串 s 和一個正整數 k 。返回組成小於或等於 k 的二進位制數的 s 的最長子序列的長度。
需要注意的有:
- 子序列可以包含前導零
- 空字串被認為等於 0
- 子序列是一個字串,可以通過對一個字串刪除一些字元或不刪除字元而不改變剩餘字元的順序所產生的字元序列
這道題考查的是貪心思想,假如我們現在有一個長度為 1 的二進位制字串,如果在其左邊加 0 不會改變大小,但是會增加長度,這符合題目要找最長子序列的要求,所有儘可能在左邊加 0 ,在其左邊加 1 會使其原數大小乘二,所以我們要讓 1 儘量靠右,這樣才能在左邊不斷加 1 找出更大的數字,題目要求找一個長度最大同時又不超過 k 的二進位制子序列,我們可以從後往前遍歷 s ,先找出剛好不超過 k 的二進位制字串,然後再加上其左邊的所有 0 即為最後的結果長度。
時間複雜度為 O(N) ,空間複雜度為 O(N) 。
解答
class Solution(object):
def longestSubsequence(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
N = len(s)
for i in range(1, N+1):
if s[-i] == '1':
a = int(s[-i:], 2)
if a > k:
return s[:-i+1].count('0') + (i-1)
return len(s)
執行結果
153 / 153 test cases passed.
Status: Accepted
Runtime: 46 ms
Memory Usage: 13.6 MB
原題連結
https://leetcode.com/contest/weekly-contest-298/problems/longest-binary-subsequence-less-than-or-equal-to-k/
您的支援是我最大的動力
「其他文章」
- linux 安裝 ES 8.0 和 kibana 8.0 爬米共坑
- ES 8.0 及其生態配置過程一條龍服務
- 2022 年中紀
- leetcode 1048. Longest String Chain(python)
- leetcode 1354. Construct Target Array With Multiple Sums(python)
- leetcode 2311. Longest Binary Subsequence Less Than or Equal to K(python)
- leetcode 2304. Minimum Path Cost in a Grid(python)
- leetcode 2303. Calculate Amount Paid in Taxes(python)
- 帶你輕鬆入門 Bert
- leetcode 1332. Remove Palindromic Subsequences(python)
- leetcode 3. Longest Substring Without Repeating Characters (python)
- leetcode 2296. Design a Text Editor (python)
- leetcode 2293. Min Max Game(python)
- leetcode 1584. Min Cost to Connect All Points(python)
- leetcode 318. Maximum Product of Word Lengths(python)
- 沙灘 美女才是夏天的正確開啟方式
- leetcode 2275. Largest Combination With Bitwise AND Greater Than Zero (python)
- leetcode 2258. Escape the Spreading Fire(python)
- leetcode 2257. Count Unguarded Cells in the Grid(python)
- leetcode 2273. Find Resultant Array After Removing Anagrams(python)