原文歡迎關(guān)注http://blackblog.tech/2018/06/03/LeetCodeReview/
歡迎關(guān)注我的個(gè)人博客 http://blackblog.tech

這是一篇筆記型Blog，主要存一下最近練的代碼的筆記。LeetCode的代碼，在云端，復(fù)習(xí)起來(lái)麻煩，就這樣存下來(lái)。
目前的練習(xí)為L(zhǎng)eetCode中級(jí)算法與每日模擬賽.
沒(méi)事刷一刷LeetCode還是可以提高一下基本的代碼能力的。

LeetCode15 三數(shù)之和

題目

給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿(mǎn)足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿(mǎn)足要求的三元組集合為：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

C++代碼

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vec;
        sort(nums.begin(),nums.end());
        for(int k=0;k<nums.size();k++)
        {
            if(k>0 && nums[k]==nums[k-1])
                continue;
            int i,j;
            
            for(i=k+1,j=nums.size()-1;i<j;)
            {
                if(i>k+1 && nums[i]==nums[i-1])
                {
                    i++;
                    continue;
                }
                if(j<nums.size()-1 && nums[j]==nums[j+1])
                {
                    j--;
                    continue;
                }
                int sum = nums[i]+nums[j]+nums[k];
                if(sum==0)
                {
                    vector<int> m_vec;
                    m_vec.push_back(nums[k]);
                    m_vec.push_back(nums[i]);
                    m_vec.push_back(nums[j]);
                    vec.push_back(m_vec);
                    j--;
                    i++;
                }
                else if(sum<0) i++;
                else if(sum>0) j--;
            }
        }
        return vec;
    }
};

體會(huì)

此題直接窮舉一定爆時(shí)間
采用暴力+雙指針解法
首先對(duì)數(shù)據(jù)進(jìn)行排序。
第一次遍歷確定一個(gè)數(shù)字n，則剩下兩個(gè)數(shù)字的和必須是-n，這樣才滿(mǎn)足條件。確定兩個(gè)指針i、j，從左至右，從右至左依次遍歷。
單個(gè)指針遍歷的過(guò)程中，如果重復(fù)直接跳過(guò)，防止結(jié)果中出現(xiàn)重復(fù)的數(shù)字。
如果sum為0時(shí)，得到答案，存儲(chǔ)，繼續(xù)遍歷。
如果sum小于0，則證明當(dāng)前情況的左指針小了，左指針++。
如果sum大于0，則證明當(dāng)前情況的右指針大了，右指針--。

此題嘗試了二重暴力+二分，時(shí)間沒(méi)問(wèn)題，但是結(jié)果總出錯(cuò)，不知道為什么。

LeetCode73 矩陣置零

題目

給定一個(gè) m x n 的矩陣，如果一個(gè)元素為 0，則將其所在行和列的所有元素都設(shè)為 0。請(qǐng)使用原地算法。

樣例1:

輸入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
輸出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

樣例2:

輸入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
輸出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

C++代碼

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool Row[matrix.size()]={false};
        bool Col[matrix[0].size()]={false};
        if (matrix.size()==1 && matrix[0].size()==1) return ;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0){
                    Row[i]=true;
                    Col[j]=true;
                }
            }
        }
        
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(Row[i]) matrix[i][j]=0;
                else if(Col[j]) matrix[i][j]=0;
            }
        }
        return ;
    }
};

體會(huì)

這里使用的算法，空間復(fù)雜度O(m + n) ，并不是最優(yōu)算法。
最優(yōu)算法空間復(fù)雜度為常數(shù)級(jí)別
注意幾個(gè)細(xì)節(jié)就好
if (matrix.size()==1 && matrix[0].size()==1) return ;
這句話用來(lái)判斷[[1]]這樣的特殊情況
用于存儲(chǔ)0位的數(shù)字這樣開(kāi)辟
bool Row[matrix.size()]={false};
bool Col[matrix[0].size()]={false};
不要用vec去存儲(chǔ)0，不然難以匹配坐標(biāo)，用兩個(gè)數(shù)組一一對(duì)應(yīng)就好。

常數(shù)級(jí)別空間復(fù)雜度的算法并不復(fù)雜
就需要巧妙地利用原來(lái)矩陣的空間，這里利用第一行和第一列保存額外信息：
1 先判斷號(hào)第一行和第一列是否需要全部置零
2 有任何一個(gè)該行或者該列的元素為零那么這個(gè)第一行或者第一列的元素必然是零，就保存這個(gè)零，最后用來(lái)判斷整個(gè)矩陣的這一行或者這一列是否需要置零。
3 最后再根據(jù)前面判斷，決定是否把這個(gè)第一行和第一列置零。

LeetCode49 字謎分組

題目

