LC27. Remove Element

從一個(gè)數(shù)組里刪除指定的數(shù)。。。隨便就AC了，就不寫(xiě)了。。。騙傻子的題。

LC18. 4 Sum

與上一篇的2Sum和3Sum同類(lèi)型，求所有相加等于0的四個(gè)數(shù)的組合。

思路一樣的。先排序，然后夾逼。沒(méi)什么坑，不細(xì)說(shuō)了。

代碼：

class Solution {
public:
    vector<vector<int> > fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int> > result;
        if(nums.size() < 4)
            return result;
        sort(nums.begin(), nums.end());

        auto last = nums.end();
        for(auto a = nums.begin(); a < prev(last, 3); ++a)
        {
            for(auto b = next(a); b < prev(last, 2); ++b)
            {
                auto c = next(b);
                auto d = prev(last);

                while(c < d) //要始終保證c<d
                {
                    if( *a + *b + *c + *d < target)
                        ++c;
                    else if( *a + *b + *c + *d > target)
                        --d;
                    else
                    {
                        result.push_back({ *a, *b, *c, *d });
                        ++c;
                        --d;
                    }
                }
            }
        }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        return result;
    }
};

LC31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

這道題一開(kāi)始連題目都沒(méi)看懂，然后當(dāng)然就是谷歌啦，啊不對(duì)，百度，谷歌是啥？

全排列，就是一組數(shù)的所有排列組合。1,2,3的排列有：

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

比如例子里面的1,2,3 → 1,3,2，很顯然123的下一個(gè)排列就是132。如果當(dāng)前排列是所有排列中的最后一種，則下一個(gè)排列返回到第一個(gè)排列，如：3,2,1 → 1,2,3。

理解了這個(gè)之后，算法思想并不難。先用人話寫(xiě)一下：

1. 從右向左，尋找第一個(gè)打破遞增規(guī)律的數(shù)字，記做Partition。
2. 從右向左，尋找第一個(gè)大于分割數(shù)的數(shù)字，記做Change。
3. 調(diào)換Partition和Change。
4. 將調(diào)換后的Partition所在位置后面的數(shù)置為倒序。

算法很簡(jiǎn)單，但實(shí)現(xiàn)目前寫(xiě)不出來(lái)，這道題就當(dāng)沒(méi)做過(guò)，回頭重做。

無(wú)關(guān)內(nèi)容

去除連續(xù)空格：

// remove consecutive spaces
    std::string s = "wanna go    to      space?";
    auto end = std::unique(s.begin(), s.end(), [](char l, char r){
        return std::isspace(l) && std::isspace(r) && l == r;
    });

兩個(gè)函數(shù)：
bind1st(const Operation& op, const T& x)就是這么一個(gè)操作：x op value，而bind2nd(const Operation& op, const T& x)就是這么一個(gè)操作：value op x，其中value是被應(yīng)用bind的對(duì)象。

好了，今天就學(xué)了這么一點(diǎn)，不能學(xué)太多，不然沒(méi)法保持渣渣的水平了。