当前位置：首页 > 文章列表 > 科技周边 > 人工智能 > LeetCode229周赛题解：字符串与动态规划

LeetCode229周赛题解：字符串与动态规划

2026-01-11 08:30:52 0浏览收藏

珍惜时间，勤奋学习！今天给大家带来《LeetCode 229周赛题解：字符串与动态规划》，正文内容主要涉及到等等，如果你正在学习科技周边，或者是对科技周边有疑问，欢迎大家关注我！后面我会持续更新相关内容的，希望都能帮到正在学习的大家！

大家好！今天我们来深入探讨 LeetCode 第 229 周赛中的前三道题目。这次的周赛题目覆盖了字符串处理和动态规划 (DP) 等核心算法概念，旨在考察参赛者在实际问题中应用算法的能力。我们将详细分析每道题目的解题思路、代码实现以及一些可能的优化方向，帮助大家更好地掌握这些算法技巧。无论你是算法新手还是 LeetCode 老手，相信你都能从本文中有所收获。准备好了吗？让我们开始吧！

关键要点

字符串交替合并：掌握双指针技巧，高效地合并两个字符串，并处理长度不一致的情况。

最小操作数：理解问题本质，通过预处理计算前缀和，优化时间复杂度。

动态规划求解最大得分：识别问题的 DP 特征，设计状态转移方程，并注意边界条件的处理。

LeetCode 229 周赛算法详解

1. 交替合并字符串

这道题目的核心在于字符串的交替合并。

LeetCode 229周赛算法解析：字符串与动态规划

给定两个字符串 word1 和 word2，我们需要将它们交替合并成一个新的字符串。如果其中一个字符串比另一个长，那么将剩余的部分附加到合并后的字符串末尾。

解题思路：

最直接的思路是使用双指针分别指向 word1 和 word2 的首字符，然后交替地将字符添加到结果字符串中。当其中一个指针到达字符串末尾时，将另一个字符串的剩余部分添加到结果字符串中。

代码实现（C++）：

