{"id":2354,"date":"2018-03-24T12:50:55","date_gmt":"2018-03-24T19:50:55","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2354"},"modified":"2018-03-24T12:51:54","modified_gmt":"2018-03-24T19:51:54","slug":"leetcode-443-string-compression","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-443-string-compression\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 443. String Compression"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

\u9898\u76ee\u5927\u610f\uff1a\u5bf9\u4e00\u4e2astring\u8fdb\u884cin-place\u7684run length encoding\u3002<\/p>\n

https:\/\/leetcode.com\/problems\/string-compression\/description\/<\/a><\/p>\n

Given an array of characters, compress it\u00a0in-place<\/b><\/a>.<\/p>\n

The length after compression must always be smaller than or equal to the original array.<\/p>\n

Every element of the array should be a\u00a0character<\/b>\u00a0(not int) of length 1.<\/p>\n

After you are done\u00a0modifying the input array\u00a0in-place<\/a><\/b>, return the new length of the array.<\/p>\n

Follow up:<\/b>
\nCould you solve it using only O(1) extra space?<\/p>\n

Example 1:<\/b><\/p>\n

Input:<\/b>\r\n[\"a\",\"a\",\"b\",\"b\",\"c\",\"c\",\"c\"]\r\n\r\nOutput:<\/b>\r\nReturn 6, and the first 6 characters of the input array should be: [\"a\",\"2\",\"b\",\"2\",\"c\",\"3\"]\r\n\r\nExplanation:<\/b>\r\n\"aa\" is replaced by \"a2\". \"bb\" is replaced by \"b2\". \"ccc\" is replaced by \"c3\".\r\n<\/pre>\n
Example 2:<\/b><\/p>\n
Input:<\/b>\r\n[\"a\"]\r\n\r\nOutput:<\/b>\r\nReturn 1, and the first 1 characters of the input array should be: [\"a\"]\r\n\r\nExplanation:<\/b>\r\nNothing is replaced.\r\n<\/pre>\n
Example 3:<\/b><\/p>\n
Input:<\/b>\r\n[\"a\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"]\r\n\r\nOutput:<\/b>\r\nReturn 4, and the first 4 characters of the input array should be: [\"a\",\"b\",\"1\",\"2\"].\r\n\r\nExplanation:<\/b>\r\nSince the character \"a\" does not repeat, it is not compressed. \"bbbbbbbbbbbb\" is replaced by \"b12\".\r\nNotice each digit has it's own entry in the array.\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. All characters have an ASCII value in\u00a0[35, 126]<\/code>.<\/li>\n
  2. 1 <= len(chars) <= 1000<\/code>.<\/li>\n<\/ol>\n
    Solution<\/strong><\/h1>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(1)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 9 ms\r\nclass Solution {\r\npublic:\r\n  int compress(vector<char>& chars) {\r\n    const int n = chars.size();\r\n    int p = 0;\r\n    for (int i = 1; i <= n; ++i) {\r\n      int count = 1;\r\n      while (i < n && chars[i] == chars[i - 1]) { ++i; ++count; }\r\n      chars[p++] = chars[i - 1];\r\n      if (count == 1) continue;\r\n      for (char c : to_string(count))\r\n        chars[p++] = c;\r\n    }\r\n    return p;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem \u9898\u76ee\u5927\u610f\uff1a\u5bf9\u4e00\u4e2astring\u8fdb\u884cin-place\u7684run length encoding\u3002 https:\/\/leetcode.com\/problems\/string-compression\/description\/ Given an array of characters, compress it\u00a0in-place. The length after compression must always be smaller than or equal to the…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[270,272,273,271],"class_list":["post-2354","post","type-post","status-publish","format-standard","hentry","category-string","tag-compression","tag-encoding","tag-in-place","tag-run-length","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2354","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2354"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2354\/revisions"}],"predecessor-version":[{"id":2357,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2354\/revisions\/2357"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}