LeetCode刷题记（二）：31~60题

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

class Solution {
	public:
		void nextPermutation(vector<int>& nums) {
			int n = nums.size();
			int i = n - 2;
			
			while(i >= 0 && nums[i] >= nums[i + 1]) {
				// 找到第一个满足nums[i] < nums[i + 1]的位置i
				i--; 
			}
			
			if(i >= 0) {
				int j = n - 1;
				while(j >= 0 && nums[j] <= nums[i]) {
					// 从的数组末尾开始向前遍历，找到第一个大于nums[i]的元素的位置j
					j--; 
				}
				swap(nums[i], nums[j]);  // 交换位置 
			}
			// 将位置 i 后面的元素进行翻转，使其变为升序排列，这样就得到了下一个排列
			reverse(nums.begin() + i + 1, nums.end());
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n') 
			break;
	}
	Solution solution;
	solution.nextPermutation(nums);
	for(auto num : nums) {
		cout << num << " ";
	}
	return 0;
}

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 10^4
s[i] 为 '(' 或 ')'

#include<stack>
#include<algorithm>
#include<iostream>
using namespace std;

class Solution {
	public:
		int longestValidParentheses(string s) {
			stack<int> stk;
			stk.push(-1);
			int maxLen = 0;
			for(int i = 0; i < s.length(); i++) {
				if(s[i] == '(') {
					// 左括号
					stk.push(i); 
				} else {
					// 右括号
					stk.pop();
					if(stk.empty()) {
						stk.push(i); 
					} else {
						maxLen = max(maxLen, i - stk.top());
					}
				}
			}
			return maxLen;
		}
}; 

int main() {
	string s;
	cin >> s;
	Solution solution;
	cout << solution.longestValidParentheses(s);
	return 0;
}

33. 搜索选择排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int search(vector<int>& nums, int target) {
			int left = 0, right = nums.size() - 1;
			while(left <= right) {
				int mid = left + (right - left) / 2;
				
				if(nums[mid] == target) {
					return mid;
				}
				
				if(nums[left] <= nums[mid]) {  // 小于等于 
					if(nums[left] <= target && target < nums[mid]) {
						right = mid - 1;
					} else {
						left = mid + 1;
					}
				} else {  // 大于 
					if(nums[mid] < target && target <= nums[right]) {
						left = mid + 1;
					} else {
						right = mid - 1;
					}
				}
			}
			return -1;
		}
}; 

int main() {
	Solution solution;
	int tmp, target;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	cin >> target;
	cout << solution.search(nums, target) << endl;
	return 0;
}

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		vector<int> searchRange(vector<int>& nums, int target) {
			int left = 0, right = nums.size() - 1;
			int start = -1, end = -1;
			
			// 寻找开始位置
			while(left <= right) {
				int mid = left + (right - left) / 2;
				
				if(nums[mid] == target) {
					start = mid;
					right = mid - 1;  // 区别在这里 
				} else if(nums[mid] < target) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			} 
			
			// 寻找结束位置
			left = 0, right = nums.size() - 1;
			while(left <= right) {
				int mid = left + (right - left) / 2;
				
				if(nums[mid] == target) {
					end = mid;
					left = mid + 1;  // 区别在这里 
				} else if(nums[mid] < target) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			} 
			return {start, end}; 
		}
}; 

int main() {
	vector<int> nums;
	int target, tmp;
	Solution solution;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	cin >> target;
	vector<int> result = solution.searchRange(nums, target);
	for(auto num : result) {
		cout << num << " ";
	}
	return 0;
}

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的升序排列数组
-10^4 <= target <= 10^4

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int searchInsert(vector<int>& nums, int target) {
			int left = 0, right = nums.size() - 1;
			while(left <= right) {  // 二分查找法 
				int mid = left + (right - left) / 2;
				if(nums[mid] == target) {
					return mid;
				} else if (nums[mid] < target) {
					left = mid + 1;
				} else {
					right = mid - 1;
				} 
			}
			return left;
		}
};

int main() {
	vector<int> nums;
	int target, temp;
	while(cin >> temp) {
		nums.push_back(temp);
		if(cin.get() == '\n') 
			break;
	}
	cin>>target;
	Solution solution;
	cout<<solution.searchInsert(nums, target);
	return 0;
}

