This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

Js daily an algorithm problem, today to a very simple array related algorithm problem, to find confidence, or to be hit do not want to see the algorithm problem, ha ha, look at the specific topic

Topic describes

Write a function that reverses the input string. The input string is given as a character array s.

Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.

 

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”]

Thought analysis

  • S [x]=s[n-x-1]; s[x]=s[n-x-1]s[0] s[1] s[2] ... s[N - 1], then the character array after inversion iss[N - 1] s[N - 2] ... s[0]
  • Because of the above management, we can solve this problem by using double Pointers. We define two Pointers, left and right, with the left starting at the head of the array and right starting at the end of the array, and then declare a variable that converts the position of the item to which the pointer currently points
  • When the left does not satisfy the requirement of being less than right, it can be finished. The result obtained at this time is the result after we reverse it, and the code is as follows
/ * * *@param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    // Declare Pointers left and right to the head and tail, respectively
    let left = 0
    let right = s.length-1
    let curr = null
    // When left
    while(left < right){
        curr = s[left]
        s[left] = s[right]
        s[right] = curr
        // Move two Pointers after each inversion of two items
        left++
        right--
    }
};
Copy the code
  • There is an easier way to write the above code as follows
var reverseString = function(s) {
    const n = s.length;
    for (let left = 0, right = n - 1; left < right; ++left, --right) { [s[left], s[right]] = [s[right], s[left]]; }};Copy the code
  • Several lines of code are reduced instantly, and there is no need to use intermediate variables to do assignment conversion, but the general idea is the same, but the code implementation has been simplified and optimized

conclusion

Today’s algorithm is as simple as 1+1 equals 2. If only interviews were like this, but they can’t be that simple. Keep going, gogogo