day5

50.第一個只出現一次的字符(重點)

思路:哈希表
遍歷兩次字符串s，第一遍統(tǒng)計各個字符的出現次數，第二遍找出第一個次數為1的字符。
ps，不要去遍歷hashmap，因為map的順序未知..自己做的時候建了兩個map..

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char,int> hashmap;
        for(int i=0;i<s.size();i++){
            hashmap[s[i]]++;
        }
        char ans=' ';
        for(int i=0;i<s.size();i++){
            if(hashmap[s[i]]==1){
                ans=s[i];
                break;
            }
        }
        return ans;
    }
};

由于本題只需要一個簡單的哈希表就可以滿足要求，我們可以建立一個長度為26的數組來構建哈希表(事實上char類型也只有256種可能)。
時間復雜度o(n)
空間復雜度o(1) ：因為數組的大小是一個常數
比上面的代碼更快，用的空間更小。

class Solution {
public:
    char firstUniqChar(string s) {
        int hashmap[26]={};
        for(int i=0;i<s.size();i++){
            hashmap[s[i]-'a']++;
        }
        char ans=' ';
        for(int i=0;i<s.size();i++){
            if(hashmap[s[i]-'a']==1){
                ans=s[i];
                break;
            }
        }
        return ans;
    }
};

總結：如果需要判斷多個字符是不是在某個字符串里出現過或者統(tǒng)計多個字符在某個字符串中出現的次數，那么我們可以考慮基于數組創(chuàng)建一個簡單的哈希表，這樣可以用很小的空間消耗換來時間效率的提升。

相關題目：課本p246

50 - II .字符流中只出現一次的字符(重點)

題目：實現一個函數，用來找出字符流中第一個只出現一次的字符。例如當從字符流中只讀出前兩個字符“go”，第一個只出現一次的字符是“g”，當從該字符流中讀出前六個字符“google”，第一個只出現一次的字符就是“l(fā)”。

思路：p247-248
以前的題目可以對str(串)進行操作，現在不存在這么一個str。
流：字符流沒有存下來，無法對其進行遍歷，因此在本題中，只能在數據容器哈希表中遍歷，而且哈希表中存放的是對應字符的位置，而不是個數。

41.數據流中的中位數(重點)