36. 有效的数独

请你判断一个 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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

class Solution {
	public:
		bool isValidSudoku(vector<vector<char>>& board) {
			unordered_set<string> seen;
			for(int i = 0; i < 9; i++) {
				for(int j = 0; j < 9; j++) {
					char num = board[i][j];
					if(num != '.') {
						string row = "row" + to_string(i) + num;  // 行 
						string col = "col" + to_string(j) + num;  // 列 
						string box = "box" + to_string(i / 3) + to_string(j / 3) + num;  // 3×3宫 
						
						if(seen.count(row) || seen.count(col) || seen.count(box)) {
							return false;
						} 
						
						seen.insert(row);
						seen.insert(col);
						seen.insert(box);
					}
				}
			}
			return true;
		}
};

int main() {
	Solution solution;
	vector<vector<char>> board(9, vector<char>(9));
	for(int i = 0; i < 9; i++) {
		for(int j = 0; j < 9; j++) {
			cin >> board[i][j];
		}
	}
	cout << boolalpha << solution.isValidSudoku(board) << endl;
	return 0;
}

/*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*/

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 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"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

class Solution {
	public:
		void solveSudoku(vector<vector<char>>& board) {
			if(board.empty() || board.size() != 9 || board[0].size() != 9) {
				return;
			}
			solve(board);
		}
		
		bool solve(vector<vector<char>>& board) {
			for(int i = 0; i < 9; i++) {
				for(int j = 0; j < 9; j++) {
					if(board[i][j] == '.') {
						for(char c = '1'; c <= '9'; c++) {
							if(isValid(board, i, j, c)) {  // 判断填入数字是否破坏规则 
								board[i][j] = c;  
								if(solve(board)) {  // 递归调用 
									return true;
								}
								board[i][j] = '.';
							}
						}
						return false;
					}
				}
			}
			return true;
		}
		
		bool isValid(vector<vector<char>>& board, int row, int col, char c) {
			for(int i = 0; i < 9; i++) {
				if(board[i][col] == c || board[row][i] == c || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
					return false;
				}
			}
			return true;
		}
};

int main() {
	Solution solution;
	vector<vector<char>> board(9, vector<char>(9));
	for(int i = 0; i < 9; i++) {
		for(int j = 0; j < 9; j++) {
			cin >> board[i][j];
		}
	}
	solution.solveSudoku(board);
	
	for(const auto& row : board) {
		for(char c : row) {
			cout << c << " ";
		}
		cout << endl;
	}
	return 0;
}

/*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*/

38. 外观数列

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

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

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

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

1 <= n <= 30

#include<iostream>
#include<string>
using namespace std;

class Solution {
	public:
		string countAndSay(int n) {
			if(n == 1) {
				return "1";
			}
			
			string prev = countAndSay(n - 1);  // 递归调用，获得前一项的外观数列
			string result = "";  // 存储当前的外观数列
			int count = 1; // 记录连续相同数字的个数
			for(int i = 0; i < prev.size(); i++) {
				if(i + 1 < prev.size() && prev[i] == prev[i + 1]) {  // 如1211 
					count++;  // 如果当前数字与下一个数字相同，计数加1 
				} else {
					result += to_string(count) + prev[i];  // 将当前数字的计数和数字本身添加到结果当中
					count = 1;  // 重置计数 
				} 
			} 
			
			return result; 	
		}
}; 

int main() {
	int n;
	cin >> n;
	Solution solution;
	cout << solution.countAndSay(n) << endl;
	return 0;
}

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
			vector<vector<int>> result;
			vector<int> current;  // 存储当前组合
			backtrack(candidates, target, 0, current, result);  // 回溯搜索不同组合

			return result;
		}

		void backtrack(vector<int>& candidates, int target, int start, vector<int>& current, vector<vector<int>>& result) {
			if(target < 0) {
				return;  // 如果目标值小于0，说明当前组合不符合要求
			}

			if(target == 0) {
				result.push_back(current); // 如果目标值等于0，说明当前组合符合要求
				return;
			}

			for(int i = start; i < candidates.size(); i++) {
				current.push_back(candidates[i]);
				backtrack(candidates, target - candidates[i], i, current, result);
				current.pop_back(); // 回溯，将当前数字从当前组合中溢出
			}
		}
};

