当前位置:网站首页>leetcode刷题 (5.31) 字符串
leetcode刷题 (5.31) 字符串
2022-07-06 08:14:00 【Freya】
1. 反转字符串
题目:
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]
思路:
双指针,区别于反转链表(字符串是数组,在内存中连续分布)
笔记:
利用Python可以同时赋值的特性,数组的swap操作可以同时赋值
s[left], s[right] = s[right], s[left]
为什么不需要设置tmp变量来保存中间值?
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
因为赋值操作是等号从右往左的顺序执行,单纯把数值s.size() - 1, 0 赋给 s[left], s[right],而分开操作,一旦赋值s[i] = s[j],s[i]就会被新值覆盖,所以要先保存中间变量。
C++:
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]);
}
}
};
Python:
class Solution:
def reverseString(self, s: List[str]) -> None:
""" Do not return anything, modify s in-place instead. """
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
2. 反转字符串II
题目:
给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
输入:s = "abcdefg", k = 2
输出:"bacdfeg"
思路:
打破固有 for 循环 k++ 思维:i 每次移动 2*k 即可
题目的两个“如果”条件,可以理解为始终反转前k个(<=),然后前进2k步,难在反转前k个(<=)的处理:
对于C++,就是看到底是反转 [i, i + k) 还是 [i, n) ,可以用min()判断
对于Python,如果切片写的边界实际没达到(比如s[0:999]),默认返回实际字符串最后一个值,所以不用再判断 “剩余字符小于k的情形”。
笔记:
注:C++ reverse()函数是左开右闭,范围是 [first,last) 内全部反转。
重点不是考察reverse()操作,所以可以用库函数
C++:
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n; i += (2 * k)) {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
// 3. 剩余字符少于 k 个,则将剩余字符全部反转。—— min()取n的情况
reverse(s.begin() + i, s.begin() + min(i + k, n));
}
return s;
}
};
Python:
class Solution:
def reverseStr(self, s: str, k: int) -> str:
t = list(s)
for i in range(0, len(t), 2 * k):
# 就算字符串不足k长,也不会报错,返回的是实际长度
t[i: i + k] = reversed(t[i: i + k])
return "".join(t)
3. 替换空格
题目:
请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
输入:s = "We are happy."
输出:"We%20are%20happy."
思路:
看着很简单,就for循环检测一下遇到空格就换成字符就ok,但没有考虑到空格和新字符长度不一样的问题,所以不可能原地换,一定要扩空间。
用原地反向填充:先扩容size,再反向双指针填充可以最大程度减少空间复杂度。
但对于Python和JAVA,字符串都被设计成「不可变」的类型,(C++ string可变)即无法直接修改字符串的某一位字符,需要新建一个字符串实现(往新字符串里顺序填充即可)。
笔记:
注意审题:
s.resize(sOldSize + 2 * count);
为什么不是 3 * count ? “%20” 明明占3位?因为原本空格就占了1位
C++:
class Solution {
public:
string replaceSpace(string s) {
int count = 0;
int sOldSize = s.size();
// 统计空格数量
for (char c : s) {
if (c == ' ') count++;
}
// 修改 s 长度
s.resize(sOldSize + 2 * count);
int sNewSize = s.size();
// 倒序遍历修改
for(int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
if (s[j] != ' ')
s[i] = s[j];
else {
s[i - 2] = '%';
s[i - 1] = '2';
s[i] = '0';
i -= 2;
}
}
return s;
}
};
Python:
class Solution:
def replaceSpace(self, s: str) -> str:
res = []
for c in s:
if c == ' ': res.append("%20")
else: res.append(c)
return "".join(res)
边栏推荐
- Yyds dry goods inventory three JS source code interpretation eventdispatcher
- "Friendship and righteousness" of the center for national economy and information technology: China's friendship wine - the "unparalleled loyalty and righteousness" of the solidarity group released th
- On why we should program for all
- 1202 character lookup
- esRally国内安装使用避坑指南-全网最新
- 好用的TCP-UDP_debug工具下载和使用
- wincc7.5下载安装教程(Win10系统)
- hcip--mpls
- 在 uniapp 中使用阿里图标
- Parameter self-tuning of relay feedback PID controller
猜你喜欢
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Easy to use tcp-udp_ Debug tool download and use
[nonlinear control theory]9_ A series of lectures on nonlinear control theory
The Vice Minister of the Ministry of industry and information technology of "APEC industry +" of the national economic and information technology center led a team to Sichuan to investigate the operat
Nft智能合约发行,盲盒,公开发售技术实战--拼图篇
It's hard to find a job when the industry is in recession
Learn Arduino with examples
面向个性化需求的在线云数据库混合调优系统 | SIGMOD 2022入选论文解读
Circular reference of ES6 module
C language custom type: struct
随机推荐
Image fusion -- challenges, opportunities and Countermeasures
Analysis of pointer and array written test questions
Circuit breaker: use of hystrix
Binary tree creation & traversal
MySQL view tablespace and create table statements
Sanzi chess (C language)
Learn Arduino with examples
Data governance: 3 characteristics, 4 transcendence and 3 28 principles of master data
The resources of underground pipe holes are tight, and the air blowing micro cable is not fragrant?
[research materials] 2022 China yuancosmos white paper - Download attached
Common functions for PHP to process strings
Yu Xia looks at win system kernel -- message mechanism
matplotlib. Widgets are easy to use
C语言自定义类型:结构体
将 NFT 设置为 ENS 个人资料头像的分步指南
[Yugong series] February 2022 U3D full stack class 010 prefabricated parts
C language - bit segment
Grayscale upgrade tidb operator
二叉树创建 & 遍历
使用 BR 备份 TiDB 集群数据到兼容 S3 的存储