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

這是一篇筆記型Blog幽邓，主要存一下最近練的代碼的筆記仗谆。LeetCode的代碼，在云端裸准，復(fù)習(xí)起來麻煩，就這樣存下來审残。
目前的練習(xí)為LeetCode中級算法與每日模擬賽.
沒事刷一刷LeetCode還是可以提高一下基本的代碼能力的汤纸。

LeetCode15 三數(shù)之和

題目

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

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

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

滿足要求的三元組集合為：
[
  [-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;
    }
};

體會

此題直接窮舉一定爆時間
采用暴力+雙指針解法
首先對數(shù)據(jù)進(jìn)行排序。
第一次遍歷確定一個數(shù)字n荡陷，則剩下兩個數(shù)字的和必須是-n雨效，這樣才滿足條件。確定兩個指針i亲善、j设易，從左至右，從右至左依次遍歷蛹头。
單個指針遍歷的過程中，如果重復(fù)直接跳過戏溺，防止結(jié)果中出現(xiàn)重復(fù)的數(shù)字渣蜗。
如果sum為0時，得到答案旷祸，存儲在孝，繼續(xù)遍歷竹宋。
如果sum小于0，則證明當(dāng)前情況的左指針小了没龙，左指針++。
如果sum大于0肢执，則證明當(dāng)前情況的右指針大了，右指針--。

此題嘗試了二重暴力+二分既峡，時間沒問題，但是結(jié)果總出錯碧查，不知道為什么运敢。

LeetCode73 矩陣置零

題目

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

樣例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 ;
    }
};

體會

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

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

LeetCode49 字謎分組

題目

給定一個字符串?dāng)?shù)組宁昭，將字母異位詞組合在一起跌宛。字母異位詞指字母相同，但排列不同的字符串积仗。

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

說明：

所有輸入均為小寫字母疆拘。
不考慮答案輸出的順序。

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;
    }
};

體會

題目邏輯很清晰
自己手動實(shí)現(xiàn)了一個算法寂曹，但是最后一組數(shù)據(jù)沒有過鞍テ！Ｂ≡病漱挚！難受！Ｃ煅酢旨涝！等一下附上代碼。
這個題目的思路很清晰侣背，利用Map白华，將每次排序過的字符串作為Key慨默，將剩下的字符串作為Val存放進(jìn)去，最后整體存放在一個二維Vector里面就可以了弧腥。

附一下差一組數(shù)據(jù)沒過的代碼

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 顏色排序

題目

給定一個包含紅色厦取、白色和藍(lán)色，一共 n 個元素的數(shù)組鸟赫，原地對它們進(jìn)行排序蒜胖，使得相同顏色的元素相鄰，并按照紅色抛蚤、白色台谢、藍(lán)色順序排列。
此題中岁经，我們使用整數(shù) 0朋沮、 1 和 2 分別表示紅色、白色和藍(lán)色缀壤。
注意:
不能使用代碼庫中的排序函數(shù)來解決這道題樊拓。
示例:

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

進(jìn)階：
一個直觀的解決方案是使用計數(shù)排序的兩趟掃描算法。
首先塘慕，迭代計算出0筋夏、1 和 2 元素的個數(shù)，然后按照0图呢、1条篷、2的排序，重寫當(dāng)前數(shù)組蛤织。
你能想出一個僅使用常數(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);
    }
};

體會

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

LeetCode347 Top K Frequent Elements

題目

給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素指蚜。
例如乞巧，
給定數(shù)組 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]摊鸡。
注意：
你可以假設(shè)給定的 k 總是合理的绽媒，1 ≤ k ≤ 數(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;
    }
};

體會

一道說難不難些椒，說簡單不簡單的題。
熟練使用stl很重要掸刊。
這道題利用到了map通過val排序的方法，將map轉(zhuǎn)化成vector<pair<int,int>>的方法需要掌握赢乓，注意自己要寫sort函數(shù)忧侧，sort函數(shù)一定是全局變量或者是static類型石窑。

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

題目

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

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

示例 2:

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

說明:
你可以假設(shè) k 總是有效的肯夏，且 1 ≤ k ≤ 數(shù)組的長度经宏。

C++代碼

class Solution {
public:
int partition(vector<int>&nums, int low, int high)//找樞紐
{
    int first = low;
    int last = high;
    int key = nums[first];//用字表的第一個記錄作為樞軸
    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;//返回一個樞紐
}
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) //計算后面一段的長度，如果等于k表示找到了第k大
        return nums[index];
    else if(length > k)//如果后面的一段的長度大于k驯击，證明第k大的數(shù)在后面一段
        return find_k(nums,index+1,r,k);
    else if(length <k)//如果后面的一段的長度小于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);
    }
};

體會

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

LeetCode425 電話號碼的字母組合

