LeetCode：STL中实用函数（一）

这篇博客主要是记录一下我在刷LeetCode时，使用STL快速解题的学习笔记。熟练使用STL能避免重复造轮子，加快解题的速度。

移除重复元素 std::unique()

移除重复元素，这是经常会碰到的一个情况。任务比较简单，这里就介绍使用STL函数来解决这问题。这里需要使用的函数是：std::unique。
功能：将第一次出现的元素从前往后排，其他重复出现的元素依次排在后面
返回值：返回迭代器，迭代器指向的是重复元素的首地址。
如下图示：

看例子

vector<int>nums{6,8,7,7,7,6,6, 2, 2, 1, 1, 2,3, 3, 3, 4, 4, 5 };//未排序的情况下
auto re_nums1 = unique(nums.begin(), nums.end());//vector<int>::iterator 
vector<int>res1(nums.begin(), re_nums1);// res={6 8 7 6 2 1 2 3 4 5}，只是将重复的相邻元素移到后面去了,没有实现去重
sort(nums.begin(), nums.end());//对nums排序
auto re_nums2 = unique(nums.begin(), nums.end());
vector<int>res2(nums.begin(), re_nums2);//res2={1,2,3,4,5,6,7,8}，真正实现了去重

例题、移除重复元素 LeetCode 26

给定已排序数组nums，原地（即不申请额外空间）移除重复元素，保证移除后的每个元素只出现一次，返回移除后数组的长度。例如nums=[1,1,2],返回长度为2，此时nums=[1,2]。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto x_iter=unique(nums.begin(),nums.end());
        nums.erase(x_iter,nums.end());
        return nums.size();
    }
};

例题、移除重复元素 LeetCode 80

题目的要求也是移除重复元素，每个元素最多出现2次。例如nums=[1,1,1,2,2,3,3,3],则移除重复元素之后的nums=[1,1,2,2,3,3]，返回移除后nums的长度是6。这里做些修改，将最多出现的次数换成一个变量size。分析一下这道题，由于是已经排序过的，因此只需要设置一个变量，要保证nums[index]!=nums[index-size]即可。

class Solution {
public:
    int helper(vector<int>& nums,int size=2)
    {
        if(nums.size()<=size)return nums.size();
        int idex=size;
        for(int i=size;i<nums.size();i++)
        {
            if(nums[i]!=nums[idex-size])
                nums[idex++]=nums[i];
        }
        return idex;
    }
    int removeDuplicates(vector<int>& nums) {
        return helper(nums,2);
    }
};

删除特定元素 std::remove()

这也是STL中的操作函数。这里主要是说明一下remove函数，在STL中，remove只是将待删除的元素移到vector后面去了，但并没有删除该元素。和上面的std::unique函数是一样的。remove返回的位置和上面的std::unique函数也是一样的。如果要移除元素的话，需要配合vector中的erase函数同时使用。如下面的例子。

vector<int>nums{ 2,2,2,3,0, 1, 2,4, 2, 3, 0, 4, 2 };
auto x = std::remove(nums.begin(), nums.end(),2);
nums.erase( x,nums.end());
//删除后nums=[3,0,1,4,5,0,4]

例题、移除元素 LeetCode 27

给定一个数组nums和一个值val，删除nums中所有的val值。例如nums = [0,1,2,2,3,0,4,2], val = 2,返回值为5，删除元素val后，nums=[0,1,3,0,4]

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        auto x=std::remove(nums.begin(),nums.end(),val);
        nums.erase(x,nums.end());
        return nums.size();
    }
};

元素查找或元素出现次数 std::count()

函数功能如标题。下面就举一个LeetCode上的例子。

例题、旋转排序数组查找 LeetCode 81

题目意思是假设一个升序的排序数组，在某个节点处进行了旋转，比如nums=[0,0,1,2,2,5,6],旋转之后为[2,5,6,0,0,1,2]。给定一个target，查找target是否存在。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        return std::count(nums.begin(),nums.end(),target)>0? true:false;
    }
};

哈希表map和unordered_map

