【leetcode 簡單】 第一百零六題

  • 2020 年 1 月 19 日
  • 筆記

給定一組字元,使用原地演算法將其壓縮。

壓縮後的長度必須始終小於或等於原數組長度。

數組的每個元素應該是長度為1 的字元(不是 int 整數類型)。

在完成原地修改輸入數組後,返回數組的新長度。

進階: 你能否僅使用O(1) 空間解決問題?

示例 1:

輸入:  ["a","a","b","b","c","c","c"]    輸出:  返回6,輸入數組的前6個字元應該是:["a","2","b","2","c","3"]    說明:  "aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

示例 2:

輸入:  ["a"]    輸出:  返回1,輸入數組的前1個字元應該是:["a"]    說明:  沒有任何字元串被替代。

示例 3:

輸入:  ["a","b","b","b","b","b","b","b","b","b","b","b","b"]    輸出:  返回4,輸入數組的前4個字元應該是:["a","b","1","2"]。    說明:  由於字元"a"不重複,所以不會被壓縮。"bbbbbbbbbbbb"被「b12」替代。  注意每個數字在數組中都有它自己的位置。

注意:

  1. 所有字元都有一個ASCII值在[35, 126]區間內。
  2. 1 <= len(chars) <= 1000
class Solution:      def compress(self, chars):          """          :type chars: List[str]          :rtype: int          """          count,i = 1,0 #count為 字元重複次數,i為最終返回列表長度          chars_len = len(chars)          for j in range(1,chars_len+1):              if j < chars_len and chars[j] == chars[j-1]:                  count+=1 #當chars的當前位置字元和前一個位置字元相等時,增加字元重複次數的計數              else:                  chars[i] = chars[j-1] #當chars的當前位置字元和前一個位置字元不相等時,更改列表i位置的元素                  i += 1                #i的位置後移一位                  if count > 1:         #如果存在重複的字元 將count轉換為字元串 賦值到列表i的位置                      for a in str(count):                          chars[i] = a                          i += 1                  count = 1            #初始化count          return i #i是最後更改後列表的長度