如何稳定地做个渣渣2

LC27. Remove Element

从一个数组里删除指定的数。。。随便就AC了，就不写了。。。骗傻子的题。

LC18. 4 Sum

与上一篇的2Sum和3Sum同类型，求所有相加等于0的四个数的组合。

思路一样的。先排序，然后夹逼。没什么坑，不细说了。

代码：

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

这道题一开始连题目都没看懂，然后当然就是谷歌啦，啊不对，百度，谷歌是啥？

全排列，就是一组数的所有排列组合。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的下一个排列就是132。如果当前排列是所有排列中的最后一种，则下一个排列返回到第一个排列，如：3,2,1 → 1,2,3。

理解了这个之后，算法思想并不难。先用人话写一下：

1. 从右向左，寻找第一个打破递增规律的数字，记做Partition。
2. 从右向左，寻找第一个大于分割数的数字，记做Change。
3. 调换Partition和Change。
4. 将调换后的Partition所在位置后面的数置为倒序。

算法很简单，但实现目前写不出来，这道题就当没做过，回头重做。

无关内容

去除连续空格：

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

两个函数：
bind1st(const Operation& op, const T& x)就是这么一个操作：x op value，而bind2nd(const Operation& op, const T& x)就是这么一个操作：value op x，其中value是被应用bind的对象。

---

好了，今天就学了这么一点，不能学太多，不然没法保持渣渣的水平了。