@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup

1, dry

Replace Spaces Implement a function that replaces each space in the string S with "%20". Example 1: Input: s = "We are happy." Output: "We%20are%20happy." Limit: 0 <= length of s <= 10000 Pass count 227,105 Submit Count 297,856Copy the code

2. Iterate over add

The best way to think about it is to create a new string, then iterate over the original string, modify it if it meets the requirements, and keep it if it doesn’t.

Algorithm flow:

  1. Initialize a string called res;
  2. Iterate over each character x in the original string s:
    1. When x is a space: add string “%20” to res;
    2. When x is not a space: add character x to res;
  3. Returns the string res.
// Interview question 05
class Solution {
public:
	string replaceSpace(string s) {
		string res;
		for (auto x : s)
		{
			if (x == ' ') res += "% 20";
			else res += x;
		}
		returnres; }};Copy the code

/* Time complexity: O(n). Iterate over the string s once. Space complexity: O(n) */
Copy the code

3. Modify in situ

Notice that the space complexity, because I’m creating a new answer string, is not constant.

Algorithm flow:

  1. Initialization: the length of the string s oldl;
  2. Count the number of Spaces: traverse s, s += “00”;
  3. Newl: specifies the length of the string after adding “%20”.
  4. Reverse traversal: I refers to the element at the end of string S;
    1. When s[I] is a space: change the elements of the string newl to “%20”, each time newl needs to be moved;
    2. When s[I] is not a space: change the element of the string newl to C;
  5. Returns the modified string s;
// Interview question 05
// Standard practice
class Solution {
public:
	string replaceSpace(string s) {
		int oldl = s.length() - 1;
		for (int i = 0; i <= oldl; i++) {
			if (s[i] == ' ') {
				s += "00"; }}int newl = s.length() - 1;
		if (newl <= oldl) {
			return s;
		}
		for (int i = oldl; i >= 0; i--) {
			char c = s[i];
			if (c == ' ') {
				s[newl--] = '0';
				s[newl--] = '2';
				s[newl--] = The '%';
			}
			else{ s[newl--] = c; }}returns; }};Copy the code

4. Complexity

/* Time complexity: O(n). Iterate over the string s once. Space complexity: O(1). Since the s-length is extended in place, O(1)O(1) extra space is used. * /
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…