首页 > 代码库 > 一个朋友面试时遇到的算法题（怎么组合后得到最大整数）
一个朋友面试时遇到的算法题（怎么组合后得到最大整数）
首先，这篇的标题是我借来的，两周前，我看过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 = http://www.mamicode.com/""; 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 =http://www.mamicode.com/ 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 = http://www.mamicode.com/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 #endregion169 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 else198 throw new Exception("查找最大字符时出错");199 }200 }201 }
一个朋友面试时遇到的算法题（怎么组合后得到最大整数）