int main() {
	vector<int> candidates;
	int tmp, target;
	while(cin >> tmp) {
		candidates.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	cin >> target;
	Solution solution;
	vector<vector<int>> result = solution.combinationSum(candidates, target);
//	for(vector<int> combo : result) {
//		cout << "[";
//		for(int num : combo) {
//			cout << num << " ";
//		}
//		cout << "]" << endl;
//	}
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	return 0;
}

40. 组合总和Ⅱ

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
			vector<vector<int>> result;
			vector<int> current;  // 存储当前组合
			sort(candidates.begin(), candidates.end());
			backtrack(candidates, target, 0, current, result);  // 回溯搜索不同组合
			
			return result;
		}
		
		void backtrack(vector<int>& candidates, int target, int start, vector<int>& current, vector<vector<int>>& result) {
			if(target < 0) {
				return;  // 如果目标值小于0，说明当前组合不符合要求
			}

			if(target == 0) {
				result.push_back(current); // 如果目标值等于0，说明当前组合符合要求
				return;
			}

			for(int i = start; i < candidates.size(); i++) {
				if(i > start && candidates[i] == candidates[i - 1]) {
					continue;  // 避免重复组合，如果当前数字与前一个数字相同，则跳过 
				}
				
				current.push_back(candidates[i]);  // 将当前数字加入到当前组合
				backtrack(candidates, target - candidates[i], i + 1, current, result);  // 从i + 1开始回溯 
				current.pop_back();  // 回溯 
			}	
		}
};

int main() {
	vector<int> candidates;
	int tmp, target;
	while(cin >> tmp) {
		candidates.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	cin >> target;
	
	Solution solution;
	vector<vector<int>> result = solution.combinationSum2(candidates, target);
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	return 0;
}

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		/*
		将数组中的每个正整数 num 放到数组的第 num - 1 个位置上，
		并将该位置的数取负值表示 num 存在。最后遍历数组，找到第一个正数所在的位置，
		返回该位置加一即为缺失的最小正整数。
		*/
		int firstMissingPositive(vector<int>& nums) {
			int n = nums.size();
			
			// 将所有非正数和大于n的数置为 n+1
			for(int i = 0; i < n; i++) {
				if(nums[i] <= 0 || nums[i] > n) {
					nums[i] = n + 1;
				}
			} 
			
			// 标记出现过的数
			for(int i = 0; i < n; i++) {
				int num = abs(nums[i]);
				if(num <= n) {
					nums[num - 1] = -abs(nums[num - 1]);
				}
			} 
			
			// 找到第一个未出现的正整数
			for(int i = 0; i < n; i++) {
				if(nums[i] > 0) {
					return i + 1;
				}
			} 
			
			return n + 1;
		}
}; 

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	Solution solution;
	cout << solution.firstMissingPositive(nums);
	return 0;
}

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Solution {
	public:
		int trap(vector<int>& height) {
			int n = height.size();
			if(n == 0) {
				return 0;
			}
			
			int ans = 0;
			stack<int> st;
			
			for(int i = 0; i < n; i++) {
				while(!st.empty() && height[i] > height[st.top()]) {
					int top = st.top();
					st.pop();
					if(st.empty()) {
						break;
					}
					int distance = i - st.top() - 1;
					int bounded_height = min(height[i], height[st.top()]) - height[top];
					ans += distance * bounded_height;
				}
				st.push(i);
			}
			
			return ans;
		}
};

