每日一题之《剑指offer》32,33题

第32题：把数组排成最小的数

难易度：⭐⭐

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个
例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323

对于本题，贪心策略的本质在于比较上，如果贪心策略为：

贪心思路A:
如果有字符串a和字符串b
a < b
那么对于String[] strs = {a,b} 将字符串拼接后的字典序为 a+b

贪心思路A是错误的，因为可以找到反例：

String a = "b"
String b = "ba"
"b" < "ba"
如果对于贪心策略A正确，那么String strs = {"b","ba"} 将字符串拼接后的结果为"bba"
但是我们知道正确 的结果应该为"bab"

正确的比较部分的贪心策略为：

如果字符串a和字符串b有：
a.concat(b) < b.concat(a)
那么对于String[] strs = {a,b} 将字符串拼接后的字典序为 a+b

因为贪心算法的证明非常繁琐，这里不给予证明，代码如下：

代码如下:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;

public class Solution {
    public static class MyComparator implements Comparator<String>{
        @Override
        public int compare(String a,String b){
            return (a + b).compareTo(b + a);
        }
    }
    public String PrintMinNumber(int [] numbers) {
        String[] strArr = new String[numbers.length];
        for(int i = 0;i < numbers.length;i++){
            strArr[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(strArr,new MyComparator());
        String res = "";
        for(int i = 0;i < strArr.length;i++){
            res += strArr[i];
        }
        return res;
    }
}

第33题：丑数

难易度：⭐⭐

题目描述:
把只包含质因子2、3和5的数称作丑数（Ugly Number)
例如6、8都是丑数，但14不是，因为它包含质因子7
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数

本题的思路是用空间去换时间。

要求出第多少个位置的丑数，就开辟多大的数组空间。因为向丑数数组中新添加的丑数一定是原本丑数数组中某个数字乘以2或者乘以3或者乘以5所得到的。我们使用p2,p3,p5三个指针标记数组当中的位置，通过类似于穷举的方法，它们对应的位置的数分别乘以2，3，5然后依次同丑数数组中顺序添加的最后一个数做比较，如果小于等于数组中最后的一个数，那么就向后移动一个位置。具体的思路可以看代码。
代码如下：

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0){
            return 0;
        }
        int[] uglyNumberArr = new int[index];
        uglyNumberArr[0] = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        int nextIndex = 1;
        while(nextIndex < index){
            uglyNumberArr[nextIndex] = getMin(uglyNumberArr[p2]*2,uglyNumberArr[p3]*3,uglyNumberArr[p5]*5);
            while(uglyNumberArr[p2]*2 <= uglyNumberArr[nextIndex]){
                p2++;
            }
            while(uglyNumberArr[p3]*3 <= uglyNumberArr[nextIndex]){
                p3++;
            }
            while(uglyNumberArr[p5]*5 <= uglyNumberArr[nextIndex]){
                p5++;
            }
            nextIndex++;
        }
        int res = uglyNumberArr[index - 1];
        uglyNumberArr = null;
        return res;
    }
    public static int getMin(int a,int b,int c){
        int min = a < b ? a : b;
        return min < c ? min : c;    
    }
}