代码随想录算法训练营 Day 7

less than 1 minute read

Published:

Q1. LeetCode 344

思路:因为不能使用额外空间,所以采用双指针的方法,初始值分别为0和len(s) - 1。那么每次只需要交换指针所指字符即可

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

复杂度分析

时间复杂度:O($n$) 空间复杂度:O(1)

Q2. LeetCode 541

思路:首先将字符串以2k的长度进行划分,在每个区间中取前k个进行翻转

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        start_idx = 0
        while start_idx < len(s):
            end_idx = start_idx + k
            s = s[:start_idx] + s[start_idx:end_idx][::-1] + s[end_idx:]
            start_idx = start_idx + 2 * k
        
        return s

复杂度分析

时间复杂度:O($n$) 空间复杂度:O(1)

Q3. KamaCoder 54

思路:判断字符是否为数字,如果是,则替换为number。否则采用原字符

def replace_num(s):
    r = ''
    for i in range(len(s)):
        if ord('0') <= ord(s[i]) <= ord('9'):
            r += 'number'
        else:
            r += s[i]
    
    return r


data = input()
res = replace_num(data)

print(res)

复杂度分析

时间复杂度:O($n$) 空间复杂度:O($n$)

Take some notes

Python里面的string也是不可改的,所以也是需要额外空间的。空间复杂度:O(n)