思路1:建立一個vector不斷存儲數據流的數，每次尋找中位數時，就對vector 排序，然后取中間值。
超時

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> nums;
    MedianFinder() {
        nums.clear();
    }
    
    void addNum(int num) {
        nums.push_back(num);
    }
    
    double findMedian() {
        sort(nums.begin(),nums.end());
        if(nums.size()&1){
            return 1.0*nums[nums.size()/2];
        }
        else{
            return (nums[nums.size()/2] + nums[nums.size()/2-1])/2.0;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

其實不必對數組排序也可以，但同樣TLE

編輯代碼

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> nums;
    MedianFinder() {
        nums.clear();
    }
    
    void addNum(int num) {
        nums.push_back(num);
    }
    
    double findMedian() {
        int l=0,r=(int)nums.size()-1;//注意size()有坑
        int mid=partition(l,r);
        while(mid!=nums.size()/2){
            if(mid>nums.size()/2){
                r=mid-1;
                mid=partition(l,r);
            }
            else{
                l=mid+1;
                mid=partition(l,r);
            }
        }
        if(nums.size()&1){
            return 1.0*nums[mid];
        }
        else{
            return (nums[mid] + nums[mid-1])/2.0;
        }
    }

    int partition(int l,int r){
        int pivot=nums[l];
        int index=l;
        for(int i=l+1;i<=r;i++){
            if(nums[i]<=pivot){
                index++;
                swap(nums[i],nums[index]);
            }
        }
        swap(nums[l],nums[index]);
        return index;
    }
};

思路2:
受到40題的啟發(fā)：”當需要在某個數據容器內頻繁查找及替換最大值時，我們要想到二叉樹是一個合適的選擇，并能想到用堆或者紅黑樹等特殊的二叉樹來實現“
我希望每加入一個數就能調整數據容器的結構，使得很容易取到中間值。

• multiset & map

class MedianFinder {
public:
    /** initialize your data structure here. */
    multiset<int> nums;
    MedianFinder() {
        nums.clear();
    }
    
    void addNum(int num) {
        nums.insert(num);
    }
    
    double findMedian() {
        int index=0;
        multiset<int>::iterator it=nums.begin();
        //size()的返回值是unsigned類型
        //永遠的坑 當是0之后 如果0-1 答案并不是 -1
        //所以最好不要對他進行減法，或者可以強制轉int
        while(index < nums.size()/2 ){
            index++;
            it++;
       }
       //while過后，it指向nums.size()/2，index為nums.size()/2；
        if(nums.size()&1){
            return *it;
        }
        else{
            return (*it + *(--it))/2.0;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

map沒寫

• 堆/優(yōu)先隊列
  沒寫

上面沒寫是因為set表現極差，說明我的思路不好。

思路3:

42.連續(xù)子數組的最大和(重點)

思路：動態(tài)規(guī)劃
例如，輸入的數組為{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子數組為｛3, 10, -4, 7, 2}。因此輸出為該子數組的和18 。

我們試著從頭到尾逐個累加示例數組中的每個數字。初始化和為0。第一步加上第一個數字1， 此時和為1。接下來第二步加上數字-2，和就變成了-1。第三步刷上數字3。我們注意到由于此前累計的和是－1 ，小于0，那如果用-1 加上3 ，得到的和是2 ， 比3 本身還小。也就是說,從第一個數字開始的子數組的和會小于從第三個數字開始的子數組的和。因此我們不用考慮從第一個數字開始的子數組，之前累計的和也被拋棄。

我們從第三個數字重新開始累加，此時得到的和是3 。接下來第四步加10，得到和為13 。第五步加上-4， 和為9。我們發(fā)現由于-4 是一個負數，因此累加-4 之后得到的和比原來的和還要小。因此我們要把之前得到的和13 保存下來，它有可能是最大的子數組的和。第六步加上數字.7，9 加7 的結果是16，此時和比之前最大的和13 還要大，把最大的子數組的和由13更新為16。第七步加上2，累加得到的和為18，同時我們也要更新最大子數組的和。第八步加上最后一個數字-5，由于得到的和為13 ，小于此前最大的和18，因此最終最大的子數組的和為18 ，對應的子數組是｛3, 10, -4, 7, 2｝。

如果用函數f(i)表示以第i個數字結尾的子數組的最大和，那么我們需要求出max(f(i)),其中0<=i<n。可用如下遞歸公式求f(i)。

ps:最大的子數組和并不是f(n),即以最后一個數字結尾的子數組的最大和

代碼1:不額外建立數組保存f(i)
可以將原數組 nums 用作 dp 列表，即直接在 nums 上修改即可。
由于省去 dp 列表使用的額外空間，因此空間復雜度從 O(N) 降至O(1)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max=nums[0];//!不應該是一個極小值，因為你的for循環(huán)從1開始的
        for(int i=1;i<nums.size();i++){
            if(nums[i-1]>0){
                nums[i]=nums[i-1]+nums[I];
            }
            if(nums[i]>max) max=nums[I];
        }
        return max;
    }
};

代碼2:其實用兩個變量CurSum MaxSum,即可。
有的時候，題目要求可能不能修改原有數組，考慮到在dp列表中，dp[i]只和dp[i-1]有關,所以用兩個參數存儲循環(huán)過程中的dp[i]和dp[i-1]的值即可.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int CurSum=0,MaxSum=-1000;//題目說數字范圍為-100～100
        for(int i=0;i<nums.size();i++){
            if(CurSum>=0){
                CurSum+=nums[i];
            }
            else{
                CurSum=nums[i];
            }
            if(MaxSum<CurSum) MaxSum=CurSum;
        }
        return MaxSum;
    }
};

時間復雜度o(n) 空間復雜度o(1)
ps:獲取vector的最后一個元素

• return vec.at((int)vec.size()-1);//或者直接取值，不用at
• return vec.back();
• return vec.end()-1;
• return vec.rbegin();

43. 1～n 整數中 1 出現的次數(重點)

不會寫
思路1:遍歷每個數，計算其中1的個數。
TLE

class Solution {
public:
    int countDigitOne(int n) {
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=countOne(i);
        }
        return ans;
    }
    int countOne(int n){
        int sum=0;
        while(n!=0){
            if(n%10==1) sum++;
            n/=10;
        }
        return sum;
    }
};

思路2:課本p222-224
看不懂..

思路3.
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/javadi-gui-by-xujunyi/
找規(guī)律
11.85% 50%

class Solution {
public:
    int countDigitOne(int n) {
        string s=to_string(n);
        return f(n);
    }
    int f(int n){
        if(n<=0) return 0;
        string s=to_string(n);
        int high = s[0]-'0';
        int poww = pow(10, s.size()-1);
        int last = n - high*poww;
        if (high == 1) {
            return f(poww-1) + last + 1 + f(last);
        } else {
            return poww + high*f(poww-1) + f(last);
        }
    }
};

