LeetCode：STL中实用函数（二）

发表于 | 分类于

这篇博客接着上一篇博客，继续记录的是关于STL的一些使实用操作函数。

全排列

全排列这部分还是接着上面博客的最后一道题讲。

例题、LeetCode 60 Permutation Sequence

给定n和k，返回第k个序列排列，n的取值为1到9之间。总共有(n)!中排列。同样通过举例分析比较容易理解。
思路：假设n=4,k=17，这时所有的排列如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1234
1243
1324
1342
1423
1432
2134
2143
2314 
2341
2413
2431
3124
3142
3214
3241
3412	<--- k = 17
3421
4123
4132
4213
4231
4312
4321

那么下面我们来看k = 17这种情况的每位数字如何确定，由于k = 17是转化为数组下标为16：
（1）最高位可取1,2,3,4中的一个，每个数字出现(4-1)！= 6次，所以k=16的第一位数字的下标为16 / (4-1)！ = 2，即3被取出，此时k1=k%(4-1)！=4;
（2）第二位此时从1,2,4中取一个，每个数字出现(3-1)!=2次，所以k=16的第二位数字的下标为k1/(3-1)!=2，即4被取出，此时k2=k1%(3-1)!=0；
（3）第三位此时从1,2中取出一个，每个数字出现(2-1)!=1次，所以k=16的第三位数字的下标为k2/(2-1)!=0,即1被取出，此时k3=k2%(2-1)!=0;
（4）剩下的数字只有2，即最后一位就是2。
假设有n和不重复的元素，第k个排列是$a_1a_2a_3…a_n$，那么总结规律如下：
$a_1=k/(n-1)!,k1=k\%(n-1)!$
$a_2=k1/(n-2)!,k2=k1\%(n-2)!$
$…$
$a_n=kn-1/0!$
需要注意几点的问题是，构造排列数从最高位开始，当选出一个数字后，就应当把这个数字erase掉，防止后面又出现。上面讲的很复杂，其实代码实现非常简单，参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        string num = "123456789";
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
        --k;
        for (int i = n; i >= 1; --i) {
            int j = k / f[i - 1];
            k %= f[i - 1];
            res.push_back(num[j]);
            num.erase(num.begin()+j);
        }
        return res;
    }
};

例题、LeetCode 46 permutations

给定一个无重复元素的数组，输出数组的全排列。

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

这道题比较简单。可以直接使用STL中的next_permutation函数就能得到。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> orig = nums;
        vector<vector<int> > result;
        do{
            result.push_back(nums);
            next_permutation(nums.begin(),nums.end());
        }while(orig!=nums);
        return result;
    }
};

例题、LeetCode 47 permutations

和LeetCode 46 一样，也是求数组的全排列，只不过，题目要求是数组中元素可能存在重复元素。

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

这道题使用上面同样的方法就可以得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
     vector<int> orig = nums;
        vector<vector<int> > result;
        do{
            result.push_back(nums);
            next_permutation(nums.begin(),nums.end());
        }while(orig!=nums);
        
        return result;
    }
};

是不是感觉和上面的代码一模一样啊，哈哈。可能有人在想你这是直接调用了STL中的next_premutations,有本事别用STL啊。“没有条件，那就创造条件”，实现出一个和STL一样功能的函数就行了。next_premutation函数的返回值是bool类型的。我们只需要将上一篇博客实现的NextPermutations稍微修改一下就行了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool nextPermutation(vector<int>& nums) {
    if(nums.size()<=1)return false;
    int nextIndex=nums.size()-2;
    bool flag=false;
    while(nextIndex>=0&&nums[nextIndex]>=nums[nextIndex+1])
        nextIndex--;
    if(nextIndex>=0){
        flag=true;
    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());
    return flag;
    }

关于数组或字符串全排列的题目就这么多，只要熟悉了STL中全排列函数的调用都不是问题。

STL二分查找