在c++11标准前，c++标准库中只有一种map，但是它的底层实现并不是适合所有的场景。map底层是使用红黑树实现的，查询时间复杂度为$O(logn)$。由于STL中的map因为是有序的二叉树存储，所以对key值需要有大小的判断，因此存储的数据是有序的。在c++11标准中添加了unordered_map，unordered_map底层才是使用哈希表实现的，查询时间复杂度为$O(1)$，存储的数据是散列的，全程使用无需比较元素的key值大小，因此存储的数据是无序的。下面来看个例子。

//test.cpp
#include<iostream>
#include<map>
#include<string>
#include<unordered_map>
using namespace std;
int main()
{
	map<string, int>person;
	person.insert(pair<string, int>("cici", 22));
	person.insert(pair<string, int>("alien", 20));
	person.insert(pair<string, int>("bob", 21));
	person.insert(pair<string, int>("kenni", 24));
	person.insert(pair<string, int>("alex", 19));
	cout << "*******map*******" << endl;
	for (auto iter = person.begin(); iter != person.end(); iter++)
		cout << iter->first << "-" << iter->second << endl;
	cout << "*******unordered_map*******" << endl;
	unordered_map<string, int>person2;
	person2.insert(pair<string, int>("cici", 22));
	person2.insert(pair<string, int>("alien", 20));
	person2.insert(pair<string, int>("bob", 21));
	person2.insert(pair<string, int>("kenni", 24));
	person2.insert(pair<string, int>("alex", 19));
	for (auto iter = person2.begin(); iter != person2.end(); iter++)
		cout << iter->first << "-" << iter->second << endl;
	return 0;
}
使用命令编译：g++ test.cpp -o test -std=c++11 
执行可执行文件：./test
结果如下：
*******map*******
alex-19
alien-20
bob-21
cici-22
kenni-24
*******unordered_map*******
alex-19
cici-22
bob-21
alien-20
kenni-24

可以看出map的数据存储根据key值进行了排序操作，而unordered_map没有排序。下面就举一个LeetCode上难度为hard的题目，使用哈希表来做。

例题、最长连续序列 LeetCode 128

给定一个无序整型数组，寻找最长连续元素序列的长度。

Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

如果允许$O(nlogn)$的时间复杂度，那么可以先排序，不过本题要求的是$O(n)$。由于序列中元素时无序的，又要求$O(n)$，首先想到使用哈希表。用一个哈希表记录每个元素是否被使用，对每个元素，以该元素为中心，网左右扩展，直到不连续为止。记录下最长的长度。时间复杂度为$O(n)$，空间复杂度为$O(n)$。

class Solution {
public:
   int longestConsecutive(vector<int>& nums) {
	unordered_map<int, bool>used;//记录元素是否被使用
	for (auto i : nums) used[i] = false;
	int longest = 0;
	for (auto i : nums)
	{
		if (used[i])continue;
		used[i] = true;
		int len = 1;
		for (int j = i + 1; used.find(j) != used.end(); j++)
		{
			used[j] = true;
			++len;
		}
			
		for (int j = i - 1; used.find(j) != used.end(); --j) {
			used[j] = true;
			++len;
		}
		longest = max(longest, len);
	}
	return longest;
}
};

例题、Two Sum LeetCode 1

给定整型数组，寻找两个数，使得这两个数相加等于target，返回两个数的下标。

Example
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

如果直接使用暴力求解的话，方法一，复杂度为$O(n^2)$，会超时；方法二，先排序，后左右夹逼，排序$O(nlogn)$，左右夹逼$O(n)$,最终还是$O(nlogn)$，但此时只能返回两个数，无法返回下标；方法三，使用哈希表，存储每个数的小标，复杂度为$O(n)$。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>res;
        unordered_map<int,int>index_map;
        for(int i=0;i<nums.size();i++)
            index_map[nums[i]]=i;
        for(int i=0;i<nums.size();i++)
        {
            int gap=target-nums[i];
            if(index_map.find(gap)!=index_map.end()&&index_map[gap]!=i)
            {
                res.push_back(i);
                res.push_back(index_map[gap]);
                break;
            }
        }
         return res;   
    }
};

