算法打卡第八天

26.四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

• 解题思路：

和三数之和类似，使用双指针法，在三数之和的基础上再套一层for循环

1. 排序

首先对数组进行排序，这样可以方便后续的去重操作，并且能够利用双指针快速查找满足条件的四元组。

2. 双层循环

• 外层循环：固定第一个数 nums[k]。为了避免重复计算，当 nums[k] 与前一个数相同时，直接跳过。
• 内层循环：固定第二个数 nums[i]。同样为了避免重复计算，当 nums[i] 与前一个数相同时，跳过。

3. 双指针

在固定了 nums[k] 和 nums[i] 之后，使用双指针 left 和 right 分别指向剩余部分的两端：

• 如果 nums[k] + nums[i] + nums[left] + nums[right] 小于目标值，说明需要更大的数，因此将 left 指针右移。
• 如果大于目标值，说明需要更小的数，因此将 right 指针左移。
• 如果等于目标值，将这四个数加入结果集，并移动 left 和 right 指针，同时跳过重复的值以避免重复结果。

4. 剪枝

• 外层剪枝：如果 nums[k] 已经大于目标值且为正数，后续的数只会更大，因此可以直接退出外层循环。
• 内层剪枝：如果 nums[k] + nums[i] 已经大于目标值且为正数，后续的数只会更大，因此可以直接退出内层循环。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 使用双指针
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        // 存储结果集
        vector<vector<int>> result;
        // 排序
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++)
        {
            // 剪枝处理 nums[k] >= 0避免负数相加跳过结果集
            if (nums[k] > target && nums[k] >= 0)
            {
                break;
            }
            //  k去重
            if (k > 0 && nums[k] == nums[k - 1])
            {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++)
            {
                // 2级剪枝处理  k和i现在是一个整体
                if (nums[k] + nums[i] > target &&  nums[i] >= 0)
                {
                    break;
                }
                //  i去重
                if (i > k + 1 && nums[i] == nums[i - 1])
                {
                    continue;
                }
                // 双指针定义
                int left = i + 1;
                int right = nums.size() - 1;
                while (left < right) // 指针相遇结束
                {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if (long(nums[k]) + nums[i] + nums[left] + nums[right] < target)
                    {
                        left++;
                    }
                    else if (long(nums[k]) + nums[i] + nums[left] + nums[right] > target)
                    {
                        right--;
                    }
                    // 找到目标 添加到结果集里面
                    else
                    {
                        result.push_back(vector<int>{nums[k], 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;
    }
};

• 时间复杂度: O(n^3)
• 空间复杂度: O(1)

27.反转字符串

（力扣344题）

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]

• 解题思路

1. 双指针初始化： 定义两个指针 i 和 j，i 指向字符串的开头（索引 0），j 指向字符串的末尾（索引为字符串长度减 1）。
2. 循环交换字符： 通过 for 循环，当 i 小于字符串长度的一半时，交换 i 和 j 指针所指向的字符。每次循环后，i 向后移动（递增），j 向前移动（递减）。
3. 终止条件： 当 i 达到字符串长度的一半时，循环结束，此时字符串已经完成反转。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 使用双指针
class Solution {
public:
    void reverseString(vector<char>& s) 
    {
        for(int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }
};
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

28. 反转字符串II

（力扣541题)

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

• 解题思路

1. 定义反转函数：实现一个通用的 reverse 函数，用于反转字符串中指定范围的字符。通过双指针法，从两端向中间交换字符，直到两个指针相遇。
2. 遍历字符串：使用一个循环，每次跳过 2k 个字符，处理字符串的每一段。
3. 分情况反转：
   • 如果当前段的长度大于或等于 k，则反转从当前索引 i 到 i + k - 1 的子串。
   • 如果剩余字符不足 k 个，则反转从当前索引 i 到字符串末尾的所有字符。
4. 返回结果：完成所有段的反转后，返回最终反转后的字符串。

代码

#include <iostream>
#include <algorithm>
using namespace std;
class Solution
{
public:
    // 实现reverse库函数
    void reverse(string &s, int start, int end)
    {
        for (int i = start, j = end; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }
    string reverseStr(string s, int k)
    {

        for (int i = 0; i < s.size(); i += 2 * k)
        {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            if (i + k <= s.size())
            {
                reverse(s, i, i + k - 1);   //-1因为下标从0开始
            }
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            else
            {
                reverse(s, i , s.size() - 1 );
            }
        }
        return s;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)或O(n), 取决于使用的语言中字符串是否可以修改.

#include <iostream>
using namespace std;
// 双指针法
int main()
{
    // 从标准输入读取字符串，直到输入结束
    string s;

    while (cin >> s)
    {
        // 初始化旧字符串的索引，从最后一个字符开始
        int sOldIndex = s.size() - 1;
        //  统计数字的个数
        int count = 0;

        // 遍历字符串，统计数字字符的数量
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                count++;
            }
        }

        // 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
        // resize用于调整字符串的大小 *5因为因为数字本身已经占了1个位置
        s.resize(s.size() + count * 5);
        //  初始化新字符串的索引，从最后一个字符开始
        int sNewIndex = s.size() - 1;
        //    如果是数字字符 从后往前插入"number"
        while (sOldIndex >= 0)
        {
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9')
            {
                s[sNewIndex--] = 'r';
                s[sNewIndex--] = 'e';
                s[sNewIndex--] = 'b';
                s[sNewIndex--] = 'm';
                s[sNewIndex--] = 'u';
                s[sNewIndex--] = 'n';
            }
            // 如果不是数字字符，直接复制到新位置
            else
            {
                s[sNewIndex--] = s[sOldIndex];
            }

            // 旧字符串索引向前移动
            sOldIndex--;
        }
        cout << s << endl;
    }
    return 0;
}

29 替换数字

(卡码网54题)

题目描述

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

输入描述

输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

打印一个新的字符串，其中每个数字字符都被替换为了number

输入示例

a1b2c3

输出示例

anumberbnumbercnumber

提示信息

数据范围：
1 <= s.length < 10000。

• 解题思路

1.输入处理

使用 cin >> s 逐行读取输入字符串。cin >> s 会读取以空白字符分隔的单词，因此每行输入被视为一个独立的字符串。

2. 统计数字字符数量

在处理每行字符串时，首先统计字符串中数字字符的数量。通过遍历字符串，检查每个字符是否在 '0' 到 '9' 之间，统计数字字符的数量 count。

3. 调整字符串大小

根据统计的数字字符数量，调整字符串的大小。每个数字字符替换为 "number" 后，字符串长度会增加 5（"number" 的长度为 6，而数字本身占 1 个位置，因此净增加 5）。因此，调用 s.resize(s.size() + count * 5) 来扩充字符串的大小。

4. 从后往前替换

使用双指针法从后往前处理字符串：

• sOldIndex：从原始字符串的末尾开始，逐个字符向前遍历。
• sNewIndex：从新字符串的末尾开始，逐个字符向前插入。

对于每个字符：

• 如果是数字字符，从后往前插入 "number"。
• 如果不是数字字符，直接将该字符复制到新位置。

5. 输出结果

处理完每行字符串后，输出替换后的结果。

代码

#include <iostream>
using namespace std;
// 双指针法
int main()
{
    // 从标准输入读取字符串，直到输入结束
    string s;

    while (cin >> s)
    {
        // 初始化旧字符串的索引，从最后一个字符开始
        int sOldIndex = s.size() - 1;
        //  统计数字的个数
        int count = 0;

        // 遍历字符串，统计数字字符的数量
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                count++;
            }
        }

        // 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
        // resize用于调整字符串的大小 *5因为因为数字本身已经占了1个位置
        s.resize(s.size() + count * 5);
        //  初始化新字符串的索引，从最后一个字符开始
        int sNewIndex = s.size() - 1;
        //    如果是数字字符 从后往前插入"number"
        while (sOldIndex >= 0)
        {
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9')
            {
                s[sNewIndex--] = 'r';
                s[sNewIndex--] = 'e';
                s[sNewIndex--] = 'b';
                s[sNewIndex--] = 'm';
                s[sNewIndex--] = 'u';
                s[sNewIndex--] = 'n';
            }
            // 如果不是数字字符，直接复制到新位置
            else
            {
                s[sNewIndex--] = s[sOldIndex];
            }

            // 旧字符串索引向前移动
            sOldIndex--;
        }
        cout << s << endl;
    }
    return 0;
}

补充知识点：resize函数

• 函数原型

void resize(size_type n, char c = char());

• n：新的字符串长度。

• c：（可选）如果字符串长度增加，新添加的字符将被初始化为 c。如果省略，默认使用空字符（'\0'）。

• 功能

  • 增加字符串长度：如果 n 大于当前字符串的长度，resize 会在字符串末尾添加指定的字符（或默认的空字符），直到字符串长度达到 n。
  • 减少字符串长度：如果 n 小于当前字符串的长度，resize 会截断字符串，使其长度变为 n。

30.翻转字符串里的单词

（力扣151题)

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

