Arrays in JS (including leetcode examples) < continuous update ~>

Array

Basic characteristics

• JavaScript Has encapsulated a relatively complete array for us （ Automatic expansion , Allow to store different types of data ）

• In the middle of the array Insert and Delete Low performance , But the search speed is fast （ Subscript search ）

Common methods

increase / Delete

Method name	explain	Return value
unshift( Parameters 1…)	Head increase , Modify the original array	Return to the new length
push( Parameters 1…)	Tail increase , Modify the original array	Return to the new length
shift()	Head deletion , Modify the original array	Returns the value of the deleted element
pop()	Deletion at the end , Modify the original array	Returns the value of the deleted element

Change order

Method name	explain	Return value
reverse()	Flip array , Modify the original array	Return a new array
sort()	Use it directly , Will treat numbers as strings , Just look at the first place ; Callback use , Sort ; Modify the original array	Return a new array

//  Can't be used directly arr.sort, Will sort by string , That is, sort according to the first digit 
//  You have to add one inside function Determine the order 
var arr=[1,20,60,7];
arr.sort() //1,20,60,7
arr.sort(function(a,b){
    
	return(a-b);// Ascending order 
    return(b-a);// Descending order 
});

Inquire about

Method name	explain	Return value
indexOf( Parameters )	From the front to the back , Just find one	The first index number that satisfies the condition , There is no return -1
lastIndexOf( Parameters )	Look back and forth , Just find one	The first index number that satisfies the condition , There is no return -1
includes( Parameters , Starting position )	Find if it exists	true/false

Connect 、 Intercept 、 Filter 、 to update

Method name	explain	Return value
concat()	Connect two or more arrays , Does not affect the original array	return New array
slice()	Array truncation slice(begin,end), Does not affect the original array	return Intercepts the new array of parts
filter(item=>item.done)	Does not affect the original array	return New array
splice()	An array of update splice(begin, Number ,item1…itemX) The third parameter is optional , No filling is interception , Will affect the original array	return Intercepts the new array of parts

//  Be careful ：splice()、slice() It's all about the head and the tail 
    var arr=[1,20,60,7];
    var newArr = arr.slice(0,3)
    console.log(newArr);// [1,20,60]

Traverse

• Array.from()

Convert a class array or traversable object into a real array

Array.from( Traversable object name )

• forEach(function(value,index,arr) {})

No return value , It has no effect on the original array

arr.forEach(function(value,index,arr) {
    })
// value The element currently traversing 
// index Currently traversing the index of the element 
// arrobj Entire array 

• map(function(value,index,arr) {})

Support return return , It has no effect on the original array

array.map(function(value,index,arr), thisValue)
// value  Mandatory . The value of the current element 
// index  Optional . The index value of the current element 
// arr  Optional . The array object to which the current element belongs 
// thisValue  Optional . Object as the callback to execute , Pass to function , Used as a  "this"  Value . If you omit  thisValue, Or into  null、undefined, So the callback function's  this  For global objects .
//  Returns a new array 

//  Equate to 
function myMap(fn){
    
//this Is the array that calls this method 
	let newArr = []
	for(let i = 0;i<this.length;i++){
    
      let result = fn(this[i],i,this)
      newArr.push(result)
	}
	return newArr
}

Judge condition traversal query

// callback There are three parameters .
// value： Array elements found in each iteration .
// index： Index of array elements found in each iteration .
// arr： The array to be looked up .

• every(callback)

All items meet the condition , return true

• some(callback)

As long as there is A condition is satisfied , will return true

• find(callback)

Find the elements that match the criteria , Find the first value and return , No return found undefined

• findIndex(callback)

Find the elements that match the criteria , Find the first value and return its index , No return found -1

Be careful ：find() The value returned is ,indexOf() The index is returned

findIndex Than indexOf More powerful , You can find the object array through the callback function , but indexOf You can specify the index at which to start searching

Array to string

Method name	explain	Return value
toString()	Convert an array to a string , Comma separated each item	Returns a string
join(“ Separator ”)	Convert all elements in the array into a string	Returns a string

leetcode Example

217. There are duplicate elements

var containsDuplicate = function(nums) {
    
    let arr = []
    for(let i = 0 ; i<nums.length;i++){
    
        if(arr.indexOf(nums[i])==-1){
    
            arr.push(nums[i])
        }else{
    
            return true
        }
    }
    return false
};

53. Maximum subarray and

The first thought was direct violence , Save all the results in an array , Compare to get the maximum , But this will exceed the array storage limit

So we use Dynamic programming

var maxSubArray = function(nums) {
    
    let res = nums[0]
    let sum = 0
    for(const num of nums){
    
        //  If and sum Greater than 0, It means good for the future , Continue to count backwards 
        if(sum>0){
    
            sum += num
        }else{
    
            // sum Less than or equal to 0, Unfavorable to the later calculation , Calculate directly from the current value 
            sum = num
        }
        //  Use the old one res Relatively new sum, Assign the greater to res
        res = Math.max(res,sum)
    }
    return res
};

88. Merge two ordered arrays