思路4:
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/shu-wei-dp-by-xun-zhao-liu-xing-luo-np70/
找規(guī)律得到遞推公式

感覺這幾個題解也不錯，但是沒精力看了，這題太難了。。
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/zi-jie-ti-ku-jian-43-kun-nan-1n-zheng-shu-zhong-1-/
https://leetcode-cn.com/problems/number-of-digit-one/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-50/
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/c-cong-ge-wei-bian-li-dao-zui-gao-wei-yi-ci-qiu-ji/
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/cong-di-wei-dao-gao-wei-cong-gao-wei-dao-esqj/

44.數字序列中某一位的數字(重點)

思路1:
很清晰：最直觀的方法就是從0開始逐一枚舉每個數字。每枚舉一個數字，就求出該數字是幾位數，并把該數字的位數和前面所有數字的位數累加。如果位數之和仍然小于或者等于輸入n，則繼續(xù)枚舉下一個數字。當累加的數位大于n時，那么第n位數字一定在這個數字里，再找出對應的那一位。
TLE
自己的代碼不如上面的思路清晰，但本質是一樣的；
為何自己的思路總是不清晰？
寫代碼之前先想清楚

class Solution {
public:
    int findNthDigit(int n) {
        int ans=0;
        for(int i=1;n>0;i++){
            int len_i=0;
            vector<int> digit_i;//個位在前
            int temp=i;
            while(temp){
                digit_i.push_back(temp%10);
                temp/=10;
                len_i++;
            }
            if(n>len_i){
                n-=len_i;
            }
            else if(n<=len_i){
                ans=digit_i[digit_i.size()-n];
                break;
            }
        }
        return ans;
    }
};

思路2:
思考還有沒有更快的方法？我們是不是可以找出某些規(guī)律從而跳過若干數字？
以求序列中1001位為例：
序列的前10位是0~9，所以第1001位一定在10之后，因此這10個數可以直接跳過。我們再從后面緊跟的序列中找到991（991=1001-10）位的數字。
接下來180!!位數字是10~99的兩位數。由于991>180，所以第991位所有的兩位數之后。我們再跳過90個兩位數，繼續(xù)從后面找881（881=991-180）位。
接下來的2700位是900個100~999的三位數中的一位。由于881<2700，所以第881位是某個三位數中的一位。由于881=270+1，這意味著第881位是從100開始的第270個數字370的中間位，也就是7 。

代碼寫不出來，糾結了半天，是錯的，最后仿照課本寫

class Solution {
public:
    int findNthDigit(int n) {
        if(n<0) return -1;

        int digits=1;
        while(true){
            //計算digits位的數至多有多少種情況 記為numbers
            int numbers=0;
            if(digits==1){
                numbers=10;
            }
            else{
                numbers=9*pow(10,digits-1);
            }
            if(n<(long)numbers*digits){//注意溢出以及判斷式的寫法 
                //當要找的那一位數字位于某m位數之中后，接著找出那一位數字
                int beginNumber=digits==1?0:pow(10,digits-1);//起始數字
                int number=beginNumber+n/digits;//要找的數
                int indexFromRight=digits-n%digits;
                for(int i=1;i<indexFromRight;i++){
                    number/=10;
                }
                return number%10;

            }
            n-=numbers*digits;
            digits++;
        }
        return -1;
    }
};

之前一直糾結下標從0開始，但是或許不用糾結。因為雖然從0開始計數，但算第0位。

別人寫的