在STL中关于二分查找相关的函数有三个：lower_bound，upper_bound，binary_search。这三个函数都是表示在first和last中的前闭后开区间进行二分查找。

  • lower_bound(first,last,val)：在已排序区间[first,last）内查找第一个大于或等于val的元素的位置。如果所有元素都小于val,则返回last的位置，且last位置是越界的。
  • upper_bound(first,last,val)：在已排序区间[first,last）内查找第一个大于val的元素的位置。如果所有元素都小于val,则返回last的位置，且last位置是越界的。
  • binary_search(first,last,val)：试图在已排序的区间[first,last)中寻找元素val,若存在，则返回true,若不存在，则返回false。返回单纯的布尔值或许不能满足要求，因此需要使用上面两个函数提供额外的信息。

上面三个函数的时间复杂度都是$O(log(last-first))$,下面用这个例子解释上面两个函数比较容易理解。

此外，如果碰到不允许使用上面两个函数的情况下，该如何实现那两个函数呢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int upper_bound(int l, int r, int val)
{
	while (l<r)
	{
		int mid = (l + r) >> 2;
		if (a[mid] > val)r = mid;
		else
			l = mid + 1;
	}
	return l;
}

int lower_bound(int l,int r,int x)
{  while(l<r){
	int mid = (l + r) >> 2;
	if(a[mid]>=x)r=mid;
	else l=mid+1;
}
return l;
}

例题、LeetCode 34 Find First and Last Position of Element in Sorted Array

给定一个已排序数组，寻找给定值target在数组中的起始位置和终止位置。如果没找到返回[-1,-1]，算法时间复杂度要求为$O(log n)$。
分析：已经排好序了，而且时间复杂度已经给出，毫无疑问肯定得使用二分查找的方法。下面就使用上面介绍的函数来实现。

1
2
3
4
5
6
7
8
Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> searchRange(vector<int>& nums, int target) {
	if (!nums.size())
		return{ -1, -1 };
	auto x = lower_bound(nums.begin(), nums.end(), target);
	if (x == nums.end())
		return{ -1, -1 };
	int l = distance(nums.begin(), x);
	auto y = upper_bound(nums.begin(), nums.end(), target);
	int r = distance(nums.begin(), prev(y));
	if (nums[l] != target)//not found
		return{ -1, -1 };
	else
		return{ l, r };

}

LeetCode 35 Search Insert Position

给定一个已排序数组和给定值target,如果给定值在数组中则返回数组中位置，如果没有，返回在数组中顺序插入给定值得位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

这道题比上一道题还要简单一点，直接使用lower_bound就能得到结果。代码如下：

1
2
3
int searchInsert(vector<int>& nums, int target) {
        return distance(nums.begin(),lower_bound(nums.begin(),nums.end(),target));
    }

加速C++输入输出流

在刷题时，输入输出，我们往往倾向于使用cin,cout来输入输出。对于复杂的输入时，使用cin相比scanf速度要更慢很多，这是因为cin会把需要输入/输出的东西先写入缓存中，再输出，导致效率降低。使用如下语句就能打消iostream的输入输出缓存，节省很多时间。不过实际上使用了using namespace std后面就可以添加如下代码了。

1
2
3
4
5
static const auto speedup = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

下面举个相关的LeetCode题目去感受一下其加速效果。

例题、LeetCode 36 Valid Sudoku

给定一个99的表格。。如下表格所示。判断这个表格是否是一个数独表格

判定规则：
（1）每行必须包含数字1-9，且不能出现重复；
（2）每列必须包含数字1-9，且不能出现重复；
（3）每个33的子方格中也必须包含数字1-且不能重复。
表格也可以是部分填充，空表格位置用“，”表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Example 1
Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2
Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

看例题的意思，我们只需要判断每行每列是否存在重复元素以及33小方格是否存在重复元素即可。
先不去看怎么实现的这个算法，先看一下使用和不使用加速代码，通过所有case的耗时。很明显输入是99个字符。这就需要不断的使用cin进行数据的读取。下面是使用与不使用时的耗时比较。
使用后：

使用前：

同样的代码，只是使用与不使用加速代码的区别，一个是12ms，一个是4ms，加速效果非常明显。下面来看一下这道题具体大算法实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static const auto speedup = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board)
{
	vector<bool>used(10, false);
	//判断每行每列是否存在重复
	for (int i = 0; i < 9; ++i) {
		fill(used.begin(), used.end(), false);//行
		for (int j = 0; j < 9; ++j)
			if (!check(board[i][j], used))
				return false;
		fill(used.begin(), used.end(), false);//列
		for (int j = 0; j < 9; ++j)
			if (!check(board[j][i], used))
				return false;
	}
	for (int r = 0; r < 3; ++r)
		for (int c = 0; c < 3; ++c) {
		fill(used.begin(), used.end(), false);//3*3小方格
		for (int i = r * 3; i < r * 3 + 3; ++i)
			for (int j = c * 3; j < c * 3 + 3; ++j)
				if (!check(board[i][j], used))
					return false;
		}
	return true;
}
bool check(char ch, vector<bool>&used) {
	if (ch == '.') return true;
	if (used[ch - '1']) return false;
	return used[ch - '1'] = true;
}
};

字符串大小写转换

在c++中会经常碰到关于字符串字符大小写转换的操作。在alogrithm文件中包含了这样的一个transform函数。下面就举个例子来了解一下transoform 函数的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main()
{
    string str="how are you";
    transform(str.begin(),str.end(),str.begin(),::toupper);//转换为大写
    cout << str << endl;
    return 0;
}

注意一下，这里transform函数有四个参数，前两个表示字符串的起始位置，第三个参数表示转换之后，输出到原str字符串的起始地址；最后一个参数是转换操作，可以选择tolower,toupper。这里就举一道相关的题目。

例题、LeetCode 125 Valid Palindrome

判断字符串是否为回文字符串，只考虑字母数字字符，不考虑其他字符。

1
2
3
4
5
6
7
8
Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:

Input: "race a car"
Output: false

这道题基本上没啥难度，设置两个指针，遍历一遍就可以判断出该字符串是否为回文字符串。嗖嗖的就写了如下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPalindrome(string s) {
      if (s.size() <= 1)return true;
	 transform(s.begin(), s.end(), s.begin(), ::tolower);
	 cout << s << endl;
	 int l = 0, r = s.size() - 1;

	 while (l < r)
	 {
		 while (l<s.size()&&s[l]<'a' || s[l]>'z')l++;
		 while (r<s.size()&&s[r]<'a' || s[r]>'z')r--;
		 cout << s[l] << "-" << s[r] << endl;
		 if (s[l] != s[r]){ return false; }
		 else{ l++; r--; }
	 }
	 return true;
    }
};

代码的case通过率是451/476，始终达不到100%，需要考虑很多特殊的例子。改的头疼。于是参考网上的做法，修改代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPalindrome(string s) {
   transform(s.begin(), s.end(), s.begin(), ::tolower);
	 int l = 0, r = s.size()-1 ;
	 while (l<r)
	 {
		 if (!isalnum(s[l]))l++;
		 else if (!isalnum(s[r]))r--;
		 else if (s[l] != s[r]) return false;
		 else{ l++; r--; }
	 }
    return true;
    }
};

这里顺便介绍几个c的函数。

  • isalnum():判断字符是英文字母（大小写）或数字；
  • isalpha():判断字符是英文字母；
  • isdigit():判断字符是数字；

关于STL常用函数这里先记录这么多，后续刷题碰到了会再来补充。