真正的不重复数字实现，像人一样去编程

题目要求如下：

如果一个数字十进制表达时，不存在连续两位相同，则称之为“不重复数”。例如，105、164和198都是“不重复数”，而11、100和122不是。实现一个函数，用一个long类型（ long类型数字A），实现返回大于A的最小“不重复数”。

看到两个朋友在做这个算法题

夏小冰的代码，运算时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/archive/2009/09/05/1560905.html，如需转载请自行联系原作者