給定一個(gè)字符串?dāng)?shù)組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"],
輸出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

說(shuō)明：

所有輸入均為小寫(xiě)字母。
不考慮答案輸出的順序。

C++代碼

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string,vector<string>> str_map;
        vector<vector<string>> res;
        for(auto str : strs)
        {
            string tmp=str;
            sort(tmp.begin(),tmp.end());
            str_map[tmp].push_back(str);
        }

        for(auto val : str_map)
        {
            //sort(val.second.begin(),val.second.end());
            res.push_back(val.second);
        }
        return res;
    }
};

體會(huì)

題目邏輯很清晰
自己手動(dòng)實(shí)現(xiàn)了一個(gè)算法，但是最后一組數(shù)據(jù)沒(méi)有過(guò)?。。。‰y受?。?！等一下附上代碼。
這個(gè)題目的思路很清晰，利用Map，將每次排序過(guò)的字符串作為Key，將剩下的字符串作為Val存放進(jìn)去，最后整體存放在一個(gè)二維Vector里面就可以了。

附一下差一組數(shù)據(jù)沒(méi)過(guò)的代碼

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> res;
    vector<string> fir_str;
    fir_str.push_back(strs[0]);
    res.push_back(fir_str);

    for(int i=1;i<strs.size();i++)
    {
        string tmp = strs[i];
        sort(tmp.begin(),tmp.end());
        bool flag=false;
        
        for (int j = 0; j < res.size(); j++) {
            string m_tmp = res[j][0];
            sort(m_tmp.begin(), m_tmp.end());
            if (tmp == m_tmp) {
                res[j].push_back(strs[i]);
                flag = true;
                break;
            }
        }
        
        if(!flag)
        {
            vector<string> new_str;
            new_str.push_back(strs[i]);
            res.push_back(new_str);
        }
        sort(res.begin(),res.end());
    }
    return res;
}
};

LeetCode75 顏色排序

題目

給定一個(gè)包含紅色、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組，原地對(duì)它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
注意:
不能使用代碼庫(kù)中的排序函數(shù)來(lái)解決這道題。
示例:

輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]

進(jìn)階：
一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法。
首先，迭代計(jì)算出0、1 和 2 元素的個(gè)數(shù)，然后按照0、1、2的排序，重寫(xiě)當(dāng)前數(shù)組。
你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎？

C++代碼

騷操作法：

void sortColors(vector<int>& nums) {
    map<int,vector<int>> m;
    for(int i=0;i<nums.size();i++)
    {
        int k=nums[i];
        m[k].push_back(k);
    }
    nums.erase(nums.begin(),nums.end());
    for(auto val : m)
    {
        for(int i=0;i<val.second.size();i++)
            nums.push_back(val.second[i]);
    }
}

快速排序：

class Solution {
public:
    void qsort(vector<int>& nums,int l,int r)
    {
        if(l>r) return;
        int mid = nums.size()/2;
        int i=l;
        int j=r;
        int flag = nums[l];

        while(i!=j)
        {
            while(i<j&&nums[j]>=flag)
                j--;
            while(i<j&&nums[i]<=flag)
                i++;
            int tmp;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        nums[l] =nums[i];
        nums[i] = flag;

        qsort(nums,i+1,r);
        qsort(nums,l,i-1);
    
    }
    void sortColors(vector<int>& nums) {
        qsort(nums,0,nums.size()-1);
    }
};

體會(huì)

用map可以直接排序有點(diǎn)意思
熟練一下快排

LeetCode347 Top K Frequent Elements

題目

給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。
例如，
給定數(shù)組 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。
注意：
你可以假設(shè)給定的 k 總是合理的，1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)。
你的算法的時(shí)間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小。

C++代碼

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> m;
        vector<int> res;
        for(int i=0;i<nums.size();i++)
        {
            m[nums[i]] +=1;
        }
        vector<pair<int,int>> vtMap;
        
        for(auto it=m.begin();it!=m.end();it++)
            vtMap.push_back(make_pair(it->first,it->second));
        
        sort(vtMap.begin(),vtMap.end(),cmp_by_val);
        
        for(int i=0;i<k;i++)
            res.push_back(vtMap[i].first);
        
        return res;
    }
    static bool cmp_by_val(pair<int,int> &a,pair<int,int> &b)
    {
        return a.second>b.second;
    }
};

體會(huì)

一道說(shuō)難不難，說(shuō)簡(jiǎn)單不簡(jiǎn)單的題。
熟練使用stl很重要。
這道題利用到了map通過(guò)val排序的方法，將map轉(zhuǎn)化成vector<pair<int,int>>的方法需要掌握，注意自己要寫(xiě)sort函數(shù)，sort函數(shù)一定是全局變量或者是static類(lèi)型。