int main() {
	int tmp;
	vector<int> height;
	while(cin >> tmp) {
		height.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	Solution solution;
	cout << solution.trap(height);
	return 0;
}

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

#include<iostream>
#include<cctype>
#include<vector>
using namespace std;

class Solution {
	public:
		string multiply(string num1, string num2) {
			/*
			先将两个数相乘得到中间结果，然后将中间结果按位相加，最后将结果转换为字符串形式返回。
			*/
			int m = num1.size(), n = num2.size();
			vector<int> res(m + n, 0);
			for(int i = m - 1; i >= 0; i--) {
				for(int j = n - 1; j >= 0; j--) {
					int mul = (num1[i] - '0') * (num2[j] - '0');
					int sum = mul + res[i + j + 1];
					res[i + j] += sum / 10;
					res[i + j + 1] = sum % 10;
				}
			}
			
			string result = "";
			for(int num : res) {
				if(!(result.empty() && num == 0)) {
					result.push_back(num + '0');
				}
			}
			
			return result.empty() ? "0" : result;
		}
};

int main() {
	string num1, num2;
	cin >> num1 >> num2;
	Solution solution;
	cout << solution.multiply(num1, num2) << endl;
	return 0;
}

44. 通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：

输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

提示：

0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、'?' 或 '*' 组成

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		bool isMatch(string s, string p) {
			int m = s.size(), n = p.size();
			vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
			dp[0][0] = true;
			
			for(int j = 1; j <= n; j++) {
				if(p[j - 1] == '*') {
					dp[0][j] = dp[0][j - 1];  // true 
				}
			}

			for(int i = 1; i <= m; i++) {
				for(int j = 1; j <= n; j++) {
					if(p[j - 1] == '*') {
						dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
					} else if(p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
						dp[i][j] = dp[i - 1][j - 1];
					}
				}
			}

			return dp[m][n];
		}
};

int main() {
	string s, p;
	cin >> s >> p;
	Solution solution;
	cout << boolalpha << solution.isMatch(s, p);
	return 0;
}

45. 跳跃游戏Ⅱ

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		int jump(vector<int>& nums) {
			int n = nums.size();
			if(n == 1) {
				return 0;
			}
			
			int maxPos = nums[0];  // 当前能到达的最远位置
			int maxSteps = nums[0]; // 跳跃一次能到达的最远位置
			int jumps = 1;
			
			for(int i = 1; i < n; i++) {
				if(maxPos < i) {
					return -1;  // 无法到达当前位置 
				}
				
				if(i > maxSteps) {
					maxSteps = maxPos;
					++jumps;
				}
				
				maxPos = max(maxPos, i + nums[i]);
			} 
			
			return jumps;
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	
	Solution solution;
	cout << solution.jump(nums);
	
	return 0;
}

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		vector<vector<int>> permute(vector<int>& nums) {
			vector<vector<int>> result;
			vector<int> current;
			vector<bool> used(nums.size(), false);
			backtrack(nums, used, current, result);
			
			return result;
		}
		
		void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& result) {
			if(current.size() == nums.size()) {
				result.push_back(current);
				return;
			}
			
			for(int i = 0; i < nums.size(); i++) {
				if(used[i]) {
					continue;
				}
				
				used[i] = true;
				current.push_back(nums[i]);
				backtrack(nums, used, current, result);
				current.pop_back();
				used[i] = false;
			}
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	
	Solution solution;
	vector<vector<int>> result = solution.permute(nums);
	
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	return 0;
}

47. 全排列Ⅱ

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

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

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<int>> permute(vector<int>& nums) {
			sort(nums.begin(), nums.end());
			vector<vector<int>> result;
			vector<int> current;
			vector<bool> used(nums.size(), false);
			backtrack(nums, used, current, result);
			
			return result;
		}
		
		void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& result) {
			if(current.size() == nums.size()) {
				result.push_back(current);
				return;
			}
			
			for(int i = 0; i < nums.size(); i++) {
				if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
					continue;
				}
				
				used[i] = true;
				current.push_back(nums[i]);
				backtrack(nums, used, current, result);
				current.pop_back();
				used[i] = false;
			}
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	
	Solution solution;
	vector<vector<int>> result = solution.permute(nums);
	
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	return 0;
}

48. 旋转图像

#include <vector>

class Solution {
public:
    void rotate(std::vector<std::vector<int>>& matrix) {
        int n = matrix.size();

        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                std::swap(matrix[i][j], matrix[n - 1 - i][j]);
            }
        }

        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                std::swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		void rotate(vector<vector<int>>& matrix) {
			int n = matrix.size();
			
			// 先沿着对角线翻转
			for(int i = 0; i < n; i++) {
				for(int j = i + 1; j < n; j++) {
					swap(matrix[i][j], matrix[j][i]);
				}
			} 
			
			// 再沿着垂直中线翻转
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n / 2; j++) {
					swap(matrix[i][j], matrix[i][n - 1 - j]);
				}
			} 
			
		}
};

