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

admin 百科 2025-12-19 17

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

关键要点

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

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

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

LeetCode 229 周赛算法详解

1. 交替合并字符串

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

☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 免费无限量使用 DeepSeek R1 模型☜☜☜

LeetCode 229周赛算法解析：字符串与动态规划-第1张图片-佛山资讯网

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

解题思路：

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

代码实现（C++）：

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ans = "";
        int i = 0, j = 0;
        while (i < word1.size() || j < word2.size()) {
            if (i < word1.size()) {
                ans += word1[i++];
            }
            if (j < word2.size()) {
                ans += word2[j++];
            }
        }
        return ans;
    }
};

登录后复制

代码解析：

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周赛算法解析：字符串与动态规划-第2张图片-佛山资讯网

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

解题思路：

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

具体步骤：

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

代码实现（C++）：

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 < n; i++) {
            if (boxes[i - 1] == '1') {
                cnt++;
                sum += i - 1;
            }
            left[i] = sum + cnt;
        }

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

        for (int i = 0; i < n; i++) {
            ans[i] = left[i] + right[i];
        }

        return ans;
    }
};

登录后复制

代码解析：