首頁 後端開發 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)

熱門話題

Java教學
1677
14
CakePHP 教程
1431
52
Laravel 教程
1334
25
PHP教程
1280
29
C# 教程
1257
24
說明PHP中的安全密碼散列(例如,password_hash,password_verify)。為什麼不使用MD5或SHA1? 說明PHP中的安全密碼散列(例如,password_hash,password_verify)。為什麼不使用MD5或SHA1? Apr 17, 2025 am 12:06 AM

在PHP中,應使用password_hash和password_verify函數實現安全的密碼哈希處理,不應使用MD5或SHA1。1)password_hash生成包含鹽值的哈希,增強安全性。 2)password_verify驗證密碼,通過比較哈希值確保安全。 3)MD5和SHA1易受攻擊且缺乏鹽值,不適合現代密碼安全。

PHP類型提示如何起作用,包括標量類型,返回類型,聯合類型和無效類型? PHP類型提示如何起作用,包括標量類型,返回類型,聯合類型和無效類型? Apr 17, 2025 am 12:25 AM

PHP類型提示提升代碼質量和可讀性。 1)標量類型提示:自PHP7.0起,允許在函數參數中指定基本數據類型,如int、float等。 2)返回類型提示:確保函數返回值類型的一致性。 3)聯合類型提示:自PHP8.0起,允許在函數參數或返回值中指定多個類型。 4)可空類型提示:允許包含null值,處理可能返回空值的函數。

PHP和Python:解釋了不同的範例 PHP和Python:解釋了不同的範例 Apr 18, 2025 am 12:26 AM

PHP主要是過程式編程,但也支持面向對象編程(OOP);Python支持多種範式,包括OOP、函數式和過程式編程。 PHP適合web開發,Python適用於多種應用,如數據分析和機器學習。

在PHP和Python之間進行選擇:指南 在PHP和Python之間進行選擇:指南 Apr 18, 2025 am 12:24 AM

PHP適合網頁開發和快速原型開發,Python適用於數據科學和機器學習。 1.PHP用於動態網頁開發,語法簡單,適合快速開發。 2.Python語法簡潔,適用於多領域,庫生態系統強大。

PHP和Python:深入了解他們的歷史 PHP和Python:深入了解他們的歷史 Apr 18, 2025 am 12:25 AM

PHP起源於1994年,由RasmusLerdorf開發,最初用於跟踪網站訪問者,逐漸演變為服務器端腳本語言,廣泛應用於網頁開發。 Python由GuidovanRossum於1980年代末開發,1991年首次發布,強調代碼可讀性和簡潔性,適用於科學計算、數據分析等領域。

PHP和框架:現代化語言 PHP和框架:現代化語言 Apr 18, 2025 am 12:14 AM

PHP在現代化進程中仍然重要,因為它支持大量網站和應用,並通過框架適應開發需求。 1.PHP7提升了性能並引入了新功能。 2.現代框架如Laravel、Symfony和CodeIgniter簡化開發,提高代碼質量。 3.性能優化和最佳實踐進一步提升應用效率。

為什麼要使用PHP?解釋的優點和好處 為什麼要使用PHP?解釋的優點和好處 Apr 16, 2025 am 12:16 AM

PHP的核心優勢包括易於學習、強大的web開發支持、豐富的庫和框架、高性能和可擴展性、跨平台兼容性以及成本效益高。 1)易於學習和使用,適合初學者;2)與web服務器集成好,支持多種數據庫;3)擁有如Laravel等強大框架;4)通過優化可實現高性能;5)支持多種操作系統;6)開源,降低開發成本。

PHP的影響:網絡開發及以後 PHP的影響:網絡開發及以後 Apr 18, 2025 am 12:10 AM

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

See all articles