概述

这是由 LeetCode 官方推出的经典面试题目清单，我们将题目重新整理规划，从而为大家提供更好的练习体验和帮助大家找到理想的工作。 我们将题目分为以下三个部分：

• 初级算法 - 帮助入门
• 中级算法 - 巩固训练
• 高级算法 - 提升进阶

这一系列 LeetBook 将帮助您掌握算法及数据结构，并提高您的编程能力。

编程能力就像任何其他技能一样，也是一个可以通过刻意练习大大提高的。

大多数经典面试题目都有多种解决方案。 为了达到最佳的练习效果，我们强烈建议您至少将此清单里的题目练习两遍，如果可以的话，三遍会更好。

在第二遍练习时，你可能会发现一些新的技巧或新的方法。 到第三遍的时候，你会发现你的代码要比第一次提交时更加简洁。 如果你达到了这样的效果，那么恭喜你，你已经掌握了正确的练习方法！

数组

数组问题在面试中出现频率很高，你极有可能在面试中遇到。

我们推荐以下题目：只出现一次的数字，旋转数组，两个数组的交集 II 和 两数之和。

1.01 删除有序数组的重复项

给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。
更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：
输入：nums = [1, 1, 2]
输出：2, nums = [1, 2, _]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
输出：5, nums = [0, 1, 2, 3, 4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

//方法一调用系统库函数，测试通过
int removeDuplicates(vector<int>& nums) {
	int length = nums.size();
	if (length == 0 || length == 1) return length;
	auto x = unique(nums.begin(), nums.end());
	vector<int>::iterator it = nums.begin();
	int count = 0;
	while (it != x)
	{
		++count;
		it++;
	}
	return count;
}
// 方法二快慢指针，测试通过
int removeDuplicates(vector<int>& nums) {
	int length = nums.size();
	if (length == 0 || length == 1) return length;
	int slow = 1;
	int fast = 1;
	while (fast < length)
	{
		if (nums[fast] != nums[fast - 1])
		{
			nums[slow++] = nums[fast++];
		}
		else
		{
			++fast;
		}
	}
	return slow;
}
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

1.02 买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和 / 或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润 。

示例 1：
输入：prices = [7, 1, 5, 3, 6, 4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：
输入：prices = [1, 2, 3, 4, 5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：
输入：prices = [7, 6, 4, 3, 1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

// 方法一动态规划，测试通过
// 考虑两种情况，nohold当天交易结束未持有股票，可能是前一天没有持股今天也没有购买或者前一天持股今天抛售；
// hold当天交易结束持有股票，可能是前一天持股今天没有抛售或者前一天没有持股今天购买股票。
int maxProfit_II(vector<int>& prices) {
	int length = prices.size();
	if (length == 1) return 0;
	vector<vector<int> > dp(length, vector<int>(2));
	dp[0][0] = 0;
	dp[0][1] = -prices[0];
	for (int i = 1; i < length; ++i)
	{
		dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
		dp[i][1] = std::max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
	}
	return dp[length - 1][0];
}
// 方法二动态规划优化，测试通过
// 使用变量代替数组，思路同方法一完全相同
int maxProfit_II(vector<int>& prices) {
	if (prices.size() < 2) return 0;
	int length = prices.size();
	int hold = -prices[0];
	int nohold = 0;
	for (int i = 1; i < length; ++i)
	{
		nohold = std::max(nohold, hold + prices[i]);
		hold = std::max(hold, nohold - prices[i]);
	}
	return nohold;
}
// 方法二贪心算法，测试通过
// 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
int maxProfit_II(vector<int>& prices) {
	if (prices.size() < 2) return 0;
	int length = prices.size();
	int total = 0;
	for (int i = 0; i < length - 1; ++i)
	{
		total += std::max(0, prices[i + 1] - prices[i]);
	}
	return total;
}
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
38
39
40
41
42

1.03 旋转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
输出 : [5, 6, 7, 1, 2, 3, 4]
解释 :
向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]

示例 2 :
输入：nums = [-1, -100, 3, 99], k = 2
输出：[3, 99, -1, -100]
解释 :
向右轮转 1 步 : [99, -1, -100, 3]
向右轮转 2 步 : [3, 99, -1, -100]

// 方法一普通旋转，超时
// 计算余数可以大幅提高效率，但时间复杂度仍然高
void move_right(vector<int>& nums)
{
	int length = nums.size();
	int tmp = nums[length - 1];
	for (int i = length - 1; i > 0; --i)
	{
		nums[i] = nums[i - 1];
	}
	nums[0] = tmp;
}
void rotate(vector<int>& nums, int k) {
	int length = nums.size();
	if (length < 2) return;
	k = k % length;
	if (k >= 0)
	{
		while (k--)
		{
			move_right(nums);
		}
	}
}
// 方法二反转数列，测试通过
// On级别的时间复杂度
void ReverseArray(vector<int>& nums, int left, int right) {
	while (left < right) {
		std::swap(nums[left++], nums[right--]);
	}
}
void rotate(vector<int>& nums, int k) {
	int n = nums.size();
	k = n - (k % n);
	ReverseArray(nums, 0, k - 1);
	ReverseArray(nums, k, n - 1);
	ReverseArray(nums, 0, n - 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
32
33
34
35
36
37
38

1.04 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：
输入：nums = [1, 2, 3, 1]
输出：true

示例 2：
输入：nums = [1, 2, 3, 4]
输出：false

示例 3：
输入：nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
输出：true

// 方法一排序，测试通过
// 排完序两两比较
bool containsDuplicate(vector<int>& nums) {
	std::sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size() - 1; ++i)
	{
		if (nums[i] == nums[i + 1]) return true;
	}
	return false;
}
// 方法二哈希表，测试通过
// 时间复杂度较低
bool containsDuplicate(vector<int>& nums) {
	unordered_set<int> myset;
	bool res = false;
	for (auto x : nums)
	{
		auto flag = myset.find(x);
		if (flag == myset.end())
		{
			myset.insert(x);
		}
		else
		{
			res = true;
			break;
		}
	}
	return res;
}
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

1.05 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2, 2, 1]
输出 : 1

示例 2 :
输入 : [4, 1, 2, 1, 2]
输出 : 4

// 方法一哈希表，测试通过
// 记录每个数字出现的次数，然后查找只出现一次的数字
int singleNumber(vector<int>& nums) {
	unordered_map<int, int> mymap;
	for (auto x : nums)
	{
		auto res = mymap.find(x);
		if (res != mymap.end())
		{
			res->second += 1;
		}
		else
		{
			mymap.insert(std::pair<int, int>(x, 0));
		}
	}
	unordered_map<int, int>::iterator it = mymap.begin();
	for (; it != mymap.end(); ++it)
	{
		if (it->second == 0) break;
	}
	return it->first;
}

// 方法二哈希表，测试通过
// 向表中填入数字，遇到重复的数字将其删除，最后一定剩下一个单独的数字将其返回
int singleNumber(vector<int>& nums) {
	unordered_set<int> myset;
	for (auto x : nums)
	{
		if (myset.find(x) != myset.end())
		{
			myset.erase(x);
		}
		else
		{
			myset.insert(x);
		}
	}
	unordered_set<int>::iterator it = myset.begin()++;
	return *it;
}

// 方法三位运算，测试通过
// 通过异或性质0^a = a, a^a = 0, a^b^a = a^a^b = b得到结论，时间复杂度低
int singleNumber(vector<int>& nums) {
	int reduce = 0;
	for (auto x : nums)
	{
		reduce ^= x;
	}
	return reduce;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

1.06 两个数组的交集

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，
应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：
输入：nums1 = [1, 2, 2, 1], nums2 = [2, 2]
输出：[2, 2]

示例 2:
输入：nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
输出：[4, 9]

// 方法一哈希表，测试通过
// 采用两个哈希表，记录两个数组中元素出现个数，空间复杂度高
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
	map<int, int> map1;
	map<int, int> map2;
	for (auto x : nums1)
	{
		auto it = map1.find(x);
		if (it != map1.end())
		{
			it->second += 1;
		}
		else
		{
			map1.insert(std::pair<int, int>(x, 1));
		}
	}
	for (auto x : nums2)
	{
		auto it = map2.find(x);
		if (it != map2.end())
		{
			it->second += 1;
		}
		else
		{
			map2.insert(std::pair<int, int>(x, 1));
		}
	}
	if (nums1.size() <= nums2.size())
	{
		vector<int> res;
		map<int, int>::iterator it = map1.begin();
		for (; it != map1.end(); ++it)
		{
			auto x = map2.find(it->first);
			if (x != map2.end())
			{
				int count = std::min(it->second, x->second);
				for (int i = 0; i < count; ++i)
				{
					res.push_back(x->first);
				}
			}
		}
		return res;
	}
	else
	{
		vector<int> res;
		map<int, int>::iterator it = map2.begin();
		for (; it != map2.end(); ++it)
		{
			auto x = map1.find(it->first);
			if (x != map1.end())
			{
				int count = std::min(it->second, x->second);
				for (int i = 0; i < count; ++i)
				{
					res.push_back(x->first);
				}
			}
		}
		return res;
	}
}

// 方法二哈希表，测试通过
// 代码简洁，空间消耗小
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
	unordered_map<int, int> mymap;
	for (auto x : nums1)
	{
		auto it = mymap.find(x);
		if (it != mymap.end())
		{
			it->second += 1;
		}
		else
		{
			mymap.insert(std::pair<int, int>(x, 1));
		}
	}
	vector<int> res;
	for (auto x : nums2)
	{
		auto it = mymap.find(x);
		if (it != mymap.end())
		{
			if (it->second != 0)
			{
				res.push_back(x);
				it->second -= 1;
			}
		}
	}
	return res;
}

// 方法三排序+双指针，测试通过
// 排序后定义两个指针遍历两个数组
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
	std::sort(nums1.begin(), nums1.end());
	std::sort(nums2.begin(), nums2.end());
	vector<int>::iterator it1 = nums1.begin();
	vector<int>::iterator it2 = nums2.begin();
	vector<int> result;
	while (it1 != nums1.end() && it2 != nums2.end())
	{
		if (*it1 == *it2)
		{
			result.push_back(*it1);
			++it1;
			++it2;
		}
		else if (*it1 < *it2)
		{
			++it1;
		}
		else
		{
			++it2;
		}
	}
	return result;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

1.07 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：
输入：digits = [1, 2, 3]
输出：[1, 2, 4]
解释：输入数组表示数字 123。

示例 2：
输入：digits = [9,9,9,9]
输出：[1, 0, 0, 0, 0]
解释：输入数组表示数字 10000。

示例 3：
输入：digits = [0]
输出：[1]

// 直接法,测试通过
vector<int> plusOne(vector<int>& digits) {
	int n = digits.size();
	if (digits[n - 1] != 9)
	{
		digits[n - 1] += 1;
		return digits;
	}
	else
	{
		int c = 1;
		for (int i = n - 1; i >= 0; --i)
		{
			if (c == 0) break;
			digits[i] += 1;
			digits[i] %= 10;
			if (digits[i] != 0) c = 0;
		}
		if (c == 1)
		{
			vector<int> newarray;
			newarray.push_back(1);
			for (auto x : digits)
			{
				newarray.push_back(x);
			}
			return newarray;
		}
		return digits;
	}
}
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

1.08 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0, 1, 0, 3, 12]
输出 : [1, 3, 12, 0, 0]

示例 2 :
输入 : nums = [0]
输出 : [0]

// 方法一直接法，测试通过
void moveZeroes(vector<int>& nums) {
	int n = nums.size();
	int index = 0;
	for (int i = 0; i < n; ++i)
	{
		if (nums[i] != 0)
		{
			nums[index++] = nums[i];
		}
	}
	while (index < n)
	{
		nums[index++] = 0;
	}
}

// 方法二双指针，测试通过
// 左指针左边保证非零值，右指针到左指针之间保证零值
void moveZeroes(vector<int>& nums) {
	int n = nums.size(), left = 0, right = 0;
	while (right < n) {
		if (nums[right]) {
			swap(nums[left], nums[right]);
			left++;
		}
		right++;
	}
}
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

1.09 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：因为 nums[0] + nums[1] == 9 ，返回[0, 1] 。

示例 2：
输入：nums = [3, 2, 4], target = 6
输出：[1, 2]

示例 3：
输入：nums = [3, 3], target = 6
输出：[0, 1]

// 方法一暴力枚举，测试通过
// 时间复杂度很高，不建议使用
vector<int> twoSum(vector<int>& nums, int target) {
	vector<int> resarray;
	bool flag = false;
	for (int i = 0; i < nums.size(); ++i)
	{
		for (int j = i + 1; j < nums.size(); ++j)
		{
			if (nums[i] + nums[j] == target)
			{
				resarray.push_back(i);
				resarray.push_back(j);
				flag = true;
				break;
			}
		}
		if (flag) break;
	}
	return resarray;
}

// 方法二哈希表，测试通过
// 遍历数组，查找target-nums[i]，查找成功返回，不成功插入，时间复杂度很低
vector<int> twoSum(vector<int>& nums, int target) {
	unordered_map<int, int> hashtable;
	for (int i = 0; i < nums.size(); ++i)
	{
		auto ret = hashtable.find(target - nums[i]);
		if (ret != hashtable.end())
		{
			return { ret->second,i };
		}
		hashtable.insert(std::pair<int, int>(nums[i], i));
	}
	return {};
}
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

1.10 有效数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1 - 9 在每一行只能出现一次。
数字 1 - 9 在每一列只能出现一次。
数字 1 - 9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

示例 1：
输入：board =
[ [“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”]]
输出：true

示例 2：
输入：board =
[ [“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”]]

// 方法一自己的方法，测试通过
// 代码复杂，时间、空间复杂度高，不建议采用
class index
{
	public:
		int _x;
		int _y;
		index(int x, int y) :_x(x), _y(y) {}
		bool operator==(index& a)
		{
			if (_x == a._x || _y == a._y) return true;
			return false;
		}
};
bool isValidSudoku(vector<vector<char>>& board) {
	unordered_multimap<char, index> hashmap;
	map<char, int> counttable;
	for (int i = 1; i <= 9; ++i)
	{
		counttable.insert(std::pair<char, int>('0' + i, 0));
	}
	for (int i = 0; i < board.size(); ++i)
	{
		for (int j = 0; j < board[i].size(); ++j)
		{
			if (board[i][j] == '.') continue;
			auto ret = hashmap.find(board[i][j]);
			if (ret != hashmap.end())
			{
				auto cnt = hashmap.count(board[i][j]);
				index position(i, j);
				for (; cnt > 0; cnt--, ret++)
				{
					if (ret->second == position) return false;
				}
			}
			hashmap.insert(std::pair<char, index>(board[i][j], index(i, j)));
		}
	}
	for (int i = 0; i < 9; ++i)
	{
		for (int j = 0; j < 9; ++j)
		{
			int p = i / 3 * 3 + j / 3;
			int q = i % 3 * 3 + j % 3;
			auto ret = counttable.find(board[p][q]);
			if (ret != counttable.end())
			{
				ret->second += 1;
				if (ret->second >= 2) return false;
			}
		}
		map<char, int>::iterator it = counttable.begin();
		while (it != counttable.end())
		{
			it->second = 0;
			++it;
		}
	}
	return true;
}

// 方法二直接求解法，测试通过
// 设置行列以及子矩阵的二维矩阵，一次性判断所有条件。空间、时间复杂度很低，建议采用
bool isValidSudoku(vector<vector<char>>& board) {
	int row[9][10] = { 0 };
	int col[9][10] = { 0 };
	int box[9][10] = { 0 };
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == '.') continue;
			int curNumber = board[i][j] - '0';
			if (row[i][curNumber]) return false;
			if (col[j][curNumber]) return false;
			if (box[j / 3 + (i / 3) * 3][curNumber]) return false;

			row[i][curNumber] = 1;
			col[j][curNumber] = 1;
			box[j / 3 + (i / 3) * 3][curNumber] = 1;
		}
	}
	return true;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

