[JS] - [string - application] - learning notes

Statement ： This note is based on the Nuggets brochure , If you want to learn more details , Please move https://juejin.cn/book/6844733800300150797

1 Basic algorithm skills

1. Reverse string

Direct correlation API

const str = 'juejin'  
//  Define the inverted string 
const res = str.split('').reverse().join('')

console.log(res) // nijeuj

2. Determine whether a string is palindrome string

function isPalindrome(str) {
    
    //  Reverse the string first 
    const reversedStr = str.split('').reverse().join('')
    //  Judge whether the reversal is equal 
    return reversedStr === str
}

Symmetrical features

function isPalindrome(str) {
    
    //  The length of the cache string 
    const len = str.length
    //  Traverse the first half , Judge whether the and the second half are symmetrical 
    for(let i=0;i<len/2;i++) {
    
        if(str[i]!==str[len-i-1]) {
    
            return false
        }
    }
    return true
}

2.1 The derivation of palindrome string

describe ：
Given a non empty string s, most Delete one character . Determine whether it can be a palindrome string .
Input : “aba”
Output : True
Example 2:
Input : “abca”
Output : True

Ideas ：

1. Define a function Determines whether a string is palindromic
2. Define left and right pointers respectively ,i and j
3. In symmetry , Go left and right together
4. Encounter asymmetric , Delete one on the left , Judge to skip Left Whether the string after the pointer element is a palindrome ; Delete one on the right , Judge to skip Right Whether the string after the pointer element is a palindrome ;
5. if , Then the whole string is palindrome
   

const validPalindrome = function(s) {
    

    const len = s.length

    // i、j Left and right pointers respectively 
    let i=0, j=len-1
    
    //  When the left and right pointers are symmetrical , Move towards the middle together 
    while(i<j&&s[i]===s[j]) {
    
        i++ 
        j--
    }
    
    //  Try to determine whether the string is palindrome after skipping the left pointer element 
    if(isPalindrome(i+1,j)) {
    
      return true
    }
    //  Try to determine whether the string is palindrome after skipping the right pointer element 
    if(isPalindrome(i,j-1)) {
    
        return true
    }
    
    //  Tool method , Used to determine whether the string is palindrome 
    function isPalindrome(st, ed) {
    
        while(st<ed) {
    
            if(s[st] !== s[ed]) {
    
                return false
            }
            st++
            ed--
        } 
        return true
    }
    
    //  Default return  false
    return false 
};

3 String matching problem ( Regular expressions )

describe ：
Design a data structure that supports the following two operations ：void addWord(word)
bool search(word)
search(word) You can search for text or regular expression strings , The string contains only letters . or a-z
（. It can mean any letter ）

Ideas ：

search It can search for words , You can also search for regular expressions .
If included . Is a regular expression
If it is an ordinary string , Directly to Map Find out if there is this key;
If it's a regular expression , Then create a regular expression object , Judge Map In a string of the same length , Whether there is one that can match this regularity .

Add ：

Use RegExp object
stay JavaScript in ,RegExp An object is a regular expression object with predefined properties and methods
Use test():
test() Method to detect whether a string matches a pattern , If the string contains matching text , Then return to true, Otherwise return to false.

for example ：
The following example is used to search for characters in a string “e”：

var patt = /e/;
patt.test("The best things in life are free!");

The string contains “e”, So the output of this instance is ：true

Concrete realization ：

1. Constructors

const WordDictionary = function () {
    
   #  Initializes an object literal , To undertake  Map  Role 
  this.words = {
    }
};

2. The method of adding a string

WordDictionary.prototype.addWord = function (word) {
    
  #  If an array of the corresponding length of the string already exists , Only add 
  
  if (this.words[word.length]) {
    
    this.words[word.length].push(word)
  } else {
    
  
    #  If the array corresponding to the length of the string does not exist , First create 
    this.words[word.length] = [word]
  }
};

3. Search method

WordDictionary.prototype.search = function (word) {
    
  const len = word.length
  # 1  If the length of the string is  Map  The corresponding array in does not exist at all , You can judge that the string does not exist 
  if (!this.words[len]) {
    
    return false
  }
  
  # 2  If the string does not contain ‘.’, Then it must be a normal string 
  if (!word.includes('.')) {
    
    //  Locate the string array with the same length as the target string , Find out if the string exists 
    return this.words[len].includes(word)

  }

  # 3  Otherwise it is a regular expression , First create a regular expression object 
  const reg = new RegExp(word)

  # 4  As long as there is a string matching the regular expression in the array , Just go back to true
  return this.words[len].some((item) => {
    
    return reg.test(item)
  })
};

