{"id":437,"date":"2013-05-13T15:10:06","date_gmt":"2013-05-13T22:10:06","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=437"},"modified":"2013-05-13T16:15:13","modified_gmt":"2013-05-13T23:15:13","slug":"ctci-ch-1-5","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=437","title":{"rendered":"CTCI: Ch. 1-5"},"content":{"rendered":"<p>\n\t<strong>Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the &ldquo;compressed&rdquo; string would not become smaller than the original string, your method should return the original string.<\/strong>\n<\/p>\n<p>\n\t<!--more-->\n<\/p>\n<pre class=\"brush:cpp;\">\r\n#include &lt;iostream&gt;\r\n#include &lt;math.h&gt;\r\nusing namespace std;\r\nint coutCompression(char *inputStr);\r\nstring compressStr(char *inputStr);\r\n\r\nstring compressStr(char *inputStr)\r\n{\r\n    int compressSize = coutCompression(inputStr);\r\n    if(compressSize &gt;= strlen(inputStr))\r\n    {\r\n        return inputStr;\r\n    }\r\n    else\r\n    {\r\n        int count = 1;\r\n        char last = inputStr[0];\r\n        string newStr = &quot;&quot;;\r\n        \r\n        for(int i=1;i&lt;strlen(inputStr);i++)\r\n        {\r\n            if(inputStr[i] == last)\r\n            {\r\n                count++;\r\n            }\r\n            else\r\n            {\r\n                \/\/ string (size_t n, char c);\r\n                newStr += string(1,last) + to_string(count);\r\n                last = inputStr[i];\r\n                count = 1;\r\n            }\r\n        }\r\n        newStr += string(1,last) + to_string(count);\r\n        return newStr;\r\n    }\r\n    \r\n}\r\n\r\nint coutCompression(char *inputStr)\r\n{\r\n    int size = 0;\r\n    int count = 1;\r\n    char last = inputStr[0];\r\n\r\n    for(int i=1;i&lt;strlen(inputStr);i++)\r\n    {\r\n        if(inputStr[i] == last)\r\n        {\r\n            count++;\r\n        }\r\n        else\r\n        {\r\n            last = inputStr[i];\r\n            size += 1 + (floor(log10(abs(count))) + 1);\r\n            \/*\r\n                Find the length of an integer:\r\n                    if count != 0, digits = floor(log10(abs(count))) + 1\r\n                    if count = 0, digits = 1\r\n             *\/\r\n            count = 1;\r\n        }\r\n    }\r\n    size += 1 + (floor(log10(abs(count))) + 1); \/\/count the last char, for example, last=&quot;aaa&quot; in this case\r\n    \r\n    return size;\r\n}\r\n\r\nint main(int argc, const char * argv[])\r\n{\r\n    char inputStr[] = &quot;aabcccccaaa&quot;;\r\n    cout&lt;&lt;compressStr(inputStr)&lt;&lt;endl;\r\n    \r\n    return 0;\r\n}\r\n<\/pre>\n<p>\n\t&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the &ldquo;compressed&rdquo; string would not become smaller than the original string, your method should return the original &hellip; <a href=\"http:\/\/cywang.no-ip.org\/wordpress\/?p=437\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[19,6],"tags":[],"class_list":["post-437","post","type-post","status-publish","format-standard","hentry","category-chapter-1-arrays-and-strings","category-cracking-the-coding-interview"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/437","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=437"}],"version-history":[{"count":5,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/437\/revisions"}],"predecessor-version":[{"id":442,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/437\/revisions\/442"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=437"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}