算法刷题分享-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法刷题分享。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

（一）动态规划——背包专题

导语：动态规划是一种常用的算法思想，广泛应用于各类问题的求解中。而背包问题则是动态规划中最经典且常见的问题之一。背包问题涉及在给定容量的背包中选择物品以达到最优解的目标。本篇博客将专注于介绍和讨论与背包问题相关的动态规划算法。我们将探索不同类型的背包问题，并详细讲解其动态规划的解决思路。

题目：01背包问题 LeetCode 416
题目概述：01背包问题是最基础的背包问题之一。给定一组物品，每个物品有重量和价值，背包具有一定的容量，需要在不超过背包容量的前提下，选择物品使得总价值最大化。
题解：使用动态规划求解，定义dp[i][j]表示前i个物品放入容量为j的背包中所能达到的最大价值。状态转移方程如下：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

def knapsack01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][capacity]

题目：完全背包问题 - LeetCode 322
题解：完全背包问题是一个经典的背包问题。给定一组面额不同的硬币和一个总金额，求出能够凑成总金额所需的最少硬币数量。使用动态规划求解，定义dp[i]表示凑成金额i所需的最少硬币数量。状态转移方程如下：dp[i] = min(dp[i], dp[i-coin] + 1)，其中coin表示硬币的面额。核心代码段：

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

题目：多重背包问题 - LeetCode 879
题解：多重背包问题是背包问题的一种扩展形式，每个物品有数量限制。给定一组工作，每个工作有所需的成本和利润，求出在不超过预算的前提下，能够获得的最大利润。使用动态规划求解，定义dp[i][j]表示前i个工作在预算不超过j的情况下所能达到的最大利润。状态转移方程如下：dp[i][j] = dp[i-1][j] + dp[i-1][j-cost]，其中cost表示第i个工作的成本。核心代码段：

def profitableSchemes(n, minProfit, group, profit):
    m = len(group)
    MOD = 10 ** 9 + 7
    dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, m + 1):
        currGroup, currProfit = group[i - 1], profit[i - 1]
        for j in range(n, currGroup - 1, -1):
            for k in range(minProfit, -1, -1):
                dp[j][k] += dp[j - currGroup][max(0, k - currProfit)]
                dp[j][k] %= MOD

    return sum(dp[n]) % MOD

（二）贪心——区间专题

导语：在算法问题中，区间类问题是一类常见而重要的问题。贪心算法是一种常用的解决区间类问题的方法，它通过每一步选择当前最优解来达到整体最优解的目标。本篇博客将介绍贪心算法在解决区间类问题中的应用，并提供几个示例来说明其实现过程。通过阅读本文，你将了解贪心算法的基本思想以及如何运用它解决不同类型的区间类问题。

题目：区间选点
题目描述：给定一组区间，从中选取尽可能多的互不相交的区间，使得选取的区间数最大。
题解：贪心法是解决区间选点问题的常用方法。首先，将所有区间按照右端点从小到大进行排序。然后，从第一个区间开始，选择右端点最小的区间，并排除与该区间相交的其他区间。重复该过程，直到遍历完所有区间。选取的区间即为答案。核心代码段：

void intervalSelection(vector<pair<int, int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    vector<pair<int, int>> selectedIntervals;
    int lastEnd = INT_MIN;

    for (const auto& interval : intervals) {
        if (interval.first > lastEnd) {
            selectedIntervals.push_back(interval);
            lastEnd = interval.second;
        }
    }

    // 输出选取的区间
    for (const auto& interval : selectedIntervals) {
        cout << "[" << interval.first << ", " << interval.second << "]" << endl;
    }
}

题目：区间覆盖
题目描述：给定一组区间，找到最少的区间，使得它们的并集覆盖整个区间范围。
题解：贪心法是解决区间覆盖问题的常用方法。首先，将所有区间按照右端点从小到大进行排序。然后，从第一个区间开始，选择最小的右端点，并排除与该右端点相交的其他区间。重复该过程，直到覆盖整个区间范围。核心代码段：

void intervalCover(vector<pair<int, int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    vector<pair<int, int>> selectedIntervals;
    int lastEnd = INT_MIN;
    int minRight = INT_MAX;

    for (const auto& interval : intervals) {
        if (interval.first > lastEnd) {
            selectedIntervals.push_back(interval);
            lastEnd = interval.second;
            minRight = min(minRight, interval.second);
        }
    }

    // 输出选取的区间
    for (const auto& interval : selectedIntervals) {
        cout << "[" << interval.first << ", " << interval.second << "]" << endl;
    }
}

题目：区间分组
题目描述：给定一组区间，将它们划分为尽可能少的组，使得每组中的区间互不相交。
题解：贪心法是解决区间分组问题的常用方法。首先，将所有区间按照右端点从小到大进行排序。然后，遍历每个区间，将它与当前组中的最后一个区间进行比较。如果不相交，则将该区间加入当前组；如果相交，则新建一组，并将该区间加入新的组。重复该过程，直到遍历完所有区间。核心代码段：

