首頁 後端開發 php教程 從左、右各取K個字符

從左、右各取K個字符

Nov 24, 2024 pm 08:44 PM

Take K of Each Character From Left and Right

2516。從左右各取K個字元

難度:

主題:雜湊表、字串、滑動視窗

給定一個由字元 'a'、'b' 和 'c' 組成的字串 s 以及一個非負整數 k。每分鐘,您可以選取 s 的最左邊字符,或 s 的最右邊字符。

傳回最少取得至少 k 個字元所需的分鐘數,如果不可能取得每個字元的k 個,則傳回-1角色

範例1:

  • 輸入: s = "aabaaaacaabc", k = 2
  • 輸出: 8
  • 解釋:從 s 左邊取三個字元。您現在有兩個“a”字元和一個“b”字元。
    • 從 s 右側取五個字元。您現在有四個“a”字元、兩個“b”字元和兩個“c”字元。
    • 總共需要3 5 = 8分鐘。
    • 可以證明8是最少需要的分鐘數。

範例2:

  • 輸入: s = "a", k = 1
  • 輸出: -1
  • 解釋: 不可能取 'b' 或 'c',因此回傳 -1。

約束:

  • 1 5
  • s 僅由字母 'a'、'b' 和 'c' 組成。
  • 0

提示:

  1. 先計算每個字元的出現頻率並檢查是否可能。
  2. 如果從左側取x個字符,那麼從右側最少需要取多少個字符?對 0 ≤ x ≤ s.length 範圍內的所有 x 值求此值。
  3. 使用兩指標方法來避免多次計算相同的資訊。

解:

我們可以使用帶有兩個指標的滑動視窗技術來找到從左側和右側取出至少 k 個字元('a','b','c')所需的最小分鐘數字串。

問題分解:

  • 給定一個只包含 'a'、'b' 和 'c' 的字串 s。
  • 我們需要從字串的最左邊或最右邊的字元中取得每個字元至少出現的 k 次。
  • 我們需要確定實現此目標所需的最小分鐘數,如果不可能,則傳回 -1。

方法:

  1. 初步檢查

    • 如果 k == 0,我們可以直接回傳 0,因為不需要任何字元。
    • 如果 k 超過字串中任意字元出現的次數,則立即傳回 -1。
  2. 頻率計數:

    • 我們需要統計 'a'、'b' 和 'c' 在字串 s 中出現了多少次,以確保甚至可以收集到每個字元的 k 個。
  3. 滑動視窗技術:

    • 使用兩個指標(左和右)的滑動視窗方法。
    • 維護兩個指針,並從字串兩端滑動它們以收集所需的字元。
    • 對於從左側取出的每個字符,計算需要從右側取出的最少字符數才能滿足要求。
  4. 最佳化

    • 我們可以在擴展或收縮視窗時追蹤字元計數,而不是重複地重新計算每個視窗的字元計數。

讓我們用 PHP 實作這個解:2516。從左右各取K個

<?php
/**
 * @param String $s
 * @param Integer $k
 * @return Integer
 */
