This is the 17th day of my participation in the August Text Challenge.More challenges in August

Brush questions, please go to LeetCode to brush questions together when you have time. By brushing questions, you can consolidate the data structure and algorithm foundation. The accumulated improvement is really great, especially now all the better factories will test the algorithm

If you also want to brush the algorithm of the plan, can encourage each other to exchange learning

Today’s content refers to questions 5 and 6 in offer(version 2) in leetCode

Let’s get started

Replace the blank space

The title goes like this:

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

Limitations:

0 <= the length of s <= 10000Copy the code

This problem is very simple. See how many ways you can do it

Idea 1: replaceAll

function replaceSpace(str){
    return str.replaceAll(' '.'% 20')}console.log( replaceSpace( "We are happy."))//"We%20are%20happy."
Copy the code

Idea 2: Replace/regular

function replaceSpace(str){
    / / method
    return str.replace(/\ +/g.'% 20')
    / / method 2
    return str.replace(/\s/g.'% 20')}console.log( replaceSpace( "We are happy."))//"We%20are%20happy."
Copy the code

Idea 3: Split/join

Use split to split the string into an array of strings with Spaces, and join to concatenate each element of the array

function replaceSpace(str){
    return str.split(' ').join('% 20');
}
console.log( replaceSpace( "We are happy."))//"We%20are%20happy."
Copy the code

Idea 4: Traversal

Iterate over each character and replace it if it is empty, or determine the Unicode code for each character (32 is the Unicode code for Spaces) and replace it if it is empty

function replaceSpace(str) {
  let finishStr = ""
  for(let s of str){
    / / method
    finishStr += s === "" ? "% 20" : s
    // The unicode code for method two Spaces is 32
    finishStr += s.charCodeAt() === 32 ? "% 20" : s
  }
  return finishStr
}
console.log( replaceSpace( "We are happy."))//"We%20are%20happy."
Copy the code

Print the linked list from end to end

The title goes like this:

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

The sample

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

limit

0 <= List length <= 10000Copy the code

Idea 1: Header insertion

Create an empty array, loop through the list, insert each value in the list to the head of the array, and return the array in reverse order

function reversePrint(head){
    let arr = []
    while(head){
        arr.unshift(head.val)
        head = head.next
    }
    return arr
}
Copy the code

Idea 2: Recursion

So you take the current value, you pass in the next value, you call yourself recursively, and you merge, and you end up going from the end of the list one by one into a new array, and you return the reverse result

function reversePrint(head){
  return! head ? [] : reversePrint(head.next).concat(head.val) }Copy the code

Idea 3: Stack

Using the stack, using the characteristics of the stack first in then out, put the value of the linked list in order into a stack, put the first natural at the bottom, and then take out the value from top to bottom in another stack, and return, is also to achieve the effect of reverse order

function reversePrint(head){
  let stack1 = []
  let stack2 = []
  while(head){
      stack1.push(head.val)
      head = head.next
  }
  for(let i = 0, len = stack1.length; i < len; i++){
      // pop() removes and returns the last element
      stack2[i] = stack1.pop()
  }
  return stack
}
Copy the code

Links are not the same as arrays, so if you don’t already know, linked lists can use val and next to get the current and next values. Its structure consists of Pointers connecting nodes into a chain, which is very important in interviews

Because there are ready-made APIS, this structure is rarely used in ordinary work, so it is more necessary to practice and master the basics

Today’s brush questions here, if you also want to brush questions, you can encourage each other to exchange

conclusion

Praise and support, hand left lingering fragrance, and have honor yan

Thank you for being here!