31.整數(shù)中1出現(xiàn)的次數(shù)

求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)晒喷？
為此他特別數(shù)了一下1~13中包含1的數(shù)字有1孝偎、10、11凉敲、12衣盾、13因此共出現(xiàn)6次,但是對(duì)于后面問(wèn)題他就沒(méi)轍了。
ACMer希望你們幫幫他,并把問(wèn)題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）爷抓。

這個(gè)題在前面的一篇文章里面有寫(xiě)到過(guò)更普及的K出現(xiàn)的次數(shù)雨效，關(guān)鍵點(diǎn)有兩個(gè)：
1.統(tǒng)計(jì)的是k出現(xiàn)的次數(shù)，而不是包含k的數(shù)字的個(gè)數(shù)废赞，例如統(tǒng)計(jì)1出現(xiàn)的次數(shù)，那么11出現(xiàn)了2次,因此可以直接采用對(duì)每一位進(jìn)行分析出現(xiàn)K的次數(shù)叮姑，然后把所有的結(jié)果相加即可唉地；
2.對(duì)每一位進(jìn)行分析的時(shí)候要分大于K据悔，小于K，等于K三種情況來(lái)討論耘沼，以n=31245,k=2為例
1這一位极颓，a=3,b=245，最大的是22999,因此可能結(jié)果為2000-2999,12000-12999,22000-22999群嗤，共a1000=3000個(gè)菠隆；
2這一位，a=31狂秘，b=45,前面的從0-30都沒(méi)問(wèn)題骇径，可以取31100種，但當(dāng)前面為31時(shí)者春，只能取31200-31245共46種破衔，故共計(jì)3100+46=3146種；
4這一位钱烟，與小于K大致相同晰筛，但更多一些，a=312,b=5,那么從200-299,1200-1299,2200-2299....31200-31299均可拴袭，共(a+1)*10=3130種
按這個(gè)思路读第，把每一位出現(xiàn)K的可能加起來(lái)就是最后K出現(xiàn)的總次數(shù)
代碼如下

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n<0){
            return 0;
        }
        //用copyn來(lái)設(shè)置循環(huán)中止的條件，每次循環(huán)都使得copyn = copyn/10;
        int copyn = n;
        //用cnt來(lái)記錄當(dāng)前的位置拥刻，如個(gè)位就是10的0次方位
        int cnt = 0;
        //用sum來(lái)記錄最后的結(jié)果
        int sum = 0;
        while(copyn!=0){
            copyn /= 10;
            //對(duì)于a,mid,b以312的2這一位為例
            //a = 312/10=31
            int a = n/(int)Math.pow(10,cnt+1);
            //mid = 312%10/1=2
            int mid = n%(int)Math.pow(10,cnt+1)/(int)Math.pow(10,cnt);
            //b = 312%10%1 = 0
            int b = n%(int)Math.pow(10,cnt+1)%(int)Math.pow(10,cnt);
            if(mid<1){
                sum += a*(int)Math.pow(10,cnt);
            }
            if(mid==1){
                sum += a*(int)Math.pow(10,cnt)+b+1;
            }
            if(mid>1){
                sum += (a+1)*(int)Math.pow(10,cnt);
            }
            cnt++;
        }
        return sum;
    }
}

32.把數(shù)組排成最小的數(shù)

輸入一個(gè)正整數(shù)數(shù)組怜瞒，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)泰佳。
例如輸入數(shù)組{3盼砍，32，321}逝她，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323浇坐。

這個(gè)題的思路就是比較給定數(shù)組中的任意兩個(gè)數(shù)，例如3和32黔宛，由于323小于332近刘，所以32排在3前面，再比較3和321臀晃，由于3213小于3321觉渴，所以321排在3前面，最后比較32和321徽惋，由于32132小于32321案淋，所以321排在32前面，故排序大小順序?yàn)閇321,32,3]最后拼接起來(lái)得到的就是最后的結(jié)果险绘，即最小的數(shù)321323,由于考慮整數(shù)可能越界踢京，而且整數(shù)拼接起來(lái)可能比較麻煩誉碴，因此這里采用字符串進(jìn)行操作，且在對(duì)字符串進(jìn)行排序的時(shí)候用到lamda表達(dá)式瓣距；
代碼如下

import java.util.Arrays;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if(numbers==null||numbers.length==0){
            return "";
        }
        //用一個(gè)字符串?dāng)?shù)組存儲(chǔ)所有數(shù)字轉(zhuǎn)化成的字符串
        String[] nums = new String[numbers.length];
        for(int i=0;i<numbers.length;i++){
            //+""代表轉(zhuǎn)化為字符串
            nums[i] = numbers[i]+"";
        }
        //這里使用Arrays.sort進(jìn)行排序時(shí)用來(lái)了lambda表達(dá)式
        //即將s1+s2和s2+s1進(jìn)行升序排列
        Arrays.sort(nums,(s1,s2)->(s1+s2).compareTo(s2+s1));
        //最后將全部結(jié)果拼接起來(lái)黔帕，得到最后的輸出
        String res = "";
        for(String s:nums){
            res += s;
        }
        return res;
    }
}

33.丑數(shù)

把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）蹈丸。
例如6成黄、8都是丑數(shù)，但14不是逻杖，因?yàn)樗|(zhì)因子7奋岁。 
習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)弧腥。

該題的核心思想就是新的丑數(shù)依然是由老的丑數(shù)構(gòu)成的厦取，我們需要建立一個(gè)新的數(shù)組不斷存儲(chǔ)新加入的丑數(shù)，然后用三個(gè)指針指向2,3,5所在的該丑數(shù)數(shù)組的位置管搪，然后用2,3,5指針?biāo)傅奈恢玫某髷?shù)分別去乘以2,3,5選擇最小的虾攻，然后使得構(gòu)成這個(gè)新丑數(shù)的這個(gè)數(shù)的指針向后移動(dòng)一位，如果相同更鲁，則同時(shí)移動(dòng)一位霎箍，例如23和32，則index_2和index_3同時(shí)后移一位澡为；
代碼如下

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0){
            return 0;
        }
        //用3個(gè)指針指向2,3,5指向的丑數(shù)數(shù)組中的位置
        int index_2 = 0,index_3 = 0,index_5 = 0;
        int[] ugly_nums = new int[index];
        ugly_nums[0] = 1;
        for(int i=1;i<index;i++){
            //選擇最小的最為新丑數(shù)
            ugly_nums[i] = Math.min(Math.min(ugly_nums[index_2]*2,ugly_nums[index_3]*3),Math.min(ugly_nums[index_2]*2,ugly_nums[index_5]*5));
            int t2 = ugly_nums[i]/2,t3 = ugly_nums[i]/3,t5 = ugly_nums[i]/5;
            //判斷哪個(gè)指針需要后移
            if(t2==ugly_nums[index_2]){
                index_2++;
            }
            if(t3==ugly_nums[index_3]){
                index_3++;
            }
            if(t5==ugly_nums[index_5]){
                index_5++;
            }
        }
        //返回丑數(shù)數(shù)組總最后一個(gè)元素為第index個(gè)丑數(shù)
        return ugly_nums[index-1];
        
    }
}

34.第一個(gè)只出現(xiàn)一次的字符

在一個(gè)字符串(0<=字符串長(zhǎng)度<=10000漂坏，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符,
并返回它的位置, 如果沒(méi)有則返回 -1（需要區(qū)分大小寫(xiě)）.

本題最直觀的就是用hashmap來(lái)統(tǒng)計(jì)字符出現(xiàn)的次數(shù)，也可以建立一個(gè)整數(shù)數(shù)組媒至，通過(guò)將字符轉(zhuǎn)化為ASCII碼顶别，然后整數(shù)數(shù)組對(duì)應(yīng)位置上加一，然后再遍歷原字符串或轉(zhuǎn)化為的字符數(shù)組拒啰，返回第一個(gè)在整數(shù)數(shù)數(shù)組中為1的值
流程為

1.將String轉(zhuǎn)為一個(gè)字符數(shù)組c驯绎，如“abc”--->{‘a(chǎn)’,‘b’,‘c’};
2.建立一個(gè)容量為256的整型數(shù)組arr，每一位的下標(biāo)對(duì)應(yīng)著ASCII值
3.遍歷字符數(shù)組c,例如遍歷到了'a'谋旦，那么就在arr[(int)'a']的位置對(duì)應(yīng)的值+1
4.最后再遍歷一遍c剩失，找到第一個(gè)在arr中的值為1的那個(gè)字符，例如遍歷到了'a'且arr[int(a)]==1,那么就返回這個(gè)'a'所在的位置即可

代碼如下

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.length()==0||str==null){
            return -1;
        }
        //將String轉(zhuǎn)化為字符數(shù)組
        char[] arr = str.toCharArray();
        //建立一個(gè)整型數(shù)組册着，作用類似于hashmap拴孤，其中res的下標(biāo)i--->字符的ASCII值
        int[] res = new int[256];
        //遍歷一遍arr，使res中對(duì)應(yīng)位置的hash值加一
        for(char c:arr){
            res[(int)c]++;
        }
        //找到第一個(gè)hash值為1的字符甲捏，輸出它的位置
        for(int i=0;i<arr.length;i++){
            if(res[(int)arr[i]]==1){
                return i;
            }
        }
        return -1;
    }
}

35.數(shù)組中的逆序?qū)?/p>

在數(shù)組中的兩個(gè)數(shù)字演熟，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α?輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P司顿。
并將P對(duì)1000000007取模的結(jié)果輸出绽媒。 即輸出P%1000000007

該題的思路就是使用歸并排序蚕冬，就是通過(guò)遞歸將數(shù)組拆分為最小的依次相鄰的兩個(gè)單元，然后用兩個(gè)指針?lè)謩e指向左右數(shù)組的頭部是辕，若左邊指針指向的元素大于右邊指針指向的元素，那么在左邊數(shù)組中指針指向的元素后面的數(shù)全部都大于右邊數(shù)組中指針指向的元素猎提，這些全部都構(gòu)成逆序?qū)袢瑲w并排序中我們還需要一個(gè)輔助數(shù)組去存儲(chǔ)順序大小排列好的元素，這才叫做歸并锨苏，最后統(tǒng)計(jì)所有這些逆序?qū)Ω斫蹋褪俏覀冃枰慕Y(jié)果，注意不要超出界限伞租。
代碼如下

public class Solution {
    //防止cnt溢出所以用一個(gè)long類型
    private long cnt = 0;
    private int[] tmp;  

    public int InversePairs(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return (int)(cnt % 1000000007);
    }

    private void mergeSort(int[] nums, int l, int h) {
        if (h - l < 1)
            return;
        //求出中值分界線
        int m = l + (h - l) / 2;
        //歸并排序贞谓，這里采用遞歸，可以想象葵诈，第一次遞歸到最結(jié)尾的時(shí)候
        //一個(gè)長(zhǎng)度為2的數(shù)組裸弦，對(duì)左右繼續(xù)遞歸都只有一個(gè)元素了，因此直接return
        //然后再執(zhí)行merge這個(gè)函數(shù)作喘，此時(shí)長(zhǎng)度為2,相當(dāng)于最小的一個(gè)子單元的歸并排序
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, h);
        merge(nums, l, m, h);
    }

    private void merge(int[] nums, int l, int m, int h) {
        //指針i指向左邊數(shù)組的頭部理疙，j指向右邊數(shù)組的頭部，k指向輔助數(shù)組的當(dāng)前元素位置,
        //我們要將兩個(gè)數(shù)組中的元素依次比較大小泞坦，然后存入輔助數(shù)組中
        //再將原數(shù)組中從l到h的所有元素替換為輔助數(shù)組中從l到h的所有元素
        int i = l, j = m + 1, k = l;
        //這里不用&&而用||是因?yàn)榭赡茏笥抑心硞€(gè)數(shù)組的指針走到頭了
        //那么此時(shí)我們需要做的就是把另外一個(gè)數(shù)組的所有元素替換到輔助數(shù)組中
        //因此while中是并列的四個(gè)條件
        while (i <= m || j <= h) {
            if (i > m)
                tmp[k] = nums[j++];
            else if (j > h)
                tmp[k] = nums[i++];
            else if (nums[i] <= nums[j])
                tmp[k] = nums[i++];
            else {
                tmp[k] = nums[j++];
                //這里是說(shuō)窖贤，當(dāng)左邊的某個(gè)元素大于右邊的元素的時(shí)候
                //那么左邊數(shù)組中這個(gè)元素后的所有元素都大于當(dāng)前右邊指向的這個(gè)元素
                //統(tǒng)計(jì)左邊數(shù)組中這個(gè)元素后的所有元素的個(gè)數(shù)就是我們要求的逆序?qū)?                this.cnt += m - i + 1;
            }
            k++;
        }
        for (k = l; k <= h; k++)
            nums[k] = tmp[k];
    }
}