一个朋友面试时遇到的算法题（怎么组合后得到最大整数）
首先，这篇的标题是我借来的，两周前，我看过MrWrong发的一篇帖子（http://www.cnblogs.com/MrWrong/p/3986158.html），初看时感觉就是一个排列问题，然后洒洒水般的写了一段，结果被版主指出误点，当时我真的头蒙了，坐在那里两个小时，想不出比较好的方法（全排列，然后比较大小的方法排除，这个不借鉴，如果有十个不一样的元素，全排列方法有3628800中，如果在多一位元素就是39916800，已经比前一个多十倍了，需要的内存指数上升），然后又碰到十一国庆，也把这个问题滞后了（当初给版主回复：这个问题很好，稍等，一等就是两周...），昨天才想到还有这么回事，回家就认真看了看问题，小子虽然不才，但是也把它解决了。
题目如下：
一个正整数数组：如， 14 32 133 152
将其串起来得到能表示的最大整数（这里就是3215214133）
这道题原贴主提供的几种方法，当时我看看也是云里雾里的，不明觉厉。可能技术层次上有差异吧，毕竟人家是只老雕，咱不过是只小鸟。
这道题我采用的方法：集合分类；从首到尾逐个字符处理，排除非最大字符的元素。（中间集合元素会衍生）
处理过程看下代码，比较清晰：
//如果长度比需求的小，向后补【补的时候注意已经存在的项不再添加】
CheckLength(curIndex, ref eList);
//找出最大字符
Char maxChar = GetMaxChar(eList, curIndex);
//删除非最大字符
DelNoMaxChar(curIndex, maxChar, ref eList);
举例吧：14 32 133 152
1.分集合（集合模型定义{ {可能最大元素} , {剩余元素} } ）：{ {14,32,133,152} , { } } ，从第一位开始检查。
2.首先检查每个字符的长度是否足够1（看来都足够长）
3.然后找出最大字符 maxChar = 3
4.将首字符非3的移到其他集合{{32} , {14,133,152}}
5.检查第二字符，由于现在最大集合只有一个元素，所以就是它自己，现在集合仍是{{32} , {14,133,152}}
6.检查第三字符，由于最大集合32不足三位，需要补数，补后集合{ {32|14,32|133,32|152} , { } }
7.找出第三个字符最大 maxChar = 1 ,都是1 ,集合保持不变 { {32|14,32|133,32|152} , { } }
8.找出第四个字符最大 maxChar = 5, 最大集合排除非5 ,执行后集合{ {32|152} , {14,133} }
.... 之后方法如上。
注：代码中部分实现跟以上稍有不同，但是主要解决方式是相同的。
以下是源代码：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Text.RegularExpressions; 6 7 namespace ConsoleApplication2 8 { 9 public class Cluster 10 { 11 /// <summary> 12 /// 已使用 13 /// </summary> 14 public List<string> UseList; 15 /// <summary> 16 /// 未使用 17 /// </summary> 18 public List<string> RemainingList; 19 20 private string stringValue = ""; 21 public string StringValue 22 { 23 get { return stringValue; } 24 } 25 26 public Cluster() 27 { 28 this.UseList = new List<string>(); 29 this.RemainingList = new List<string>(); 30 } 31 32 public Cluster(string stringValue) 33 : this() 34 { 35 this.stringValue = stringValue; 36 } 37 38 public void Add(string item) 39 { 40 int index = -1; 41 for (int i = 0; i < RemainingList.Count; i++) 42 { 43 if (RemainingList[i] == item) 44 { 45 index = i; 46 } 47 } 48 49 if (index >= 0) 50 { 51 RemainingList.RemoveAt(index); 52 UseList.Add(item); 53 this.stringValue += item; 54 } 55 else 56 { 57 throw new ArgumentException("剩余中不存在该元素:" + item); 58 } 59 } 60 61 public Cluster Clone() 62 { 63 Cluster ret = new Cluster(this.stringValue); 64 ret.UseList.AddRange(this.UseList.ToArray()); 65 ret.RemainingList.AddRange(this.RemainingList.ToArray()); 66 67 return ret; 68 } 69 } 70 71 public class Program 72 { 73 static void Main(string[] args) 74 { 75 AppDomain.CurrentDomain.UnhandledException += (s, e) => { Console.WriteLine(e.ExceptionObject.ToString()); Console.ReadKey(); }; 76 77 //List<string> orgList = new List<string>() { "33", "48", "5", "53", "54", "544", "54444", "546", "55" }; 78 List<string> orgList = null; 79 80 if (args.Length > 0) 81 { 82 orgList = new List<string>(); 83 orgList.AddRange(args); 84 } 85 else 86 { 87 orgList = new List<string>() { "33", "48", "5", "53", "54", "544", "54444", "546", "55" }; 88 } 89 90 CheckNum(orgList); 91 List<Cluster> eList = new List<Cluster>(); 92 //连接后的字符串最大长度 93 int maxLength = 0; 94 foreach (var item in orgList) 95 maxLength += item.Length; 96 97 foreach (var item in orgList) 98 { 99 Cluster el = new Cluster(); 100 el.RemainingList.AddRange(orgList.ToArray()); 101 el.Add(item); 102 103 eList.Add(el); 104 } 105 106 for (int curIndex = 0; curIndex < maxLength; curIndex++) 107 { 108 //如果长度比需求的小，向后补【补的时候注意已经存在的项不再添加】 109 CheckLength(curIndex, ref eList); 110 //找出最大字符 111 Char maxChar = GetMaxChar(eList, curIndex); 112 //删除非最大字符 113 DelNoMaxChar(curIndex, maxChar, ref eList); 114 } 115 116 var list = eList; 117 118 Console.WriteLine(eList[0].StringValue); 119 Console.ReadKey(); 120 } 121 122 static void DelNoMaxChar(int index, char maxChar, ref List<Cluster> list) 123 { 124 for (int i = list.Count - 1; i >= 0; i--) 125 { 126 Cluster el = list[i]; 127 if (el.StringValue[index] < maxChar) 128 { 129 list.RemoveAt(i); 130 } 131 } 132 } 133 134 static void CheckNum(List<string> list) 135 { 136 Regex regNumber = new Regex(@"^\d+$"); 137 foreach (var item in list) 138 { 139 if (!regNumber.IsMatch(item)) 140 { 141 throw new ArgumentException("数组中有非数字符号: " + item); 142 } 143 } 144 } 145 146 static void CheckLength(int index, ref List<Cluster> list) 147 { 148 for (int i = 0; i < list.Count;) 149 { 150 if (list[i].StringValue.Length <= index) 151 { 152 Cluster curCluster = list[i]; 153 154 foreach (var item in curCluster.RemainingList) 155 { 156 #region 去除可能重复 157 bool flag = false; //重复标志 158 string stringvalue = curCluster.StringValue + item; 159 160 for (int j = 0; j < list.Count; j++) 161 { 162 if (String.Equals(list[j].StringValue, stringvalue)) 163 { 164 flag = true; 165 break; 166 } 167 } 168 #endregion 169 170 if (!flag) 171 { 172 Cluster clone = curCluster.Clone(); 173 clone.Add(item); 174 list.Add(clone); 175 } 176 } 177 178 list.RemoveAt(i); 179 continue; 180 } 181 i++; 182 } 183 } 184 185 static Char GetMaxChar(List<Cluster> list, int index) 186 { 187 Char targetChar = ‘\0‘; 188 189 for (int i = 0; i < list.Count; i++) 190 { 191 if (list[i].StringValue[index] > targetChar) 192 targetChar = list[i].StringValue[index]; 193 } 194 195 if (targetChar != ‘\0‘) 196 return targetChar; 197 else 198 throw new Exception("查找最大字符时出错"); 199 } 200 } 201 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
