返回不重复数的实现 另类实现方式
原题目请参考： 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; 33: var nextNum = temp; 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.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只用一瞬间。就没有统计时间了。未进行溢出处理。
欢迎大家指正讨论。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]