{"id":5167,"date":"2019-05-10T19:52:01","date_gmt":"2019-05-11T02:52:01","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5167"},"modified":"2019-05-10T20:04:02","modified_gmt":"2019-05-11T03:04:02","slug":"leetcode-640-solve-the-equation","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-640-solve-the-equation\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 640. Solve the Equation"},"content":{"rendered":"\n<p>Solve a given equation and return the value of&nbsp;<code>x<\/code>&nbsp;in the form of string &#8220;x=#value&#8221;. The equation contains only &#8216;+&#8217;, &#8216;-&#8216; operation, the variable&nbsp;<code>x<\/code>&nbsp;and its coefficient.<\/p>\n\n\n\n<p>If there is no solution for the equation, return &#8220;No solution&#8221;.<\/p>\n\n\n\n<p>If there are infinite solutions for the equation, return &#8220;Infinite solutions&#8221;.<\/p>\n\n\n\n<p>If there is exactly one solution for the equation, we ensure that the value of&nbsp;<code>x<\/code>&nbsp;is an integer.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> \"x+5-3+x=6+x-2\"\n<strong>Output:<\/strong> \"x=2\"\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> \"x=x\"\n<strong>Output:<\/strong> \"Infinite solutions\"\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> \"2x=x\"\n<strong>Output:<\/strong> \"x=0\"\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> \"2x+3x-6x=x+2\"\n<strong>Output:<\/strong> \"x=-1\"\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input:<\/strong> \"x=x+2\"\n<strong>Output:<\/strong> \"No solution\"<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Parse the equation<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/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, 0 ms, 8.5 MB\nclass Solution {\npublic:\n  string solveEquation(const string& equation) {    \n    auto parse = [](string_view s) -> vector<int> { \n      int a{0}, b{0};\n      int sign = 1;\n      long t = 0;\n      bool d = false;\n      for (char c : s) {\n        if (isdigit(c)) {\n          d = true;\n          t = t * 10 + c - '0';\n        } else {\n          if (c == 'x')\n            a += (d ? t : 1) * sign;\n          else {          \n            b += t * sign;\n            sign = c == '+' ? 1 : -1;\n          }\n          d = false;\n          t = 0;\n        }\n      }\n      b += t * sign;\n      return {a, b};\n    };\n\n    auto pos = equation.find('=');\n    auto l = parse(string_view(equation).substr(0, pos));\n    auto r = parse(string_view(equation).substr(pos + 1));\n    l[0] -= r[0];\n    l[1] -= r[1];\n    if (l[0] == 0)\n      return l[1] == 0 ? \"Infinite solutions\" : \"No solution\";\n    return \"x=\" + to_string(-l[1] \/ l[0]);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Solve a given equation and return the value of&nbsp;x&nbsp;in the form of string &#8220;x=#value&#8221;. The equation contains only &#8216;+&#8217;, &#8216;-&#8216; operation, the variable&nbsp;x&nbsp;and its coefficient.&#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":[31,177,4],"class_list":["post-5167","post","type-post","status-publish","format-standard","hentry","category-string","tag-math","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5167","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=5167"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5167\/revisions"}],"predecessor-version":[{"id":5170,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5167\/revisions\/5170"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5167"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5167"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5167"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}