資訊專欄INFORMATION COLUMN
摘要：返回一個(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è)字母只會(huì)出現(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ù)較少。
解答：
這是一個(gè)典型的合并區(qū)間問題，我們可以記錄每個(gè)字符的最小起點(diǎn)和最大終點(diǎn)，這樣每個(gè)字符就形成了一個(gè)存在區(qū)間。把交叉的區(qū)間不斷擴(kuò)大，然后并保存，最后輸出所有合并后的區(qū)間的重點(diǎn)-起點(diǎn)+1。
java ac代碼:
class Solution {
int[]hashmin = new int["z"+1],hashmax = new int["z"+1];
{
for(int i = "a";i <= "z";i++)
{
hashmin[i] = 9999;
hashmax[i] = -1;
}
}
public List partitionLabels(String S) {
List ans = new ArrayList(1000);
for(int i = 0;i < S.length();i++)
{
char c = S.charAt(i);
hashmin[c] = Math.min(hashmin[c],i);
hashmax[c] = Math.max(hashmax[c],i);
}
ArrayList list = new ArrayList(1000);
for(int i = 0;i < S.length();i++)
if(list.isEmpty()||hashmin[S.charAt(i)] > list.get(list.size()-1))
{
list.add(hashmin[S.charAt(i)]);
list.add(hashmax[S.charAt(i)]);
}
else list.set(list.size()-1,Math.max(list.get(list.size()-1),hashmax[S.charAt(i)]));
for(int i = 0;i < list.size(); i += 2)
ans.add(list.get(i+1)-list.get(i)+1);
return ans;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73374.html
摘要：寫在前面今天這篇文章是貪心算法系列的第三篇?jiǎng)澐肿帜竻^(qū)間。前文回顧貪心算法分發(fā)糖果刷題匯總匯總貼今日題目字符串由小寫字母組成。返回一個(gè)表示每個(gè)字符串片段的長度的列表。示例輸入輸出解釋劃分結(jié)果為。每個(gè)字母最多出現(xiàn)在一個(gè)片段中。 寫在前面 今天這篇文章是貪心算法系列的第三篇--劃分字母區(qū)間。 前文回顧： 【LeetCode】貪心算法--分發(fā)糖果（135） 刷題匯總： 【LeetCode】匯總...
Problem A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers represe...
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹特征的無向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁：應(yīng)無所住而生...
閱讀 2785·2021-10-11 11:08
閱讀 1503·2021-09-30 09:48
閱讀 1062·2021-09-22 15:29
閱讀 1050·2019-08-30 15:54
閱讀 990·2019-08-29 15:19
閱讀 542·2019-08-29 13:12
閱讀 3176·2019-08-26 13:53
閱讀 979·2019-08-26 13:28
