LeetCodeCampsDay8字符串01

LeetCodeCampsDay8字符串part01

双指针/字符串反转/python列表与字符串互换/python列表语法糖

344. 反转字符串

https://leetcode.cn/problems/reverse-string/

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

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

思路零

使用python内置库函数，可以了解下

代码

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # method1
				s[::] = s[::-1]
        # method2
        # s[::] = reversed(s)

思路一双指针

使用双指针，一个从头开始一个从尾部开始，逐个交换即可

代码

时间复杂度O(N)
空间复杂度O(1)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        L = len(s)
        left = 0
        right = L - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

思路二用range

因为while每次都要判断条件，增加了时间复杂度，可以使用range(0, L//2)

代码

时间复杂度O(N)
空间复杂度O(1)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        L = len(s)
        for i in range(L//2):
            s[i], s[L - i - 1] = s[L - i -1], s[i]

思路三用栈

将数据入栈，再逐个弹出；缺点是需要两个循环

代码

时间复杂度O(N)
空间复杂度O(1)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        L = len(s)
        stack = []
        for i in s:
            stack.append(i)
        for i in range(L):
            s[i] = stack.pop()

541. 反转字符串 II

https://leetcode.cn/problems/reverse-string-ii/

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

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

思路

输入是字符串，必须经过处理转成列表；字符串无法被直接修改
使用反转字符串的思路，写个完全反转的辅助函数
主思路，使用两个指针，每次按2k的长度对s进行滑动（所谓滑动窗口）
1. 对窗口内的子段进行长度判断，如果长度大于等于k，则只反转前k个；否则反转窗口内所有内容
更新left与right；其中left = right；而right = left + 2 * k;

代码

时间复杂度O(N)
空间复杂度O(1)

class Solution:
    def reverseStrClip(self, s:list) -> str:
        L = len(s)
        for i in range(L//2):
            s[i], s[L - i - 1] = s[L - i -1], s[i]
        return s

    def reverseStr(self, s: str, k: int) -> str:
      	# 字符串无法被修改，必须转成list
        s = list(s)
        left = right = 0
        L = len(s)
        # 退出条件是left到底
        while left <  L:
            left = right
            right = left + 2 * k
            if right - left >= k:
                s[left: left+k] = self.reverseStrClip(s[left: left+k])
            else:
              	# 因为剩下所有的内容已经小于k了，全部反转即可
              	s[left:] = self.reverseStrClip(s[left:])
                #s[left: right] = self.reverseStrClip(s[left: right])
        # 转回字符串
        return "".join(s)

改进，同样的，推荐使用range而不是while，可以提高速度

Range(0, L, 2 * k)，即将i作为left，而right每次手动计算下即可

class Solution:
    def reverseStrClip(self, s:list) -> str:
        L = len(s)
        for i in range(L//2):
            s[i], s[L - i - 1] = s[L - i -1], s[i]
        return s

    def reverseStr(self, s: str, k: int) -> str:
        # 设置好开始结束区间
        # 一共两个条件
        s = list(s)
        left = right = 0
        # 退出条件是left到底
        L = len(s)
        for i in range(0, L , 2 * k):
            if i + k <= L:
                s[i: i + k] = self.reverseStrClip(s[i: i + k])
            else:
              	# 剩下内容个数小于k，全部反转
              	# s[i:] = self.reverseStrClip(s[i:]) 也是可以的
                s[i: i + 2 * k] = self.reverseStrClip(s[i: i + 2 * k])
        return "".join(s)

思路二(Python列表特性语法糖)

Python列表特性语法糖

更直接一点儿，都不用进行条件判断，直接对每次2k内的前k个元素进行反转即可（不用管它长度是大于k还是小于k，直接按k个进行切片）
这里利用了python的一个列表性质：s[start:end]，哪怕end越出了实际长度，python只会把它当成s[start:-1]，也就是把start后所有内容返回，而不会报错；
- 比如s = [‘a’, ‘b’] 且k = 4，如果i = 0时，s[0 + 4]会是[‘a’, ‘b’]
利用这种性质，可以直接s[i: i + k] = self.reverseStrClip(s[i: i + k]) ，而不用进行长度的判断；这也算是语法糖了，这种东西最好不要用，不然容易解释不清楚，还以为这样的算法是正确的，但没想到是语言在兜底

代码

时间复杂度O(N)
空间复杂度O(N)

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
				L = len(s)
        s = list(s)
        for i in range(0, L, 2 * k):
          	# 
            s[i: i + k] = s[i: i + k][::-1]
            # 或者用自己写的函数也行
            # s[i: i + k] = self.reverseStrClip(s[i: i + k])
        return "".join(s)

54.替换数字

https://kamacoder.com/problempage.php?pid=1064

题目描述

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

输入描述

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

输出描述

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

输入示例

a1b2c3

输出示例

anumberbnumbercnumber

提示信息

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

思路

偷懒思路：字符串转成列表，再判断是否为数字，是则替换
可以使用ord()来找ascii码，比较通用；或者使用python库函数s.isdigit()

代码

def foo(s:str) -> str:
    s = list(s)
    L = len(s)
    for i in range(L):
        if ord('9') >= ord(s[i]) >= ord('0'):
            s[i] = "number"
    return "".join(s)

s = input()
print(foo(s))

思路二(纯算法)

如果需要正常写，需要进行 数组扩展 以及 数组填充（倒序填充）
先统计原数组内的digital个数，再创建个新数组res，容量为len(s) + countDig * 5
随后，使用双指针，同时对s与res从后向前遍历，如果遇到s[indexOld]是digital则将res[indexNew-5: indexNew+1]="number"直接赋值即可，或者逐个赋值；如果不是digital，直接将s[indexOld]复制到res[indexNew]即可

代码

class solution():
    def foo(self, s: str) -> str:
        L = len(s)
        # 统计str中digital个数
        countDigital = sum(1 for i in s if i.isdigit())
        # 创建新结果数组, 等于原数组长度 + countDigital * 5
        res = [''] * (countDigital * 5 + L)
        # 从后向前对res进行填充
        newIndex = len(res) - 1
        oldIndex = L - 1
        while oldIndex >= 0:
            if s[oldIndex].isdigit():
                res[newIndex - 5: newIndex + 1] = "number"
                newIndex -= 6
            else:
                res[newIndex] = s[oldIndex]
                newIndex -= 1
            oldIndex -= 1
        
        return "".join(res)

s = input()
solu = solution()
print(solu.foo(s))