亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

【LeetCode】貪心算法--劃分字母區(qū)間（763）

honhon / 3039人閱讀

摘要：寫在前面今天這篇文章是貪心算法系列的第三篇?jiǎng)澐肿帜竻^(qū)間。前文回顧貪心算法分發(fā)糖果刷題匯總匯總貼今日題目字符串由小寫字母組成。返回一個(gè)表示每個(gè)字符串片段的長度的列表。示例輸入輸出解釋劃分結(jié)果為。每個(gè)字母最多出現(xiàn)在一個(gè)片段中。

寫在前面

今天這篇文章是貪心算法系列的第三篇--劃分字母區(qū)間。

前文回顧：

【LeetCode】貪心算法--分發(fā)糖果（135）

刷題匯總：

【LeetCode】匯總貼（NO.1-20）

今日題目

字符串 S 由小寫字母組成。我們要把這個(gè)字符串劃分為盡可能多的片段，同一個(gè)字母只會出現(xiàn)在其中的一個(gè)片段。返回一個(gè)表示每個(gè)字符串片段的長度的列表。

示例 1:
輸入: S = "ababcbacadefegdehijhklij"
輸出: [9,7,8]
解釋:
劃分結(jié)果為 "ababcbaca", "defegde", "hijhklij"。
每個(gè)字母最多出現(xiàn)在一個(gè)片段中。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯(cuò)誤的，因?yàn)閯澐值钠螖?shù)較少。

注意:
S的長度在[1, 500]之間。
S只包含小寫字母"a"到"z"。

題目分析

解決此題關(guān)鍵就是找到能分割的條件，對S的每個(gè)字符進(jìn)行判斷，看是否此字符是被分割到另一個(gè)字符中，從題目中得到每個(gè)字母最多出現(xiàn)在一個(gè)片段中，那么從第一個(gè)字符開始，它的最后一個(gè)相同的字符一定在這個(gè)片段中，得到第一個(gè)條件：

當(dāng)此字符在前面分割中出現(xiàn)，就不能當(dāng)做分割點(diǎn)

只有這個(gè)條件就可以了嗎？我們再考慮一下，當(dāng)前字符并沒有在前面分割的區(qū)間中出現(xiàn)，是不是能直接作為分割點(diǎn)呢？以下面的字符串為例進(jìn)行分割。

“aaaaab cdaefgh”
當(dāng)判斷b的時(shí)候，先在前面已經(jīng)分好的字符串a(chǎn)aaaa里面沒有，符合找到的第一個(gè)條件，如果我們把b當(dāng)做新的分割點(diǎn)，很明顯是錯(cuò)誤的，因?yàn)樵赽后面的字符串里，又一次出現(xiàn)了a，當(dāng)我們以b作為分割點(diǎn)是不符合條件的，因此得到第二個(gè)限制條件：
分割點(diǎn)后面不能出現(xiàn)前面一個(gè)字符串中的字符。

進(jìn)行了上面的分析但是可以用python做個(gè)弊,使用rindex()方法，從第一個(gè)字符開始，假設(shè)位置為a，用rindex方法找到最后一次出現(xiàn)的位置b，那么這個(gè)區(qū)間就為[a,b]。之后每個(gè)字符都找最后一個(gè)位置，如果在區(qū)間之外則擴(kuò)大區(qū)間，如果遍歷到區(qū)間的最后一個(gè)位置，則結(jié)束，長度就為結(jié)束位置減開始位置加1。

代碼實(shí)現(xiàn)

class Solution:

def partitionLabels(self, S):
    """
    :type S: str
    :rtype: List[int]
    """

    i = 0
    res = []
    while i < len(S):
        start = i
        end = S.rindex(S[i])
        for j in range(i,len(S)):
            last = S.rindex(S[j])
            if last > end:
                end = last
            elif j == end:
                res.append(end-start + 1)
                i = end + 1
                break
    return res

推薦閱讀：

python異常報(bào)錯(cuò)詳解

機(jī)器學(xué)習(xí)實(shí)戰(zhàn)--住房月租金預(yù)測（3）

機(jī)器學(xué)習(xí)實(shí)戰(zhàn)--住房月租金預(yù)測（2）

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/45041.html

相關(guān)文章

  • 力扣(LeetCode)763

    摘要：返回一個(gè)表示每個(gè)字符串片段的長度的列表。示例輸入輸出解釋劃分結(jié)果為。每個(gè)字母最多出現(xiàn)在一個(gè)片段中。像的劃分是錯(cuò)誤的，因?yàn)閯澐值钠螖?shù)較少。把交叉的區(qū)間不斷擴(kuò)大，然后并保存，最后輸出所有合并后的區(qū)間的重點(diǎn)起點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述：字符串 S 由小寫字母組成。我們要把這個(gè)字符串劃分為盡可能多的片段，同一個(gè)字母只會出現(xiàn)在其中的...

    stdying 評論0 收藏0

  • 除了畫佩奇我們還要玩點(diǎn)更高級的

    摘要：啥是佩奇已不重要。佩奇是他用搜集的所有信息，一點(diǎn)一滴的用心創(chuàng)造編織愛的過程。畫佩奇的代碼已經(jīng)上傳到后臺，公眾號后臺回復(fù)社會人即可獲取。 你告訴爺爺你需要什么東西呀，爺爺給你準(zhǔn)備，佩奇，什么是佩奇呀？... 這是一個(gè)發(fā)生在大山里的故事，但故事的情節(jié)所有人都不會陌生?？爝^年了，在農(nóng)村爺爺給城里的孫子打電話，孫子說想要佩奇，為了滿足孩子的心愿，爺爺開始滿村子找佩奇… 當(dāng)除夕夜家人團(tuán)聚，爺爺開...

    Dean 評論0 收藏0

  • 除了畫佩奇我們還要玩點(diǎn)更高級的

    摘要：啥是佩奇已不重要。佩奇是他用搜集的所有信息，一點(diǎn)一滴的用心創(chuàng)造編織愛的過程。畫佩奇的代碼已經(jīng)上傳到后臺，公眾號后臺回復(fù)社會人即可獲取。 你告訴爺爺你需要什么東西呀，爺爺給你準(zhǔn)備，佩奇，什么是佩奇呀？... 這是一個(gè)發(fā)生在大山里的故事，但故事的情節(jié)所有人都不會陌生?？爝^年了，在農(nóng)村爺爺給城里的孫子打電話，孫子說想要佩奇，為了滿足孩子的心愿，爺爺開始滿村子找佩奇… 當(dāng)除夕夜家人團(tuán)聚，爺爺開...

    tomener 評論0 收藏0

  • LeetCode——Longest Substring Without Repeating Char

    摘要：原問題我的沙雕解法無重復(fù)字母存在重復(fù)字母挨打最暴力的無腦解法，耗時(shí)。。。 原問題 Given a string, find the length of the?longest substring?without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...

    forsigner 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<