4 The conversion between string and number （ Regular expressions ）

describe ：
Please come to realize a atoi function , Make it possible to convert strings to integers .

Suppose our environment can only store 32 A signed integer of bit size , So the value range is [−2^31, 2^31 − 1]. If the value exceeds this range , Please return INT_MAX (2^31 − 1) or INT_MIN (−2^31)

First , This function discards useless... As needed The leading space character .
When the first non empty character we find is just perhaps negative Time of signal , Then combine the symbol with as many consecutive numbers as possible on the back face ;
Suppose the first non empty character is Numbers , Then combine it directly with the following consecutive numeric characters , Form an integer .

Be careful ： Suppose the first in the string Non space characters Is not a Valid integer characters 、 The string is empty or string When only white space characters are included , Then your function doesn't need to be converted .
In any case , If the function cannot be effectively converted , Please return 0.

Input
“words and 987”
Output :
0
explain : The first non empty character is ‘w’, But it's not a number or a positive 、 Minus sign . Therefore, a valid conversion cannot be performed .

Input :
“-91283472332”
Output :
-2147483648
explain : Numbers “-91283472332” exceed 32 Bit signed integer range . Therefore return INT_MIN (−2^31)

Ideas ：

1. Use regular matching , Some pictures match legal number strings , Otherwise return to null
2. Use the bayonet to judge the range
3. Return the conversion result

1. Calculation range （ Minimum - Maximum ）

//  Calculate the maximum 
const max = Math.pow(2,31) - 1
//  Calculate the minimum 
const min = -max - 1

2. Remove spaces
   The first one is ：trim() Method

let str = ' +10086'
str.trim() // '+10086'

The second kind ： Regular \s*
\s Means null character ,* Follow other symbols , signify “ The preceding symbol can appear 0 Times or times .
legal ： Possible spaces + The sign + Numeric string + Other character contents , Corresponding regular /\s*([-\+]?[0-9]*).*/

explain ：
() The content enclosed , It's something to store extra
[] Between the matching characters in is “ or ” The relationship between ? Zero or one
\+ The reason for adding a slash character , Because + It is a regular matcher with special function , Here we're going to let it go back + The original meaning of characters , So use a \ To complete escape .
[0-9]*, yes 0-9 Integer between , matching 0 One or more matches are successful .
final . This is the meaning of any character ,.* Used to match any non numeric character at the end of a string . We see .* Is excluded from the capture group , So this thing will not be stored additionally , It has been “ Enucleation ” 了 .

3. Get capture results

const reg = /\s*([-\+]?[0-9]*).*/
const groups = str.match(reg)

test() Method returns a Boolean value , Simple judgment “ match ”. To get matching results , We need to schedule match() Method , The first complete match will be returned （ As the first... Of the array 0 term ）, Capture group （ As the first... Of the array 1 And the first 1+ term ）.
Here we define only one capture Group , So you can go from groups[1] Get the results of our capture

Complete code

//  The input parameter is a string 
const myAtoi = function(str) {
    
    //  Write regular expressions 
    const reg = /\s*([-\+]?[0-9]*).*/
    
    #1.  Get capture group 
    const groups = str.match(reg)
    
    #2.  Calculate the maximum 
    const max = Math.pow(2,31) - 1
    //  Calculate the minimum 
    const min = -max - 1
    #3. targetNum  Used to store the converted numbers 
    let targetNum = 0
    //  If the match is successful 
    if(groups) {
    
        //  Try to convert the captured structure 
        targetNum = +groups[1]
        //  Be careful , Even if successful , There may also be non numeric situations , For example, a single '+'
        if(isNaN(targetNum)) {
    
            //  When a valid conversion is not possible , Please return  0
            targetNum = 0
        }
    }
    #2.  Bayonet judgment 
    if(targetNum > max) {
    
        return max
    } else if( targetNum < min) {
    
        return min
    }
    //  Return the conversion result 
    return targetNum
};

Be careful ：
=+
= It's assignment
+ Represents that the following number is positive
=- Represents that the following number is negative
Tell compiler , Don't put the Numbers As a string to splice

I learned this today https://juejin.cn/book/6844733800300150797/section/6844733800350482445