int main() {
	int n;
	cin >> n;
	vector<vector<int>> matrix(n, vector<int>(n));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> matrix[i][j];
		}
	}
	
	Solution solution;
	solution.rotate(matrix);
	
	cout << "[";
	for(int i = 0; i < n; i++) {
		cout << "[";
		for(int j = 0; j < n; j++) {
			if(j == n - 1) {
				cout << matrix[i][j];
			} else {
				cout << matrix[i][j] << ", ";
			}
		}
		if(i == n - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	
	return 0;
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

提示：

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<string>> groupAnagrams(vector<string>& strs) {
			unordered_map<string, vector<string>> groupMap;
			
			for(const string& str : strs) {
				string sortedStr = str;
				sort(sortedStr.begin(), sortedStr.end());
				groupMap[sortedStr].push_back(str);  // 将排序后的字符串作为键，原始字符作为值 
			}
			
			vector<vector<string>> result;
			for(const auto& pair : groupMap) {
				result.push_back(pair.second);
			}
			
			return result;
		}
};

int main() {
	vector<string> strs;
	string tmp;
	while(cin >> tmp) {
		strs.push_back(tmp);
		if(cin.get() == '\n')
			break;
	}
	
	Solution solution;
	vector<vector<string>> result = solution.groupAnagrams(strs);
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << "\"" << result[i][j] << "\"";
			} else {
				cout << "\"" << result[i][j] << "\"" << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	
}

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
n 是一个整数
要么 x 不为零，要么 n > 0 。
-10^4 <= xn <= 10^4

#include<iostream>
using namespace std;

class Solution {
	public:
		double myPow(double x, int n) {
			if(n == 0) {
				return 1.0;
			}
			
			double half = myPow(x, n / 2);
			
			if(n % 2 == 0) {
				return half * half;
			} else if(n > 0) {
				return half * half * x;
			} else {
				return half * half / x;
			}
		}
};

int main() {
	double x;
	int n;
	cin >> x >> n;
	Solution solution;
	cout << solution.myPow(x, n);
	return 0;
}

51. N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		vector<vector<string>> solveNQueens(int n) {
			vector<vector<string>> result;
			vector<string> board(n, string(n, '.'));
			DFS(result, board, 0, n);
			
			return result;
		}
		
		void DFS(vector<vector<string>>& result, vector<string>& board, int row, int n) {
			if(row == n) {
				result.push_back(board);
				return;
			}
			
			for(int col = 0; col < n; col++) {
				if(isValid(board, row, col, n)) {
					board[row][col] = 'Q';
					DFS(result, board, row + 1, n);
					board[row][col] = '.';
				}
			}
		}
		
		bool isValid(vector<string>& board, int row, int col, int n) {
			for(int i = 0; i < row; i++) {  // 检查同一列是否存在皇后 
				if(board[i][col] == 'Q') {
					return false;
				}
			}
			
			for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {  // 检查左上方是否存在皇后
				if(board[i][j] == 'Q') {
					return false;
				}
			}
			
			for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {  // 检查右上方是否存在皇后
				if(board[i][j] == 'Q') {
					return false;
				}
			}
			
			return true;
		}
};

int main() {
	int n;
	cin >> n;
	Solution solution;
	vector<vector<string>> result = solution.solveNQueens(n);
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << "\"" << result[i][j] << "\"";
			} else {
				cout << "\"" << result[i][j] << "\"" << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	
	return 0;
}

52. N皇后Ⅱ

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 9

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int totalNQueens(int n) {
			vector<vector<string>> result;
			vector<string> board(n, string(n, '.'));
			DFS(result, board, 0, n);
			
			return result.size();
		}
		
		void DFS(vector<vector<string>>& result, vector<string>& board, int row, int n) {
			if(row == n) {
				result.push_back(board);
				return;
			}
			
			for(int col = 0; col < n; col++) {
				if(isValid(board, row, col, n)) {
					board[row][col] = 'Q';
					DFS(result, board, row + 1, n);
					board[row][col] = '.';
				}
			}
		}
		
		bool isValid(vector<string>& board, int row, int col, int n) {
			for(int i = 0; i < row; i++) {  // 检查同一列是否存在皇后 
				if(board[i][col] == 'Q') {
					return false;
				}
			}
			
			for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {  // 检查左上方是否存在皇后
				if(board[i][j] == 'Q') {
					return false;
				}
			}
			
			for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {  // 检查右上方是否存在皇后
				if(board[i][j] == 'Q') {
					return false;
				}
			}
			
			return true;
		}
};

