{"id":9016,"date":"2021-12-04T22:16:33","date_gmt":"2021-12-05T06:16:33","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9016"},"modified":"2021-12-04T22:17:28","modified_gmt":"2021-12-05T06:17:28","slug":"leetcode-2094-finding-3-digit-even-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-2094-finding-3-digit-even-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2094. Finding 3-Digit Even Numbers"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>digits<\/code>, where each element is a digit. The array may contain duplicates.<\/p>\n\n\n\n<p>You need to find&nbsp;<strong>all<\/strong>&nbsp;the&nbsp;<strong>unique<\/strong>&nbsp;integers that follow the given requirements:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The integer consists of the&nbsp;<strong>concatenation<\/strong>&nbsp;of&nbsp;<strong>three<\/strong>&nbsp;elements from&nbsp;<code>digits<\/code>&nbsp;in&nbsp;<strong>any<\/strong>&nbsp;arbitrary order.<\/li><li>The integer does not have&nbsp;<strong>leading zeros<\/strong>.<\/li><li>The integer is&nbsp;<strong>even<\/strong>.<\/li><\/ul>\n\n\n\n<p>For example, if the given&nbsp;<code>digits<\/code>&nbsp;were&nbsp;<code>[1, 2, 3]<\/code>, integers&nbsp;<code>132<\/code>&nbsp;and&nbsp;<code>312<\/code>&nbsp;follow the requirements.<\/p>\n\n\n\n<p>Return&nbsp;<em>a&nbsp;<strong>sorted<\/strong>&nbsp;array of the unique integers.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> digits = [2,1,3,0]\n<strong>Output:<\/strong> [102,120,130,132,210,230,302,310,312,320]\n<strong>Explanation:<\/strong> \nAll the possible integers that follow the requirements are in the output array. \nNotice that there are no <strong>odd<\/strong> integers or integers with <strong>leading zeros<\/strong>.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> digits = [2,2,8,8,2]\n<strong>Output:<\/strong> [222,228,282,288,822,828,882]\n<strong>Explanation:<\/strong> \nThe same digit can be used as many times as it appears in <code>digits<\/code>. \nIn this example, the digit 8 is used twice each time in 288, 828, and 882. \n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> digits = [3,7,5]\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong> \nNo <strong>even<\/strong> integers can be formed using the given digits.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> digits = [0,2,0,0]\n<strong>Output:<\/strong> [200]\n<strong>Explanation:<\/strong> \nThe only valid integer that can be formed with three digits and <strong>no leading zeros<\/strong> is 200.\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> digits = [0,0,0]\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong> \nAll the integers that can be formed have <strong>leading zeros<\/strong>. Thus, there are no valid integers.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>3 &lt;=&nbsp;digits.length &lt;= 100<\/code><\/li><li><code>0 &lt;= digits[i] &lt;= 9<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Enumerate all three digits even numbers<\/strong><\/h2>\n\n\n\n<p>Check 100, 102, &#8230; 998. Use a hashtable to check whether all digits are covered by the given digits.<\/p>\n\n\n\n<p>Time complexity: O(1000*lg(1000))<br>Space complexity: O(10)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> findEvenNumbers(vector<int>& digits) {\n    vector<int> counts(10);\n    for (int d : digits) ++counts[d];\n    vector<int> ans;\n    for (int x = 100; x < 1000; x += 2) {\n      bool valid = true;\n      vector<int> c(10);\n      for (int t = x; t > 0; t \/= 10)\n        valid &= (++c[t % 10] <= counts[t % 10]);           \n      if (valid) ans.push_back(x);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;digits, where each element is a digit. The array may contain duplicates. You need to find&nbsp;all&nbsp;the&nbsp;unique&nbsp;integers that follow the given&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[222,601,82],"class_list":["post-9016","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-easy","tag-enumerate","tag-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9016","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=9016"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9016\/revisions"}],"predecessor-version":[{"id":9019,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9016\/revisions\/9019"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9016"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9016"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9016"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}