LeetCode215 數(shù)組中的第K個(gè)最大元素

題目

在未排序的數(shù)組中找到第 k 個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。
示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

示例 2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

說(shuō)明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。

C++代碼

class Solution {
public:
int partition(vector<int>&nums, int low, int high)//找樞紐
{
    int first = low;
    int last = high;
    int key = nums[first];//用字表的第一個(gè)記錄作為樞軸
    while (first != last)
    {
        while (nums[last] >= key && first < last)
            last--;
        swap(nums[first], nums[last]);
        while (nums[first] <= key && first < last)
            first++;
        swap(nums[first], nums[last]);
    }
    return first;//返回一個(gè)樞紐
}
int find_k(vector<int>& nums,int l,int r,int k)
{
    int index=partition(nums,l,r);
    int length = r-index+1;
    if(length == k) //計(jì)算后面一段的長(zhǎng)度，如果等于k表示找到了第k大
        return nums[index];
    else if(length > k)//如果后面的一段的長(zhǎng)度大于k，證明第k大的數(shù)在后面一段
        return find_k(nums,index+1,r,k);
    else if(length <k)//如果后面的一段的長(zhǎng)度小于k，證明第k大的數(shù)在前面一段
        return find_k(nums,l,index-1,k-length);//k-length 去掉已經(jīng)被劃分的數(shù)字
}
int findKthLargest(vector<int>& nums, int k) {
    return find_k(nums,0,nums.size()-1,k);
    }
};

體會(huì)

利用快排思想查找第k大的數(shù)字，注意把patition和find_k分開(kāi)寫(xiě)，寫(xiě)到一起容易出錯(cuò)。
時(shí)間復(fù)雜度：
該算法的平均時(shí)間復(fù)雜度為O(N)（詳細(xì)的推導(dǎo)過(guò)程看算法導(dǎo)論9.2節(jié)）,最壞情況為N^2，即每次劃分把數(shù)組變?yōu)闉椋╪-1） 和1的兩斷。

LeetCode425 電話號(hào)碼的字母組合

題目

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。
大概是這樣的：
base[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

示例:

輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

說(shuō)明:
盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。

C++代碼

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.length()<=0) 
        {
            vector<string> v;
            return v;
        }//此處為題目要求
        vector<string> res;
        int index=0;
        string str="";
        letterCombinationsSearch(digits,str,index,res);
        return res;
    }
    void letterCombinationsSearch(string digits,string str,int index, vector<string> &res)//注意啊，這里一定是取地址?。?！
    {
        if(index==digits.size())
        {
            res.push_back(str);//搜索觸底 將當(dāng)前的字符串存入結(jié)果中
            return;
        }
        string base[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        for(int i=0;i< base[digits[index]-'0'].size();i++)//自行領(lǐng)悟
        {
            str +=base[digits[index]-'0'][i];//將base數(shù)組對(duì)應(yīng)位置的每個(gè)字母都放進(jìn)字符串。
            letterCombinationsSearch(digits,str,index+1,res);//遞歸，尋找下一個(gè)字母。
            str.pop_back();//ad找完之后，彈出d，準(zhǔn)備放入e
        }
    }
};

體會(huì)

整個(gè)問(wèn)題就是一個(gè)dfs+回溯。
舉個(gè)例子，比如“234”，先一口氣找到adg，然后彈出g，找到adh，彈出h，找到adi，彈出i，彈出d，找到aeg，以此類(lèi)推。

LeetCode46 全排列

題目

給定一個(gè)沒(méi)有重復(fù)數(shù)字的序列，返回其所有可能的全排列。
示例:

輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

C++代碼

