算法训练 2024.7.27 17：25

1. 两数之和

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

输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]  // 因为 nums[0] + nums[1] = 2 + 7 = 9
1
2

#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 {};  // 如果没有解
}

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

2.反转链表

题目： 反转一个单链表。
示例：

输入: 1 -> 2 -> 3 -> 4 -> 5 -> null
输出: 5 -> 4 -> 3 -> 2 -> 1 -> null
1
2

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 是否为有效的括号

题目： 给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。

示例：

输入: "{[]}"
输出: true
1
2

#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();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.最长公共前缀

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

示例：

输入: ["flower","flow","flight"]
输出: "fl"
1
2

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

5.合并两个有序数组

题目： 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使合并后的数组仍然是有序的。

示例：

输入: nums1 = [1,2,3], m = 3, nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
1
2

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--];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

6. 岛屿的个数

题目： 给定一个二维网格，其中 1（表示陆地）和 0（表示水），计算岛屿的数量。一个岛屿是由相邻的 1（水平或垂直方向）组成的。

示例：

输入:
11110
11010
11000
00000
输出: 1
1
2
3
4
5
6

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;
}
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

7. 最小路径和

题目： 给定一个包含非负整数的 m x n 网格，找出一条从左上角到右下角的路径，使得路径上的数字总和最小。

示例：

输入:
[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]
输出: 7  // 因为路径为 1 → 3 → 1 → 2 → 1，总和为 7。
1
2
3
4
5
6
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];
}
1
2
3
4
5
6
7
8
9
10
11
12

8. 三数之和

题目： 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c 使得 a + b + c = 0。请你找出所有满足条件且不重复的三元组。

示例：

输入: [-1,0,1,2,-1,-4]
输出: [[-1,-1,2],[-1,0,1]]
1
2

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

9. 计数质数

题目： 统计所有小于非负整数 n 的质数的数量。

示例：

输入: 10
输出: 4  // 质数是 2, 3, 5, 7
1
2

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

10. 字符串转换整数 ( atoi)

题目： 实现 myAtoi(string s) 将字符串转换为 32 位有符号整数。

示例：

输入: "42"
输出: 42
输入: "   -42"
输出: -42
1
2
3
4

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20