題目

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

示例:

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

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

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ù)組對應(yīng)位置的每個字母都放進(jìn)字符串。
            letterCombinationsSearch(digits,str,index+1,res);//遞歸洪唐，尋找下一個字母钻蹬。
            str.pop_back();//ad找完之后，彈出d凭需，準(zhǔn)備放入e
        }
    }
};

體會

整個問題就是一個dfs+回溯问欠。
舉個例子，比如“234”粒蜈，先一口氣找到adg顺献，然后彈出g，找到adh枯怖，彈出h注整，找到adi，彈出i，彈出d肿轨，找到aeg寿冕，以此類推。

LeetCode46 全排列

題目

給定一個沒有重復(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]);//存入一個沒有用過的數(shù)字
                used[i]=true;//用過的數(shù)字標(biāo)記為true
                permute_search(nums,used,tmp,res);
                tmp.pop_back();//彈出剛剛用過的數(shù)字
                used[i]=false;//將所對應(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;
    }
};

體會

一道非常簡單dfs+回溯題目，創(chuàng)建一個used數(shù)組用來存儲當(dāng)前每個數(shù)字的使用狀態(tài)驹暑。核心部分都寫了注釋玫恳，這里就不贅述了。

LeetCode78 子集

題目

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums优俘，返回該數(shù)組所有可能的子集（冪集）京办。
說明：解集不能包含重復(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ù)字
            res.push_back(tmp);//將臨時數(shù)組放入答案數(shù)組中
            subsets_search(nums,tmp,i+1,res);//遞歸調(diào)用兼吓，注意這里是i+1臂港，不是index+1，因?yàn)槭褂胕ndex會出現(xiàn)1 3已被放入视搏，index=2审孽，遞歸index=3，將3也放入tmp浑娜，這樣會出現(xiàn)1 3 3 的情況佑力。
            tmp.pop_back();//將臨時數(shù)組減少一個數(shù)字，用于回溯
        }
    }

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

};

體會

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

LeetCode202 快樂數(shù)

題目

編寫一個算法來判斷一個數(shù)是不是“快樂數(shù)”秽誊。
一個“快樂數(shù)”定義為：對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和琳骡，然后重復(fù)這個過程直到這個數(shù)變?yōu)?1锅论，也可能是無限循環(huán)但始終變不到 1。如果可以變?yōu)?1楣号，那么這個數(shù)就是快樂數(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;
        }
    }
};

體會

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

LeetCode172 階乘后的零

題目

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

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

示例 2:

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

說明: 你算法的時間復(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;
    }
};

體會

技巧題什往！
關(guān)鍵在于5的數(shù)量了那么該問題的實(shí)質(zhì)是要求出1~100含有多少個5由特殊推廣到一般的論證過程可得：
1扳缕、 每隔5個，會產(chǎn)生一個0别威，比如 5躯舔， 10 ，15省古，20...
2 粥庄、每隔 5×5 個會多產(chǎn)生出一個0，比如 25豺妓，50惜互，75，100
3 琳拭、每隔 5×5×5 會多出一個0训堆，比如125.

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

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

LeetCode50 Pow(x, n)

題目

實(shí)現(xiàn) pow(x, n) 盟蚣，即計算 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
說明:
-100.0 < x < 100.0
n 是 32 位有符號整數(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;
    }
};

體會

技巧題阐枣！
這里解釋一下代碼
比如我們計算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 中序遍歷二叉樹

題目

給定一個二叉樹，返回它的中序 遍歷。
示例:

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

輸出: [1,3,2]

進(jìn)階: 遞歸算法很簡單蔼两，你可以通過迭代算法完成嗎甩鳄？

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é)果存儲在tmp中额划，用一個循環(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)俊戳，此時curr==null
                current = s.top()->right;//修改current為當(dāng)前棧頂元素的右節(jié)點(diǎn)揖赴，
                s.pop();//彈出當(dāng)前棧頂元素
            }
        }
        return res;
    }
};

體會

難度不高
中序遍歷，如果不考慮安全性的話抑胎，幾句話就可以寫完呢燥滑。
使用棧的方法可以大大提升效率，建議使用阿逃。

LeetCode55 跳躍游戲

題目

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

示例 1:

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

示例 2:

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

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++) //遍歷每一個位置
        {
            for(int j=1;j<=nums[i];j++)//計算當(dāng)前位置每種可能跳的情況
            {
                if(dp[i]) dp[i+j]=true;//如果當(dāng)前位置能跳到澎嚣，下一個位置才能
            }
        }
        return dp[nums.size()-1];
    }
};

體會

