algorithm库函数

1.reverse 翻转

(a.begin(),a.end()) reverse(a,a+n)

举个栗子

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector<int>a({1,2,3,4,5});
    reverse(a.begin(),a.end());
    for(auto x:a) cout << x <<' ';
    return 0;
}

2.unique 去重

需要保证相同元素在一起才行，个人建议先sort
m=unique(begin,end)-begin //m为不重复的个数
或者a.erase(unique(begin,end),end)
举个栗子

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector<int>a({1,2,2,3,3,4,4,4});//vector赋初值时不要等号
    int m=unique(a.begin(),a.end())-a.begin();
    cout << m <<endl;
    for(int i=0;i<m;i++) cout << a[i]<<' ';
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector<int>a({1,2,2,3,3,4,4,4});//vector赋初值时不要等号
    a.erase(unique(a.begin(),a.end()),a.end());
    for(auto x:a) cout << x <<' ';
    return 0;
}

3.random_shuffle 随机打乱

用法同reverse
注：可通过更改随机种子，让随机数变得不同

include <ctime>
scand(time(0));

4.sort 排序

默认从小到大排序
如果需要从大到小排序，那么可以加个greater<int>() 或者自写cmp函数
举个栗子

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    vector<int>a({1,3,2,5,2});
    sort(a.begin(),a.end(),greater<int>());
    for(auto x:a) cout << x <<' ';
    return 0;
}

给结构体排序：

1.重载小于号

struct Rec
{
    int x,y;
    bool operator<(const Rec &t)const
    {
        return x<t.x;//t是什么?例如a[0]与a[1]比较,t就是a[1]
    }a[N];
}

2.cmp函数

bool cmp(Rec a, Rec b)
{
    return a.x < b.x;
}

5.lower_bound/upper_bound 二分，区别在于后者无等于

int *p=lower_bound(begin,end,a);//*p为大于等于a的第一个元素
int t=lower_bound(begin,end,a)-begin;//*p为大于等于a的第一个元素的下标

其它注意：queue不能随机遍历

最后：视频中的部分例题

68. 0到n-1中缺失的数字

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        unordered_set<int> S;
        //将所有可能的数字都放进哈希表
        for(int i=0;i<=nums.size();i++) S.insert(i);
        //将已有的删掉，剩下的那个数字就是需要补充的
        for(auto x:nums) S.erase(x);
        return *S.begin();
    }
};

32. 调整数组顺序使奇数位于偶数前面

class Solution {
public:
    void reOrderArray(vector<int> &array) {
/*思路：让i指针遍历的都为奇数，j指针遍历的都为偶数
i:若为奇数那么就一直往后走;j:若为偶数那么就一直往前走
当两个奇数都不能走的时候就说明i指向偶数，j指向奇数，此时交换两个指针
这个过程一直到i与j相遇或者错开时停下
*/
        int i = 0, j = array.size() - 1;
        while(i < j)
        {
            while(i < j && array[i] % 2) i++;
            while(i < j && array[j] % 2 == 0) j--;
            if(i < j) swap(array[i], array[j]);
        }
    }
};

17. 从尾到头打印链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int>res;
        for(auto p = head; p; p = p->next) res.push_back(p->val);
        reverse(res.begin(), res.end());
        return res;
    }
};

20. 用两个栈实现队列

/*例如搬书，自己手上有几十本书，需要将最底下那本抽出来。
于是，我们可以找个工具人，将除了最底下的那本都一本一本甩给他。
最后抽出那本书后，再让他把他手上的书按顺序给我。
*/
class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> s1, s2;

    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while(s1.size()>1) s2.push(s1.top()),s1.pop();//把书都甩给工具人，自己只拿一本书
        int t = s1.top();
        s1.pop();
        while(s2.size()) s1.push(s2.top()),s2.pop();//那本书被取出来了，让工具人把书还给我，不需要他了，赶他下线
        return t;
    }

    /** Get the front element. */
    int peek() {
        while(s1.size()>1) s2.push(s1.top()),s1.pop();//把书都甩给工具人，自己只拿一本书
        int t = s1.top();
        while(s2.size()) s1.push(s2.top()),s2.pop();//那本书被取出来了，让工具人把书还给我，不需要他了，赶他下线
        return t;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */

53. 最小的k个数

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        sort(input.begin(), input.end());
        vector<int>res;
        for (int i = 0; i < k; i ++ ) res.push_back(input[i]);
        return res;
    }
};

75. 和为S的两个数字

/*在哈希表查看有没有可以凑成一对的那个数字*/
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int>S;
        for(auto x:nums)
        {
            if(S.count(target-x)) return {x,target-x};//用count函数
            S.insert(x);
        }
    }
};

51. 数字排列

class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {
        //先排序之后才能使用next_permutation(begin,end)
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        do{
            res.push_back(nums);
        }while(next_permutation(nums.begin(),nums.end()));
        return res;
    }
};

26. 二进制中1的个数

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++)
            if (n >> i & 1)
                res++;
    return res;
    }
};

862. 三元组排序

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
struct Data
{
  int x;
  double y;
  string z;

  bool operator< (const Data &t) const
  {
      return x < t.x;
  }
}a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i].x >>a[i].y >> a[i].z;
    sort(a, a+n);
    //printf输出字符串需要加.c_str())
    for (int i = 0; i < n; i ++ ) printf("%d %.2lf %s\n",a[i].x,a[i].y,a[i].z.c_str());
    return 0;
}