题目要求如下:
如果一个数字十进制表达时,不存在连续两位相同,则称之为“不重复数”。例如,105、164和198都是“不重复数”,而11、100和122不是。实现一个函数,用一个long类型( long类型数字A),实现返回大于A的最小“不重复数”。
看到两个朋友在做这个算法题
趣味算法:返回不重复数的实现 夏小冰
算法,一个永恒的话题,挑战你的编程之美 winzheng
夏小冰的代码,运算时1122, 18, 21,123, 98都有正确结果,但是100011,121989999的答案是错的
winzheng的结果如下
A=1122, 18, 21,123, 98,100011,121989999
结果:1201,19,23,124,101,101010,123010101
看起来功能都是实现了
但是仔细看代码他是把输入的A不断加1,并且判断结果的数字是否符合要求?
//只要是一个人,就不会这么去做的(sorry,兄弟)
*其实我们在编程的时候更多的要从自身角度出发。从问题的固有规律出发,设想一个人是如何来解决这个问题的。并且把解决问题的步骤转化为程序,就能写出比较好的算法了。
想想如果给一个人一个100位长的数字,他会用这种不断加1的办法来解决问题吗?
《编程之美》
这个是winzheng的标题,不过从他的代码里只能感受到对CPU无情的蹂躏。
以至于
如果数据更大,例如:121989999991999,花了好几分钟也没算出来,这个时候真的需要考虑时间复杂度等问题了。
解决这个问题只要把计算机当人看就可以了
1、将输入数加1
2、人类会从最高位的下一位作为当前位开始逐位寻找相邻的连续数,如果没有,则该数字就是目标值
3、如果当前位和前一位相同,把当前位的数字加1
3.1 如果加1后导致进位,则当前位等于前一位,前一位加1,返回3.1
3.2 加1后不进位,返回原始数字最高位到当前位的数据,后续拼接上“0101…”组成的剩余部分即可
3.3 进位到最高位,则返回1,后续拼接上“0101…”组成的剩余部分即可
代码如下
public static long GetNextNotDuplicatedValue4(long a)
{
//原始数据转换成数组
char[] arr = a.ToString().ToCharArray();
//从最高位的下一位作为当前位开始逐位寻找相邻的连续数
for (int i = 1; i < arr.Length; i++)
{
//如果相邻两位重复
if (arr[i - 1] == arr[i])
{
//如果当前位和前一位相同
while (i > 0 && arr[i - 1] == arr[i])
{
//把当前位的数字加1
arr[i] = (char)((arr[i] - 48 + 1) % 10 + 48);
//如果加1后导致进位
while (i > 0 && arr[i] == '0')
{
//前一位加1
arr[i - 1] = (char)((arr[i - 1] - 48 + 1) % 10+48);
//当前位等于前一位
i--;
}
}
//加1后不进位(i != 0),返回原始数字最高位到当前位的数据,后续拼接上“0101…”组成的剩余部分即可
//进位到最高位(i == 0),则返回1,后续拼接上“0101…”组成的剩余部分即可
string t = i == 0 ? "1" : new string(arr.TakeWhile((item, index) => index <= i).ToArray());
return long.Parse(t + makestring2(arr.Length - i-Math.Sign(i)*1));
}
}
//如果没有,则该数字就是目标值
return a;
}
static string makestring2(int i)
{
StringBuilder s = new StringBuilder(i);
for (int j = 0; j < i; j++)
{
s.Append(j % 2==0? "0" : "1");
}
return s.ToString(); ;
}
运行速度仅和A的位数部分相关
计算121989999991999也是瞬间的
总结:
把计算机当亲兄弟来看待,虽然他傻得只会不知疲倦得做加法
另外:
算法绝不是书上学来的那几种
环顾一下四周,想想人类是如何改变世界的,然后再让计算机兄弟来帮忙
测试数据也是非常重要的一个东西
出处:http://www.cnblogs.com/Chinese-xu/
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
如有问题,可以通过 Chinese_Xu@126.com 联系我,非常感谢。