A:
这个是典型的constructive的题目。
每次添加一个新的数字的时候,看前2位。
class Solution { public: string longestDiverseString(int a, int b, int c) { string res = ""; helper(a, 'a', b, 'b', c, 'c', res); return res; } private: void helper(int a, char ca, int b, char cb, int c, char cc, string& res) { int n = res.length(); if (a >= b && a >= c) { if (a <= 0) return; if (b < c) { return helper(a, ca, c, cc, b, cb, res); } // now we have (a>=b && a>=c) and b >= c if (n <= 1 || res.back() != ca || res[n - 2] != ca) { res += ca; return helper(a - 1, ca, b, cb, c, cc, res); }else if (b >= 1) { res += cb; // can only transfer char to char in this way, res+cb would give error return helper(a, ca, b - 1, cb, c, cc, res); } }else if (b >= a && b >= c) { return helper(b, cb, a, ca, c, cc, res); }else{ // if(c >= a && c >= b) { return helper(c, cc, a, ca, b, cb, res); } } };
Mistakes:
一开始,在转换情况的时候,用了
if (b >= a && b >= c) {
然而对于 (2,2,2)或者(2,2,1)的输入,就会永远进行下去。
我们的措施,就是先处理(a>=b a>=c 。 )然后再转换
其实,为了避免上面的错误。我们可以稍微修改一下代码.。 让其只在小于的时候,才更换
class Solution { public: string longestDiverseString(int a, int b, int c) { string res = ""; helper(a, 'a', b, 'b', c, 'c', res); return res; } private: void helper(int a, char ca, int b, char cb, int c, char cc, string& res) { int n = res.length(); if(a<b) return helper(b, cb, a, ca, c, cc, res); if(a<c) return helper(c, cc, a, ca, b, cb, res); if (b < c) return helper(a, ca, c, cc, b, cb, res); if (a <= 0) return; // now we have a>=1 && a>=b && a>=c && b >= c if (n <= 1 || res.back() != ca || res[n - 2] != ca) { res += ca; return helper(a - 1, ca, b, cb, c, cc, res); }else if (b >= 1) { res += cb; // can only transfer char to char in this way, res+cb would give error return helper(a, ca, b - 1, cb, c, cc, res); } } };
No comments:
Post a Comment