如何快速实现趣味算法，找出不重复数的独特方法？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1326个文字，预计阅读时间需要6分钟。
原创新题请参考以下内容：
题目：假设一个数字在十进制表示时，不存在连续两位数字相同的情况，则称该数字为不重复数。例如，105、164和198都是不重复数。请编写一个程序，从1到10000中找出所有的不重复数，并输出它们。
原题目请参考： 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只用一瞬间。就没有统计时间了。未进行溢出处理。
欢迎大家指正讨论。
博客文章 by Pandor Cai is licensed under a Creative Commons 署名-非商业性使用-禁止演绎 2.5 中国大陆 License.
本文共计1326个文字，预计阅读时间需要6分钟。
原创新题请参考以下内容：
题目：假设一个数字在十进制表示时，不存在连续两位数字相同的情况，则称该数字为不重复数。例如，105、164和198都是不重复数。请编写一个程序，从1到10000中找出所有的不重复数，并输出它们。
原题目请参考： 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只用一瞬间。就没有统计时间了。未进行溢出处理。
欢迎大家指正讨论。
博客文章 by Pandor Cai is licensed under a Creative Commons 署名-非商业性使用-禁止演绎 2.5 中国大陆 License.