1.11 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：
输入：matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
输出： [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ]

示例 2：
输入：matrix = [ [5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16] ]
输出： [ [15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11] ]

// 找规律法，测试通过
// 首先上下交换，然后对角线交换
void rotate(vector<vector<int>>& matrix) {
	int row = matrix.size();
	int first = 0, last = row - 1;
	while (first < last)
	{
		std::swap(matrix[first], matrix[last]);
		first++;
		last--;
	}
	for (int i = 0; i < row; ++i)
	{
		for (int j = i + 1; j < row; ++j)
		{
			std::swap(matrix[i][j], matrix[j][i]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

字符串

字符串问题在面试中出现频率很高，你极有可能在面试中遇到。

我们推荐以下题目：反转字符串，字符串中第一个唯一字符，字符串转整数（atoi）和 实现 strStr() 。

2.01 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：
输入：s = [“h”, “e”, “l”, “l”, “o”]
输出：[“o”, “l”, “l”, “e”, “h”]

示例 2：
输入：s = [“H”, “a”, “n”, “n”, “a”, “h”]
输出：[“h”, “a”, “n”, “n”, “a”, “H”]

// 方法一调用算法库函数，测试通过
void reverseString(vector<char>& s) {
	reverse(s.begin(), s.end());
}

// 方法二双指针，测试通过
void reverseString(vector<char>& s) {
	int left = 0;
	int right = s.size() - 1;
	while (left < right)
	{
		std::swap(s.at(left), s.at(right));
		left++;
		right--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.02 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：
输入：x = 123
输出：321

示例 2：
输入：x = -123
输出： - 321

示例 3：
输入：x = 120
输出：21

示例 4：
输入：x = 0
输出：0

// 防止算数溢出，设置INT_MAX INT_MIN
int reverse(int x) {
	int res = 0;
	while (x != 0)
	{
		int t = x % 10;
		if (res > INT_MAX / 10 || res < INT_MIN / 10) return 0;
		res = res * 10 + t;
		x = x / 10;
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.03 字符串中的第一个唯一字符

给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 - 1 。

示例 1：
输入 : s = “leetcode”
输出 : 0

示例 2 :
输入 : s = “loveleetcode”
输出 : 2

示例 3 :
输入 : s = “aabb”
输出 : -1

// 方法一数组，测试通过
// 用数组存储字符出现的次数，然后再遍历一遍数组，直到找到第一个计数为1的元素返回其下标
int firstUniqChar(string s) {
	int* arr = (int*)malloc(sizeof(int) * 26);
	memset(arr, 0, sizeof(int) * 26);
	for (int i = 0; i < s.size(); ++i)
	{
		arr[s[i] - 'a'] += 1;
	}
	for (int i = 0; i < s.size(); ++i)
	{
		if (arr[s[i] - 'a'] == 1) return i;
	}
	return -1;
}

// 方法二哈希表，测试通过
// 将方法一的数组改成哈希表即可
int firstUniqChar(string s) {
	unordered_map<char, int> hashtable;
	for (int i = 0; i < s.size(); ++i)
	{
		auto x = hashtable.find(s[i]);
		if (x != hashtable.end())
		{
			x->second += 1;
		}
		else
		{
			hashtable.insert(make_pair(s[i], 1));
		}
	}
	for (int i = 0; i < s.size(); ++i)
	{
		if (hashtable.find(s[i])->second == 1) return i;
	}
	return -1;
}

// 方法三哈希表，测试通过
// 使用哈希表，不记录出现次数，记录首次出现的下标
// 如果再次出现，就讲原先的下标记成-1，然后遍历数组，找到第一个不为-1的元素返回其下标
int firstUniqChar(string s) {
	unordered_map<char, int> hashmap;
	for (int i = 0; i < s.length(); ++i)
	{
		auto x = hashmap.find(s[i]);
		if (x != hashmap.end())
		{
			x->second = -1;
		}
		else
		{
			hashmap.insert(make_pair(s[i], i));
		}
	}
	for (int i = 0; i < s.length(); ++i)
	{
		if (hashmap.find(s[i])->second != -1) return i;
	}
	return -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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

附加题 前k个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：
输入 : words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出 : [“i”, “love”]
解析 : “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

示例 2：
输入 : [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”] , k = 4
输出 : [“the”, “is”, “sunny”, “day”]
解析 : “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

// 哈希表，测试通过
// 记录所用单词的出现频率，然后根据题目要求排序，并取出前k个字母返回
vector<string> topKFrequent(vector<string>& words, int k) {
	unordered_map<string, int> cnt;
	for (auto& word : words) {
		++cnt[word];
	}
	vector<string> rec;
	for (auto& x : cnt) {
		rec.emplace_back(x.first);
	}
	sort(rec.begin(), rec.end(), [&](const string& a, const string& b) -> bool {
		return cnt[a] == cnt[b] ? a < b : cnt[a] > cnt[b];
		});
	rec.erase(rec.begin() + k, rec.end());
	return rec;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.04 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出 : true

示例 2 :
输入 : s = “rat”, t = “car”
输出 : false

// 方法一哈希表，测试通过
// 统计第一个单词中字母个数，与第二个单词中所有字母作差，如果小于零说明不是异位词
bool isAnagram(string s, string t) {
	unordered_map<char, int> hashtable;
	for (int i = 0; i < s.size(); ++i)
	{
		++hashtable[s[i]];
	}
	for (int i = 0; i < t.size(); ++i)
	{
		--hashtable[t[i]];
	}
	auto it = hashtable.begin();
	while (it != hashtable.end())
	{
		if (it->second != 0) return false;
		++it;
	}
	return true;
}

// 方法二哈希表，测试通过
// 思路同方法一，但是哈希表使用数组方式，速度较方法一更快
bool isAnagram(string s, string t) {
	if (s.size() != t.size()) return false;
	vector<int> table(26, 0);
	for (auto& x : s)
	{
		table[x - 'a']++;
	}
	for (auto& x : t)
	{
		table[x - 'a']--;
		if (table[x - 'a'] < 0) return false;
	}
	return true;
}

// 方法三排序，测试通过
// 如果两个字母是异位词，那么经过排序后一定相等
bool isAnagram(string s, string t) {
	if (s.size() != t.size()) return false;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	return s == t;
}
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
38
39
40
41
42
43
44
45
46

2.05 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:
输入: “A man, a plan, a canal: Panama”
输出 : true
解释：“amanaplanacanalpanama” 是回文串

示例 2 :
输入 : “race a car”
输出 : false
解释：“raceacar” 不是回文串

// 双指针，测试通过
// 主要是要跳过非字母数字字符以及转换大小写字母然后比较即可
bool isPalindrome(string s) {
	if (s.empty()) return true;
	int left = 0;
	int right = s.size() - 1;
	while (left <= right)
	{
		if (!isalnum(s[left]))
		{
			left++;
			continue;
		}
		if (!isalnum(s[right]))
		{
			right--;
			continue;
		}
		if (isupper(s[left])) s[left] = tolower(s[left]);
		if (isupper(s[right])) s[right] = tolower(s[right]);
		if (s[left] == s[right])
		{
			left++;
			right--;
		}
		else return false;
	}
	return true;
}
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

2.06 字符串转换整数

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C / C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

• 读入字符串并丢弃无用的前导空格。
• 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
• 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
• 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
• 如果整数数超过 32 位有符号整数范围[−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
• 返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：
输入：s = “42”
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步：“42”（当前没有读入字符，因为没有前导空格）
^
第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
^
第 3 步：“42”（读入 “42”）
^
解析得到整数 42 。
由于 “42” 在范围[-231, 231 - 1] 内，最终结果为 42 。

示例 2：
输入：s = " -42"
输出： - 42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 ‘-’ 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 “42”）
^
解析得到整数 - 42 。
由于 “-42” 在范围[-231, 231 - 1] 内，最终结果为 - 42 。

示例 3：
输入：s = “4193 with words”
输出：4193
解释：
第 1 步：“4193 with words”（当前没有读入字符，因为没有前导空格）
^
第 2 步：“4193 with words”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
^
第 3 步：“4193 with words”（读入 “4193”；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 “4193” 在范围[-231, 231 - 1] 内，最终结果为 4193 。

// 方法一逻辑方法，测试通过
// 根据题意考虑各种情况，给出合适条件判断
// 缺点是题目条件要求多，极易造成代码的架构混乱，不建议采用
int myAtoi(string s) {
	int res = 0;
	int c = 1;
	int i = 0;
	while (i < s.size())
	{
		if (s[i] == ' ')
		{
			i++;
		}
		else if (s[i] == '-')
		{
			c = -1;
			i++;
			break;
		}
		else if (s[i] == '+')
		{
			c = 1;
			i++;
			break;
		}
		else break;
	}
	for (int j = i; j < s.size(); ++j)
	{
		if (isdigit(s[j]))
		{
			int num = s[j] - '0';
			// 越界判断
			if (res > INT_MAX / 10 || res == INT_MAX / 10 && num > INT_MAX % 10)
			{
				return c == -1 ? INT_MIN : INT_MAX;
			}
			res = res * 10 + num;
		}
		else break;
	}
	return res * c;
}

// 方法二自动机，测试通过
// 程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s'。
// 这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s' 的表格即可解决题目中的问题。
// 这是一种类似状态方案的思想，代码清晰明了，建议采用
class Automaton {
	string state = "start";
	unordered_map<string, vector<string>> table = {
		{"start",		{"start", "signed", "in_number", "end"}},
		{"signed",		{"end", "end", "in_number", "end"}},
		{"in_number",	{"end", "end", "in_number", "end"}},
		{"end",			{"end", "end", "end", "end"}}
	};

	int get_col(char c) {
		if (isspace(c)) return 0;
		if (c == '+' or c == '-') return 1;
		if (isdigit(c)) return 2;
		return 3;
	}
public:
	int sign = 1;
	long long ans = 0;

	void get(char c) {
		state = table[state][get_col(c)];
		if (state == "in_number") {
			ans = ans * 10 + c - '0';
			ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
		}
		else if (state == "signed")
			sign = c == '+' ? 1 : -1;
	}
};
int myAtoi(string str) {
	Automaton automaton;
	for (char c : str)
		automaton.get(c);
	return automaton.sign * automaton.ans;
}

// 方法三剑走偏锋法，测试通过
// 利用C++ stringstream类，直接进行转换
int myAtoi(string str)
{
	stringstream ss(str);
	int n;
	ss >> n;
	return n;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

2.07 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  - 1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

// 方法一朴素算法，测试通过
// 按照规则逐个匹配即可
int strStr(string haystack, string needle) {
	if (needle.empty()) return 0;
	int ih = 0;
	int in = 0;
	for (; ih < haystack.size(); )
	{
		if (in == needle.size()) break;
		if (haystack[ih] == needle[in])
		{
			in++;
			ih++;
		}
		else
		{
			ih = ih - in + 1;
			in = 0;
		}
	}
	if (in == needle.size()) return ih - needle.size();
	else return -1;
}

// 方法二调用系统库函数，测试通过
int strStr(string haystack, string needle) {
	return haystack.find(needle);
}
// 方法三KMP算法
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

2.08 外观数组

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n - 1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1. 1
   1

2. 11
   1

3. 21
   1

4. 1211
   1

5. 111221
   1

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，
先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

// 遍历求解法，测试通过
// 统计相同字符个数按照题目要求填入即可
string countAndSay(int n) {
	string res = { "1" };
	for (int i = 2; i <= n; ++i)
	{
		string temp;
		int pos = 0;
		int count = 0;
		char ch = res[0];
		while (pos < res.size())
		{
			while (ch == res[pos])
			{
				count += 1;
				pos += 1;
			}
			temp += to_string(count) + ch;
			count = 0;
			ch = res[pos];
		}
		res = temp;
	}
	return res;
}
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

2.09 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：
输入：strs = [“flower”, “flow”, “flight”]
输出：“fl”

示例 2：
输入：strs = [“dog”, “racecar”, “car”]
输出：“”
解释：输入不存在公共前缀。

// 方法一纵向比较法，测试通过
string longestCommonPrefix(vector<string>& strs) {
	string res;
	for (int i = 0; i < strs[0].size(); ++i)
	{
		int count = 1;
		for (int j = 1; j < strs.size(); ++j)
		{
			if (strs[j][i] == strs[0][i])
			{
				count += 1;
			}
			else return res;
		}
		if (count == strs.size())
		{
			res.push_back(strs[0][i]);
		}
	}
	return res;
}

// 方法二横向比较法，测试通过
string longestCommonPrefix(vector<string>& strs) {
	string prefix = strs[0];
	for (int i = 1; i < strs.size(); ++i)
	{
		int length = std::min(prefix.size(), strs[i].size());
		int j = 0;
		for (; j < length; ++j)
		{
			if (prefix[j] != strs[i].at(j))
			{
				break;
			}
		}
		prefix = prefix.substr(0, j);
		if (!prefix.size())
		{
			break;
		}
	}
	return prefix;
}


// 方法三分治法，测试通过
// 以单词为单位划分，划分至两两比较最长前缀，以此求得原问题的解
string longestCommonPrefix(string& str1, string& str2)
{
	int length = std::min(str1.size(), str2.size());
	for (int index = 0; index < length; ++index)
	{
		if (str1[index] != str2[index])
		{
			return str1.substr(0, index);
		}
	}
	return str1.substr(0, length);
}
string longestCommonPrefix(vector<string>& strs, int left, int right)
{
	if (left == right)
	{
		return strs[left];
	}
	else
	{
		int mid = (left + right) / 2;
		string lcpleft = longestCommonPrefix(strs, left, mid);
		string lcpright = longestCommonPrefix(strs, mid + 1, right);
		return longestCommonPrefix(lcpleft, lcpright);
	}
}
string longestCommonPrefix(vector<string>& strs) {
	return longestCommonPrefix(strs, 0, strs.size() - 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77