代码随想录算法训练营Day8 | LeetCode344 反转字符串、LeetCode541 反转字符串II、卡码网:54.替换数字、LeetCode151 翻转字符串里的单词、卡码网:55.右旋转字符串

Posted by 慕念 on February 28, 2024

LeetCode344 反转字符串

题目链接/文章讲解/视频讲解:https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html

✌思路:双指针,i指开头,j指结尾,交换,i往右移,j往左移,直到j≤i

344.反转字符串

class Solution(object):
    def reverseString(self, s):
        """
        
        :type s: List[str]
        
        :rtype: None Do not return anything, modify s in-place instead.
        
        """
        
        j = len(s) - 1
        i = 0
        while j > i:
            tmp = s[i]
            s[i] = s[j]
            s[j] = tmp
            i += 1
            j -= 1
        return s

LeetCode541 反转字符串II

题目链接/文章讲解/视频讲解:https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html

✌思路:按照题目意思分类讨论,剩余字符少于k个和其他情况

class Solution(object):
    def reverseStr(self, s, k):
        """
        
        :type s: str
        
        :type k: int
        
        :rtype: str
        
        """
        
        s = list(s)
        for i in range(0, len(s), 2 * k):
            rest = len(s) - i
            if rest < k:    # 剩余字符少于 k 个
                
                j = len(s) - 1
                while i < j:
                    s[i], s[j] = s[j], s[i]
                    i += 1
                    j -= 1
                break
            # 剩余字符>=k个    
            
            j = i + k - 1
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1
        return ''.join(s) 	# list转string

优化版本:

  1. 使用range(start, end, step)来确定需要调换的初始位置

  2. 对于字符串s = ‘abc’,如果使用s[0:999] ===> ‘abc’。字符串末尾如果超过最大长度,则会返回至字符串最后一个值,这个特性可以避免一些边界条件的处理。

  3. 用切片整体替换,而不是一个个替换.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        
        def reverse_substring(text):
            left, right = 0, len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        
        res = list(s)

        for cur in range(0, len(s), 2 * k):
            res[cur: cur + k] = reverse_substring(res[cur: cur + k])
        
        return ''.join(res)

卡码网:54.替换数字

题目链接/文章讲解:https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html

✌思路:isdigit()判断字符串是否是数字

s = list(input())

for i in range(len(s)):
    if s[i].isdigit():
        s[i] = 'number'
        
print( ''.join(s))

其他判断是否是数字的方法:

str1 = input()
ans = ""
for ss in str1:
    if ord("0") <= ord(ss) <= ord("9"):
        ans += "number"
    else:
        ans += ss
print(ans)

极致做法:从后向前替换

首先扩充数组到每个数字字符替换成 “number” 之后的大小。

例如 字符串 “a5b” 的长度为3,那么 将 数字字符变成字符串 “number” 之后的字符串为 “anumberb” 长度为 8。

如图:

img

然后从后向前替换数字字符,也就是双指针法,过程如下:i指向新长度的末尾,j指向旧长度的末尾。

img

LeetCode151 翻转字符串里的单词

题目链接/文章讲解/视频讲解:https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html

✌思路:没用库函数,写的比较复杂,先处理空格再合并单词再反转

class Solution(object):
    def reverseWords(self, s):
        """
        
        :type s: str
        
        :rtype: str
        
        """
        
        s = list(s)
        # 先处理空格
        
        i = 0
        while i < len(s):
            if s[i] == " ":
                if i == 0:  # 删除所有前导空格
                    
                    s.pop(i)    # pop根据索引删除List中的元素,删除后循环条件中的len(s)会变化
                    
                    continue
                j = i + 1

                while j < len(s) and s[j] == " ":  # 多个空格
                    
                    s.pop(j)

                if j >= len(s): # 说明i是尾随空格
                    
                    s.pop(i)
                    break
            i += 1
        
        # 合并单词
        
        res = []
        i = 0
        while i < len(s):
            j = i + 1
            word = "" + s[i]
            while j < len(s) and s[j] != " ":
                word += s[j]
                j += 1
            res.append(word)
            i = j + 1
        
        # 反转
        
        i = 0
        j = len(res) - 1
        while i < j:
            res[i], res[j] = res[j], res[i]
            i += 1
            j -= 1

        return " ".join(res)

库函数:

        s = s.strip()	# 去除前后空白
    
        s = s.split()	# 根据空格划分
        
        s = s[::-1]		# 反转整个字符串

不需要额外空间的解题思路:使用整体反转+局部反转就可以实现反转单词顺序的目的

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

举个例子,源字符串为:”the sky is blue “

  • 移除多余空格 : “the sky is blue”
  • 字符串反转:”eulb si yks eht”
  • 单词反转:”blue is sky the”
class Solution:
    def reverseWords(self, s: str) -> str:
        # 删除前后空白
        
        s = s.strip()
        # 反转整个字符串
        
        s = s[::-1]
        # 将字符串拆分为单词,并反转每个单词
        
        s = ' '.join(word[::-1] for word in s.split())
        return s

卡码网:55.右旋转字符串

题目链接/文章讲解:

https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.htmlhttps://programmercarl.com/0151.翻转字符串里的单词.html)

✌思路:利用python的切片

num = int(input())
string = input()

res = string[len(string)-num:] + string[:len(string)-num]
print (res)

进阶:不能申请额外空间,只能在本串上操作

需要将字符串右移n位,字符串相当于分成了两个部分,如果n为2,符串相当于分成了两个部分。右移n位,就是将第二段放在前面,第一段放在后面,先不考虑里面字符的顺序,是不是整体倒叙就行了。如图:

img

此时第一段和第二段的顺序是我们想要的,但里面的字符位置被我们倒叙,那么此时我们在把 第一段和第二段里面的字符再倒叙一把,这样字符顺序不就正确了。 如图:

img

其实,思路就是 通过 整体倒叙,把两段子串顺序颠倒,两个段子串里的的字符在倒叙一把,负负得正,这样就不影响子串里面字符的顺序了。

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); //获取长度
    
    
    reverse(s.begin(), s.end()); // 整体反转
    
    reverse(s.begin(), s.begin() + n); // 先反转前一段,长度n
    
    reverse(s.begin() + n, s.end()); // 再反转后一段
    

    cout << s << endl;

}