/* 數字范圍    數量  位數    占多少位
    1-9        9      1       9
    10-99      90     2       180
    100-999    900    3       2700
    1000-9999  9000   4       36000  ...

    例如 2901 = 9 + 180 + 2700 + 12 即一定是4位數,第12位   n = 12;
    數據為 = 1000 + (12 - 1)/ 4  = 1000 + 2 = 1002
    定位1002中的位置 = (n - 1) %  4 = 3    s.charAt(3) = 2;
ps:從下標為 0 開始的序列中取第 n 個，則其下標為n - 1。
如字符串 "1002" ，如果下標從0開始，則要找的第四個字符的下標是3 。
*/
class Solution {
    public int findNthDigit(int n) {
        int digit = 1;   // n所在數字的位數
        long start = 1;  // 數字范圍開始的第一個數
        long count = 9;  // 占多少位
        while(n > count){
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}

思路也挺清晰
https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/

45.把數組排成最小的數(重點)

思路1:求出數組中所有數字的全排列，然后把每個排列拼起來，最后求出拼起來的數字的最小值。求數組的排列類似于38題：字符串的排列

思路2:課本227-230
想得出來就見鬼了

46.把數字翻譯成字符串(重點)

本題考點：從問題中分析出遞歸的表達式，并且能夠優(yōu)化遞歸代碼，用基于循環(huán)的代碼來避免不必要的重復計算。

重點：定義函數f(i)表示從第i位數字開始的不同翻譯的數目，
那么 f(i)=f(i+1)+g(i,i+1) * f(i+2)
當第i位和第i+1位兩位數字拼接起來的數字在10～25的范圍內時(不是小于等于25即可),g(i,i+1)的值為1，否則為0；

但上述遞歸很明顯存在重復計算，具體分析如下：以12258為例。如前所述，翻譯12258可以分解成兩個子問題：翻譯1和2558。接下來我們翻譯第一個子問題中剩下的2558，同樣也可以分解成兩個子問題：翻譯2和258，以及翻譯22和58.注意到子問題翻譯258重復出現了 。

遞歸從最大的問題開始自上而下解決問題。我們也可以從最小的子問題開始自下而上解決問題，這樣就可以消除重復的子問題。也就是說，我們從數字的末尾開始，然后從右到左翻譯并計算不同翻譯的數目。

自己寫的遞歸
但是遞歸的邊界條件糾結了很久才寫出來，后來是靜下心來思考可能出現的最終情況：l==r、r-l==1、l>r對應的返回值，才寫出來的。其實心里很沒有底。

class Solution {
public:
    int translateNum(int num) {
        string s=to_string(num);
        return translateNumCore(0,s.size()-1,s);
        //其實不必傳s.size()-1
    }

    int translateNumCore(int l,int r,string &s){
        if(l==r){
            return 1;
        }
        else if(r-l==1){
            if((s[l]-'0')*10+s[l+1]-'0' <= 25 && s[l]!='0'){
            //僅僅寫小于等于25時不夠的呀
                return 2;
            }
        }
        else if(l>r) return 0;

        if((s[l]-'0')*10+s[l+1]-'0' <= 25 && (s[l]-'0')*10+s[l+1]-'0' >=10){
        //僅僅寫小于等于25時不夠的呀
            return translateNumCore(l+1,r,s)+translateNumCore(l+2,r,s);
        }
        else{
            return translateNumCore(l+1,r,s);
        }
    }
};

按照上述的優(yōu)化遞歸思路寫的代碼

class Solution {
public:
    int translateNum(int num) {
        if(num<0) return 0;
        string s=to_string(num);
        
        vector<int> f(s.size(),0);
        if(s.size()==1) return 1;
        f[s.size()-1]=1;
        int temp=(s[s.size()-2]-'0')*10+s[s.size()-1]-'0';
        if(temp<=25 && temp >=10){
            f[s.size()-2]=2;
        }
        else{
            f[s.size()-2]=1;
        }

        for(int i=s.size()-3;i>=0;i--){
            int temp=(s[i]-'0')*10+s[i+1]-'0';
            if(temp<=25 && temp >=10){
                f[i]=f[i+2]+f[i+1];
            }
            else{
                f[i]=f[i+1];
            }
        }
        return f[0];
    }
};

不使用數組

class Solution {
public:
    int translateNum(int num) {
        if(num<0) return 0;
        string s=to_string(num);
    
        if(s.size()==1) return 1;
        int f1=1,f2;
        int temp=(s[s.size()-2]-'0')*10+s[s.size()-1]-'0';
        if(temp<=25 && temp >=10){
            f2=2;
        }
        else{
            f2=1;
        }

        int f3=f2;//size等于2的情況下，沒有進入循環(huán)， 但是下面返回f3
        for(int i=s.size()-3;i>=0;i--){
            int temp=(s[i]-'0')*10+s[i+1]-'0';
            if(temp<=25 && temp >=10){
                f3=f2+f1;
            }
            else{
                f3=f2;
            }
            int temp2=f2;
            f2=f3;
            f1=temp2;
        }
        return f3;
    }
};

課本的代碼看了，嗯不知道寫得如何，只是看了看，在p232
可以看看別人寫的遞歸代碼 別人的題解 以及評論區(qū)
今天這題搞太久了 下次再刷
當時自己寫真的寫了很久
https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/shou-hui-tu-jie-dfsdi-gui-ji-yi-hua-di-gui-dong-ta/
https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-by-leetcode-sol/
https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/dong-tai-gui-hua-dp-by-z1m/

評論區(qū)也沒看

47.禮物的最大價值

思路：動態(tài)規(guī)劃
轉移方程： dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        //定長數組，且初始化為0
        int r=grid.size(),c=grid[0].size();
        vector<vector<int>> dp(r+1, vector<int>(c+1, 0));
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[r][c];
    }
};

