{"id":6683,"date":"2020-05-03T18:57:17","date_gmt":"2020-05-04T01:57:17","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6683"},"modified":"2020-05-03T19:26:50","modified_gmt":"2020-05-04T02:26:50","slug":"leetcode-1432-max-difference-you-can-get-from-changing-an-integer","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1432-max-difference-you-can-get-from-changing-an-integer\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1432. Max Difference You Can Get From Changing an Integer"},"content":{"rendered":"\n<p>You are given an integer&nbsp;<code>num<\/code>. You will apply the following steps exactly&nbsp;<strong>two<\/strong>&nbsp;times:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Pick a digit&nbsp;<code>x (0&nbsp;&lt;= x &lt;= 9)<\/code>.<\/li><li>Pick another digit&nbsp;<code>y (0&nbsp;&lt;= y &lt;= 9)<\/code>. The digit&nbsp;<code>y<\/code>&nbsp;can be equal to&nbsp;<code>x<\/code>.<\/li><li>Replace all the occurrences of&nbsp;<code>x<\/code>&nbsp;in the decimal representation of&nbsp;<code>num<\/code>&nbsp;by&nbsp;<code>y<\/code>.<\/li><li>The new integer&nbsp;<strong>cannot<\/strong>&nbsp;have any leading zeros, also the new integer&nbsp;<strong>cannot<\/strong>&nbsp;be 0.<\/li><\/ul>\n\n\n\n<p>Let&nbsp;<code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>&nbsp;be the results of applying the operations to&nbsp;<code>num<\/code>&nbsp;the first and second times, respectively.<\/p>\n\n\n\n<p>Return&nbsp;<em>the max difference<\/em>&nbsp;between&nbsp;<code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>.<\/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> num = 555\n<strong>Output:<\/strong> 888\n<strong>Explanation:<\/strong> The first time pick x = 5 and y = 9 and store the new integer in a.\nThe second time pick x = 5 and y = 1 and store the new integer in b.\nWe have now a = 999 and b = 111 and max difference = 888\n<\/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> num = 9\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> The first time pick x = 9 and y = 9 and store the new integer in a.\nThe second time pick x = 9 and y = 1 and store the new integer in b.\nWe have now a = 9 and b = 1 and max difference = 8\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> num = 123456\n<strong>Output:<\/strong> 820000\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> num = 10000\n<strong>Output:<\/strong> 80000\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> num = 9288\n<strong>Output:<\/strong> 8700\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= num &lt;= 10^8<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n<p>Try all possible pairs of (x, y)<\/p>\n\n\n\n<p>Time complexity: O(10*10*logn)<br>Space complexity: O(logn)<\/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  int maxDiff(int num) {\n    int min_num = INT_MAX;\n    int max_num = INT_MIN;\n    for (char x = '0'; x <= '9'; ++x)\n      for (char y = '0'; y <= '9'; ++y) {\n        string n = to_string(num);\n        for (char&#038; c : n)\n          if (c == x) c = y;\n        if (n[0] == '0') continue;\n        int v = stoi(n);\n        min_num = min(min_num, v);\n        max_num = max(max_num, v);\n      }\n    return max_num - min_num;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Greedy<\/strong><\/h2>\n\n\n\n<p>Maximize A and Minimize B<\/p>\n\n\n\n<p>A - B will the answer.<\/p>\n\n\n\n<p>To maximize A, find the left most digit that is not 9, replace that digit with 9.<br>e.g. 121 => 919<br>e.g. 9981 => 9991<br>To minimize B, fin the left most digit that is not 1 or 0, replace that digit with 0 (if not the first one) or 1.<br>e.g. 1024 -> 1004<br>e.g. 2024 -> 1014<\/p>\n\n\n\n<p>Time complexity: O(logn)<br>Space complexity: O(logn)<\/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  int maxDiff(int num) {\n    string s = to_string(num);\n    const int n = s.length();\n    string n1(s);\n    string n2(s);\n    s += '#'; \/\/ append an unmatchable char to avoid out_of_bound.\n    int x = 0;\n    int y = 0;\n    while (x < n &#038;&#038; (s[x] == '0' || s[x] == '1')) ++x;\n    while (y < n &#038;&#038; s[y] == '9') ++y;    \n    for (char&#038; c : n1)\n      if (c == s[x]) c = x ? '0' : '1';\n    for (char&#038; c : n2)\n      if (c == s[y]) c = '9';    \n    return stoi(n2) - stoi(n1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer&nbsp;num. You will apply the following steps exactly&nbsp;two&nbsp;times: Pick a digit&nbsp;x (0&nbsp;&lt;= x &lt;= 9). Pick another digit&nbsp;y (0&nbsp;&lt;= y &lt;=&#8230;<\/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":[],"class_list":["post-6683","post","type-post","status-publish","format-standard","hentry","category-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6683","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=6683"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6683\/revisions"}],"predecessor-version":[{"id":6687,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6683\/revisions\/6687"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6683"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6683"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6683"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}