2023-12-11|閱讀時間 ‧ 約 3 分鐘

連三碼相同的最大值 Leetcode #2264 Largest 3-SameDigit Num in String

題目敘述

題目會給我們一個字串,要求我們連三碼相同的數字,最大值是多少?

例如 給定輸入="1111222555333",最大值是555


如果無解,則返回空字串""

英文版的題目敘述在這裡


測試範例

Example 1:

Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".

Example 2:

Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.

Example 3:

Input: num = "42352338"
Output: ""
Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

約束條件

Constraints:

  • 3 <= num.length <= 1000
  • num only consists of digits.

演算法

依照題意,從左到右掃描,紀錄連續三碼相同的字元如果比之前的還大,就更新為最大值

實作上要留意的就是:

  1. 迭代的下標,小心不要超出界外。
  2. 題目給的輸入是字串,我們計算過程中會轉成int整數型別,最後輸出答案時,記得轉換回字串的形式

程式碼

class Solution(object):
 def largestGoodInteger(self, num):
  
  largest = -1
  
  for i in range(2, len(num)):

   if num[i] == num[i-1] and num[i-1] == num[i-2]:
    cur_digit = int(num[i])
    largest = max(largest, cur_digit)

  if largest == -1:
   return ""

  # Largest 3 same digit number in terms of string
  return str(largest) * 3

複雜度分析

時間複雜度: O(n)

線性掃描,從右到左掃描每個字元,總共耗時O(n)


空間複雜度: O(1)

所使用到的都是固定尺寸的臨時變數,佔用空間為常數級別O(1)


Reference:

[1] Python O(n) by iteration [w/ Comment] - Largest 3-Same-Digit Number in String - LeetCode

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.