function takeCharacters($s, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
echo takeCharacters("aabaaaacaabc", 2);  // Output: 8

// Example 2
echo takeCharacters("a", 1);  // Output: -1
?>
登入後複製

解釋:

  1. 初始設定

    • 我們計算整個字串中「a」、「b」和「c」的出現次數,以確保可以收集至少 k 個字元。
    • 如果任意字元數小於 k,則傳回 -1。
  2. 滑動視窗:

    • 我們使用兩個指標(左和右)從兩端建立一個滑動視窗。
    • 我們透過移動右側指標來擴展視窗並增加遇到的字元數。
    • 一旦目前視窗中的每個字元至少有 k 個,我們就會嘗試從左側縮小視窗以最小化分鐘數(佔用的字元)。
  3. 最小化時間

    • 每次收集所有類型的 k 個字元時,我們都會透過比較視窗的大小來追蹤所需的最少分鐘數。

時間複雜度:

  • 計算字元最初需要 O(n)。
  • 滑動視窗操作需要 O(n),因為左右指標都在字串上移動一次。
  • 整體時間複雜度為 O(n)。

邊緣情況:

  • 如果 k == 0,則回傳 0。
  • 如果不可能取出每個字元的 k,則傳回 -1。

聯絡連結

如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!

如果您想要更多類似的有用內容,請隨時關注我:

  • 領英
  • GitHub

以上是從左、右各取K個字符的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

在PHP API中說明JSON Web令牌(JWT)及其用例。 在PHP API中說明JSON Web令牌(JWT)及其用例。 Apr 05, 2025 am 12:04 AM

JWT是一種基於JSON的開放標準,用於在各方之間安全地傳輸信息,主要用於身份驗證和信息交換。 1.JWT由Header、Payload和Signature三部分組成。 2.JWT的工作原理包括生成JWT、驗證JWT和解析Payload三個步驟。 3.在PHP中使用JWT進行身份驗證時,可以生成和驗證JWT,並在高級用法中包含用戶角色和權限信息。 4.常見錯誤包括簽名驗證失敗、令牌過期和Payload過大,調試技巧包括使用調試工具和日誌記錄。 5.性能優化和最佳實踐包括使用合適的簽名算法、合理設置有效期、

會話如何劫持工作,如何在PHP中減輕它? 會話如何劫持工作,如何在PHP中減輕它? Apr 06, 2025 am 12:02 AM

會話劫持可以通過以下步驟實現:1.獲取會話ID,2.使用會話ID,3.保持會話活躍。在PHP中防範會話劫持的方法包括:1.使用session_regenerate_id()函數重新生成會話ID,2.通過數據庫存儲會話數據,3.確保所有會話數據通過HTTPS傳輸。

PHP 8.1中的枚舉(枚舉)是什麼? PHP 8.1中的枚舉(枚舉)是什麼? Apr 03, 2025 am 12:05 AM

PHP8.1中的枚舉功能通過定義命名常量增強了代碼的清晰度和類型安全性。 1)枚舉可以是整數、字符串或對象,提高了代碼可讀性和類型安全性。 2)枚舉基於類,支持面向對象特性,如遍歷和反射。 3)枚舉可用於比較和賦值,確保類型安全。 4)枚舉支持添加方法,實現複雜邏輯。 5)嚴格類型檢查和錯誤處理可避免常見錯誤。 6)枚舉減少魔法值,提升可維護性,但需注意性能優化。

描述紮實的原則及其如何應用於PHP的開發。 描述紮實的原則及其如何應用於PHP的開發。 Apr 03, 2025 am 12:04 AM

SOLID原則在PHP開發中的應用包括:1.單一職責原則(SRP):每個類只負責一個功能。 2.開閉原則(OCP):通過擴展而非修改實現變化。 3.里氏替換原則(LSP):子類可替換基類而不影響程序正確性。 4.接口隔離原則(ISP):使用細粒度接口避免依賴不使用的方法。 5.依賴倒置原則(DIP):高低層次模塊都依賴於抽象,通過依賴注入實現。

解釋PHP中的晚期靜態綁定(靜態::)。 解釋PHP中的晚期靜態綁定(靜態::)。 Apr 03, 2025 am 12:04 AM

靜態綁定(static::)在PHP中實現晚期靜態綁定(LSB),允許在靜態上下文中引用調用類而非定義類。 1)解析過程在運行時進行,2)在繼承關係中向上查找調用類,3)可能帶來性能開銷。

什麼是REST API設計原理? 什麼是REST API設計原理? Apr 04, 2025 am 12:01 AM

RESTAPI設計原則包括資源定義、URI設計、HTTP方法使用、狀態碼使用、版本控制和HATEOAS。 1.資源應使用名詞表示並保持層次結構。 2.HTTP方法應符合其語義,如GET用於獲取資源。 3.狀態碼應正確使用,如404表示資源不存在。 4.版本控制可通過URI或頭部實現。 5.HATEOAS通過響應中的鏈接引導客戶端操作。

您如何在PHP中有效處理異常(嘗試,捕捉,最後,投擲)? 您如何在PHP中有效處理異常(嘗試,捕捉,最後,投擲)? Apr 05, 2025 am 12:03 AM

在PHP中,異常處理通過try,catch,finally,和throw關鍵字實現。 1)try塊包圍可能拋出異常的代碼;2)catch塊處理異常;3)finally塊確保代碼始終執行;4)throw用於手動拋出異常。這些機制幫助提升代碼的健壯性和可維護性。

PHP中的匿名類是什麼?您何時可以使用它們? PHP中的匿名類是什麼?您何時可以使用它們? Apr 04, 2025 am 12:02 AM

匿名類在PHP中的主要作用是創建一次性使用的對象。 1.匿名類允許在代碼中直接定義沒有名字的類,適用於臨時需求。 2.它們可以繼承類或實現接口,增加靈活性。 3.使用時需注意性能和代碼可讀性,避免重複定義相同的匿名類。

See all articles