当前位置:网站首页>Leetcode question brushing (5.31) string
Leetcode question brushing (5.31) string
2022-07-06 08:20:00 【Freya】
1. Reverse string
subject :
Write a function , Its function is to invert the input string . Input string as character array s Given in the form of .
Do not allocate extra space to another array , You have to modify the input array in place 、 Use O(1) To solve this problem .
Input :s = ["h","e","l","l","o"]
Output :["o","l","l","e","h"]
Ideas :
Double pointer , Different from reverse linked list ( A string is an array , Continuously distributed in memory )
note :
utilize Python Properties that can be assigned at the same time , Array of swap Operations can be assigned at the same time
s[left], s[right] = s[right], s[left]
Why do not you need to set tmp Variables to hold intermediate values ?
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
Because the assignment operation is executed in the order of equal signs from right to left , Simply put the value s.size() - 1, 0 Assign to s[left], s[right], And operate separately , Once assigned s[i] = s[j],s[i] Will be overwritten by the new value , So save the intermediate variables first .
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. Reverse string II
subject :
Given a string s And an integer k, From the beginning of the string , Each count to 2k Characters , Just reverse this 2k The first... In the character k Characters .
If the remaining characters are less than k individual , Reverse all remaining characters .
If the remaining characters are less than 2k But greater than or equal to k individual , Before reversal k Characters , The rest of the characters remain the same .
Input :s = "abcdefg", k = 2
Output :"bacdfeg"
Ideas :
Break the inherent for loop k++ thinking :i Each move 2*k that will do
Two topics “ If ” Conditions , It can be understood as always before reversing k individual (<=), And move on 2k Step , It's difficult before reversing k individual (<=) To deal with :
about C++, Is to see whether it is reverse [i, i + k) still [i, n) , It can be used min() Judge
about Python, If the boundary of the slice is not reached ( such as s[0:999]), The last value of the actual string is returned by default , So you don't have to judge “ The remaining characters are less than k The circumstances of ”.
note :
notes :C++ reverse() The function is left open and right closed , The scope is [first,last) Reverse all inside .
The point is not to investigate reverse() operation , So you can use library functions
C++:
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n; i += (2 * k)) {
// 1. every other 2k Before characters k Characters to reverse
// 2. The remaining characters are less than 2k But greater than or equal to k individual , Before reversal k Characters
// 3. The remaining characters are less than k individual , Reverse all remaining characters .—— min() take n The situation of
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):
# Even if the string is insufficient k Long , No errors reported , The actual length is returned
t[i: i + k] = reversed(t[i: i + k])
return "".join(t)
3. Replace blank space
The finger of the sword Offer 05
subject :
Please implement a function , Put the string s Replace each space in with "%20".
Input :s = "We are happy."
Output :"We%20are%20happy."
Ideas :
It's easy to see , Just for Loop detection. If you encounter spaces, replace them with characters ok, However, it does not take into account the different length of spaces and new characters , So it's impossible to change in place , We must expand space .
use In situ reverse filling : Expand first size, Then reverse the double pointer filling It can minimize the space complexity .
But for the Python and JAVA, Strings are designed to 「 immutable 」 The type of ,(C++ string variable ) That is, you cannot directly modify a character of the string , You need to create a new string implementation ( Fill the new string in sequence ).
note :
Pay attention to the examination :
s.resize(sOldSize + 2 * count);
Why not 3 * count ? “%20” Mingmingzhan 3 position ? Because the original space is occupied 1 position
C++:
class Solution {
public:
string replaceSpace(string s) {
int count = 0;
int sOldSize = s.size();
// Count the number of spaces
for (char c : s) {
if (c == ' ') count++;
}
// modify s length
s.resize(sOldSize + 2 * count);
int sNewSize = s.size();
// Traversal modification in reverse order
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)
边栏推荐
- 使用 Dumpling 备份 TiDB 集群数据到兼容 S3 的存储
- Make learning pointer easier (3)
- 【T31ZL智能视频应用处理器资料】
- 远程存储访问授权
- Introduction to number theory (greatest common divisor, prime sieve, inverse element)
- Remote storage access authorization
- [secretly kill little partner pytorch20 days -day01- example of structured data modeling process]
- [research materials] 2021 live broadcast annual data report of e-commerce - Download attached
- VMware 虚拟化集群
- Online yaml to CSV tool
猜你喜欢
Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
CISP-PTE实操练习讲解
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
Asia Pacific Financial Media | female pattern ladyvision: forced the hotel to upgrade security. The drunk woman died in the guest room, and the hotel was sentenced not to pay compensation | APEC secur
2022 Inner Mongolia latest water conservancy and hydropower construction safety officer simulation examination questions and answers
让学指针变得更简单(三)
It's hard to find a job when the industry is in recession
"Designer universe" APEC design +: the list of winners of the Paris Design Award in France was recently announced. The winners of "Changsha world center Damei mansion" were awarded by the national eco
Analysis of pointer and array written test questions
C language custom type: struct
随机推荐
[untitled]
Asia Pacific Financial Media | "APEC industry +" Western Silicon Valley invests 2trillion yuan in Chengdu Chongqing economic circle to catch up with Shanghai | stable strategy industry fund observatio
从 TiDB 集群迁移数据至另一 TiDB 集群
How to use information mechanism to realize process mutual exclusion, process synchronization and precursor relationship
Go learning notes (3) basic types and statements (2)
Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
2022 Inner Mongolia latest water conservancy and hydropower construction safety officer simulation examination questions and answers
synchronized 解决共享带来的问题
3. File operation 3-with
2. File operation - write
Convolution, pooling, activation function, initialization, normalization, regularization, learning rate - Summary of deep learning foundation
Circuit breaker: use of hystrix
Use Alibaba icon in uniapp
IoT -- 解读物联网四层架构
On the day of resignation, jd.com deleted the database and ran away, and the programmer was sentenced
远程存储访问授权
Pyqt5 development tips - obtain Manhattan distance between coordinates
Summary of MySQL index failure scenarios
[secretly kill little partner pytorch20 days -day01- example of structured data modeling process]