为了春招开始刷leetcode。

之前学竞赛的时候更多注意的是在给定时限和空间限制下完成问题，一般也不会要求你原地完成xxx，卡nlogn，卡常数之类的。而且对于快排啊，堆之类的就直接调库了，很少自己写。此外，一些在竞赛中被归为【乱搞】并且很少出的题我也没有仔细总结过。但是在实际工程和面试中这些都是要遇到的，这时候我就发现自己很菜。于是在这里记录一下以前没有注意到的细节和想法。

next_permutation实现

next_permutation大家都很熟悉，但是其实现我没有深究过，今天绞尽脑汁，写了一坨，感觉非常不爽。最后看了别人的博客写出了以下简洁的代码：

    string next_per(string x) {
        int i=x.length()-1,j=i-1;
        while(i>0&&x[j]>=x[i])j--,i--; //确定变动的范围
        if(i<=0)return "";
        i=x.length()-1;
        while(x[i]<=x[j])i--;
        swap(x[i],x[j]);
        reverse(x.begin()+j+1,x.end());
        return x;
    }

上面这段的意思是这样的：

首先，我们要求一段字符串的下一个排列，那么我们肯定是动这个字符串结尾的一个子串。具体的说，我们会动【从末尾往前数，第一个不满足逆字典序排列】的子串。所以我们要首先确定变动的范围。只要找到两个相邻的字符，使得他们满足x[j-1]<x[j]就行（因为这样就顺字典序了，意味着可以找到下一个排列）。

然后，在变动的范围里，找到第一个比刚刚找到的那个x[j]字典序大的字符x[i]，也就是x[i]>x[j]（我们找到的这个x[i]会是比x[j]大的最小字符）。如果此时交换这两个字符，字典序大的就会跑到前面去，这时候变动的范围里会变成一个逆序排列的字符串。因为是找紧挨着的下一个排列，显然应该将逆序排列字符串变成字典顺序的字符串，所以reverse一下。

感觉这个只可意会，不可言传。（另外递归也可）

快排Partition

以前压代码压的太厉害，自己都不知道自己快排在写什么，这里重新理解了一下。

    int partition(vector<int>&arr,int l,int r) {
        int i=l,j=r,x=arr[l]; //找标杆 把标杆这里挖了个坑
        while(i<j) {
            while(x<=arr[j]&&i<j)j--; //从右往左找到第一个比标杆小的
            if(i<j) {
                arr[i]=arr[j]; //换到左边原来标杆的位置 j这里多了个坑
                i++;
            }
            while(x>=arr[i]&&i<j)i++; //从左往右找到第一个比标杆大的
            if(i<j) {
                arr[j]=arr[i]; //换到右边刚刚挖的坑里
                j--;
            }
        }
        arr[i]=x; //最后别忘了把标杆放到他应该在的位置
        return i;
    }

具体就是上面的注释了。

双指针法

以前把这种做法叫做乱搞，现在可以归到一类里面去了。具体就是你维护两个指针i,j。然后i是每个循环都正常走，j是一般不走，当你想要维护的区间[i,j]不符合条件时，j再向前走，让[i,j]重新满足条件，具体可以看一道题：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/ 统计优美字数组，具体就是要维护一个奇数数量为k的区间。代码不写了。

链表奇技淫巧

先前就听说过大步小步法搞链表，还没遇到过题。

今天见了一道题：两个链表相交，在交点后都完全重合，求交点 https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

最简单的做法就是搞两个指针h1,h2，一起走。当h1走到头时，切到第二个链表的开头。当h2走到头时，切到第一个链表的开头。这时候这俩再走，直到h1==h2，就是交点了。

左移(旋转)字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

实现很巧妙。你首先可以把字符串分为前后两部分，前半部分是要挪到后面去的，后面要挪到前面来。也就是字符串ab要变成ba。做法利用(a^tb^t)^t=ba。只要先reverse前面，再reverse后面，最后整体reverse即可。

一个常数优化

严格来说，这个是在我面试时遇到的。给你一个递增数组，可以有重复数字。要求找到a[i]=i的所有数字。O(N)扫一遍，要常数优化。

我只想了一个跳的做法，就是如果a[i]>i，那么可以直接跳到i这个位置。

向下取整转向上取整

x/y本身是向下取整的，如果想转向上取整应该这么写：(x + (y – 1)) / y