class Solution {
public:
    void permute_search(vector<int>&nums,vector<bool>&used,vector<int>&tmp,vector<vector<int>>&res)
    {
        if(tmp.size()==nums.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(!used[i])
            {
                tmp.push_back(nums[i]);//存入一個(gè)沒(méi)有用過(guò)的數(shù)字
                used[i]=true;//用過(guò)的數(shù)字標(biāo)記為true
                permute_search(nums,used,tmp,res);
                tmp.pop_back();//彈出剛剛用過(guò)的數(shù)字
                used[i]=false;//將所對(duì)應(yīng)的使用狀態(tài)改為false

            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int index=-1;
        vector<int> tmp;
        vector<bool> used(nums.size(), false);
        permute_search(nums,used,tmp,res);
        return res;
    }
};

體會(huì)

一道非常簡(jiǎn)單dfs+回溯題目，創(chuàng)建一個(gè)used數(shù)組用來(lái)存儲(chǔ)當(dāng)前每個(gè)數(shù)字的使用狀態(tài)。核心部分都寫(xiě)了注釋?zhuān)@里就不贅述了。

LeetCode78 子集

題目

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
說(shuō)明：解集不能包含重復(fù)的子集。
示例:

輸入: nums = [1,2,3]
輸出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

C++代碼

class Solution {
public:
    void subsets_search(vector<int>& nums,vector<int>&tmp,int index,vector<vector<int>> &res)
    {
        if(index==nums.size())
        {
            return ;
        }
        for(int i=index;i<nums.size();i++)
        {
            tmp.push_back(nums[i]);//將臨時(shí)數(shù)組增加一個(gè)數(shù)字
            res.push_back(tmp);//將臨時(shí)數(shù)組放入答案數(shù)組中
            subsets_search(nums,tmp,i+1,res);//遞歸調(diào)用，注意這里是i+1，不是index+1，因?yàn)槭褂胕ndex會(huì)出現(xiàn)1 3已被放入，index=2，遞歸index=3，將3也放入tmp，這樣會(huì)出現(xiàn)1 3 3 的情況。
            tmp.pop_back();//將臨時(shí)數(shù)組減少一個(gè)數(shù)字，用于回溯
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> tmp;//創(chuàng)建一個(gè)臨時(shí)數(shù)組用于增加刪除數(shù)字
        vector<vector<int>>res;//結(jié)果數(shù)組
        res.push_back(tmp);
        int index=0;
        subsets_search(nums,tmp,index,res);
        return res;
    }

};

體會(huì)

簡(jiǎn)單回溯題，重點(diǎn)已經(jīng)在注釋中寫(xiě)的很清晰了。
這個(gè)題比較有意思的地方就在于每次都要把tmp都放入res中。
注意遞歸調(diào)用參數(shù)是i+1，不是index+1，因?yàn)槭褂胕ndex會(huì)出現(xiàn)1 3已被放入，index=2，遞歸index=3，將3也放入tmp，這樣會(huì)出現(xiàn)1 3 3 的情況。

LeetCode202 快樂(lè)數(shù)

題目

編寫(xiě)一個(gè)算法來(lái)判斷一個(gè)數(shù)是不是“快樂(lè)數(shù)”。
一個(gè)“快樂(lè)數(shù)”定義為：對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和，然后重復(fù)這個(gè)過(guò)程直到這個(gè)數(shù)變?yōu)?1，也可能是無(wú)限循環(huán)但始終變不到 1。如果可以變?yōu)?1，那么這個(gè)數(shù)就是快樂(lè)數(shù)。
示例:

輸入: 19
輸出: true
解釋: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

C++代碼

騷操作法：

class Solution {
public:
    bool isHappy(int n) {
        while(1)
        {
            int k=0;
            while(n)
            {
                k+=(n%10)*(n%10);
                n/=10;
            }
            if(k==1) return true;
            if(k==4) return false;
            n = k;
        }
    }
};

常規(guī)解法：

class Solution {
public:
    bool isHappy(int n) {
        vector<int> vec;
        while(1)
        {
            int k=0;
            while(n)
            {
                k+=(n%10)*(n%10);
                n/=10;
            }
            if(k==1) return true;
            for(int i=0;i<vec.size();i++)
            {
                if(k==vec[i]) return false;
            }
            vec.push_back(k);
            n = k;
        }
    }
};

體會(huì)

有意思的一道題！
先說(shuō)常規(guī)解法：
所有的不開(kāi)心數(shù)最后都無(wú)法得到1，意味著他們一定會(huì)陷入一個(gè)有重復(fù)數(shù)字出現(xiàn)的循環(huán)，所以只要使用一個(gè)vector存儲(chǔ)一下所有出現(xiàn)的數(shù)字，有相同的就返回false。
再來(lái)一波騷操作：
不是快樂(lè)數(shù)的數(shù)稱(chēng)為不快樂(lè)數(shù)（unhappy number），所有不快樂(lè)數(shù)的數(shù)位平方和計(jì)算，最後都會(huì)進(jìn)入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循環(huán)中。
所以只需要判斷一下4就可以了。

LeetCode172 階乘后的零

題目

給定一個(gè)整數(shù) n，返回 n! 結(jié)果尾數(shù)中零的數(shù)量。
示例 1:

輸入: 3
輸出: 0
解釋: 3! = 6, 尾數(shù)中沒(méi)有零。

示例 2:

輸入: 5
輸出: 1
解釋: 5! = 120, 尾數(shù)中有 1 個(gè)零.

說(shuō)明: 你算法的時(shí)間復(fù)雜度應(yīng)為 O(log n) 。

C++代碼

class Solution {
public:
    int trailingZeroes(int n) {
        int count=0;
        while(n)
        {
            count+=n/5;
            n/=5;
        }
        return count;
    }
};

