涩视频在线观看,91超碰人妻,AA片在线播放,69视频网在线观看,国产内射免费观看视频,日韩av男人天堂,免费无码国产在线观看,变态另类一区

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做?編碼最短長(zhǎng)度的字符串，我們先來(lái)看題面：

https://leetcode-cn.com/problems/encode-string-with-shortest-length/

Given a non-empty string, encode the string such that its encoded length is the shortest.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.

Note:

1、k will be a positive integer and encoded string will not be empty or have extra space.
2、You may assume that the input string contains only lowercase English letters. The string's length is at most 160.
3、If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.

給定一個(gè) 非空字符串，將其編碼為具有最短長(zhǎng)度的字符串。

編碼規(guī)則是：k[encoded_string]，其中在方括號(hào) encoded_string 中的內(nèi)容重復(fù) k 次。

注：

k 為正整數(shù)且編碼后的字符串不能為空或有額外的空格。

你可以假定輸入的字符串只包含小寫的英文字母。字符串長(zhǎng)度不超過(guò) 160。

如果編碼的過(guò)程不能使字符串縮短，則不要對(duì)其進(jìn)行編碼。如果有多種編碼方式，返回任意一種即可。

示例? ? ? ? ? ? ? ? ? ? ? ? ?

示例 1：

輸入："aaa"
輸出："aaa"
解釋：無(wú)法將其編碼為更短的字符串，因此不進(jìn)行編碼。

示例 2：

輸入："aaaaa"
輸出："5[a]"
解釋："5[a]"?比 "aaaaa"?短 1?個(gè)字符。

示例 3：

輸入："aaaaaaaaaa"
輸出："10[a]"
解釋："a9[a]"?或 "9[a]a"?都是合法的編碼，和 "10[a]"?一樣長(zhǎng)度都為 5。

示例 4：

輸入："aabcaabcd"
輸出："2[aabc]d"
解釋："aabc"?出現(xiàn)兩次，因此一種答案可以是 "2[aabc]d"。

示例 5：

輸入："abbbabbbcabbbabbbc"
輸出："2[2[abbb]c]"
解釋："abbbabbbc"?出現(xiàn)兩次，但是 "abbbabbbc"?可以編碼為 "2[abbb]c"，因此一種答案可以是 "2[2

解題

https://www.cnblogs.com/grandyang/p/6194403.html

這道題讓我們壓縮字符串，把相同的字符串用中括號(hào)括起來(lái)，然后在前面加上出現(xiàn)的次數(shù)，感覺(jué)還是一道相當(dāng)有難度的題呢。參考了網(wǎng)上大神的帖子才弄懂該怎么做，這道題還是應(yīng)該用DP來(lái)做。我們建立一個(gè)二維的DP數(shù)組，其中dp[i][j]表示s在[i, j]范圍內(nèi)的字符串的縮寫形式(如果縮寫形式長(zhǎng)度大于子字符串，那么還是保留子字符串)，那么如果s字符串的長(zhǎng)度是n，最終我們需要的結(jié)果就保存在dp[0][n-1]中，然后我們需要遍歷s的所有子字符串，對(duì)于任意一段子字符串[i, j]，我們\\我們以中間任意位置k來(lái)拆分成兩段，比較dp[i][k]加上dp[k+1][j]的總長(zhǎng)度和dp[i][j]的長(zhǎng)度，將長(zhǎng)度較小的字符串賦給dp[i][j]，然后我們要做的就是在s中取出[i, j]范圍內(nèi)的子字符串t進(jìn)行合并。合并的方法是我們?cè)谌〕龅淖址畉后面再加上一個(gè)t，然后在這里面尋找子字符串t的第二個(gè)起始位置，如果第二個(gè)起始位置小于t的長(zhǎng)度的話，說(shuō)明t包含重復(fù)字符串，舉個(gè)例子吧，比如 t = "abab", 那么t+t = "abababab"，我們?cè)诶锩嬲业诙€(gè)t出現(xiàn)的位置為2，小于t的長(zhǎng)度4，說(shuō)明t中有重復(fù)出現(xiàn)，重復(fù)的個(gè)數(shù)為t.size()/pos = 2個(gè)，那么我們就要把重復(fù)的地方放入中括號(hào)中，注意中括號(hào)里不能直接放這個(gè)子字符串，而是應(yīng)該從dp中取出對(duì)應(yīng)位置的字符串，因?yàn)橹貜?fù)的部分有可能已經(jīng)寫成縮寫形式了，比如題目中的例子5。再看一個(gè)例子，如果t = "abc"，那么t+t = "abcabc"，我們?cè)诶锩嬲业诙€(gè)t出現(xiàn)的位置為3，等于t的長(zhǎng)度3，說(shuō)明t中沒(méi)有重復(fù)出現(xiàn)，那么replace就還是t。然后我們比較我們得到的replace和dp[i][j]中的字符串長(zhǎng)度，把長(zhǎng)度較小的賦給dp[i][j]即可，時(shí)間復(fù)雜度為O(n3)，空間復(fù)雜度為O(n2)，參見(jiàn)代碼如下：

class?Solution?{
public:
????string?encode(string?s)?{
????????int?n = s.size();
????????vector<vector<string>> dp(n, vector<string>(n, ""));
????????for?(int?step = 1; step <= n; ++step) {
????????????for?(int?i = 0; i + step - 1?< n; ++i) {
????????????????int?j = i + step - 1;
????????????????dp[i][j] = s.substr(i, step);
????????????????for?(int?k = i; k < j; ++k) {
????????????????????string?left = dp[i][k], right = dp[k + 1][j];
????????????????????if?(left.size() + right.size() < dp[i][j].size()) {
????????????????????????dp[i][j] = left + right;
????????????????????}
????????????????}
????????????????string?t = s.substr(i, j - i + 1), replace = "";
????????????????auto?pos = (t + t).find(t, 1);
????????????????if?(pos >= t.size()) replace = t;
????????????????else?replace = to_string(t.size() / pos) + '['?+ dp[i][i + pos - 1] + ']';
????????????????if?(replace.size() < dp[i][j].size()) dp[i][j] = replace;
????????????}
????????}
????????return?dp[0][n - 1];
????}
};