营销型网站设计价格,wordpress网页版入口看文,重庆景点攻略,网站设计制作费用今天#xff0c;带来字符串相关算法的讲解。文中不足错漏之处望请斧正#xff01;
理论基础点这里 1. 替换空格
题目描述#xff1a;请实现一个函数#xff0c;把字符串 s 中的每个空格替换成%20。 来源#xff1a;力扣#xff08;LeetCode#xff09; 难…今天带来字符串相关算法的讲解。文中不足错漏之处望请斧正
理论基础点这里 1. 替换空格
题目描述请实现一个函数把字符串 s 中的每个空格替换成%20。 来源力扣LeetCode 难度简单 提示 0 s 的长度 10000 示例 1 输入s “We are happy.” 输出“We%20are%20happy.”
题意转化
把字符串内的所有 替换为%20.
解决思路(抽象)
使用额外空间
创建一个空字符串, 遍历给定字符串s, 遇到字符的时候直接插入空字符串, 遇到空格的时候插入%20.
不使用额外空间
不用额外空间就要扩容统计空格个数每个空格替换成“%20”就意味着每个空格都需要额外两个字符的空间。
扩容后从后向前替换。
为什么是从后向前因为从前向后替换数组元素每次替换完都要把后面所有元素往后移动这就是O(n^2)的复杂度了。
编程实现(具体)
使用额外空间
class Solution {
public:string replaceSpace(string s) {string ret;for(char ch : s) {if(ch ) ret %20;else ret ch;}return ret;}
};不使用额外空间
class Solution {
public:string replaceSpace(string s) {// 扩容int count 0; //空格个数for(char ch : s) if(ch ) count;int oldSize s.size();s.resize(s.size() count * 2);int newSize s.size();// 从后向前替换for(int i oldSize - 1, j newSize - 1; i j; --i, --j) {if(s[i] ! ) {s[j] s[i];} else {s[j] 0;s[j - 1] 2;s[j - 2] %;j - 2; //多了两次操作j指针对应移动}}return s;}
};2. 反转单词
给你一个字符串 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) 额外空间复杂度的 原地 解法。
题意转化
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串.
解决思路(抽象)
首先, 要保证单词之间用单个空格连接(头尾没有空格).
原地处理的话, 可以使用双指针重新填充字符串:
fast遍历s拿字符遇到空格就跳过slow从头填充合法字符串
简单说, 每次遇到空格就自己把单词填充上, 再手动添加一个空格, 就可以满足题目要求.
单词顺序颠倒, 我们无法直接实现, 但我们能做什么?
颠倒字符串顺序颠倒单个单词顺序
前者就可以颠倒单词顺序, 只不过会让单个单词也颠倒, 我们再次颠倒每个单词, 不就得到了题目要求的字符串了吗. 比如 如 hello world , 整体反转后是 dlrow olleh然后对单词反转 world hello . 简单说, 先总体反转, 再局部反转.
编程实现(具体)
最后一个单词, 可以在反转单词内部顺序的循环中处理, 也可以跳出循环单独处理.
最后一个单词反转单词内部顺序的循环中处理:
class Solution {
public:string reverseWords(string s) {//双指针重新填充字符串int slow; // 填充字符串int fast; // 遍历sfor (slow 0, fast 0; fast s.size(); fast) {if (s[fast] ) continue; // 如果是空格就跳过// 填充当前单词while (fast s.size() s[fast] ! ) s[slow] s[fast];// 填充空格(只有最后一个单词后不需要填充)s[slow] ;}s.resize(slow - 1); // 去掉多余的空格(最后一个单词后不需要填充, 但我们默认填充了)cout 处理后的字符串: s endl;// 整体反转reverse(s.begin(), s.end());// 局部反转int wordBegin 0;int wordEnd 0;while (wordEnd s.size()) {if (s[wordEnd] || wordEnd s.size()) {reverse(s.begin() wordBegin, s.begin() wordEnd);wordBegin wordEnd 1;wordEnd wordBegin;}wordEnd;}return s;}
};最后一个单词跳出循环单独处理:
class Solution {
public:string reverseWords(string s) {//双指针重新填充字符串int slow; // 填充字符串int fast; // 遍历sfor (slow 0, fast 0; fast s.size(); fast) {if (s[fast] ) continue; // 如果是空格就跳过// 填充当前单词while (fast s.size() s[fast] ! ) s[slow] s[fast];// 填充空格(只有最后一个单词后不需要填充)s[slow] ;}s.resize(slow - 1); // 去掉多余的空格(最后一个单词后不需要填充, 但我们默认填充了)cout 处理后的字符串: s endl;// 整体反转reverse(s.begin(), s.end());// 局部反转int wordBegin 0;int wordEnd 0;while (wordEnd s.size()) {if (s[wordEnd] ) {reverse(s.begin() wordBegin, s.begin() wordEnd);wordBegin wordEnd 1;wordEnd wordBegin;}wordEnd;}reverse(s.begin() wordBegin, s.begin() wordEnd); // 反转最后一个单词return s;}
};今天的分享就到这里了感谢您能看到这里。
这里是培根的blog期待与你共同进步