<code>class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ans = "";
        int i = 0, j = 0;
        while (i </code>

代码解析：

ans：用于存储合并后的字符串。
i、j：分别指向 word1 和 word2 的当前字符。
while 循环：只要 i 或 j 没有到达字符串末尾，就继续循环。
if 语句：分别判断 i 和 j 是否越界，如果没有越界，则将当前字符添加到 ans 中，并将指针后移。
最后，返回合并后的字符串 ans。

复杂度分析：

时间复杂度：O(m+n)，其中 m 和 n 分别是 word1 和 word2 的长度。
空间复杂度：O(1)，只使用了常数级别的额外空间。

总结：

这道题目相对简单，主要考察的是字符串操作和双指针技巧。理解题意后，代码实现并不复杂。在面试或笔试中，遇到类似的题目，一定要注意边界条件的处理。

2. 移动所有球到每个盒子所需的最小操作数

这道题目要求计算将所有球移动到每个盒子所需的最小操作数。

LeetCode 229周赛算法解析：字符串与动态规划

给定一个二进制字符串 boxes，其中 '1' 代表盒子中有球，'0' 代表盒子是空的。对于每个盒子，我们需要计算将所有球移动到该盒子所需的最小操作数。

解题思路：

对于每个盒子 i，我们需要计算所有其他盒子中的球移动到 i 所需的操作数。一个直接的想法是遍历所有其他盒子，并计算它们到 i 的距离。但是，这样的时间复杂度是 O(n^2)，其中 n 是盒子的数量。为了优化时间复杂度，我们可以使用前缀和的思想。

具体步骤：

预处理：计算每个位置左侧和右侧的球的数量。
计算操作数：对于每个盒子 i，使用预处理的信息计算将所有球移动到 i 所需的操作数。

代码实现（C++）：

<code>class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> ans(n, 0);
        vector<int> left(n, 0), right(n, 0);

        int cnt = 0, sum = 0;
        for (int i = 1; i = 0; i--) {
            if (boxes[i + 1] == '1') {
                cnt++;
                sum += n - 2 - i;
            }
            right[i] = sum + cnt;
        }

        for (int i = 0; i </int></int></int></code>

代码解析：

left[i]：存储将所有球移动到盒子 i 左侧的操作数。
right[i]：存储将所有球移动到盒子 i 右侧的操作数。
两个 for 循环：分别计算 left 和 right 数组。
最后一个 for 循环：计算每个盒子的最小操作数。

复杂度分析：

时间复杂度：O(n)，其中 n 是盒子的数量。
空间复杂度：O(n)，使用了额外空间存储 left 和 right 数组。

总结：

这道题目考察的是问题转化和前缀和的思想。通过预处理计算前缀和，我们可以将时间复杂度从 O(n^2) 降低到 O(n)，从而提高算法的效率。

3. 乘法运算的最大得分

这道题目涉及到最大化乘法运算的得分。

LeetCode 229周赛算法解析：字符串与动态规划

给定两个整数数组 nums 和 multipliers，长度分别为 n 和 m，其中 m nums 的第一个或最后一个元素，将其与 multipliers 数组的当前元素相乘，然后从 nums 中移除该元素。我们的目标是最大化总得分。

解题思路：

这道题目可以使用动态规划来解决。关键在于识别问题的 DP 特征，并设计合适的状态转移方程。

状态定义：

dp[i][j]：表示使用了 multipliers 数组的前 i 个元素，并且 nums 数组的左侧使用了 j 个元素时，所能获得的最大得分。

状态转移方程：

在每一步操作中，我们有两种选择：

选择 nums 的第一个元素：dp[i][j] = dp[i-1][j-1] + multipliers[i] * nums[j]
选择 nums 的最后一个元素：dp[i][j] = dp[i-1][j] + multipliers[i] * nums[n - (i - j) - 1]

我们需要选择两种选择中得分较高的那个，因此状态转移方程为：

dp[i][j] = max(dp[i-1][j-1] + multipliers[i] * nums[j], dp[i-1][j] + multipliers[i] * nums[n - (i - j) - 1])

代码实现（C++）：

<code>class Solution {
public:
    vector<int> Nums, Mul;
    int n, m;
    int dp[1002][1002];

    int ok(int l, int r) {
        if (l + r == m) return 0;
        if (dp[l][r] != -1e9) return dp[l][r];
        int ans = max(ok(l + 1, r) + Mul[l + r] * Nums[l], ok(l, r + 1) + Mul[l + r] * Nums[n - r - 1]);
        return dp[l][r] = ans;
    }

    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        Nums = nums;
        Mul = multipliers;
        n = nums.size();
        m = multipliers.size();
        for (int i = 0; i </int></int></int></code>

代码解析：

dp[i][j]：存储最大得分。
使用递归 + 记忆化搜索实现动态规划，避免重复计算。
注意处理边界条件和初始化 DP 数组。

复杂度分析：

时间复杂度：O(m^2)，其中 m 是 multipliers 的长度。
空间复杂度：O(m^2)，使用了额外空间存储 DP 数组。

总结：

这道题目是典型的 DP 问题，关键在于状态定义和状态转移方程的设计。掌握了 DP 的基本思想，就可以轻松解决这类问题。

核心功能

LeetCode

LeetCode 提供了以下核心功能：

海量题库：LeetCode 拥有一个庞大的题库，包含各种难度级别的算法题目，可以满足不同水平的用户的需求。
在线评测：LeetCode 提供在线评测功能，用户可以提交代码并立即获得结果，方便调试和优化。
讨论区：LeetCode 拥有一个活跃的讨论区，用户可以在这里交流解题思路、分享代码等。
模拟面试：LeetCode Premium 提供模拟面试功能，帮助用户熟悉面试流程和提高面试技巧。

Sketchpad

Sketchpad 提供了以下核心功能：

多种绘图工具：Sketchpad 提供了多种绘图工具，例如铅笔、刷子、形状等，可以满足不同的绘图需求。
颜色选择器：Sketchpad 提供了一个颜色选择器，用户可以自由选择颜色。
图层管理：Sketchpad 支持图层管理，用户可以创建和编辑多个图层。
导出功能：Sketchpad 支持导出图片，用户可以将作品保存到本地。

使用场景

LeetCode

LeetCode 的使用场景包括：

算法学习：LeetCode 是一个学习算法的绝佳平台，通过练习各种算法题目，可以提高编程能力。
面试准备：LeetCode 是一个面试准备的必备工具，通过刷题可以熟悉面试中常见的算法题目。
日常练习：LeetCode 可以作为日常练习的平台，保持编程思维的活跃。

Sketchpad

Sketchpad 的使用场景包括：

快速绘制草图：Sketchpad 可以用于快速绘制草图，例如产品原型、流程图等。
在线协作：Sketchpad 支持多人在线协作，方便团队进行头脑风暴和设计讨论。
教学演示：Sketchpad 可以用于教学演示，例如数学公式、几何图形等。

相关问题

动态规划 (DP) 在算法竞赛和实际开发中的应用？

动态规划 (DP) 是一种强大的算法设计技巧，广泛应用于算法竞赛和实际开发中。它的核心思想是将复杂问题分解为更小的子问题，并存储子问题的解，从而避免重复计算，提高算法效率。理解DP首先要理解重叠子问题和最优子结构两个概念重叠子问题：如果一个问题可以分解成若干个子问题，且这些子问题之间存在重叠，即某些子问题会被多次计算，那么这个问题就适合使用动态规划来解决。最优子结构：如果一个问题的最优解包含其子问题的最优解，那么这个问题就具有最优子结构性质，也适合使用动态规划来解决。应用场景：最优化问题：动态规划常用于解决最优化问题，例如：最短路径问题：寻找图中两个节点之间的最短路径。背包问题：在给定容量的背包中放入价值最高的物品。最长公共子序列问题：寻找两个字符串的最长公共子序列。计数问题：动态规划也可以用于解决计数问题，例如：组合计数问题：计算从 n 个不同元素中选择 k 个元素的方式数。路径计数问题：计算从一个节点到另一个节点的路径数。决策问题：动态规划还可以用于解决决策问题，例如：最优决策问题：在多个选项中选择最优的决策。资源分配问题：如何合理地分配资源以获得最大效益。动态规划的实现方式：自顶向下（记忆化搜索）：从问题的顶层开始，递归地解决子问题。为了避免重复计算，使用一个表格来存储已经计算过的子问题的解。自底向上（递推）：从问题的底层开始，逐步计算子问题的解，直到计算出整个问题的解。总结：动态规划是一种非常重要的算法设计技巧，掌握它可以帮助我们解决很多复杂的问题。在实际应用中，我们需要根据问题的特点选择合适的实现方式，并注意边界条件的处理。

算法竞赛中常用的算法技巧有哪些？

算法竞赛考察的是参赛者运用计算机科学中的算法和数据结构来解决问题的能力。除了扎实的基础知识，一些常用的算法技巧也能帮助你在比赛中脱颖而出：分治法：将一个复杂的问题分解成两个或更多的相同或相似的子问题，再把子问题分解成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧在处理大规模数据时非常有效。贪心算法：在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心算法不一定总是能找到全局最优解，但对于某些问题，它是非常有效的。二分查找：用于在有序数组中查找特定元素的搜索算法。它的时间复杂度为 O(log n)，比线性查找更快。排序算法：熟练掌握各种排序算法（如快速排序、归并排序、堆排序等）及其适用场景。排序是很多算法的基础，能够为后续操作提供便利。搜索算法：包括深度优先搜索（DFS）和广度优先搜索（BFS）。它们常用于解决图论问题和组合问题。图论算法：掌握常见的图论算法，如最短路径算法（Dijkstra、Floyd-Warshall）、最小生成树算法（Prim、Kruskal）等。数据结构：熟练使用各种数据结构，如数组、链表、栈、队列、堆、树、图等。不同的数据结构适用于不同的问题，选择合适的数据结构可以提高算法效率。动态规划 (DP)：将复杂问题分解为更小的子问题，并存储子问题的解，从而避免重复计算，提高算法效率。动态规划常用于解决最优化问题。位运算：巧妙使用位运算可以提高算法的效率。例如，使用位运算可以快速计算一个数的平方、判断一个数是否为 2 的幂等。数学知识：一些数学知识在算法竞赛中也很有用，如数论、组合数学、线性代数等。代码模板在LeetCode等算法测试网站上会有不少模板，合理利用代码模板能节省很多时间

理论要掌握，实操不能落！以上关于《LeetCode229周赛题解：字符串与动态规划》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！