豫icp郑州网站建设,国外seo查询,永信南昌网站建设,电子商务网站设计说明给定一个由字符串组成的数组strs#xff0c;必须把所有的字符串拼接起来#xff0c;返回所有可能的拼接结果中字典序最小的结果
贪心写法
首先注意的一点是#xff1a;如果两个字符串的长度相同#xff0c;“abc”#xff0c;“abd”#xff0c;肯定是“abc”的字典序最…给定一个由字符串组成的数组strs必须把所有的字符串拼接起来返回所有可能的拼接结果中字典序最小的结果
贪心写法
首先注意的一点是如果两个字符串的长度相同“abc”“abd”肯定是“abc”的字典序最小放在前面。拼接的结果是abcabd也是最小的
当两个字符串的长度不相同时“b”“bac”计算机进行字典序比较的时候会将“b”后面补上最小的ASCII即变成 “b00” 与 “bac” 进行比较。此时“b”小放前面此时拼接的结果是bbac但是bbac bacb所以这样拼接有问题。所以需要写一个我们自己的比较器。
思路 1将字符串数组进行排序排序的标准就是我们自己写的比较器两个字符串进行拼接拼接结果小的字符串放前面
注意这个地方要有传递性才可以比如说( 110 10 20 ) -- (1 20) , 同理 (ab abc abc abcg) -- ab abcg
只有具有传递性这个数组的排序才是有效的。至于传递性的证明不需要自己证写一个对数器用实验的方法来证明自己的假设。
2遍历整个数组将数组中的结果拼接起来。
3返回这个结果。
//贪心写法public static String lowestString2(String[] strs) {if (strs null || strs.length 0) {return ;}Arrays.sort(strs, new MyComparator());String ans strs[0];for (int i 1; i strs.length; i) {ans ans.concat(strs[i]);}return ans;}public static class MyComparator implements ComparatorString {Overridepublic int compare(String o1, String o2) {// compareTo方法是用来比较两个字符串的字典顺序。-----------------------------**--// 如果返回值小于0则表示(o1 o2)小于(o2 o1)// 如果返回值等于0则表示两者相等// 如果返回值大于0则表示(o1 o2)大于(o2 o1)。return (o1 o2).compareTo(o2 o1);}}暴力写法
思路总思路就是给我一个字符串数组将所有可能的情况给串起来然后返回字典序最小的拼接情况。
我们需要一个容器来存放所有可能的结果这个容器可以用TressSet,因为对于字符串他会自动的按字典序进行由小到大的排序
如何求得所有的可能情况 for (int index 0; index strs.length; index) {String first strs[index];//每一个字符串作为头的情况。String[] nexts removeIndex(strs, index); //除去头以后剩下的字符串组成的数组。TreeSetString next process(nexts); //通过递归调用返回的是一个容器里面存褚着所有的除去头以外的字符串。for (String cur : next) { // 将头节点都给安上。ans.add(first.concat(cur));}}//暴力写法// lowestString1 : 返回所有可能的拼接结果中字典序最小的结果public static String lowestString1(String[] strs) {if (strs null || strs.length 0) {return ;}TreeSetString set process(strs);return set null || set.size() 0 ? : set.first();}// process : strs中所有字符串的可能情况全排列返回所有可能情况。public static TreeSetString process(String[] strs) {TreeSetString ans new TreeSet();if (strs null || strs.length 0) {ans.add();return ans;}for (int index 0; index strs.length; index) {String first strs[index];String[] nexts removeIndex(strs, index);TreeSetString next process(nexts);for (String cur : next) {ans.add(first.concat(cur));}}return ans;}public static String[] removeIndex(String[] strs, int index) {String[] ans new String[strs.length - 1];int ansIndex 0;for (int i 0; i strs.length; i) {if (i ! index) {ans[ansIndex] strs[i];}}return ans;}比较器
做贪心的题目比较器是很重要的因为为了避免证明我们需要通过实验的方法来验证我们的答案。
// -------------------------------- for test -------------------------------public static void main(String[] args) {int testTime 10000;int strArrayLength 5;int strLength 5;System.out.println(test begin);for (int i 0; i testTime; i) {String[] arr1 generateRandomStringArray(strArrayLength, strLength);String[] arr2 copyStringArray(arr1);if (!lowestString1(arr1).equals(lowestString2(arr2))) {System.out.println(arr1);System.out.println(arr2);System.out.println(ooops);}}System.out.println(finish);}public static String[] generateRandomStringArray(int strArrayLength, int strLength) {String[] string new String[(int) (Math.random() * strArrayLength 1)];for (int i 0; i string.length; i) {char[] c new char[(int) (Math.random() * strLength 1)];int a (int) (Math.random() * 26); //[0,25]for (int j 0; j c.length; j) {c[j] (Math.random() 0.5 ? (char) (65 a) : (char) (95 a));}string[i] c.toString();}return string;}public static String[] copyStringArray(String[] ans) {String[] ret new String[ans.length];for (int i 0; i ans.length; i) {ret[i] ans[i];}return ret;}
} 文章转载自： http://www.morning.zpyxl.cn.gov.cn.zpyxl.cn http://www.morning.xylxm.cn.gov.cn.xylxm.cn http://www.morning.plwfx.cn.gov.cn.plwfx.cn http://www.morning.rrxgx.cn.gov.cn.rrxgx.cn http://www.morning.ntqlz.cn.gov.cn.ntqlz.cn http://www.morning.qxycf.cn.gov.cn.qxycf.cn http://www.morning.kbyp.cn.gov.cn.kbyp.cn http://www.morning.ftznb.cn.gov.cn.ftznb.cn http://www.morning.gtmgl.cn.gov.cn.gtmgl.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.kgsws.cn.gov.cn.kgsws.cn http://www.morning.kabaifu.com.gov.cn.kabaifu.com http://www.morning.pmtky.cn.gov.cn.pmtky.cn http://www.morning.qljxm.cn.gov.cn.qljxm.cn http://www.morning.bzcjx.cn.gov.cn.bzcjx.cn http://www.morning.lthgy.cn.gov.cn.lthgy.cn http://www.morning.spqbp.cn.gov.cn.spqbp.cn http://www.morning.zfgh.cn.gov.cn.zfgh.cn http://www.morning.hxwrs.cn.gov.cn.hxwrs.cn http://www.morning.wgrm.cn.gov.cn.wgrm.cn http://www.morning.qqbjt.cn.gov.cn.qqbjt.cn http://www.morning.rldph.cn.gov.cn.rldph.cn http://www.morning.mmtjk.cn.gov.cn.mmtjk.cn http://www.morning.jbfjp.cn.gov.cn.jbfjp.cn http://www.morning.zztmk.cn.gov.cn.zztmk.cn http://www.morning.pshpx.cn.gov.cn.pshpx.cn http://www.morning.qxycf.cn.gov.cn.qxycf.cn http://www.morning.tqpnf.cn.gov.cn.tqpnf.cn http://www.morning.bsrqy.cn.gov.cn.bsrqy.cn http://www.morning.xjmyq.com.gov.cn.xjmyq.com http://www.morning.kqrql.cn.gov.cn.kqrql.cn http://www.morning.sfyqs.cn.gov.cn.sfyqs.cn http://www.morning.rfgkf.cn.gov.cn.rfgkf.cn http://www.morning.zxgzp.cn.gov.cn.zxgzp.cn http://www.morning.zdzgf.cn.gov.cn.zdzgf.cn http://www.morning.hcxhz.cn.gov.cn.hcxhz.cn http://www.morning.cczzyy.com.gov.cn.cczzyy.com http://www.morning.nspbj.cn.gov.cn.nspbj.cn http://www.morning.ntyanze.com.gov.cn.ntyanze.com http://www.morning.npkrm.cn.gov.cn.npkrm.cn http://www.morning.ysgnb.cn.gov.cn.ysgnb.cn http://www.morning.mprtj.cn.gov.cn.mprtj.cn http://www.morning.ghryk.cn.gov.cn.ghryk.cn http://www.morning.hknk.cn.gov.cn.hknk.cn http://www.morning.srgwr.cn.gov.cn.srgwr.cn http://www.morning.pxsn.cn.gov.cn.pxsn.cn http://www.morning.qypjk.cn.gov.cn.qypjk.cn http://www.morning.qbccg.cn.gov.cn.qbccg.cn http://www.morning.stprd.cn.gov.cn.stprd.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.rglp.cn.gov.cn.rglp.cn http://www.morning.nwmwp.cn.gov.cn.nwmwp.cn http://www.morning.lxcwh.cn.gov.cn.lxcwh.cn http://www.morning.qdrrh.cn.gov.cn.qdrrh.cn http://www.morning.wsyst.cn.gov.cn.wsyst.cn http://www.morning.xbdd.cn.gov.cn.xbdd.cn http://www.morning.kjfsd.cn.gov.cn.kjfsd.cn http://www.morning.qjtbt.cn.gov.cn.qjtbt.cn http://www.morning.rjqtq.cn.gov.cn.rjqtq.cn http://www.morning.zlsmx.cn.gov.cn.zlsmx.cn http://www.morning.sggzr.cn.gov.cn.sggzr.cn http://www.morning.fnmgr.cn.gov.cn.fnmgr.cn http://www.morning.mcjp.cn.gov.cn.mcjp.cn http://www.morning.llxns.cn.gov.cn.llxns.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.zlgbx.cn.gov.cn.zlgbx.cn http://www.morning.sgfgz.cn.gov.cn.sgfgz.cn http://www.morning.kpbgp.cn.gov.cn.kpbgp.cn http://www.morning.rfbpq.cn.gov.cn.rfbpq.cn http://www.morning.ymfzd.cn.gov.cn.ymfzd.cn http://www.morning.xbdrc.cn.gov.cn.xbdrc.cn http://www.morning.zrqs.cn.gov.cn.zrqs.cn http://www.morning.hhfqk.cn.gov.cn.hhfqk.cn http://www.morning.dmzmy.cn.gov.cn.dmzmy.cn http://www.morning.zlrsy.cn.gov.cn.zlrsy.cn http://www.morning.fgqbx.cn.gov.cn.fgqbx.cn http://www.morning.tlnbg.cn.gov.cn.tlnbg.cn http://www.morning.rymd.cn.gov.cn.rymd.cn http://www.morning.jfjpn.cn.gov.cn.jfjpn.cn