體會(huì)

技巧題！
關(guān)鍵在于5的數(shù)量了那么該問(wèn)題的實(shí)質(zhì)是要求出1~100含有多少個(gè)5由特殊推廣到一般的論證過(guò)程可得：
1、 每隔5個(gè)，會(huì)產(chǎn)生一個(gè)0，比如 5， 10 ，15，20...
2 、每隔 5×5 個(gè)會(huì)多產(chǎn)生出一個(gè)0，比如 25，50，75，100
3 、每隔 5×5×5 會(huì)多出一個(gè)0，比如125.

所以100！末尾有多少個(gè)零為：100/5+100/25=20+4=24那么1000！末尾有多少個(gè)零呢？同理得： 1000/5+1000/25+1000/125=200+40+8=248

接著，請(qǐng)問(wèn)N！的末尾有多少個(gè)零呢？
其實(shí) 也是同理的
N/5+N/25+……
如計(jì)算 2009! 的末尾有多少個(gè)0:2009/5 = 401
1~2009之間有 401 個(gè)數(shù)是 5 的倍數(shù)(余數(shù)省略).401/5 = 80
1~2009 之間有 80 個(gè)數(shù)是 25 的倍數(shù).80/5 = 16
1~2009 之間有 16 個(gè)數(shù)是 125 的倍數(shù). 16/5 = 3
1~2009 之間有 3個(gè)數(shù)是 625 的倍數(shù). 3/5 = 0
1~2009 之間有 0 個(gè)數(shù)是 3125 的倍數(shù).
所以, 2009！ 的末尾有 401 + 80 + 16 + 3 = 500 個(gè)0.

LeetCode50 Pow(x, n)

題目

實(shí)現(xiàn) pow(x, n) ，即計(jì)算 x 的 n 次冪函數(shù)。

示例 1:

輸入: 2.00000, 10
輸出: 1024.00000

示例 2:

輸入: 2.10000, 3
輸出: 9.26100

示例 3:

輸入: 2.00000, -2
輸出: 0.25000

解釋: 2-2 = 1/22 = 1/4 = 0.25
說(shuō)明:
-100.0 < x < 100.0
n 是 32 位有符號(hào)整數(shù)，其數(shù)值范圍是 [?2^31, 2^31 ? 1] 。

C++代碼

class Solution {
public:
    double myPow(double x, int n) {
        if(n<0) return 1/power(x,-n);
        else return power(x,n);
    }
    double power(double x,int n)
    {
        if(n==0) return 1;
        double half = power(x,n/2);
        if(n%2==0) return half*half;
        else return x*half*half;
    }
};

體會(huì)

技巧題！
這里解釋一下代碼
比如我們計(jì)算2^7
可以拆分為 2^3 * 2^3 * 2
2^3可以繼續(xù)拆分為 2^1 * 2^1 * 2
所以2^7可以拆分了 2^3 * 2^3 * 2 分為 2^1 * 2^1 * 2 * 2^1 * 2^1 * 2 * 2

LeetCode105 中序遍歷二叉樹(shù)

題目

給定一個(gè)二叉樹(shù)，返回它的中序 遍歷。
示例:

輸入: [1,null,2,3]
   1
    \
     2
    /
   3

輸出: [1,3,2]

進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

C++代碼

遞歸（不考慮安全性）

class Solution {
public:
    vector<int> res;
    void inorderTraversal2(TreeNode* root)
    {
        if(root==NULL) { return;}
        inorderTraversal(root->left);//遍歷左子節(jié)點(diǎn)
        res.push_back(root->val);//存入當(dāng)前節(jié)點(diǎn)的值 也就是中節(jié)點(diǎn)
        inorderTraversal(root->right);//遍歷右子節(jié)點(diǎn)
        return ;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inorderTraversal2(root);
        return res;
    }
};

遞歸（考慮安全性，不使用全局變量）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==NULL) { vector<int> v;return v;}
        vector<int> res;
        vector<int> tmp_left;
        tmp_left = inorderTraversal(root->left);//遍歷左子節(jié)點(diǎn)
        if(!tmp_left.empty())
        {
            for(int i=0;i<tmp_left.size();i++)
            {
                res.push_back(tmp_left[i]);//上一次遞歸的結(jié)果存儲(chǔ)在tmp中，用一個(gè)循環(huán)獲取所有數(shù)據(jù)。
            }
        }
        res.push_back(root->val);//存入當(dāng)前節(jié)點(diǎn)的值 也就是中節(jié)點(diǎn)

        vector<int> tmp_right;
        tmp_right = inorderTraversal(root->right);//遍歷右子節(jié)點(diǎn)
        if(!tmp_right.empty())
        {
            for(int i=0;i<tmp_right.size();i++)
            {
                res.push_back(tmp_right[i]);
            }
        }
        return res;
    }
};

