preface

Today is the second day of my hard steel algorithm, my foundation is really poor. The article focuses on the record summary, I am also curious about how long I will insist, I only in the form of writing an article to record the question brush every day to keep a positive attitude, or every time to see a while lazy 😭. Only when I see your feedback can I continue to stick to it!

Past articles:

👨💻 First day of learning algorithms from scratch ~ (binary search, double pointer, add two numbers, longest loop substring)

Brush the topic

283. Move the zero

var moveZeroes = function(nums) {
    let left = 0,right = 0
    while(right < nums.length){
        if(nums[right]){
            [nums[right],nums[left]] = [nums[left],nums[right]]
            left ++
        }
        right++
    }
};
Copy the code

Each iteration moves the position of the right pointer to the right, but only moves the position of the left pointer to the right if the current iteration is not zero. In this way, the left pointer is kept at the position of 0. If the current iteration is not zero, the left pointer is switched with the left pointer. Move non-zero values to the front. Anything that’s not zero at the end of the loop moves to the left.

Here is a more intuitive way to write, is not immediately clear:

/ * * *@param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let zeroPosition = 0
    nums.forEach((item,index) = >{
        if(item){
            [nums[zeroPosition],nums[index]] = [nums[index],nums[zeroPosition]]
            zeroPosition++
        }
    })
};
Copy the code

7. Integer inversion

The number overflow threshold is calculated using math.pow, and positive and negative records are calculated using math.sign

• Math.pow(2,31) gets the maximum number
• Math.sign() gets the positive and negative values of numbers

var reverse = function(x) {
    const sign = Math.sign(x)
    x = Math.abs(x)
    const num =  sign * parseInt((' ' + x).split(' ').reverse().join(' ')) 
    if(num > Math.pow(2.31)||num < Math.pow(-2.31)) {return 0
    }
    return num
};
Copy the code

This problem is relatively simple, converted to a string and then converted to an array and flipped, flipped to a number, a judgment can be ~

9. A palindrome

Cannot be converted to a string to determine whether it is a palindrome.

The core of the implementation is to create a new variable, flip the number over, assign a value to the new variable, and determine whether the new variable is the same as the number passed in.

/ * * *@param {number} x
 * @return {boolean}* /
var isPalindrome = function(x) {
    if(x < 0|| (x! = =0&&x%10= = =0)) {return false
    }
    let resverNum = 0
    let num = x
    while(num){
        resverNum = resverNum * 10 + num % 10
        num = Math.floor(num/10)}return x === resverNum
};
Copy the code

I’m going to exclude some numbers, negative numbers, non-zero numbers divisible by 10, because if the last digit is 0 the first digit has to be 0, but the first digit of an integer can’t be zero so I’m going to exclude that.

The next step is to flip the number by creating a new value, starting with 0. Divide the original number by ten and add the remainder to the new variable, dividing the original number by ten until it rounded to zero, while the new variable multiplied by ten each time and added the remainder, so that when the loop was complete, the number flipped.

20. Valid brackets

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {
    const arr = s.split(' ')
    if(arr.length % 2! = =0) {return false
    }
    const map = {
        '(':') '.'{':'} '.'[':'] '
    }
    const stack = []
    for(let item of s){
        if(map[item]){
            stack.unshift(map[item])
        }
        else{
            const match = stack.shift()
            if(match ! == item){return false}}}if(stack.length){
        return false
    }
    return true
};
Copy the code

This question is about interviewing old customers. Although I haven’t brushed leetcode before, I still feel very friendly about this question.

The implementation idea lies in two points, one is to create an object to store the corresponding relationship of parentheses, and then create a stack, using the last in first out feature of the stack to match parentheses

In JS stack implementation is through array simulation, using unshift and Shift two API simulation on the stack operation.

11. Container that holds the most water