int main() {
	int n;
	cin >> n;
	Solution solution;
	int result = solution.totalNQueens(n);
	cout << result << endl;
	
	
	return 0;
}

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组

是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		int maxSubArray(vector<int>& nums) {
			int res = nums[0];
			
			for(int i = 1; i < nums.size(); i++) {
				nums[i] += max(nums[i - 1], 0);
				res = max(res, nums[i]);
			}
			
			return res;
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	
	Solution solution;
	cout << solution.maxSubArray(nums);
	
	return 0;
}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

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

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		vector<int> spiralOrder(vector<vector<int>>& matrix) {
			vector<int> result;
			if(matrix.empty()) {
				return result;
			}
			
			int top = 0, bottom = matrix.size() - 1;
			int left = 0, right = matrix[0].size() - 1;
			
			while(top <= bottom && left <= right) {
				// 从左到右
				for(int i = left; i <= right; i++) {
					result.push_back(matrix[top][i]);
				} 
				top++;
				
				// 从上到下
				for(int i = top; i <= bottom; i++) {
					result.push_back(matrix[i][right]);
				} 
				right--;
				
				// 从右到左
				if(top <= bottom) {
					for(int i = right; i >= left; i--) {
						result.push_back(matrix[bottom][i]);
					}
					bottom--;
				} 
				
				// 从下到上
				if(left <= right) {
					for(int i = bottom; i >= top; i--) {
						result.push_back(matrix[i][left]);
					}
					left++;
				} 
			}
			
			return result;
		}
};

int main() {
	int m, n;
	cin >> m >> n;
	vector<vector<int>> matrix(m, vector<int>(n));
	
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			cin >> matrix[i][j];
		}
	}
	
	Solution solution;
	vector<int> result = solution.spiralOrder(matrix);
	
	cout << "[";
	for(int i = 0; i < m * n; i++) {
		if(i == m * n - 1) {
			cout << result[i];
		} else {
			cout << result[i] << ", ";
		}
	}
	cout << "]";
	
	return 0;
}

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		bool canJump(vector<int>& nums) {
			int k = 0;
			for(int i = 0; i < nums.size(); i++) {
				if(i > k) {
					return false;
				}
				k = max(k, i + nums[i]);
			}
			return true;
		}
};

int main() {
	int tmp;
	vector<int> nums;
	while(cin >> tmp) {
		nums.push_back(tmp);
		if(cin.get() == '\n')	
			break;
	}
	
	Solution solution;
	cout << solution.canJump(nums);
	
	return 0;
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<int>> merge(vector<vector<int>>& intervals) {
			vector<vector<int>> merged;
			
			if(intervals.empty()) {
				return merged;
			}
			
			// 按照区间起点进行排序
			sort(intervals.begin(), intervals.end());
			
			merged.push_back(intervals[0]);
			
			for(int i = 1; i < intervals.size(); i++) {
				if(intervals[i][0] <= merged.back()[1]) {
					// 当前区间和前一个区间有重叠，更新合并后的区间的终点
					merged.back()[1] = max(merged.back()[1], intervals[i][1]); 
				} else {
					// 当前区间和前一个区间没有重叠，将当前区间加入合并后的结果中
					merged.push_back(intervals[i]); 
				}
			} 
			
			return merged;
		}
};

int main() {
	vector<vector<int>> intervals;
	int start, end;
	while(cin >> start >> end) {
		intervals.push_back({start, end});
		if(cin.get() == '\n')
			break;
	}
	
	Solution solution;
	vector<vector<int>> result = solution.merge(intervals);
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	
	return 0;
}