迭代法（使用棧完成）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* current = root;
        while(current||!s.empty())
        {
            if(current)
            {
                s.push(current);//當(dāng)前節(jié)點(diǎn)壓棧
                current = current->left;//先走左邊
            }
            else
            {
                res.push_back(s.top()->val);//將棧頂元素存入向量，現(xiàn)在curr的父節(jié)點(diǎn)，此時(shí)curr==null
                current = s.top()->right;//修改current為當(dāng)前棧頂元素的右節(jié)點(diǎn)，
                s.pop();//彈出當(dāng)前棧頂元素
            }
        }
        return res;
    }
};

體會(huì)

難度不高
中序遍歷，如果不考慮安全性的話，幾句話就可以寫(xiě)完呢。
使用棧的方法可以大大提升效率，建議使用。

LeetCode55 跳躍游戲

題目

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。
判斷你是否能夠到達(dá)最后一個(gè)位置。

示例 1:

輸入: [2,3,1,1,4]
輸出: true
解釋: 從位置 0 到 1 跳 1 步, 然后跳 3 步到達(dá)最后一個(gè)位置。

示例 2:

輸入: [3,2,1,0,4]
輸出: false
解釋: 無(wú)論怎樣，你總會(huì)到達(dá)索引為 3 的位置。但該位置的最大跳躍長(zhǎng)度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個(gè)位置。

C++代碼

class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool dp[nums.size()*2]={false};
        dp[0]=true;
        for(int i=0;i<nums.size();i++) //遍歷每一個(gè)位置
        {
            for(int j=1;j<=nums[i];j++)//計(jì)算當(dāng)前位置每種可能跳的情況
            {
                if(dp[i]) dp[i+j]=true;//如果當(dāng)前位置能跳到，下一個(gè)位置才能
            }
        }
        return dp[nums.size()-1];
    }
};

體會(huì)

emmmmm，很迷，這個(gè)也算是DP？？？
不過(guò)細(xì)想，也算是劃分子問(wèn)題了。
很簡(jiǎn)單
二重循環(huán)，都遍歷一遍，然后計(jì)算每一個(gè)可以到達(dá)的路徑。重點(diǎn)在于if(dp[i]) dp[i+j]=true，只有當(dāng)前位置能夠到達(dá)，當(dāng)前位置的下一個(gè)位置才能到。

LeetCode62 不同路徑

題目

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問(wèn)總共有多少條不同的路徑？
說(shuō)明：m 和 n 的值均不超過(guò) 100。

示例 1:

輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開(kāi)始，總共有 3 條路徑可以到達(dá)右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

輸入: m = 7, n = 3
輸出: 28

C++ 代碼

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[200][200]={0};
        dp[1][1]=0;
        for(int i=1;i<=m;i++)
            dp[i][1]=1;
        for(int i=1;i<=n;i++)
            dp[1][i]=1;
        for(int i=2;i<=m;i++)
        {
            for(int j=2;j<=n;j++)
            {
                dp[i][j]=std::max(dp[i][j],dp[i][j-1]+dp[i-1][j]);
            }
        }
        return dp[m][n];
    }
};

體會(huì)

基本DP題
dp[i][j]表示網(wǎng)格為i*j時(shí)候的方法數(shù)
狀態(tài)轉(zhuǎn)移方程：dp[i][j] = dp[i][j-1]+dp[i-1][j]
注意初始化的時(shí)候要將第一行第一列初始化為1，因?yàn)榈谝恍械谝涣性趺醋叨际?。

LeetCode322 零錢(qián)兌換

題目

給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒(méi)有任何一種硬幣組合能組成總金額，返回 -1。

示例 1:

輸入: coins = [1, 2, 5], amount = 11
輸出: 3 
解釋: 11 = 5 + 5 + 1

示例 2:

輸入: coins = [2], amount = 3
輸出: -1

說(shuō)明:
你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

C++代碼

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int min=99999999999;
        int dp[100000];
        
        //過(guò)濾一下特別大的數(shù)字
        for(int i=0;i<coins.size();i++)
            if(coins[i]>amount) coins[i]=0;
        //初始化DP數(shù)組
        for(int i=1;i<=amount;i++)
            dp[i]=999999999;
        //當(dāng)j==coins[i]時(shí)，coins[i]所對(duì)應(yīng)的價(jià)值至少有一個(gè)硬幣可以構(gòu)成
        for(int i=0;i<coins.size();i++)
            if(coins[i]!=0) dp[coins[i]]=1;
        
        for(int i=0;i<coins.size();i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {
                if(coins[i]!=0) 
                    dp[j]=std::min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount] == 999999999) return -1;
        else return dp[amount];
    }
};