• 解题思路

  本题的目标是反转字符串中的单词顺序，同时去除多余的空格。我们可以通过以下步骤实现：

  1. 去除多余空格：

     • 使用双指针法，一个指针（slow）用于记录处理后的字符串位置，另一个指针（fast）用于遍历原始字符串。
     • 遇到非空格字符时，将其复制到 slow 指针的位置，并在单词之间添加一个空格。
     • 最后调整字符串的大小，去除多余的空格。

  2. 反转整个字符串：

     • 使用双指针法，一个指针从字符串开头，另一个从结尾，交换两个指针所指向的字符，直到两个指针相遇。

  3. 反转每个单词：

     • 遍历字符串，以空格为分隔符，找到每个单词的起始和结束位置。
     • 对每个单词单独进行反转

代码

// 反转字符串中的单词
#include <iostream>
#include <algorithm>
using namespace std;
// 双指针法
class Solution
{
public:
    // 反转函数
    void reserse(string &s, int begin, int end) 翻转，区间写法：左闭右闭 []
    {
        for (int i = begin, j = end; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }
    // 翻转，区间写法：左闭右闭 []
    void removeExtraSpaces(string &s)
    {
        // 慢指针
        int slow = 0;
        // 快指针遍历字符串
        for (int i = 0; i < s.size(); ++i)
        {
            // 遇到非空格字符，开始处理
            if (s[i] != ' ')
            { // 如果不是第一个单词，添加一个空格
                if (slow != 0)
                {
                    s[slow++] = ' ';
                }
                // 补上该单词，直到遇到空格
                while (i < s.size() && s[i] != ' ')
                {
                    s[slow++] = s[i++];
                }
            }
        }
        // slow的大小即为去除多余空格后的大小。
        s.resize(slow);
    }
    string reverseWords(string s)
    {
        // 去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        removeExtraSpaces(s);
        // 反转函数
        reserse(s, 0, s.size() - 1);
        // removeExtraSpaces后保证第一个单词的开始下标一定是0
        int start = 0;
        for (int i = 0; i <= s.size(); i++)
        {
            // / 到达空格或字符串尾部，说明一个单词结束
            if (s[i] == ' ' || i == s.size())   //i == s.size()用于检查是否到达字符串末尾，确保最后一个单词也被正确处理。
            {
                reserse(s, start, i - 1);
                // 更新start
                start = i + 1;
            }
        }
        return s;
    }
};

int main() 
{
    Solution sol;
    string s = "the sky is blue";
    cout << sol.reverseWords(s) << endl; // 输出：blue is sky the
    return 0;
}

• 时间复杂度: O(n)
• 空间复杂度: O(1) 或 O(n)，取决于语言中字符串是否可变