In this post, I will introduce some problems which could solved by pure greedy technique. <\/p>\n\n\n\n
“Pure” means no other techniques are needed in this category of problems. Actually greedy can be combined by other techniques like DP. <\/p>\n\n\n\n
Note that usually greedy will be faster than Pure Dynamic Programming. But in case one could not get the greedy solution, he could also think about Pure DP as a back-up solution<\/strong> if the complexity is not that bad. <\/p>\n\n\n\n Greedy is tricky. So I will directly introduce all the problems in details. As you might know, I will update this post from time to time. <\/p>\n\n\n\n Difficulty: 4-5 points<\/p>\n\n\n\n Given a string\u00a0 Difficulty: 5-6 points<\/p>\n\n\n\n A chef\u00a0has collected data on the\u00a0 The DP version is not difficult. <\/p>\n\n\n\n However, actually, after sorting, the problem could be solved by Pure Greedy. <\/p>\n\n\n\n Difficulty: 5 points<\/p>\n\n\n\n A string is called\u00a0happy<\/em>\u00a0if it does\u00a0not have any of the strings\u00a0 If there is no such string\u00a0 Summary In this post, I will introduce some problems which could solved by pure greedy technique. “Pure” means no other techniques are needed in this category of problems. Actually greedy can be combined by other techniques like DP. Note that usually greedy will be faster than Pure Dynamic Programming. But in case one could not…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,58],"tags":[],"class_list":["post-929","post","type-post","status-publish","format-standard","hentry","category-alg","category-greedy"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/929","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=929"}],"version-history":[{"count":7,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/929\/revisions"}],"predecessor-version":[{"id":939,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/929\/revisions\/939"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=929"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=929"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=929"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Details<\/h2>\n\n\n\n
LC 1400<\/a>.\u00a0Construct K Palindrome Strings<\/h4>\n\n\n\n
s<\/code>\u00a0and an integer\u00a0k<\/code>. You should construct\u00a0k<\/code>\u00a0non-empty\u00a0palindrome\u00a0strings using\u00a0all the characters<\/strong>\u00a0in\u00a0s<\/code>. Return\u00a0True\u00a0if you can use all the characters in\u00a0s<\/code>\u00a0to construct\u00a0k<\/code>\u00a0palindrome strings or\u00a0False\u00a0otherwise.<\/p>\n\n\n\n\/\/ Greedy\n1. if k > s.size(), return false\n2. Count chars which appear odd times; these chars must be in different palindromes;\n a) if cnt_odtd > k, it is not possible to construct exact k palindromes;\n b) [KEY POINT] if cnt_odd <= k, we could always construct k palindromes, since palindrome strings could be transformed into any number of new palindromes; \nfor example, \na, aa, bb => a, a, a, bb \/\/ split, increase #palindromes\na, aa, bb => a, abba \/\/ split then insert at front and back, decrease #palindromes<\/code><\/pre>\n\n\n\nLC 1402<\/a>.\u00a0Reducing Dishes<\/h4>\n\n\n\n
satisfaction<\/code>\u00a0level of his\u00a0n<\/code>\u00a0dishes.\u00a0Chef can cook any dish in 1 unit of time. Like-time coefficient<\/em>\u00a0of a dish is defined as\u00a0the time taken to cook that dish including previous dishes multiplied by its satisfaction level \u00a0i.e.\u00a0\u00a0time[i]<\/code>*satisfaction[i]<\/code>. Return\u00a0the maximum sum of\u00a0Like-time coefficient\u00a0<\/em>that the chef can obtain after dishes preparation. Dishes can be prepared in\u00a0any\u00a0<\/strong>order and the chef can discard some dishes to get this maximum value.<\/p>\n\n\n\n\/\/ sort satisfaction first\nalg[i][t] = \n 1. alg[i + 1][t]\n 2. alg[i + 1][t + 1] + t * satisfaction[i]<\/code><\/pre>\n\n\n\n\/\/ Greedy\n\/\/ 1. All dishes with satisfaction[i] >= 0 should be cooked one by one;\n\/\/ 2. Cook some dishes with satisfaction[i] < 0 as long as it could increase the total sum;\n\/\/ after add all dishes with satisfaction[i] >= 0\nwhile (i >= 0 && satisfaction[i] + suffix_sum >= 0) {\n total_sum += satisfaction[i] + suffix_sum;\n suffix_sum += satisfaction[i];\n i--;\n}<\/code><\/pre>\n\n\n\nLC 1405<\/a>.\u00a0Longest Happy String<\/h4>\n\n\n\n
'aaa'<\/code>,\u00a0'bbb'<\/code>\u00a0or\u00a0'ccc'<\/code>\u00a0as a substring. Given three integers\u00a0a<\/code>,\u00a0b<\/code>\u00a0and\u00a0c<\/code>, return\u00a0any<\/strong>\u00a0string\u00a0s<\/code>,\u00a0which satisfies following conditions:<\/p>\n\n\n\ns<\/code> is happy <\/em>and longest possible.<\/li>s<\/code> contains at most<\/strong> a<\/code> occurrences of the letter 'a'<\/code>, at most<\/strong> b<\/code> occurrences of the letter 'b'<\/code> and at most<\/strong> c<\/code> occurrences of the letter 'c'<\/code>.<\/li>s <\/code>will only contain 'a'<\/code>, 'b'<\/code> and 'c'<\/code> letters.<\/li><\/ul>\n\n\n\ns<\/code>\u00a0return the empty string\u00a0\"\"<\/code>.<\/p>\n\n\n\n\/\/ Greedy\n1. Use priority queue to store all candidates by cnt from largest to smallest;\n2. As long as queue size is larger than 1, poll the first, second elements,\n 1) if first->cnt == second.cnt, push back only one first->ch, update a new candidate {first->cnt - 1, first->ch}\n 2) otherwise,\n 1) if first->cnt == 1, we push back only one first->ch as well;\n 2) [KEY POINT] push_back two first->ch and one second->ch, update two corresponding new candidates; (we have first->cnt >= second->cnt + 1, the intuition here to only push one second->ch is to use as least delimiters as possible; in the next turn second->cnt will at most be equal to first->cnt, so it is safe we will not have three second->ch in a row);\n3. There is at most 1 element remaining, push back as most as you could (check the last two chars)<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"