void intervalGroup(vector<pair<int, int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    vector<vector<pair<int, int>>> groups;
    groups.push_back({intervals[0]});

    for (int i = 1; i < intervals.size(); ++i) {
        bool placed = false;
        for (auto& group : groups) {
            if (group.back().second < intervals[i].first) {
                group.push_back(intervals[i]);
                placed = true;
                break;
            }
        }
        if (!placed) {
            groups.push_back({intervals[i]});
        }
    }

    // 输出分组结果
    for (int i = 0; i < groups.size(); ++i) {
        cout << "Group " << i + 1 << ":" << endl;
        for (const auto& interval : groups[i]) {
            cout << "[" << interval.first << ", " << interval.second << "]" << endl;
        }
        cout << endl;
    }
}

（三）回溯

导语：回溯法是一种经典的算法思想，通常用于解决组合、排列、子集等问题。它通过尝试所有可能的选择来递归地搜索解空间，直到找到满足条件的解或遍历完所有可能的选择。本部分博客将汇总一些常见的使用回溯法解决的算法题，并给出它们的简要题解和核心代码段。

题目：全排列 - LeetCode 46
题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
题解：使用回溯法递归地生成所有可能的排列。从第一个位置开始，依次将每个数字放置在当前位置，然后继续递归处理下一个位置，直到所有位置都被填满。需要注意的是，在回溯之前要将当前位置的数字恢复原样。核心代码段：

void backtrack(vector<int>& nums, vector<vector<int>>& res, int start) {
    if (start == nums.size()) {
        res.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        backtrack(nums, res, start + 1);
        swap(nums[start], nums[i]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    backtrack(nums, res, 0);
    return res;
}

题目：组合总和 - LeetCode 39
题目描述：给定一个无重复元素的正整数数组 candidates 和一个目标整数 target，找出 candidates 中所有可以使数字和为 target 的组合。
题解：使用回溯法递归地生成所有可能的组合，并根据条件进行剪枝。从第一个位置开始，依次将每个数字放置在当前位置，然后继续递归处理下一个位置，直到满足条件或超出目标值。需要注意的是，在回溯之前要将当前位置的数字恢复原样。核心代码段：

void backtrack(vector<int>& candidates, vector<vector<int>>& res, vector<int>& combination, int target, int start) {
    if (target == 0) {
        res.push_back(combination);
        return;
    }
    for (int i = start; i < candidates.size(); i++) {
        if (candidates[i] > target) {
            break;
        }
        combination.push_back(candidates[i]);
        backtrack(candidates, res, combination, target - candidates[i], i);
        combination.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> combination;
    backtrack(candidates, res, combination, target, 0);
    return res;
}

题目：子集 - LeetCode 78
题目描述：给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
题解：使用回溯法递归地生成所有可能的子集。从第一个位置开始，依次选择包含当前元素和不包含当前元素两种情况，然后继续递归处理下一个位置。需要注意的是，在回溯之前要将当前元素加入或移除子集中。核心代码段：
```
void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<int>& subset, int start) {
    res.push_back(subset);
    for (int i = start; i < nums.size(); i++) {
        subset.push_back(nums[i]);
        backtrack(nums, res, subset, i + 1);
        subset.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> subset;
    backtrack(nums, res, subset, 0);
    return res;
}
```

（四）双指针问题

导语：双指针法是一种常用的算法思想，通过两个指针在数组或链表等数据结构上的移动，来解决一些特定的问题。本部分博客将汇总一些常见的算法题，并给出它们的双指针法解决方案。希望这些例题能够帮助你理解和掌握双指针法的应用。文章来源地址https://www.toymoban.com/news/detail-820138.html

题目：两数之和 - LeetCode 1
题目描述：给定一个升序排列的整数数组和一个目标值，找出数组中和为目标值的两个数的下标。
题解：使用两个指针分别指向数组的首尾元素，根据两个指针指向的元素之和与目标值的关系，逐步调整指针的位置，直到找到目标值或遍历完整个数组。核心代码段：

// 两数之和问题
vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 找到目标值，返回结果
            return {left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    // 没有找到目标值，返回默认结果
    return {-1, -1};
}

题目：反转字符串- LeetCode 344
题目描述：给定一个字符串，将其原地反转。
题解：使用两个指针分别指向字符串的首尾字符，交换两个指针所指向的字符，并逐步向中间移动指针，直到两个指针相遇。核心代码段：
```
// 反转字符串问题
void reverseString(string& s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}
```
题目：删除排序数组中的重复项- LeetCode 26
题目描述：给定一个有序数组，删除数组中重复的元素，使每个元素只出现一次，并返回新数组的长度。
题解：使用两个指针，一个指针用于遍历数组，另一个指针用于记录非重复元素的位置，当遍历到不重复的元素时，将其复制到非重复元素的位置，并更新非重复元素指针的位置。核心代码段：
```
// 删除排序数组中的重复项问题
int removeDuplicates(vector<int>& nums) {
    int i = 0, j = 1;
    while (j < nums.size()) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i + 1;
}
```
题目：盛最多水的容器- LeetCode 11
题目描述：给定一个非负整数数组，每个元素表示一个竖直线的高度，找出两条线与 x 轴共同构成的容器可以容纳的最大水量。
题解：使用两个指针分别指向数组的首尾元素，计算当前指针构成的容器的面积，并记录最大面积，然后根据两个指针所指向的元素的高度来决定移动哪个指针。核心代码段：
```
// 盛最多水的容器问题
int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxArea = 0;
    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        maxArea = max(maxArea, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}
```