leetcode 2311. Longest Binary Subsequence Less Than or Equal to K（python）

語言: CN / TW / HK
時間 2022-06-24 11:15:11

持續創作，加速成長！這是我參與「掘金日新計劃 · 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

原題連結

http://leetcode.com/contest/weekly-contest-298/problems/longest-binary-subsequence-less-than-or-equal-to-k/

您的支援是我最大的動力

「」
「」