57. 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示：

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals 根据 starti 按升序排列
newInterval.length == 2
0 <= start <= end <= 10^5

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
	public:
		vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
			vector<vector<int>> result;
			int i = 0;
			
			// 将所有结束区间的值小于新区间的区间加入结果
			while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
				result.push_back(intervals[i]);
				i++;
			}
			
			// 合并重叠区间
			while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
				newInterval[0] = min(newInterval[0], intervals[i][0]);
				newInterval[1] = max(newInterval[1], intervals[i][1]);
				i++;
			} 
			result.push_back(newInterval);
			
			// 将所有区间大于新区间的区间加入结果
			while(i < intervals.size()) {
				result.push_back(intervals[i]);
				i++;
			} 
			
			return result;
		}
};

int main() {
	vector<vector<int>> intervals;
	vector<int> newInterval;
	int start, end;
	while(cin >> start >> end) {
		intervals.push_back({start, end});
		if(cin.get() == '\n')
			break;
	}
	
	cin >> start >> end;
	newInterval.push_back(start);
	newInterval.push_back(end);
	
	Solution solution;
	vector<vector<int>> result = solution.insert(intervals, newInterval);
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	
	return 0;
}

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为6的“joyboy”。

提示

1 <= s.length <= 104
s 仅有英文字母和空格 ' ' 组成
s 中至少存在一个单词

#include <iostream>
#include <string>
using namespace std;

int lengthOfLastWord(const string& s) {
    int length = 0;
    int i = s.length() - 1;

    // 从字符串末尾开始向前遍历
    while (i >= 0 && s[i] == ' ') {
        i--; // 跳过末尾的空格
    }

    // 统计最后一个单词的长度
    while (i >= 0 && s[i] != ' ') {
        length++;
        i--;
    }

    return length;
}

int main() {
    string s1;
    cin >> s1;
    cout << lengthOfLastWord(s1);
    return 0;
}

59. 螺旋矩阵Ⅱ

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

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

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		vector<vector<int>> generateMatrix(int n) {
			if(n <= 0) {
				return {};
			}
			vector<vector<int>> result(n, vector<int>(n, 0));
			
			int top = 0, bottom = n - 1;
			int left = 0, right = n - 1;
			int num = 1;
			
			while(top <= bottom && left <= right) {
				// 从左到右
				for(int i = left; i <= right; i++) {
					result[top][i] = num++;
				} 
				top++;
				
				// 从上到下
				for(int i = top; i <= bottom; i++) {
					result[i][right] = num++;
				} 
				right--;
				
				// 从右到左
				if(top <= bottom) {
					for(int i = right; i >= left; i--) {
						result[bottom][i] = num++;
					}
					bottom--;
				} 
				
				// 从下到上
				if(left <= right) {
					for(int i = bottom; i >= top; i--) {
						result[i][left] = num++;
					}
					left++;
				} 
			}
			
			return result;
		}
};

int main() {
	int n;
	cin >> n;
	
	Solution solution;
	vector<vector<int>> result = solution.generateMatrix(n);
	
	cout << "[";
	for(int i = 0; i < result.size(); i++) {
		cout << "[";
		for(int j = 0; j < result[i].size(); j++) {
			if(j == result[i].size() - 1) {
				cout << result[i][j];
			} else {
				cout << result[i][j] << ", ";
			}
		}
		if(i == result.size() - 1) {
			cout << "]";
		} else {
			cout << "], ";
		}
	}
	cout << "]";
	
	return 0;
}

60. 排列顺序

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

1 <= n <= 9
1 <= k <= n!

#include<iostream>
#include<vector>
using namespace std;

class Solution {
	public:
		string getPermutation(int n, int k) {
			string result;
			vector<int> nums;
			int fatorial = 1;
			
			for(int i = 1; i <= n; i++) {
				nums.push_back(i);
				factorial *= i;
			}
			
			k--;  // 将k转换为从0开始的索引
			
			for(int i = 0; i < n; i++) {
				factorial /= (n - i);
				int index = k / factorial;
				result += to_string(nums[index]);
				nums.erase(nums.begin() + index);
				k %= factorial;
			} 
			
			return result;
		}
};

int main() {
	int n, k;
	cin >> n >> k;
	
	Solution solution;
	cout << solution.getPermutation(n, k);
	
	return 0;
}

题目链接：题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台