emmmmm，很迷瘟芝，這個也算是DP易桃？？锌俱？
不過細(xì)想晤郑，也算是劃分子問題了。
很簡單
二重循環(huán)贸宏，都遍歷一遍造寝，然后計算每一個可以到達(dá)的路徑。重點(diǎn)在于if(dp[i]) dp[i+j]=true吭练，只有當(dāng)前位置能夠到達(dá)诫龙，當(dāng)前位置的下一個位置才能到。

LeetCode62 不同路徑

題目

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

示例 1:

輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始歹嘹，總共有 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];
    }
};

體會

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

LeetCode322 零錢兌換

題目

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)史飞。如果沒有任何一種硬幣組合能組成總金額尖昏，返回 -1。

示例 1:

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

示例 2:

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

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

C++代碼

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int min=99999999999;
        int dp[100000];
        
        //過濾一下特別大的數(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]時，coins[i]所對應(yīng)的價值至少有一個硬幣可以構(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];
    }
};

體會

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

LeetCode300 Longest Increasing Subsequence

題目

給定一個無序的整數(shù)數(shù)組吐绵，找到其中最長上升子序列的長度。
示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4 
解釋: 最長的上升子序列是 [2,3,7,101]河绽，它的長度是 4己单。

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

C++代碼

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int dp[10000];//每一個上升子序列的長度至少是1
        int res=1;
        for(int i=0;i<nums.size();i++)
            dp[i] = 1;
        for(int i=0;i<nums.size();i++) //遍歷所有的長度
        {
            for(int j=0;j<i;j++)//模擬添加逐個數(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;
    }
};

體會

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

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

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

LeetCode2 兩數(shù)相加

題目

給定兩個非空鏈表來表示兩個非負(fù)整數(shù)趟咆。位數(shù)按照逆序方式存儲添瓷，它們的每個節(jié)點(diǎn)只存儲單個數(shù)字。將兩數(shù)相加返回一個新的鏈表值纱。
你可以假設(shè)除了數(shù)字 0 之外鳞贷，這兩個數(shù)字都不會以零開頭。
示例：

輸入：(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;//用于存儲進(jìn)位
        bool l1_finish=false;//用于判斷第一個鏈表是否走完
        bool l2_finish=false;//用于判斷第二個鏈表是否走完
        while(1)
        {
            int val_tmp;//臨時存一下
            //三種情況虐唠，同時加兩個搀愧，只加一個，記得每次加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;//存儲進(jìn)位
            ListNode *new_node = new ListNode(val_tmp%10);//生成一個新的節(jié)點(diǎn)
            curr->next = new_node;//append節(jié)點(diǎn)
            curr = curr->next;//移動游標(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)疆偿，注意分情況討論有無進(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是空哦咱筛，返回下一個值
    }
};

體會

的確是簡單題，直接模擬杆故！
但我寫的好復(fù)雜把嘎帷！４︻酢饲趋！
應(yīng)該是沒寫好，以后再改吧撤蟆。
注意[5],[5]奕塑、[1,8],[0]這樣的數(shù)據(jù)，有詐家肯！

LeetCode328 奇偶鏈表

題目

給定一個單鏈表龄砰，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請注意讨衣，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號的奇偶性换棚，而不是節(jié)點(diǎn)的值的奇偶性。
請嘗試使用原地算法完成值依。你的算法的空間復(fù)雜度應(yīng)為 O(1)圃泡，時間復(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

說明:
應(yīng)當(dāng)保持奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對順序颇蜡。
鏈表的第一個節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)，第二個節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)辆亏，以此類推风秤。

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;//指針移動到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;
    }
};

體會

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

LeetCode3 無重復(fù)字符的最長子串

題目

給定一個字符串，找出不含有重復(fù)字符的最長子串的長度累提。
示例：
給定 "abcabcbb" 尘喝，沒有重復(fù)字符的最長子串是 "abc" ，那么長度就是3斋陪。
給定 "bbbbb" 朽褪，最長的子串就是 "b" ，長度是1无虚。
給定 "pwwkew" 缔赠，最長子串是 "wke" ，長度是3友题。請注意答案必須是一個子串嗤堰，"pwke" 是 子序列 而不是子串。

C++代碼

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> max_str;
        int start_index = 0;//用于記錄當(dāng)前字符串開始的位置
        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)前最長字符串起始下標(biāo)大梁棠，則修改起始下標(biāo)。相當(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);//計算最大長度
        }
        return max_length;
    }
};

體會

感謝STL
這道題的關(guān)鍵需要利用map
整個思路比較清晰
首先我們從頭開始遍歷字符串
如果當(dāng)前字符沒有在map中出現(xiàn)過，那么就將當(dāng)前字符存入map凫海，且不修改當(dāng)前子串的起始位置呛凶。
如果當(dāng)前字符在map中出現(xiàn)過，那么證明當(dāng)前子串中出現(xiàn)了相同的字母行贪，此時修改子串起始位置為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