当前位置 : 主页 > 编程语言 > 其它开发 >

趣味算法:返回不重复数的实现 另类实现方式 非常快

来源:互联网 收集:自由互联 发布时间:2022-05-26
原题目请参考: http://www.cnblogs.com/lovexyz123/archive/2009/09/04/1560166.html 题目 如果一个数字十进制表达时,不存在连续两位相同,则称之为“不重复数”。例如,105、164和198都是“不重复数

原题目请参考: http://www.cnblogs.com/lovexyz123/archive/2009/09/04/1560166.html 

题目

如果一个数字十进制表达时,不存在连续两位相同,则称之为“不重复数”。例如,105、164和198都是“不重复数”,而11、100和122不是。

下面用一个long类型( long类型数字A),实现返回大于A的最小“不重复数”。

解题思路

没有详细的统计过大家的解法(很多都在回复内贴的代码)。但感觉大家的问题主要集中在计算大数的效率上。提供一种“经验”算法供大家参考。

题目按照我的理解,大致为输入99,返回101。输入199,返回201这类的。

按照人类的(其实就是我的。。哈哈)解题方式,算法分析如下:

1. 9为特殊字符

如果这串数字的某一位和其上一位均为9,则需要返回类似“101”这样的数值。

2. 首位和次位(左起第二位)均为9为特殊情况

在这种情况下,需进位(增加数字一位)。

3. 解决连续两位重复的方式为将低位数字+1(9已经当作特殊情况处理,这种情况下不可能为9)。之所以加低位是因为需要返回最小的。

4. 任何一个数字提升(+1)后,其所有次位(例如1881111中的188变为189,所有次位为1111)都变得不重要。根据“经验”可得知,最小数为所有前位(189)加上(0101)。其中“0101”为固定不重复最小值,其长度与数字所有次位的长度相同,以0开头,用1间隔(依据“不重复数”条件分析而来)。

5. 由于可能在“99”处理后造成前一位与前两位重复(例如12199变为12201,造成了新的重复),在处理完成后重新调用函数自身进行二次处理。中断条件为结果字串中未发现重复的两位(即“不重复数”)。

如果按照此思路进行解题运算,大多数情况下算法复杂度只为O(n) (我其实不会算算法复杂度,高手可以提示一下这种算法的复杂度该如何计算。只是要表达和长度相关的意思)

代码全文
   1: using System;
   2: using System.Collections.Generic;
   3: using System.Linq;
   4: using System.Text;
   5: using System.Text.RegularExpressions;
   6: using System.Collections.ObjectModel;
   7:  
   8: namespace SubStringFrequency
   9: {
  10:     class Program
  11:     {
  12:         static void Main(string[] args)
  13:         {
  14:             var consoleInput = Console.ReadLine();
  15:             long baseNumber = long.Parse(consoleInput);
  16:  
  17:             Console.WriteLine(getAvaliableNum(baseNumber));
  18:         }
  19:  
  20:         private static string getAvaliableNum(long consoleInput)
  21:         {
  22:             if (consoleInput < 10) //single number
  23:             {
  24:                 return consoleInput.ToString();
  25:             }
  26:  
  27:             string temp = consoleInput.ToString();
  28:             var reach = 0;
  29:             StringBuilder result = new StringBuilder();
  30:             for (int i = 1; i < temp.Length; i++)
  31:             {
  32:                 var currentNum = temp[i];
  33:                 var nextNum = temp[i - 1];
  34:                 if (currentNum == nextNum)
  35:                 {
  36:                     reach += 1;
  37:                     if (currentNum == '9')
  38:                     {
  39:                         if (i == 1)
  40:                         {
  41:                             result.Append('1');
  42:                             result.Append(getMimimumUniqueNumByLength(temp.Length));
  43:                             break;
  44:                         }
  45:                         else
  46:                         {
  47:                             var hiNumber = int.Parse(result[result.Length - 1].ToString()) + 1;
  48:                             result.Remove(result.Length - 1, 1);
  49:                             result.Append(hiNumber);
  50:                             result.Append(getMimimumUniqueNumByLength(temp.Length - i + 1));
  51:                             break;
  52:                         }
  53:                     }
  54:                     else
  55:                     {
  56:                         result.Append(nextNum);
  57:                         result.Append(int.Parse(currentNum.ToString()) + 1);
  58:                         result.Append(getMimimumUniqueNumByLength(temp.Length - i - 1));
  59:                         break;
  60:                     }
  61:  
  62:                 }
  63:                 else
  64:                 {
  65:                     result.Append(nextNum);
  66:                     if (i == temp.Length - 1)
  67:                     {
  68:                         result.Append(currentNum);
  69:                     }
  70:                 }
  71:             }
  72:  
  73:             var resultString = string.Empty;
  74:  
  75:             if (reach > 0)
  76:             {
  77:                 resultString = getAvaliableNum(long.Parse(result.ToString()));
  78:             }
  79:             else
  80:             {
  81:                 resultString = result.ToString();
  82:             }
  83:             return resultString;
  84:         }
  85:  
  86:         private static string getMimimumUniqueNumByLength(int length)
  87:         {
  88:             StringBuilder sb = new StringBuilder();
  89:             var temp = 0;
  90:             for (int i = 0; i < length; i++)
  91:             {
  92:                 sb.Append(temp);
  93:                 if (temp == 0)
  94:                 {
  95:                     temp = 1;
  96:                 }
  97:                 else if (temp == 1)
  98:                 {
  99:                     temp = 0;
 100:                 }
 101:             }
 102:             return sb.ToString();
 103:         }
 104:     }
 105: }
结论

处理121989999991999只用一瞬间。就没有统计时间了。未进行溢出处理。

欢迎大家指正讨论。

Creative Commons License
博客文章 by Pandor Cai is licensed under a Creative Commons 署名-非商业性使用-禁止演绎 2.5 中国大陆 License.
网友评论