This is the 16th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

Offer 05

Replace the blank space

Implement a function that replaces each space in the string s with “%20”.

Example:

Input: s = "We are happy." Output: "We%20are%20happy."Copy the code

Limit: length of 0 <= s <= 10000

Answer key

There are a lot of solutions, using a lot of native apis, such as

  • replace / replaceAll
  • encodeURIComponent
  • split / join

Or direct violence, but these are not the focus of the investigation.

Double pointer method

Since strings cannot be modified in JS, once a string variable is reassigned, it takes time and space to create a new string, thus increasing the complexity.

Therefore, we need to use array to operate. The process is as follows:

  1. Convert the string to an array and count the number of Spaces in it.
  2. Based on the number of whitespace and the valid character length of the original string, calculate the array that just holds the replaced character length.
  3. Create two Pointers, one to the end of the group and one to the end of the valid bit of the string, to implement in-place modification.

Among them, array traversal is traversed from the back to the back, avoid from the front to the back, resulting in character modification and errors.

 var replaceSpace = function(s){
   s = s.split(""); // Used to convert a string into an array of strings
   let oldLen = s.length;
   let spaceCount = 0;
   for(let i = 0; i < oldLen; i++){
     if(s[i] === ' ') spaceCount++;
   }
   s.length += spaceCount * 2;
   for(let i = oldLen - 1, j = s.length - 1; i >= 0; i--, j--){
     if(s[i] ! = =' ') s[j] = s[i];
     else {
       s[j-2] = The '%';
       s[j-1] = '2';
       s[j] = '0';
       j -= 2; }}return s.join(' '); // To put all the elements in an array into a string
 }
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)

Method 2 traversal to add

Create a new string to operate on, and the time and space complexity are both O(n), which I won’t discuss here.

Print the list from end to end

Print the list from end to end

Enter the head node of a linked list and return the value of each node from the end to the end. (returned as an array).

Example:

Input: head = [1,3,2] output: [2,3,1]Copy the code

Limit: 0 <= List length <= 10000

Answer key

Method a conventional solution

Iterate over the list, insert each element from the array header, and output in reverse order.

 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
 / * * *@param {ListNode} head
  * @return {number[]}* /
 ​
 var reversePrint = function(head){
   let nums = [];
   let node = head;
   while(node ! = =null){
     nums.unshift(node.val);
     node = node.next;
   }
   return nums;
 }
Copy the code

Method two recursive method

The idea of recursion: recursion itself is consistent with the last-in, first-out principle of the stack, through recursion from the last result saved to the array, to achieve reverse order printing.

This method needs to pay attention to whether the stack overflow due to the long list.

 var reversePrint = function(head){
   let nums = []
   const visit = function(head){
     if(head! = =null){
       visit(head.next)
       nums.push(head.val)
     }
   };
   visit(head) // First entry
   return nums
 }
Copy the code

Method three inverse linked list method

The first list inversion, after the reversal of the list for traversal output

 var reversePrint = function(head){
   if(head === null || head.next === null) return head;
   let p = head.next;
   head.next = null;
   let tmp = null;
   while(p! = =null){
     tmp = p.next
     p.next = head
     head = p
     p = tmp
   }
   return head // Return a linked list, not an array
 }
Copy the code

Practice daily! The front end small adorable new one, hope can point to like ~