算法打卡第八天
26.四数之和给你一个由 n 个整数构成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 , nums, nums, nums] （若两个四元组元素一一对应，则认为两个四元组重复）：
[*]0 <= a, b, c, d < n
[*]a、b、c 和 d 互不相同
[*]nums + nums + nums + nums == target
你可以按 恣意次序 返回复案 。
示例 1：
输入：nums = , target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = , target = 8
输出：[]
[*]解题思绪：
和三数之和类似，使用双指针法，在三数之和的基础上再套一层for循环
1. 排序
起首对数组举行排序，这样可以方便后续的去重操作，并且可以或许利用双指针快速查找满足条件的四元组。
2. 双层循环
[*]外层循环：固定第一个数 nums。为了制止重复计算，当 nums 与前一个数相同时，直接跳过。
[*]内层循环：固定第二个数 nums。同样为了制止重复计算，当 nums 与前一个数相同时，跳过。
3. 双指针
在固定了 nums 和 nums 之后，使用双指针 left 和 right 分别指向剩余部分的两端：
[*]如果 nums + nums + nums + nums 小于目标值，阐明需要更大的数，因此将 left 指针右移。
[*]如果大于目标值，阐明需要更小的数，因此将 right 指针左移。
[*]如果等于目标值，将这四个数加入效果集，并移动 left 和 right 指针，同时跳过重复的值以制止重复效果。
4. 剪枝
[*]外层剪枝：如果 nums 已经大于目标值且为正数，后续的数只会更大，因此可以直接退出外层循环。
[*]内层剪枝：如果 nums + nums 已经大于目标值且为正数，后续的数只会更大，因此可以直接退出内层循环。
代码
#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 >= 0避免负数相加跳过结果集
if (nums > target && nums >= 0)
{
break;
}
//k去重
if (k > 0 && nums == nums)
{
continue;
}
for (int i = k + 1; i < nums.size(); i++)
{
// 2级剪枝处理k和i现在是一个整体
if (nums + nums > target &&nums >= 0)
{
break;
}
//i去重
if (i > k + 1 && nums == nums)
{
continue;
}
// 双指针定义
int left = i + 1;
int right = nums.size() - 1;
while (left < right) // 指针相遇结束
{
// nums + nums + nums + nums > target 会溢出
if (long(nums) + nums + nums + nums < target)
{
left++;
}
else if (long(nums) + nums + nums + nums > target)
{
right--;
}
// 找到目标 添加到结果集里面
else
{
result.push_back(vector<int>{nums, nums, nums, nums});
// 去重
while (left < right && nums == nums)
{
left++;
}
while (left < right && nums == nums)
{
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"]
[*]解题思绪
[*]双指针初始化： 定义两个指针 i 和 j，i 指向字符串的开头（索引 0），j 指向字符串的末尾（索引为字符串长度减 1）。
[*]循环交换字符： 通过 for 循环，当 i 小于字符串长度的一半时，交换 i 和 j 指针所指向的字符。每次循环后，i 向后移动（递增），j 向前移动（递减）。
[*]终止条件： 当 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, s);
}
}
};
};
[*]时间复杂度: 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"
[*]解题思绪
[*]定义反转函数：实现一个通用的 reverse 函数，用于反转字符串中指定范围的字符。通过双指针法，从两端向中心交换字符，直到两个指针相遇。
[*]遍历字符串：使用一个循环，每次跳过 2k 个字符，处置惩罚字符串的每一段。
[*]分情况反转：
[*]如果当前段的长度大于或等于 k，则反转从当前索引 i 到 i + k - 1 的子串。
[*]如果剩余字符不足 k 个，则反转从当前索引 i 到字符串末尾的全部字符。
[*]返回效果：完成全部段的反转后，返回最终反转后的字符串。
代码
#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, s);
}
}
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 >= '0' && s <= '9')
{
count++;
}
}
// 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
// resize用于调整字符串的大小 *5因为因为数字本身已经占了1个位置
s.resize(s.size() + count * 5);
//初始化新字符串的索引，从最后一个字符开始
int sNewIndex = s.size() - 1;
// 如果是数字字符 从后往前插入"number"
while (sOldIndex >= 0)
{
if (s >= '0' && s <= '9')
{
s = 'r';
s = 'e';
s = 'b';
s = 'm';
s = 'u';
s = 'n';
}
// 如果不是数字字符，直接复制到新位置
else
{
s = s;
}
// 旧字符串索引向前移动
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"。
[*]如果不是数字字符，直接将该字符复制到新位置。
[*]输出效果
处置惩罚完每行字符串后，输出更换后的效果。
代码
#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 >= '0' && s <= '9')
{
count++;
}
}
// 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
// resize用于调整字符串的大小 *5因为因为数字本身已经占了1个位置
s.resize(s.size() + count * 5);
//初始化新字符串的索引，从最后一个字符开始
int sNewIndex = s.size() - 1;
// 如果是数字字符 从后往前插入"number"
while (sOldIndex >= 0)
{
if (s >= '0' && s <= '9')
{
s = 'r';
s = 'e';
s = 'b';
s = 'm';
s = 'u';
s = 'n';
}
// 如果不是数字字符，直接复制到新位置
else
{
s = s;
}
// 旧字符串索引向前移动
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) 额外空间复杂度的 原地 解法。
[*] 解题思绪
本题的目标是反转字符串中的单词次序，同时去除多余的空格。我们可以通过以下步骤实现：
[*] 去除多余空格：
[*]使用双指针法，一个指针（slow）用于记载处置惩罚后的字符串位置，另一个指针（fast）用于遍历原始字符串。
[*]碰到非空格字符时，将其复制到 slow 指针的位置，并在单词之间添加一个空格。
[*]最后调解字符串的巨细，去除多余的空格。
[*] 反转整个字符串：
[*]使用双指针法，一个指针从字符串开头，另一个从结尾，交换两个指针所指向的字符，直到两个指针相遇。
[*] 反转每个单词：
[*]遍历字符串，以空格为分隔符，找到每个单词的起始和结束位置。
[*]对每个单词单独举行反转
代码
// 反转字符串中的单词
#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, s);
}
}
// 翻转，区间写法：左闭右闭 []
void removeExtraSpaces(string &s)
{
// 慢指针
int slow = 0;
// 快指针遍历字符串
for (int i = 0; i < s.size(); ++i)
{
// 遇到非空格字符，开始处理
if (s != ' ')
{ // 如果不是第一个单词，添加一个空格
if (slow != 0)
{
s = ' ';
}
// 补上该单词，直到遇到空格
while (i < s.size() && s != ' ')
{
s = s;
}
}
}
// 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 == 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)，取决于语言中字符串是否可变
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]