全排列

这里要介绍STL中关于全排列相关的两个函数prev_permutation()以及next_permutation()。先介绍一下这两个函数的功能作用。包含的头文件是algorithm。前者是求出下一个排列组合，而后者是求出上一个排列组合。举了一个简单的例子：
对序列 {a, b, c}，每一个元素都比后面的小，按照字典序列，固定a之后，a比bc都小，c比b大，它的下一个序列即为{a, c, b}，而{a, c, b}的上一个序列即为{a, b, c}，同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，其中{a, b, c}上一个元素就是{c, b, a}，{c, b, a}下一个元素就是{a，b，c}。

#include <string>
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	string str;
	cout << "input:" << endl;
	getline(cin, str);
	//sort(str.begin(), str.end());//可以自行测试一下删除后的结果
	cout << "permutation:" << endl;
	do 
	{
		cout << str << endl;
	} while (next_permutation(str.begin(),str.end()));

	return 0;
}

输出结果如下：
如果有sort话，

input:
102
permutation:
012 021 102 120 201 210

如果无sort的话，

input:
102
permutation:
102 120 201 210

可以发现少了几种组合。不过，仔细比较各种组合方法和有无sort()的输出，可以发现函数next_permutation()是按照字典序产生排列的，并且是从数组中当前的字典序开始依次增大直至到最大字典序。这里也列举一个LeetCode上相关的题目。

例题、下一个排列 LeetCode 31

给定一个数组和一个排列，求下一个排列。例如

• 1,2,3—>1,3,2
• 3,2,1—>1,2,3
• 1,1,5—>1,5,1
  下面我们先看一下使用普通方法，该怎么做这道题。如下图示，图片来源在这里。
  
  求当前序列的下一个全排列的具体做法是：
  （1）先从右到左，找出第一个不是严格递增的数字PartitionNum,这里是数字6;
  （2）接着同样也是从右到左，找出第一个大于数字6的数字ChangeNum，这里是数字7;
  （3）交换PartitionNum和ChangeNum；
  （4）将PartitionNum数字对应序号后面的全都反转一遍，结束。
  上面最坏的情况下，需要遍历数组三次，所以时间复杂度是$O(3*n)=O(n)$。
  具体代码实现如下（解法一）：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
       if(nums.size()<=1)return;
        int nextIndex=nums.size()-2;
        while(nextIndex>=0&&nums[nextIndex]>=nums[nextIndex+1])
            nextIndex--;
        if(nextIndex>=0){
        int changeIndex=nums.size()-1;
        while(nextIndex<changeIndex&&nums[changeIndex]<=nums[nextIndex])
            changeIndex--;
        swap(nums[nextIndex],nums[changeIndex]);
        }
        reverse(nums.begin()+nextIndex+1,nums.end());
    }
};

这里我们直接使用STL中的next_permutation函数来做。具体代码实现如下（方法二）：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        std::next_permutation(nums.begin(), nums.end());
        return;
    }
};

与此类似的题还有 序列排序 LeetCode 60。题目如下：

这道题必须得提及一下，因为这道题和2019年网易计算机视觉算法工程师的一道笔试题特别像。题目如下图所示所示

都是求第k个排列，只不过网易这道题将输入换成了有重复的字母。先说一下上面那道LeetCode题。求第k个排列，比较直接暴力的求法就是调用k-1次next_permutation函数就能得到。不过这个肯定不是时间最优的，不过是最快的，而且也是代码最简洁的。代码如下：

class Solution {
public:
    string getPermutation(int n, int k) {
        string s(n,'0');
        for(int i=0;i<n;i++)
            s[i]+=i+1;
        for(int i=0;i<k-1;i++)
            next_permutation(s.begin(),s.end());
        return s;
    }
};

由于这道题分析展开比较长，因此这道题的最优解法放在下一篇博客讲。这里先记录这些STL中常用的函数，下一篇博客会接着介绍一些其他的函数。