//  The main idea is to use arrays es6 New method of 
//  Yes n==0 and m==0 The situation is judged separately 
//  Others are normal , We use splice Update the array 
//  Use sort Sort 
var merge = function(nums1, m, nums2, n) {
    
    if(n==0){
    
        return nums1
    }else if(m==0){
    
        Object.assign(nums1,nums2)
    }else{
    
        nums1.splice(m,nums1.length-m,...nums2)
        nums1.sort((a,b)=>{
    
            return(a-b)
        })
    }
};

1. Sum of two numbers

The most basic double for The loop is not written

//  Use map
//  Traversal array , Use target value - Find the required value from the value of the array 
//  Take the values in the array as value, Position as key Deposit in map
//  Find the one that meets the requirements value, Go back to the corresponding key
	var twoSum = function(nums, target) {
    
      let map = new Map()
      for(let i=0; i<nums.length; i++){
    
        const number = target - nums[i]
        if(map.has(number)){
    
          return [map.get(number),i]
        }else{
    
            map.set(nums[i],i)
        }
      }
  };

350. Intersection of two arrays II

//  double for loop , Meet the same push Enter results 
//  At the same time, delete the element of the second array and jump out of this loop 
var intersect = function(nums1, nums2) {
    
    const res = []
    for(let i=0;i<nums1.length;i++){
    
        for(let j=0;j<nums2.length;j++){
    
            if(nums2[j] == nums1[i]){
    
                res.push(nums2[j])
                nums2.splice(j,1)
                break
            }
        }
    }
    return res
};


//  Hash map
//  Use map,key by nums1 The elements of ,value Is the number of occurrences of this element 
//  When there is a number of times, we encounter nums2 Same element , Just push To the results 
//  And the number of times -1
var intersect = function(nums1, nums2) {
    
    const map = new Map()
    const res = []
    for(num1 of nums1){
    
        if(map[num1]){
    
            map[num1]++
        }else{
    
            map[num1] = 1
        }
        map.set(num1,map[num1])
    }
    for(num2 of nums2){
    
      if(map.get(num2)>0){
    
        res.push(num2)
        map.set(num2,--map[num2])
      }
    }
    return res
};

121. The best time to buy and sell stocks

Be careful prices The length of , nesting for The loop must time out

//  Greedy Algorithm 
//  Traverse prices, Subtract the minimum value encountered in the previous traversal from the current value and wait until the current maximum value 
//  Compare res And the current maximum , Give the big to res
var maxProfit = function(prices) {
    
    if(prices.length<2) return 0
    let max = 0
    let minPrice = prices[0]
    for(let i=0; i<prices.length;i++){
    
        max = Math.max(max,prices[i]-minPrice)
        minPrice = Math.min(prices[i],minPrice)
    }
    return max
};

566. Reshaping the matrix

Encounter this problem , My first thought is to convert a two-dimensional array to a one-dimensional array , Then carry out the following operations

Several methods of converting two-dimensional arrays to one-dimensional arrays ( Flattening arrays )

//  Method 1 ： Traverse , Use concat Splicing 
const arr1 = [[1,2],[3,4]]
var arr2 = []
for(let i=0;i<arr1.length;i++){
    
  arr2 = arr2.concat(arr1[i])
}

//  Method 2 ： Use apply()
// apply The first parameter of is used to modify this Point to , Pass in an empty array 
// apply The second argument to is an array , Can be used as an argument to its calling function ( namely [].concat Called apply, The parameters are used arr1)
// apply Will unlock the first layer of array parameters [[1,2],[3,4]]-->[1,2],[3,4]
//  At this time to use concat The splicing can be completed 
var arr2 = [].concat.apply([],arr1);

//  Method 3 ：flat( Parameters ) Flatten the array 
//  The parameter means the number of flattened layers 
    const arr1 = [[1,2],[3,4]]
    const arr2 = arr1.flat(1) // A two-dimensional --> A one-dimensional , flat 1 layer 

Solution code

var matrixReshape = function(mat, r, c) {
    
    //  The array is flattened 
    let arr = mat.flat()
    let res = []
    if(r*c != arr.length){
    
        return mat
    }else{
    
        // r That's ok 
        for(let i=0;i<r;i++){
    
            let item = []
            // c Column 
            for(let j=0;j<c;j++){
    
                item.push(arr.shift())
            }
            res.push(item)
        }
        return res
    }
};

//  call api, Continue simplification 
function matrixReshape(mat, r, c) {
    
    const arr = mat.flat()
    const res = []
    if(r*c != arr.length) return mat
    for(let i = 0; i < r; i++){
    
        // splice Intercept array , The return value is an array of intercepted parts 
        res.push(arr.splice(0,c));
    }
    return res;
};

118. Yang hui triangle

//  Two dimensional array dynamic programming 
var generate = function(numRows) {
    
    let arr = [[1]]
    //  Traverse each line 
    for(let i=0;i<numRows;i++){
    
        arr[i] = []
        arr[i][0] = 1 //  Every line begins and ends with 1
        arr[i][i] = 1
        for(let j=1;j<i;j++){
    
            //  Dynamic programming , The problem of demolitionism 
            arr[i][j] = arr[i-1][j-1]+arr[i-1][j]
        }
    }
    return arr
};