var maxArea = function(height) {
 let maxV = 0
 let left = 0
 let right = height.length - 1
 while(left<right){
     const V = (right - left) * Math.min(height[left],height[right]) height[left]>height[right]? right--:left++if(V>maxV){
         maxV = V
     }
 }
 return maxV
};
Copy the code

The volume of the container is calculated by the distance between the two Pointers * the smaller value of the two Pointers. Then determine which side of the pointer points to the smaller value, and offset the other side of the pointer towards the middle until the two Pointers meet.

14. Longest public prefix

/ * * *@param {string[]} strs
 * @return {string}* /
var longestCommonPrefix = function(strs) {
    if(! strs.length){return ""
    }
    const minLength = Math.min(... strs.map(item= >item.length)) 
    const publicStrArr = []

    for(let i = 0; i<minLength; i++){let isPublic = true
        for(let strIndex in strs){
            if(! strs[strIndex][i]||strs[strIndex][i]! ==strs[0][i]){
                isPublic = false
                break}}if(! isPublic){break
        }
        publicStrArr.push(strs[0][i])
    }
    
    return publicStrArr.join(' ')};Copy the code

😅, first I get the length of the smallest value in the array, and then I perform two layers of traversal. The outer layer is used to traverse each string in the array, and the inner layer is used to traverse the array of strings. The isPublic variable is used to determine whether all strings in the array have the same value at the strIndex position. If they do not, the loop is broken. If they do, the array is pushed. Finally, concatenate the array into a string.

167. Sum of two numbers II – Enter ordered array

The sum of these two numbers I am most accustomed to is the use of map solution, using objects can achieve many convenient functions through the uniqueness of keys and mapping relations.

/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(numbers, target) {
    const map = {}
    for(let i in numbers){
        if(! map[target - numbers[i]] ){ map[numbers[i]] = i }else{
            return [parseInt(map[target - numbers[i]])+1.parseInt(i)+1]}}};Copy the code

First create an object map and iterate over the array of numbers. The sum of the two numbers is a constant difference between the target value and the number traversed. If the difference is a value already in the map, the sum of the two values equals target. If it’s not in the map, add the value as a key to the map

Because the array is ordered, it also meets the conditions of binary search, using binary search solution

var twoSum = function(numbers, target) {
    
    for(let i in numbers){
        i= parseInt(i)
        let left = i+ 1 
        let right = numbers.length - 1
        while(left <= right){
        const mid = Math.floor((right - left)/2 + left)
        if( numbers[i] + numbers[mid] === target){
            return [i+1,mid+1]}else if(numbers[i] + numbers[mid] < target){
            left = mid + 1
        }
        else{
            right = mid - 1}}}};Copy the code

First traverse the number array, and then perform a binary search in the range to the right of the number currently traversed. Each time judge the size relationship between the sum of the number traversed + the middle value of the binary search and target, and then continuously narrow the range

557. Reverse the word III in the string

var reverseWords = function(s) {
    s = s.split(' ').map(item= >item.split(' ').reverse().join(' ')).join(' ')
    return s
};
Copy the code

The map traverses the array by flipping each string in the array and concatenating the array with Spaces, so that the positions of the Spaces in the string remain the same.

The middle node of a linked list

This problem I think is very helpful to me, let me learn a fast and slow double pointer to point to the middle of the linked list method.

Since the linked list can not directly obtain the middle position of the pointer, so we define a fast and slow two Pointers, each time the fast pointer takes two steps, the slow pointer takes one step, the fast pointer takes two steps. When the fast pointer goes to the end of the list, the slow pointer goes right to the middle. This idea is very inspiring for me who didn’t brush the question before

var middleNode = function(head) {
    let slow,fast
    slow = fast = head;
    while (fast && fast.next) {// The fast pointer traverses until the fast pointer reaches the end
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};
Copy the code

conclusion

The second day, every day very tired, but still have to insist on ~

You are very, very welcome to like or leave a comment to let me know that someone is watching me and I am not lazy! If you have some experience in algorithm learning, you are welcome to help me ha ~