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

题目要求如下:

如果一个数字十进制表达时,不存在连续两位相同,则称之为“不重复数”。例如,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 联系我,非常感谢。

真正的不重复数字实现,像人一样去编程
分类: C#

本文转自徐少侠博客园博客,原文链接:http://www.cnblogs.com/Chinese-xu/archive/2009/09/05/1560905.html,如需转载请自行联系原作者
上一篇:关于使用ECS服务器的体验


下一篇:《21天学通Java(第6版)》—— 第 2 章 Java编程基础