優(yōu)化：使用一維數組存儲上一行的值即可,前幾行的值已經沒有利用價值

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        //定長數組，且初始化為0
        int r=grid.size(),c=grid[0].size();
        vector<int> dp(c,0);
        for(int i=0;i<r;i++){
            int pre=0;
            for(int j=0;j<c;j++){
                dp[j]=max(pre,dp[j])+grid[i][j];
                pre=dp[j];
            }
        }
        return dp[c-1];
    }
};

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        //定長數組，且初始化為0
        int r=grid.size(),c=grid[0].size();
        vector<int> dp(c+1,0);
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                dp[j]=max(dp[j-1],dp[j])+grid[i-1][j-1];
            }
        }
        return dp[c];
    }
};

48.最長不含重復字符的子字符串(重點)

思路1：動態(tài)規(guī)劃
定義函數f(i)表示以第i個字符為結尾的不包含重復字符的子字符串的最長長度。從左到右逐一掃描字符串中的每個字符，計算f(i)

• 如果第i個字符之前沒有出現過
  f(i)=f(i-1)+1;
• 如果出現過，情況稍微復雜
  d=第i個字符和它上次出現在字符串的位置的距離
  接下來分兩種情況討論
  1:d<=f(i-1)
  此時第i個字符上次出現在f(i-1)對應的最長子字符串之中
  f(i)=d
  2:d>f(i-1)
  f(i)=f(i-1)+1

該題可以以一個變量替代f數組，因為我們只用到了f(i-1)來計算f(i)

我們還需要創(chuàng)建一個數組來存儲每個字符上次出現在字符串中位置的下標，我用了map。

如果只有26個字母，可以創(chuàng)建一個長度為26的數組，該數組所有元素的值都被初始化為-1，表示該元素還沒有出現過。
不應該是0，因為0表示第一個字符。不然aaaa這種，你下面一直滿足==0(判斷是否出現過)，cur會不斷增加?；蛘哒f，如果你初始化為0，那么下標應該從1開始。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> hashmap;
        int ans=0;
        int cur=0;//以當前字符結尾的不包含重復字符的子字符串長度
        for(int i=0;i<s.size();i++){
            if(hashmap.find(s[i])== hashmap.end()){
                cur++;
            }
            else{
                if(cur<i-hashmap[s[i]]){
                    cur++;
                }
                else{
                    cur=i-hashmap[s[i]];
                }
            }
            hashmap[s[i]]=i;
            ans=max(ans,cur);
        }
        return ans;
    }
};

思路2:滑動窗口(重點)
關鍵點在于:題目中要求答案必須是 子串 的長度，意味著子串內的字符在原字符串中一定是連續(xù)的。因此我們可以將答案看作原字符串的一個滑動窗口，并維護窗口內不能有重復字符，同時更新窗口的最大值。
https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/tu-jie-hua-dong-chuang-kou-shuang-zhi-zhen-shi-xia/
沒有實現

評論區(qū)用set\雙端隊列\(zhòng)數組來維護窗口
沒有細看

49.丑數(重點)

題意：簡單來說就是，只包含 因子2、3和5 的數稱作丑數。

相關概念：

1. 質數(素數)：在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數。否則稱為合數，規(guī)定1既不是質數也不是合數。
2. 若a是b的因數，且a是質數，則稱a是b的質因數(質因子)。質因數也就是質數的因子。例如2，3，5均為30的質因數。6不是質數，所以不算。7不是30的因數，所以也不是質因數。
3. 公因數只有1的兩個非零自然數,叫做互質數。
4. 正整數的因數分解可將正整數表示為一連串的質因子相乘，質因子如重復可以用指數表示。任何正整數皆有獨一無二的質因子分解式只有一個質因子的正整數為質數。每個合數都可以寫成幾個質數（也可稱為素數)相乘的形式，這幾個質數就都叫做這個合數的質因數。

不會寫，知道丑數應該是因子2、3、5的累乘，可不知道怎么按順序的求出丑數。

