Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Constraints:
1 <= s.length <= 105s[i]is a printable ascii character.
- 可以使用two pointers，替换头和尾并依次增加指针。前提是type 要 mutable。
- 用slicing [::-1] 直接替换
- 可以用 s.reverse() 直接替换原列表或 text = reverse(s) 生成一个新列表
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# two pointers
left, right = 0, len(s)-1
while left < right:
s[left],s[right] = s[right],s[left]
left += 1
right -= 1Complexity Analysis:
Time Complexity: O(n)Space Complexity: O(1)
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:] = s[::-1]
# reversed V.S reverse
# s[:] = reversed(s) with iterable parameter
# s.reverse() no parameter in ()
# reverse(0 can only be used with lists and reveses the element of the list in place
# reversed can work with any iterable(lists, tuples, strings,etc). It doesn't modify the original iterable instead
# it creates a reverse iterator Complexity Analysis:
Time Complexity: O(n)Space Complexity: O(1)
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.
If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.
Example 1:
Input: s = "abcdefg", k = 2 Output: "bacdfeg"
Example 2:
Input: s = "abcd", k = 2 Output: "bacd"
Constraints:
1 <= s.length <= 104sconsists of only lowercase English letters.1 <= k <= 104
- right: left + k ， 用于反转。 left: left + 2*k 作为步长。 再用left < s 长度
- 最开始写时，没有意识到slicing的索引可以超过他的长度。所以用两个if 处理边界问题， 再用for loop 去循环处理2k以上长度的s。
- 直接用一个for loop 设定步长2*k, 每一次反转i+k ->使用 reversed[i:i+k]
class Solution:
def reverseStr(self, s: str, k: int) -> str:
# Initialize a left pointer to track the start of each 2k segment.
left = 0
while left < len(s):
# Calculate the right boundary for the k characters to be reversed.
right = left + k
# Reverse the k characters starting from 'left' and ending at 'right'.
# Concatenate it with the non-reversed parts of the string.
s = s[:left] + s[left:right][::-1] + s[right:]
# Move the left pointer forward by 2k to process the next segment.
left = left + 2 * k
# Return the modified string after processing all segments.
return s
# T: O(n^2/k) S: O(n)
# each iteration process 2k and run n/2k. at each iteration to process slicing and string will be O(n). In total it's about O(n^2/k)-
Time Complexity: O(n^2/k) Each iteration process 2k and run n/2k. at each iteration to process slicing and string will be O(n). In total it's about O(n^2/k) -
Space Complexity: O(n)
# T: O(n), S: O(n)
class Solution:
def reverseStr(self, s: str, k: int) -> str:
if len(s) < k:
# create new string and assign to s
return s[::-1]
elif len(s) < 2*k:
return s[:k][::-1] + s[k:]
# convert string to list
s = list(s)
for i in range(0,len(s), 2*k):
# If the remaining characters are less than k, reverse them and return the string
if len(s) - i < k:
# Use join() to convert the list back to a string
return "".join(s[:i] + s[i:][::-1])
# Reverse the next k characters in place
s[i:i+k] = s[i:i+k][::-1]
return "".join(s)
# In Python, when you slice a string with an index that is beyond the string's actual length,
# Python will not throw an error. Instead, it will adapt to the situation and return as many characters as possible.Complexity Analysis:
-
Time Complexity: -
Space Complexity:
class Solution:
def reverseStr(self, s: str, k: int) -> str:
text = list(s)
for i in range(0, len(text), 2*k):
#reverse first k
#eventhough the lenght of remaining elements is less than k
text[i:i+k] = reversed(text[i: i+k])
return "".join(text)
#T: O(n), S: O(n)Complexity Analysis:
-
Time Complexity: O(n) -
Space Complexity: O(n)
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
输入一个字符串 s,s 仅包含小写字母和数字字符。
打印一个新的字符串，其中每个数字字符都被替换为了number
a1b2c3
anumberbnumbercnumber
数据范围：
1 <= s.length < 10000。
循环读取每一个letter, 用 char.isdigit() 确认是否数字，如果True 就 text + “number”, 否则 text + char
class Solution:
def convertNumber(self, s: str)->str:
text =''
for char in s:
if char.isdigit():
text += "number"
else:
text += char
return text
sol = Solution()
s = input()
res = sol.convertNumber(s)
print(res)Complexity Analysis:
-
Time Complexity: O(n) -
Space Complexity: O(n)
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue" Output: "blue is sky the"
Example 2:
Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104scontains English letters (upper-case and lower-case), digits, and spaces' '.- There is at least one word in
s.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
- s.split() 可以去掉前后空格生成新的list(strip() 用于去掉前后空格）， 再用reverse()直接反转，最后用' '.join(word)将其转成string 返回.
- 仍然用split()转成list，接下来用两个指针 left < right 循环反转。
重点left 每移动一步就是一个word, 比如["hello", "world", "from"] 0->1 是从 "hello" to "world"
class Solution:
def reverseWords(self, s: str) -> str:
#s.strip() remove start and end space
# split() will remove space in s including start and end
words = s.split()
# reverse in place
words.reverse()
return ' '.join(words)Time Complexity: O(n) where n is the length of "s"Space Complexity: O(n) where n is the length of "s"
class Solution:
def reverseWords(self, s: str) -> str:
text = s.split()
left, right = 0, len(text)-1
while left < right:
text[left],text[right] = text[right],text[left]
left += 1
right -= 1
return " ".join(text)
# T：O(n) where n is the length of "s"
# S: O(n) where n is the length of "s"Complexity Analysis:
Time Complexity: O(n) where n is the length of "s"Space Complexity: O(n) where n is the length of "s"
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出共一行，为进行了右旋转操作后的字符串。
2 abcdefg
fgabcde
数据范围：
1 <= k < 10000,
1 <= s.length < 10000;
直接使用 slicing 创造一个新的string（无初始化）,注意： 要注意边界处理用k=k%n,将k限制在n的范围内。
class Solution:
def rotateStr(self, k: int, s: str)->str:
n = len(s)
k = k % n
text = s[n-k:] + s[:n-k]
return text
sol = Solution()
k = int(input())
s = input()
res = sol.rotateStr(k,s)
print(res)Time Complexity: O(n)Space Complexity: O(n)