體會(huì)

完全背包+最小值+恰好裝滿(mǎn)
dp[j]表示：前i個(gè)硬幣，價(jià)值為j時(shí)候的硬幣數(shù)量
使用一維數(shù)組壓縮空間
狀態(tài)轉(zhuǎn)移方程： dp[j]=min(dp[j],dp[j-coins[i]]+1)
完全背包：正序循環(huán)
最小值：min
恰好裝滿(mǎn)：初始化為inf

LeetCode300 Longest Increasing Subsequence

題目

給定一個(gè)無(wú)序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度。
示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4 
解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]，它的長(zhǎng)度是 4。

說(shuō)明:
可能會(huì)有多種最長(zhǎng)上升子序列的組合，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。
你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 。
進(jìn)階: 你能將算法的時(shí)間復(fù)雜度降低到 O(n log n) 嗎?

C++代碼

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int dp[10000];//每一個(gè)上升子序列的長(zhǎng)度至少是1
        int res=1;
        for(int i=0;i<nums.size();i++)
            dp[i] = 1;
        for(int i=0;i<nums.size();i++) //遍歷所有的長(zhǎng)度
        {
            for(int j=0;j<i;j++)//模擬添加逐個(gè)數(shù)字
            {
                if(nums[j]<nums[i])//如果nums[j]<num[i]保證是遞增序列，
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            res = max(res,dp[i]);
        }
        return res;
    }
};

體會(huì)

首先區(qū)分兩個(gè)題目！
LIS：最長(zhǎng)遞增子序列（子串）
LCS：最長(zhǎng)公共子序列（子串）

最長(zhǎng)公共子串（Longest Common Substring）與最長(zhǎng)公共子序列（Longest Common Subsequence）的區(qū)別：
子串要求在原字符串中是連續(xù)的，而子序列則只需保持相對(duì)順序一致，并不要求連續(xù)。
例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最長(zhǎng)公共子序列，但不是它們的最長(zhǎng)公共字串。
對(duì)該題是同理

這個(gè)題是求解最長(zhǎng)上升子序列
采用動(dòng)態(tài)規(guī)劃的思想
dp[i] 表示 長(zhǎng)度為i的數(shù)列中最長(zhǎng)遞增子序列的長(zhǎng)度！注意是長(zhǎng)度！
我們劃分為子問(wèn)題
從i開(kāi)始遍歷長(zhǎng)度，每次一個(gè)新長(zhǎng)度就模擬添加數(shù)字，從第一個(gè)開(kāi)始添加，如果新添加的一個(gè)數(shù)字小于當(dāng)前nums[i]的大小，那么子序列的長(zhǎng)度就會(huì)增長(zhǎng)1。
在這之前要將dp中所有的數(shù)字初始化為1，因?yàn)檫f增子序列的長(zhǎng)度至少為1。

LeetCode2 兩數(shù)相加

題目

給定兩個(gè)非空鏈表來(lái)表示兩個(gè)非負(fù)整數(shù)。位數(shù)按照逆序方式存儲(chǔ)，它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字。將兩數(shù)相加返回一個(gè)新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開(kāi)頭。
示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

C++代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0);
        ListNode *curr = head;
        int carry=0;//用于存儲(chǔ)進(jìn)位
        bool l1_finish=false;//用于判斷第一個(gè)鏈表是否走完
        bool l2_finish=false;//用于判斷第二個(gè)鏈表是否走完
        while(1)
        {
            int val_tmp;//臨時(shí)存一下
            //三種情況，同時(shí)加兩個(gè)，只加一個(gè)，記得每次加carry
            if(l1_finish==false && l2_finish==false)
                val_tmp = l1->val + l2->val + carry;
            else if(l1_finish==false && l2_finish==true)
                val_tmp = l1->val + carry;
            else if(l1_finish==true && l2_finish==false)
                val_tmp = l2->val + carry;
            
            carry = val_tmp/10;//存儲(chǔ)進(jìn)位
            ListNode *new_node = new ListNode(val_tmp%10);//生成一個(gè)新的節(jié)點(diǎn)
            curr->next = new_node;//append節(jié)點(diǎn)
            curr = curr->next;//移動(dòng)游標(biāo)
            //判斷是否到頭
            if(l1->next==NULL) 
                l1_finish = true;
            else l1 = l1->next;
            
            if(l2->next==NULL) 
                l2_finish = true;
            else l2 = l2->next;
            //結(jié)束循環(huán)，注意分情況討論有無(wú)進(jìn)位情況
            if(l1_finish && l2_finish && carry==0) break;
            else if(l1_finish && l2_finish && carry!=0)
            {
                ListNode *carry_node = new ListNode(carry);
                curr->next = carry_node;
                curr = curr->next;
                break;
            }
        }
        return head->next;//head是空哦，返回下一個(gè)值
    }
};