思路1:逐個判斷每個整數是不是丑數
課本p240-241

class Solution {
public:
    int nthUglyNumber(int n) {
        int number=0;
        while(n){
            number++;
            if(IsUgly(number)){
                n--;
            }
        }
        return number;
    }
    //0不能進入這里判斷，否則無限循環(huán)
    bool IsUgly(int num){
        while(num%2==0){
            num/=2;
        }
        while(num%3==0){
            num/=3;
        }
        while(num%5==0){
            num/=5;
        }
        return (num==1)?true:false;
    }
};

思路2:創(chuàng)建數組保存已經找到的丑數，用空間換時間
p241

計算過程中可能會溢出，雖然溢出的數字不會存入UglyNum數組中，但是他是計算過程中產生的結果，會溢出，導致程序崩潰。

class Solution {
public:
    int nthUglyNumber(int n) {
        //vector<int> UglyNum={1,2,3,5};這個不是有序的uglynum呀!
        vector<int> UglyNum={1};
        while(UglyNum.size()<n){
            int maxUgly=UglyNum.back(),minNewUgly=INT_MAX;
            for(int i=0;i<UglyNum.size();i++){
                long newUgly=(long)UglyNum[i]*2;
                if(newUgly>maxUgly && newUgly<minNewUgly){
                    minNewUgly=newUgly;
                }
                newUgly=(long)UglyNum[i]*3;
                if(newUgly>maxUgly && newUgly<minNewUgly){
                    minNewUgly=newUgly;
                }
                newUgly=(long)UglyNum[i]*5;
                if(newUgly>maxUgly && newUgly<minNewUgly){
                    minNewUgly=newUgly;
                }
            }
            UglyNum.push_back(minNewUgly);
        }
        return UglyNum.back();
    }
};

精簡一下代碼

class Solution {
public:
    int nthUglyNumber(int n) {
        //vector<int> UglyNum={1,2,3,5};這個不是有序的uglynum呀!!
        vector<int> UglyNum={1};
        while(UglyNum.size()<n){
            int maxUgly=UglyNum.back(),minNewUgly=INT_MAX;
            int factor[3]={2,3,5};
            for(int i=0;i<UglyNum.size();i++){
                for(int j=0;j<3;j++){
                    long newUgly=(long)UglyNum[i]*factor[j];
                    if(newUgly>maxUgly && newUgly<minNewUgly){
                        minNewUgly=newUgly;
                    }
                }
            }
            UglyNum.push_back(minNewUgly);
        }
        return UglyNum.back();
    }
};

思路3:對思路2進行優(yōu)化
p241-242
代碼怎么也寫不出來,因為不夠理解課本上的思路
最后按著課本的代碼，一行行敲。

思路3總結!!：
這個題用三指針，第一個丑數是1，以后的丑數都是基于前面的小丑數分別乘2，3，5構成的。我們每次添加進去一個當前計算出來個三個丑數的最小的一個，并且是誰計算的，誰指針就后移一位。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> UglyNumber={1};
        int t2=0,t3=0,t5=0;
        while(--n){
            int NewMinUgly=min(2*UglyNumber[t2],3*UglyNumber[t3]);
            NewMinUgly=min(NewMinUgly,5*UglyNumber[t5]);
            UglyNumber.push_back(NewMinUgly);
            while(2*UglyNumber[t2]<=NewMinUgly){
                t2++;
            }
            while(3*UglyNumber[t3]<=NewMinUgly){
                t3++;
            }
            while(5*UglyNumber[t5]<=NewMinUgly){
                t5++;
            }
        }
        return *UglyNumber.rbegin();
    }
};

https://leetcode-cn.com/problems/chou-shu-lcof/solution/chou-shu-ii-qing-xi-de-tui-dao-si-lu-by-mrsate/

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> UglyNumber={1};
        int t2=0,t3=0,t5=0;
        while(--n){
            int NewMinUgly=min(2*UglyNumber[t2],3*UglyNumber[t3]);
            NewMinUgly=min(NewMinUgly,5*UglyNumber[t5]);
            UglyNumber.push_back(NewMinUgly);
            if(2*UglyNumber[t2]==NewMinUgly){
                t2++;
            }
            if(3*UglyNumber[t3]==NewMinUgly){
                t3++;
            }
            if(5*UglyNumber[t5]==NewMinUgly){
                t5++;
            }
        }
        return UglyNumber.back();
    }
};

while和if都可以

51.數組中的逆序對

思路1:暴力解 TLE
時間復雜度o(n^2)

思路2: