江苏龙网

  1. 首页 > 生活 > >

求问codewar上的一道题

更新C++代码
没想到不支持C++.....
这里还有不完善的地方，如进位，99100，0000这三种情况没判断。
特别注意对于同一个j，不同的i都要尝试，例如13.它可能出现在121314中或者313233中，此时j相等，i=2时最小。81可能出现在181920中或者808182中，此时j相等，i=1时最小。

求问codewar上的一道题


class Solution{public:\tint getIndex(int tmp_num,int digit)//digit表示从左向右数第几位\t{\t\tint num = tmp_num;\t\tint index = 0;\t\tint index_i = 1;\t\twhile (tmp_num / 10) \t\t{ \t\t\tindex += index_i * 9 * pow(10, index_i - 1);\t\t\tindex_i++;\t\t\ttmp_num /= 10;\t\t}\t\tindex += (num - pow(10, index_i - 1))*index_i;\t\tindex += digit - 1;\t\treturn index;\t}\tint findIndex(string str)\t{\t\tfor (size_t j = 1; j \u0026lt;= str.length(); j++)\t\t{\t\t\tbool break_flag=false;//若有合理，则break\t\t\tfor (size_t i = 1; i \u0026lt;= j; i++)\t\t\t{\t\t\t\t//根据第位检查第位。\t\t\t\t//第ii位对应第j+ii位\t\t\t\tbool isTrue=true;//先假设合理，一旦不合理置为false\t\t\t\tint more=1;//表示进位\t\t\t\tfor (size_t ii = i; ii \u0026gt;= 1; ii--)\t\t\t\t{\t\t\t\t\tif(ii+j\u0026lt;= str.length())\t\t\t\t\t{ \t\t\t\t\tif (str == str + more)//无进位\t\t\t\t\t{\t\t\t\t\t\tmore = 0;\t\t\t\t\t}\t\t\t\t\telse \t\t\t\t\t{\t\t\t\t\t\tisTrue = false;//不合理\t\t\t\t\t\tbreak;\t\t\t\t\t}\t\t\t\t\t//if (str==\u0026#39;9\u0026#39;\u0026amp;\u0026amp;str==\u0026#39;0\u0026#39;)//有进位\t\t\t\t\t//{\t\t\t\t\t//\tmore = 1;\t\t\t\t\t//}\t\t\t\t\t}\t\t\t\t\t\t}\t\t\t\tint num = std::stoi(str.substr(i, j));//第二个数字\t\t\t\tfor (size_t jj = j+i+1; jj \u0026lt;= str.length(); jj++)//第二个数字确定了剩下的数\t\t\t\t{\t\t\t\t\tint curr = num + ceil((double)(jj - j - i) / j);\t\t\t\t\tstringstream stream;\t\t\t\t\tstream \u0026lt;\u0026lt; curr;\t\t\t\t\tstring string_temp = stream.str();\t\t\t\t\tif (string_temp != str) \t\t\t\t\t{\t\t\t\t\t\tisTrue = false;\t\t\t\t\t\tbreak;\t\t\t\t\t}\t\t\t\t}\t\t\t\tif (isTrue)\t\t\t\t{\t\t\t\t\t//求这个数字的下标，分为i==j时，根据第一个数确定，n\u0026gt;=i+j,根据第二个数确定，n\u0026lt;i+j时，用第一个和第二个拼接\t\t\t\t\tif (i == j)num = std::stoi(str.substr(0, i));\t\t\t\t\telse if (str.length() \u0026gt;= i + j)num--;\t\t\t\t\telse num = std::stoi(str.substr(i+1,j-i)+str.substr(0, i));\t\t\t\t\tcout \u0026lt;\u0026lt; str \u0026lt;\u0026lt;" index:"\u0026lt;\u0026lt; getIndex(num, j - i + 1)\u0026lt;\u0026lt;endl;\t\t\t\t\tbreak_flag = true;\t\t\t\t\tbreak;\t\t\t\t}\t\t\t}\t\t\tif (break_flag)\t\t\t\tbreak;\t\t}\t\treturn 0;\t}};
==============================================================

没做过原题，个人的思路。设参数s(总位数为n)的前i个字符是一个j位数的后i位。(n\u0026gt;=j\u0026gt;=i)。然后遍历一遍字符，检查合理性。最后返回可能的最小下标。最坏复杂度 求问codewar上的一道题
。
如12311241125这个数。
j=1，i=1设1是一个一位数。则第二位应为2。第三位应为3。第四位为4不符合。


推荐阅读


上一篇：为啥我总觉得“高清通话”听不清

下一篇：Apple Store排名是根据下载量吗