目录
1. 两数之和
题目： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，返回它们的数组下标。
示例：
输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1] // 因为 nums[0] + nums[1] = 2 + 7 = 9
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num_map;
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i];
if (num_map.find(complement) != num_map.end()) {
return {num_map[complement], i};
}
num_map[nums[i]] = i;
}
return {}; // 如果没有解
}
2.反转链表
题目： 反转一个单链表。
示例：
输入: 1 -> 2 -> 3 -> 4 -> 5 -> null
输出: 5 -> 4 -> 3 -> 2 -> 1 -> null
void reverseList(LNode*& L)
{
LNode* p, * next;
p = L->next;
L->next = NULL;
while (p)
{
next = p->next;
p->next = L->next;
L->next = p;
p = next;
}
}
3. 是否为有效的括号
题目： 给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。
示例：
输入: "{[]}"
输出: true
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
stack<char> stack;
unordered_map<char, char> bracket_map = {{'(', ')'}, {'{', '}'}, {'[', ']'}};
for (char c : s) {
if (bracket_map.count(c)) {
stack.push(c);
} else if (stack.empty() || bracket_map[stack.top()] != c) {
return false;
} else {
stack.pop();
}
}
return stack.empty();
}
4.最长公共前缀
题目： 编写一个函数来查找字符串数组中的最长公共前缀。
示例：
输入: ["flower","flow","flight"]
输出: "fl"
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
string prefix = strs[0];
for (int i = 1; i < strs.size(); ++i) {
while (strs[i].find(prefix) != 0) { // prefix 不在 strs[i] 的起始位置
prefix = prefix.substr(0, prefix.size() - 1);
if (prefix.empty()) return "";
}
}
return prefix;
}
5.合并两个有序数组
题目： 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使合并后的数组仍然是有序的。
示例：
输入: nums1 = [1,2,3], m = 3, nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1; // nums1 的最后一个有效元素的索引
int j = n - 1; // nums2 的最后一个有效元素的索引
int k = m + n - 1; // 合并后的数组的最后一个位置
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
6. 岛屿的个数
题目： 给定一个二维网格，其中 1（表示陆地）和 0（表示水），计算岛屿的数量。一个岛屿是由相邻的 1（水平或垂直方向）组成的。
示例：
输入:
11110
11010
11000
00000
输出: 1
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0') {
return;
}
grid[i][j] = '0'; // 标记为水
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) return 0;
int count = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
7. 最小路径和
题目： 给定一个包含非负整数的 m x n 网格，找出一条从左上角到右下角的路径，使得路径上的数字总和最小。
示例：
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7 // 因为路径为 1 → 3 → 1 → 2 → 1，总和为 7。
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 && j == 0) continue;
if (i == 0) grid[i][j] += grid[i][j - 1];
else if (j == 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}
8. 三数之和
题目： 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c 使得 a + b + c = 0。请你找出所有满足条件且不重复的三元组。
示例：
输入: [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) left++;
else if (sum > 0) right--;
else {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++; // 去重
while (left < right && nums[right] == nums[right - 1]) right--; // 去重
left++;
right--;
}
}
}
return result;
}
9. 计数质数
题目： 统计所有小于非负整数 n 的质数的数量。
示例：
输入: 10
输出: 4 // 质数是 2, 3, 5, 7
int countPrimes(int n) {
if (n < 3) return 0;
vector<bool> is_prime(n, true);
is_prime[0] = is_prime[1] = false; // 0 和 1 不是质数
for (int i = 2; i * i < n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j < n; j += i) {
is_prime[j] = false;
}
}
}
return count(is_prime.begin(), is_prime.end(), true);
}
10. 字符串转换整数 ( atoi)
题目： 实现 myAtoi(string s) 将字符串转换为 32 位有符号整数。
示例：
输入: "42"
输出: 42
输入: " -42"
输出: -42
int myAtoi(string s) {
int i = 0, sign = 1;
long long result = 0;
// 跳过空格
while (i < s.size() && s[i] == ' ') i++;
// 判断符号
if (i < s.size() && (s[i] == '+' || s[i] == '-')) {
sign = s[i] == '+' ? 1 : -1;
i++;
}
// 处理数字
while (i < s.size() && isdigit(s[i])) {
result = result * 10 + (s[i] - '0');
if (result * sign >= INT_MAX) return INT_MAX;
if (result * sign <= INT_MIN) return INT_MIN;
i++;
}
return static_cast<int>(result * sign);
}