每天兩題03

題目一：旋轉數組的最小數字

　　思路：說實話看這個題目看了好久題目愣是沒看懂，到底是個什麼數組啊，又不說清楚，emmm...百度了好久才知道這個數組預設其中的元素的遞增的，而且在數組中的元素可能是重覆的，比如2344445這種也是行的，我們就分別討論一下有重覆元素和沒有重覆元素的情況；

　　第一種情況：數組中沒有重覆元素；

　　順便提一句，所謂的數組的旋轉，就是每次講第一個元素放到數組的最後一個位置，比如說上面的1234旋轉一下是2341，再旋轉就是3412，再旋轉就是4123,等等，我們可以把這些旋轉後的數組叫做原數組的一個旋轉

　　不知道大家有沒有發現，1234數組的這麼多旋轉中，如果都從中間進行切分，那麼可以看到一半是從小到大進行排序的，另外一半是沒有順序的，而且很明顯的是最小的元素始終都是在沒有順序的那一半中，到這裡我們可以想到一個很簡單的辦法，就是每次都將數組且一般，找沒有順序的那個數組，然後對這個沒有順序的數組繼續進行同樣的切分，直至最後找到最小元素，這種方式也叫做二分法。

　　這裡數組不管是奇數還是偶數都一樣：

public static int min(int[] arr){
        int left=0;//數組最左邊的位置
        int right=arr.length-1;//數組最右邊的位置
        
        while (left<right) {
            int midd=(right+left)/2;//數組中間的位置
            if (arr[left]<=arr[midd]) {
                left=midd+1;
            }else{
                right=midd;
            }
        }
        return arr[left];
    }
    
    public static void main(String[] args) {
        int[] arr = {17,1,3,7,9,10};
        int[] arr2 = {5,6,10,17,1};
        System.out.println(min(arr));//1
        System.out.println(min(arr2));//1
    }

　　第二種情況：數組中有重覆的元素，我們可以試試，即使數組中有重覆的元素，比如原始數組1222334，我們將它進行旋轉，2223341,2233412,2334122，其實還是保持著第一種情況中的規律：將數組從中間進行拆分，一半是有順序的，一半是沒有順序的，註意：這裡有一種特殊情況，比如原數組是01111，經過兩次旋轉之後就是11101，此時從中間切分會發現arr[left] == arr[midd] == arr[right],無法通過比較判斷哪邊是有順序的，哪邊是沒有順序的；

　　所以如果是這種特殊情況，這裡我們就用最簡單的遍歷去找到其中最小的值就可以了，代碼跟上面差不多：

public static int minRotate(int[] arr){
        int left=0;
        int right=arr.length-1;
        while(left<right){
            int midd = (left+right)/2;
            
            //這裡就是多了一步處理，其他的代碼都是和第一種情況一樣的
            if (arr[left] == arr[midd] && arr[midd] == arr[right]) {
                for (int i = left; i < right; i++) {
                    if (arr[i]<arr[i+1]) {
                        return arr[i];
                    }
                }
                return arr[left];
            }else if (arr[midd] <= arr[right]) {
                right = midd;
            }else{
                left = midd+1;
            }
        }
        return arr[left];
    }
    
    public static void main(String[] args) {
        int[] arr = {17,1,3,7,9,10};
        int[] arr2 = {5,6,10,17,1};
        int[] arr3 = {5,5,5,2,5};
        System.out.println(minRotate(arr));//1
        System.out.println(minRotate(arr2));//1
        System.out.println(minRotate(arr3));//2
    }

題目二：剪繩子

　　 一根長度為n的繩子，剪成多段，每一段都是整數，使得這些整數相乘結果最大；我們可以簡單的知道，n=2，最大乘積是1；n=3時，最大乘積是2；n=4時，最大乘積是2x2=4；n=5時，最大乘積是2x3=6。。。

　　那麼我們現在要知道，將繩子的每一段儘量剪成多少是最合適的呢？

　　這裡比較奇葩，好像是有這麼一個規律，當n>=5的時候，對於任意的n，都有這麼的一個結論：2(n-2)>n，3(n-3)>n，我們將這兩個不等式拆開可以知道就是n>4和n>4.5（可以看到拆開並沒什麼用），其實我有一個想法，就是首先將長度為n的繩子儘量剪短成長度A，然後再將每一段剪成兩段B和C，這兩段的乘積BC要大於A，最後算出來的乘積才是最大的！然後根據上面的不等式可以看到，最好的就是剪成的每一段A都可以被2或者3整除，換句話說就是儘量剪成2或者3這個長度的，而且對於同一長度來說，3(n-3)>2(n-2)，最好剪成3，是在不行的話才剪成2（一定不要剪成1，這麼不用多說吧。。。如果有個1，那就將3中一個1丟給1，組成2x2）

　　大概就是這麼一個邏輯，代碼實現：

public static int max(int n){
        if (n<2) {
            return 0;
        }
        if (n==2) {
            return 1;
        }
        if (n==3) {
            return 2;
        }
        //優先計算這個繩子可以拆開為多少個3，假如繩子剪掉了這麼多3，餘下的長度為1，那麼就少剪掉一個3，和1拼成4
        //然後剪成兩個2
        int num3 = n/3;
        if((n-num3*3)==1){
            num3--;
        }
        //這裡就是計算繩子剪掉了很多的3之後還有多少個2
        int num2 = (n-num3*3)/2;
        //最後就是將這麼多的3相乘，所有的2相乘，然後兩個結果相乘
        return (int) Math.pow(3, num3)*(int)Math.pow(2, num2);
        
        
    }

    public static void main(String[] args) {
        System.out.println(max(6));//9

    }