Binary search

We can reduce the number of comparisons and reduce the time complexity by using its orderness. The so-called binary search is to take the value in the middle of an array, compare it with the target value, and return its index if it is equal. If the target value is greater than it, So we do the same thing from the right side of the number (or the same thing from the left side), and return -1 if we don’t find it

    var arr=[1.2.3.4.5.6]
    function binSearch(arr,target){
        let start = 0
        let end = arr.length-1
        while(start<=end){
            var mid = Math.floor((start+end)/2)
            if(arr[mid]===target){return mid}
            else if(target<arr[mid]){end=mid-1}
            else{start = mid+1}}return -1
    }
    console.log(binSearch(arr,4))
Copy the code

Longest substring of the same element

For example, ‘aabbbbccCCCCCCC’ has the longest length of C and the longest length of 9. Using a sliding window, the same element is converted, the right pointer moves to the right, count+1, different count is set to 0, and left is set to the current index

    var str = 'aabbbbccccccccc'
    function maxLengthSubstr(str){
        let count=0
        let max=0
        let left=0
        let right=0
        if(str.length==0) return 0
        if(str.length==1) return 1
        while(right! ==str.length){while(str[left]===str[right]){
                count++
                right++
            }
            max=Math.max(max,count)
            count=0
            left=right
        }
        return max
    }
    console.log(maxLengthSubstr(str))
Copy the code

Duplicate numbers in an array

In a nums array of length n, all the digits are in the range 0 to n-1. Some digits in the array are repeated, but we do not know how many digits are repeated, and we do not know how many times each digit is repeated

    var nums=[1.2.1.3]
    function findRepeadtNumber(nums){
        const map = new Map(a)for(let i=0; i<nums.length; i++){if(map.get(nums[i])===0) return nums[i]
            else{map.set(nums[i],0)}}return false
        
    }
    console.log(findRepeadtNumber(nums))
Copy the code

Maximum sum of contiguous subarrays

Input an integer array, the array of one or more consecutive integers to form a subarray, find the sum of all subarrays of the maximum dynamic programming solution

    function maxSubArray(nums){
        let pre=0
        let maxAns=nums[0]
        nums.forEach(item= >{
            pre = Math.max(pre+item,item)
            maxAns = Math.max(pre,maxAns)
        })
        return maxAns
    }
Copy the code

Find a number in a sorted array

Count the number of occurrences of a number in a sorted array violence: traversal +hashmap; Since it is an ordered array, we can use binary search to find the index of the specified number, and then use two Pointers to traverse the index backwards and forwards

    function search(nums,target){
        var index = binSearch(nums,target)
        if(index == -1) return 0
        else{
            let count=1// Once it is found, it counts itself once
            for(let i=index+1; i<nums.length; i++){if(nums[i]===nums[index]){count++}
                else{break}}for(let i=index-1; i>=0; i--){if(nums[i]===nums[index]){count++}
                else{break}}return count
        }
        
        
    }
    function binSearch(nums,target){
        var start=0
        var end=nums.length-1
        
        while(start<=end){
            var mid = Math.floor((start+end)/2)
            if(target==nums[mid]){return mid}
            else if(target<nums[mid]){end=mid-1}
            else{start = mid +1}}return -1
    }
    
    var nums=[1.1.2.2.3.4.5.5.6.6.6.7.8.9]
    console.log(search(nums,6))
Copy the code

Flip word order

For example, ‘Banana Apple pear’ is flipped to’ Pear Apple banana’ and you can have two Pointers: one for the movement within the word, one for the movement of the number of words

    function reverseWord(str){
        let p,q,res=[]//p controls the pointer movement inside the word, q controls different words
        // Remove the first space
        str=str.trim()
        p=q=str.length-1
        while(p>=0) {while(p>=0&&str[p]! =' ') {// when p is not a space
                if(str[p-1= = =' '||p==0){
                    res.push(str.substring(p,q+1))
                }
                p--
            }
         while(p>=0&&str[p]===' ') {//p refers to the space operation
             p--
             q=p
         }
        }
        return res.join(' ')}Copy the code

Left rotation string

The left rotation of a string escapes the preceding strings to the end of the string. Define a function to rotate the string left. For example, if you enter the string “abcdefg” and the number 2, the function will return “cdefgab” as the result of a left rotation of two digits.

    function reverseLeftWords(str,num){
        // Define auxiliary strings
        var tmpstr=' '
        for(let i=0; i<num; i++){ tmpstr=s[i]+tmpstr }return str.substring(n)+tmpstr
        
    }
Copy the code