第一天——数组（704. 二分查找，27. 移除元素）

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。而且数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

数组的算法题一般有以下几种处理方法

两次暴力循环

双指针

同方向
对向夹逼

704. 二分查找

学习链接

https://programmercarl.com/0704.二分查找.html

个人想法

这道题是典型的二分查找的问题，所谓二分查找的前提就是对一个有序数组进行处理，每次以数组左右下标的中间index的value作为参考点，与目标值比较，如果 value < target ，则说明所需要的index在左区域，如果 value > target 则在右区域，直到找到 value === target 或最接近的值达到要求

解题代码


function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1
    while(left <= right ){
        let mid = left + Math.floor((right - left) / 2)
        if(nums[mid] < target){
            left = mid + 1
        } else if (nums[mid] > target){
            right =  mid - 1 
        } else {
            return mid
        }
    }
    return -1
};

难点

这道题一般来说有两种解法，左闭右闭和左闭右开，两种情况的判断逻辑和取值不同，我一般会选择左闭右闭，理解更好，简单写下左闭右开的代码吧


function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length  // 差别1 right取值
    while(left < right){ // 差别2 跳出循环条件
        let mid = left + Math.floor((right - left) / 2)
        if(nums[mid] < target){
            left = mid + 1
        } else if (nums[mid] > target){
            right = mid  // 差别3 right 取值
        } else {
            return mid
        }
    }
    return -1
};

时间复杂度：O(log n)

空间复杂度：O(1)

思考

还是左闭右闭更符合我们平时数组操作的习惯

相关题目

35.搜索插入位置

解法：由于升序排列，所以只需要在 nums[mid] >= target 时记录位置，所以在每次修改right值时记录mid值


function searchInsert(nums: number[], target: number): number {
    let left = 0 ;
    let right = nums.length - 1
    let res = nums.length
    while(left <= right){
        let mid = left + Math.floor((right - left)/2)
        if(nums[mid] < target){
            left = mid + 1 
        } else {
            res = mid
            right = mid - 1
        }
    }
    return res
};

34. 在排序数组中查找元素的第一个和最后一个位置

解法：这道题等于是35的高级版，通过两个函数，一个找插入左边界，一个找右边界，在排除一些边界条件，得到结果


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {

    const getLeftPosition = (nums, target) =>{
        let left = 0;
        let right = nums.length - 1 
        let ans = 0
        while (left <= right){
            let mid = left + Math.floor((right - left) / 2)
             if(nums[mid] >= target){
                // 取左边界就找右边最接近的
                ans = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
           
        }
        return ans 
    }
    const getRightPosition = (nums, target) =>{
        let left = 0;
        let right = nums.length - 1 
        let ans = 0
        while (left <= right){
            let mid = left + Math.floor((right - left) / 2)
            if(nums[mid] <= target){
                // 取右边界找左边最接近的
                ans = mid
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return ans 
    }

    const left = getLeftPosition(nums,target)
    const right = getRightPosition(nums,target)

    if(left <= right && nums[left] === target && nums[right] === target){
        return [left,right]
    } 

    return [-1,-1]
};

69.x的平方根

解法：判断条件从 nums[mid] > target 变成 mid * mid > taget 仅此而已

因为这个题需要的是Math.floor，所以ans 在 ≤ 处取值


/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0
    let right = x
    let ans = 0
    while(left <= right){
        let mid = left + Math.floor((right - left)/ 2)
        if(mid * mid > x){
           right = mid - 1
        } else{
            left = mid + 1
            ans = mid 
        }
    }
    return ans
};

367. 有效的完全平方数

跟上题一样，最后 return ans * ans === num


/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
    let left = 0 
    let right = num
    let ans = 0
    while(left <= right){
        let mid = left + Math.floor((right - left)/2)
        if(mid * mid > num){
            right = mid - 1
        } else {
            ans = mid 
            left = mid +1
        }
    }
    return ans * ans === num
};

27.移除元素

学习链接：

https://programmercarl.com/0027.移除元素.html#算法公开课

个人想法：

这个题有个常见的问题就是直接使用splice方法生成新数组，忽略了题目中在原数组中修改的要求，导致出错。

具体解法应该使用双指针，左边i位于找到的第一个元素位置开始进行循环，右边j一直交换左右的元素内容，达到把要求的元素赶到最后一位，最后再去除掉

解题代码：


/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let slow = 0
    for(let fast = 0; fast < nums.length; fast++){
        if(nums[fast] !== val){
            nums[slow++] = nums[fast] // 如果不相等，就两个指针一起前进
        }
    }
    return slow // 剔除val的数组长度
};

难点：

去理解双指针的想法，两个指针在一个for循环里一起前进，遇到相同得值，fast前进，slow暂停，交换数值，达到把val赶到数组最后面的结果

时间复杂度：O(n)

空间复杂度：O(1)

相关题目

26.删除排序数组中的重复项

和原来的题目类似，找一个值记录每次修改后的新值，再比较即可


/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let slow = 0
    let value = Infinity
    for(let fast = 0; fast < nums.length; fast++){
        if(nums[fast] !== value){
            nums[slow++] = nums[fast]
            value = nums[fast] // 和前值不同的话更新比较的值
        }
    }
    return slow
};

283.移动零

解法1：和原题一样处理后，做一次循环，把后值都改成0


/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
   let slow = 0
   for(let fast = 0; fast < nums.length; fast++){
    if(nums[fast] !== 0){
        nums[slow++] = nums[fast]
    }
   }
   for(let i = slow;i<nums.length;i++){
     nums[i] = 0
   }
};

解法2：第一种的改进版，在我们判断到 nums[fast] !== 0 时，直接交换值nums[slow]和nums[fast]达到我们的目的,很巧妙的想法


/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
   let slow = 0
   for(let fast = 0; fast < nums.length; fast++){
    if(nums[fast] !== 0){
        let temp = nums[fast]
        nums[fast] = nums[slow]
        nums[slow++] = temp
    }
   }
};

844.比较含退格的字符串

双指针法

简单来说就是循环遍历string，遇到 # 且slow > 0退就一格，截取后判断结果是否相同


/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    const formatString = (string) => {
        let array =  string.split('')
        let slow = 0
        for(let fast = 0;fast < array.length; fast++){
            if(array[fast] !== '#'){
                array[slow++] = array[fast]
            } else if(slow > 0){
                slow --
            }
        }
        return array.splice(0,slow).join('')
    }
    return formatString(s) === formatString(t)
};

压栈，新建一个数组，遇见#就pop，剩下的join


var backspaceCompare = function(s, t) {
    const checkString = (s) =>{
        let array = s.split('')
        let left = 0
        const res = []
        for (let i = 0;i < array.length; i++){
            if(array[i] !== '#'){
                res[left] = array[i]
                left ++
            } else if(left > 0){ //# 前面有值才删
                res.pop()
                left --
            }
        }
        return res.join('')
    }
    return checkString(s) === checkString(t)
};