體會(huì)

的確是簡(jiǎn)單題，直接模擬！
但我寫(xiě)的好復(fù)雜啊?。?！
應(yīng)該是沒(méi)寫(xiě)好，以后再改吧。
注意[5],[5]、[1,8],[0]這樣的數(shù)據(jù)，有詐！

LeetCode328 奇偶鏈表

題目

給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請(qǐng)注意，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性，而不是節(jié)點(diǎn)的值的奇偶性。
請(qǐng)嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時(shí)間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點(diǎn)總數(shù)。
示例 1:

輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL

示例 2:

輸入: 2->1->3->5->6->4->7->NULL 
輸出: 2->3->6->7->1->5->4->NULL

說(shuō)明:
應(yīng)當(dāng)保持奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對(duì)順序。
鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類(lèi)推。

C++代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next==NULL) return head;//保護(hù)一下下 [],[1] 這兩種情況
        
        ListNode *new_head = new ListNode(0);
        ListNode *curr = head;
        ListNode *curr_new = new_head;
        int index =0;
        while(curr)
        {
            if(curr->next&&curr->next->next)//1,2,3,4,5這種情況
            {
            ListNode *new_node = new ListNode(curr->next->val);
            curr_new->next = new_node;
            curr_new = curr_new->next;
            ListNode *tmp_delete = curr->next;//保護(hù)內(nèi)存
            curr->next = curr->next->next;
            delete(tmp_delete);//保護(hù)內(nèi)存
            curr = curr->next;
            if(curr->next ==NULL) break;//指針移動(dòng)到5，直接break；
            }
            //1,2,3,4,5,6這種情況，最后的6要單獨(dú)處理
            else if(curr->next && !curr->next->next){
                curr_new->next = curr->next;
                break;
            }
        }
        curr->next = new_head->next;
        return head;
    }
};

體會(huì)

遍歷一遍就OK，遇到偶數(shù)存到新鏈表后刪除，最后將兩個(gè)鏈表連接。
重點(diǎn)考察鏈表的delete和append！

LeetCode3 無(wú)重復(fù)字符的最長(zhǎng)子串

題目

給定一個(gè)字符串，找出不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
示例：
給定 "abcabcbb" ，沒(méi)有重復(fù)字符的最長(zhǎng)子串是 "abc" ，那么長(zhǎng)度就是3。
給定 "bbbbb" ，最長(zhǎng)的子串就是 "b" ，長(zhǎng)度是1。
給定 "pwwkew" ，最長(zhǎng)子串是 "wke" ，長(zhǎng)度是3。請(qǐng)注意答案必須是一個(gè)子串，"pwke" 是 子序列 而不是子串。

C++代碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> max_str;
        int start_index = 0;//用于記錄當(dāng)前字符串開(kāi)始的位置
        map<char,int>::iterator it;
        int max_length = 0;//記得初始化
        for(int i=0;i<s.length();i++)
        {
            it = max_str.find(s[i]);//查找現(xiàn)在map中是否有重復(fù)的字符
            if(it!=max_str.end()&&it->second>=start_index)//如果有重復(fù)的字符，且該字符下標(biāo)比當(dāng)前最長(zhǎng)字符串起始下標(biāo)大，則修改起始下標(biāo)。相當(dāng)于左指針右移動(dòng)。
            {
                start_index = it->second+1;//修改下標(biāo)
            }
            max_str[s[i]] = i;//將當(dāng)前的字符及下標(biāo)存入map
            max_length = max(i-start_index+1,max_length);//計(jì)算最大長(zhǎng)度
        }
        return max_length;
    }
};

體會(huì)

感謝STL
這道題的關(guān)鍵需要利用map
整個(gè)思路比較清晰
首先我們從頭開(kāi)始遍歷字符串
如果當(dāng)前字符沒(méi)有在map中出現(xiàn)過(guò)，那么就將當(dāng)前字符存入map，且不修改當(dāng)前子串的起始位置。
如果當(dāng)前字符在map中出現(xiàn)過(guò)，那么證明當(dāng)前子串中出現(xiàn)了相同的字母，此時(shí)修改子串起始位置為map中與當(dāng)前字符重復(fù)的字符的下標(biāo)。

舉例：
bacdb
i=0 s[i]=b it='/0' start_index = 0 max=1
i=1 s[i]=a it='/0' start_index = 0 max=2
i=2 s[i]=c it='/0' start_index = 0 max=3
i=3 s[i]=d it='/0' start_index = 0 max=4
i=4 s[i]=b it='b' start_index = 1 max=4
return max