【代码随想录刷题笔记】——数组（持续更新中）

PaturNax 2023-03-28 原文

代码随想录——数组

理论基础

二分查找

704. 二分查找 - 力扣（LeetCode）

代码/思路

在一个有序数组中通过二分查找解决找到目标值的问题。

C++版

//版本一：左闭右闭的写法
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //定义target在[left,right]闭区间
        int left=0;
        int right = nums.size()-1;
        while(left<=right){
            //防止溢出，等同于(left + right)/2
            int middle = left + ((right-left)/2);
            if(nums[middle]>target){
                // target 在左区间，所以[left, middle - 1]
                right=middle-1;
            }else if(nums[middle]<target){
                // target在右区间，所以[middle + 1, right]
                left=middle+1;
            }else{// nums[middle] == target
                // 数组中找到目标值，直接返回下标
                return middle;
            }
        }
        //未找到目标就返回-1下标
        return -1;
    }
};

//版本二：左闭右开的写法
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //定义target在[left,right) 左闭右开区间
        int left=0;
        int right = nums.size();
        while(left<right){
            //防止溢出，等同于(left + right)/2
            int middle = left + ((right-left)/2);
            if(nums[middle]>target){
                // target 在左区间，所以[left, middle)
                right=middle;
            }else if(nums[middle]<target){
                // target在右区间，所以[middle + 1, right)
                left=middle+1;
            }else{// nums[middle] == target
                // 数组中找到目标值，直接返回下标
                return middle;
            }
        }
        //未找到目标就返回-1下标
        return -1;
    }
};

Java版

//版本一的写法
class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] 或 大于nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

JavaScript版

 //版本一的写法
var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        //注意向下取整，防止变成浮点数
        let mid = left + Math.floor((right - left)/2);
        if (nums[mid] > target) {
            right = mid - 1; 
        } else if (nums[mid] < target) {
            left = mid + 1;   
        } else {
            return mid;
        }
    }
    return -1;
};

时间复杂度

时间复杂度：\(O(\log n)\)，其中 \(n\) 是数组的长度。由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 \(O(\log n)\)，其中 \(n\) 是数组的长度。
空间复杂度：\(O(1)\)。

35. 搜索插入位置

代码/思路

暴力搜索

遍历查找

C++版

//版本一：暴力写法
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 无非就三种情况：
        // 1. 插入数组所有元素前或所有数组元素的末尾
        // 2. 找到数组中的目标索引
        // 3. 插入到数组的某个位置
        // 因此，先遍历查找
        for(int i=0;i<nums.size();i++){
            // 一旦发现大于或者等于target的num[i]，符合2与3的情况
            if(nums[i]>=target){
                return i;
            }
        }
        //当发现数组未空，或者已经遍历完了，那么返回该数组本身就符合第1种情况
        return nums.size();
    }
};

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

二分查找

这题的本质其实跟704题一模一样，最终还是可以通过二分查找决定目标值是要在数组中的索引或是应插入的位置。

C++版

//版本二：二分查找的左闭右闭的写法
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int middle=left+((right-left)/2);
            if (nums[middle] > target) {
                right = middle - 1; 
            } else if (nums[middle] < target) {
                left = middle + 1; 
            } else { 
                return middle;
            }
        }
        // 分为以下四种情况：
        // 1、目标值在数组所有元素之前  [0, -1]
        // 2、目标值等于数组中某一个元素  return middle;
        // 3、目标值插入数组中的位置，return  right + 1
        // 4、目标值在数组所有元素之后的情况,因为是右闭区间，所以 return right + 1
        return right+1;
    }
};
//版本三：二分查找的左闭右开的写法
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0,right = nums.size(); 
        while (left < right) { 
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; 
            } else if (nums[middle] < target) {
                left = middle + 1; 
            } else { 
                return middle; 
            }
        }
        // 分别为以下四种情况
        // 目标值在数组所有元素之前 [0,0)
        // 目标值等于数组中某一个元素 return middle
        // 目标值插入数组中的位置 [left, right) ，return right 即可
        // 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right
        return right;
    }
};

Java版

//版本二的写法
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; 
            if (nums[mid] > target) {
                right = mid - 1; 
            } else if (nums[mid] < target) {
                left = mid + 1; 
            } else {
                return mid;
            }
        }
        return right + 1;
    }
}

JavaScript版

//版本二的写法
var searchInsert = function (nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) >> 1);
    if (target > nums[mid]) {
        left = mid + 1;
    } else if(target < nums[mid]){
        right = mid - 1;
    }else{
        return mid;
    }
  }

  return right+1;
};

复杂度分析

时间复杂度：\(O(log n)\)
空间复杂度：\(O(1)\)

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

代码/思路

这题采用 \(C++\) 的 \(upper_bound()\) 和 \(lower_bound()\) 就可以找到目标值 \(target\) 在排序数组的开始位置和结束位置，而这两个函数可以用二分查找实现，代码参考《谷歌高畅Leetcode刷题笔记》，具体实现思路其实也可以看leetcode的官方题解。

C++版

//版本一：二分查找
class Solution {
private:
//这里采用左闭右闭的写法，upper_bound()与lower_bound()的唯一不同之处在于
//要令upper指向最后一位就令nums[mid]>target而不是像lower一样令nums[mid]>=target
    int lower_bound(vector<int> &nums,int target){
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }

    int upper_bound(vector<int> &nums,int target){
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //如果一开始的数组为空是无效的
        if(nums.empty()) return vector<int>{-1,-1};
        int lower=lower_bound(nums,target);
        //这里要减一
        int upper=upper_bound(nums,target)-1;
        //如果开始位置已经到了末尾或者根本不等于我们的目标值就是无效的
        if(lower==nums.size() || nums[lower]!=target){
            return vector<int>{-1,-1};
        }
        return vector<int>{lower,upper};
    }
};

Java版

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //根据之前的C++的代码内容，就可以知道upper_bound()和lower_bound()怎么写在一起，但是要注意之前的判断条件其实也要跟着变得如下严谨
        int lowerIndex = binarySearch(nums, target, true);
        int upperIndex = binarySearch(nums, target, false) - 1;
        //在保证lower的下标要小于upper的下标 与 upper的下标不超过nums数组的长度的情况下，再确认upper与lower值是否跟target相同，
        if (lowerIndex <= upperIndex && upperIndex < nums.length && nums[lowerIndex] == target && nums[upperIndex] == target) {
            return new int[]{lowerIndex, upperIndex};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean be_lower) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //不用担心溢出
            int mid = (left + right) / 2;
            if (nums[mid] > target || (be_lower && nums[mid] >= target)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

JavaScript版

const binarySearch = (nums, target, be_lower) => {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        //向下取整
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target || (be_lower && nums[mid] >= target)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

var searchRange = function(nums, target) {
    let ans = [-1, -1];
    const lowerIndex = binarySearch(nums, target, true);
    const upperIndex = binarySearch(nums, target, false) - 1;
    if (lowerIndex <= upperIndex && upperIndex < nums.length && nums[lowerIndex] === target && nums[upperIndex] === target) {
        ans = [lowerIndex, upperIndex];
    } 
    return ans;
};

Python版

class Solution(object):
    def searchRange(self, nums, target):
        # 这题的含义类似于C++的lower_bound 和 upper_bound 函数，具体的函数的实现，可以通过二分查找
        def lower_bound(nums,target):
            left=0;right=len(nums)
            while left<right:
                mid=left+(right-left)/2
                if nums[mid]>=target:
                    right=mid
                else:
                    left=mid+1
            return left
            
        def upper_bound(nums,target):
            left=0;right=len(nums)
            while left<right:
                mid=left+(right-left)/2
                if nums[mid]>target:
                    right=mid
                else:
                    left=mid+1
            return left
        if len(nums)==0:return [-1,-1]
        lower=lower_bound(nums,target)
        # 这里需要减一位，因为得到的值的下标会溢出
        upper=upper_bound(nums,target)-1
        if lower==len(nums) or nums[lower]!=target:
            return [-1,-1]
        return [lower,upper]

复杂度分析

时间复杂度：\(O(\log n)\) ，其中 \(n\) 为数组的长度。二分查找的时间复杂度为 \(O(\log n)\)，一共会执行两次，因此总时间复杂度为 \(O(\log n)\)。
空间复杂度：\(O(1)\)

69. x 的平方根

代码/思路

这题就是给你一个值，然后求它的算术平方根，一般人的思路也许就是硬算，就跟自己的朋友学数学一样（声明：这个朋友不是我），或者投机取巧用已有的轮子。

其实这题也可以使用二分查找，因为我们可以设置\([1,x]\)的区间（当然要注意\(x\)为\(0\)的情况），在二分查找该区间要的数值\(sqrt\)的过程中，其实令值\(x\)除以中间值\(mid\)，再跟\(sqrt\)一一比较判断即可。

C++版

//版本一：二分查找
class Solution {
public:
    int mySqrt(int x) {
        if(x==0)return x;
        int left=1,right=x;
        while(left<=right){
            int mid=left+(right-left)/2;
            int sqrt=x/mid;
            if(mid == sqrt) return mid;
            else if (mid>sqrt) right=mid-1;
            else left=mid+1;
        }
        return right;
    }
};

Java版

class Solution {
    public int mySqrt(int x) {
        int left=0,right=x,result=-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if((long) mid*mid<=x){
                result=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return result;
    }
}

JavaScript版

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

Python版

class Solution(object):
    def mySqrt(self, x):
        # 这里单独拿出0的情况分析
        if x==0:return x
        left=1;right=x
        while left<=right:
            mid=left+(right-left)/2
            sqrt=x/mid # mid*mid=x
            if mid==sqrt:
                return mid
            elif mid>sqrt:
                right=mid-1
            else:
                left=mid+1
        return right

复杂度分析

时间复杂度：\(O(\log x)\) 。
空间复杂度：\(O(1)\)。

另外跟着leetcode写袖珍计算器算法，牛顿迭代法。

袖珍计算器算法

「袖珍计算器算法」是一种用指数函数 \(\exp\) 和对数函数 \(\ln\) 代替平方根函数的方法。

我们将 \(\sqrt{x}\)写成幂的形式 \(x^{1/2}\) ，再使用自然对数 \(e\) 进行换底，即可得到

\[\sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x} \]

这样我们就可以得到 \(\sqrt{x}\) 的值了。

C++版

class Solution {
public:
    int mySqrt(int x) {
        //单独拿0出来处理
        if(x==0){
            return 0;
        }
        //经过转换的公式
        int ans=exp(0.5*log(x));
        //由于计算机无法存储浮点数的精确值，会有整数1的相差，所以要对 ans 与 ans+1 进行判断
        return ((long long)(ans+1)*(ans+1)<=x ?  ans+1:ans);    
    }
};

复杂度分析

时间复杂度：\(O(1)\)，由于内置的 \(exp\) 函数与 \(log\) 函数一般都很快，我们在这里将其复杂度视为 \(O(1)\)。
空间复杂度：\(O(1)\)。

牛顿迭代法

这理论把我看到吐了，让我想起自己不自量力地参加数学建模竞赛的那些日子。

牛顿迭代法的本质是借助泰勒级数，根据高等数学的内容，解答给的是二阶泰勒公式\(y=f(x)=x^2−C\)

以我们高中熟悉的斜线方程\(y-y_i=k(x-x_i)+b\)为例，其中斜率\(k\)为\(f(x)\)的导数。

由于选择 \(x_0=C\) 作为初始值，找点 \((x_i, x_i^2 - C)\) 作直线，之后经过转换，求的\(x\)值就成为了新的迭代结果\(x_{i+1}\)。

也即leetcode官方解答的

\[x_{i+1} = \frac{1}{2}\left(x_i + \frac{C}{x_i}\right) \]

C++版

class Solution {
public:
    int mySqrt(int x) {
        //单独拿0出来处理
        if(x==0){
            return 0;
        }
        //C表示待求出平方根的那个整数，而又选择 x_0 = C 作为初始值
        double C=x,x0=x;
        while(true){
            double xi=0.5*(x0+C/x0);
            //设立极限值
            if(fabs(x0-xi)<1e-7){
                break;
            }
            //迭代递进
            x0=xi;
        }
        //向下取整
        return int(x0);
    }
};

复杂度分析

时间复杂度：\(O(\log x)\) ，此方法是二次收敛的，相较于二分查找更快。
空间复杂度：\(O(1)\)。

367. 有效的完全平方数

代码/思路

这题如果采用暴力的写法，其实就是遍历\([1,完全平方数]\)的区间，一个一个算。

那么清楚暴力的方法后，就可以通过二分查找去缩短查找耗时。

当然其实也可以用牛顿迭代法，具体的实现步骤其实跟上一题一致，只不过由于这题的结果为布尔值，所以代码上特别处理。

C++版

//版本一：暴力写法
class Solution {
public:
    bool isPerfectSquare(int num) {
        //要防溢出，用long
        long x=1,square=1;
        while(square<=num){
            if(square==num){
                return true;
            }
            //遍历
            ++x;
            square=x*x;
        }
        //遍历完都没找到
        return false;
    }
};

//版本二：二分查找
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=0,right=num;
        while(left<=right){
            int mid=left+(right-left)/2;
            long square=(long) mid*mid;
            if(square<num){
                left=mid+1;
            }else if(square > num){
                right=mid-1;
            }else{
                return true;
            }
        }
        return false;
    }
};

//版本三：牛顿迭代法
class Solution {
public:
    bool isPerfectSquare(int num) {
        int C=num;
        double x0=num;
        while(true){
            double xi=0.5*(x0+C/x0);
            //不给用函数fabs，这里求极限值
            if(x0-xi<1e-6){
                break;
            }
            x0=xi;
        }
        int x=(int) x0;
        //判断
        return x * x == num;
    }
};

Java版

//版本二的写法
class Solution {
    public boolean isPerfectSquare(int num) {
        int left=0,right=num;
        while(left<=right){
            int mid=left+(right-left)/2;
            long square=(long) mid*mid;
            if(square<num){
                left=mid+1;
            }else if(square > num){
                right=mid-1;
            }else{
                return true;
            }
        }
        return false;

    }
}

JavaScript版

//版本二的写法
var isPerfectSquare = function(num) {
    let left=0,right=num;
    while(left<=right){
        let mid=Math.floor((left+right)/2);
        let square=mid*mid;
        if(square<num){
            left=mid+1;
        }else if(square>num){
            right=mid-1;
        }else{
            return true;
        }
    }
    return false;
};

如果是暴力

时间复杂度：\(O(\sqrt{n})\)，其中 \(n\) 为正整数 \(\textit{num}\)的最大值。我们最多需要遍历 \(\sqrt{n} + 1\)
空间复杂度：\(O(1)\)。

如果是二分查找或者牛顿迭代的话

复杂度分析

时间复杂度：\(O(\log n)\) 。
空间复杂度：\(O(1)\)。

双指针——左右、快慢

27. 移除元素

题目意思就是要通过覆盖元素的操作达到删除元素的目的，返回移除元素后的长度。

一、暴力法

最容易想到的是暴力法，外循环i查找整个数组元素，当找到该要删除的元素，便通过内循环j=i+1把后面的元素“挪”前一位，直到删无可删为止，更新数组长度与刷新i目前遍历的位置应是不重复的新元素所在位置（或是重复元素的最后位置）。

JavaScript版

//版本一：暴力
var removeElement = function(nums, val) {
    var len=nums.length;
    for(let i=0;i<len;i++){
        //找到要删除的元素
        if(nums[i]==val){
            //后面的元素网前移，覆盖这个要删除的元素
            for(let j=i+1;j<len;j++){
                nums[j-1]=nums[j];
            }
            //因为已经覆盖好了，那么i的前一个位置就是新的元素
            i--;
            //由于是被覆盖，所以相对应的长度len
            len--;
        }
    }
    return len;
};

复杂度分析

时间复杂度：\(O(n^2)\) 。
空间复杂度：\(O(1)\)。

二、快慢双指针

快指针用来找数组新元素，慢指针用来指向要被替换的元素。
这种方法不会改变元素的相对位置。

JavaScript版

var removeElement = function(nums, val) {
    //创建快慢双指针
    let fast=0,slow=0;
    //快指针用于数组新元素
    while(fast<nums.length){
        //当找到要删除的元素时候，快指针就要比慢指针多走一步，从而达到覆盖的目的
        if(nums[fast] != val){
            nums[slow]=nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
};

复杂度分析

时间复杂度：\(O(n)\) 。
空间复杂度：\(O(1)\)。

三、左右双指针

这个方法则会改变元素的相对位置。

当确保左指针小于等于右指针：

左指针的作用是要找到第一个要被删除元素的位置，因此要实现以下的逻辑：
- 在左指针不超过右指针的情况下，左指针指向的值是在遇到第一个被删除元素停住。
右指针则是在左指针不超过右指针的情况下，右指针指向的值则要保证不遇到被删除的元素，因为它要替换掉左指针指向的值。

JavaScript版

var removeElement = function(nums, val) {
    //创建左右双指针
    let left=0,right=nums.length-1;
    while(left<=right){
        //左指针要找到被删除的元素
        while(left<=right && nums[left]!=val){
            ++left;
        }
        //右指针要保持在不找删除的元素
        while(left<=right && nums[right]==val){
            --right;
        }
        //将右边不等于val的元素覆盖到左边
        if(left<right){
            nums[left++]=nums[right--];
        }
    }
    return left;
}

复杂度分析

时间复杂度：\(O(n)\) 。
空间复杂度：\(O(1)\)。

283. 移动零

这题就是给你个数组让你把数组里所有为0 的值移到非0的后面。

一、两次遍历

第一次遍历要把所有非0的数值一个接着一个的写到前面。

那么剩余的位置就是第二次遍历可以从非0数组的末尾一直加0。

JavaScript版

var moveZeroes = function(nums) {
    //找非0值的指针
    let j=0;
    //第一次遍历把所有非0值写到前面
    for(let i=0;i<nums.length;i++){
        if(nums[i]!==0){
            nums[j++]=nums[i];
        }
    }
    //第二次遍历则是要把所有0值写到后面
    for(let i=j;i<nums.length;i++){
        nums[i]=0;
    }
    return nums;
};

复杂度分析

时间复杂度：\(O(n)\) 。
空间复杂度：\(O(1)\)。

二、快慢双指针

快指针找非0值，慢指针用来跟快指针进行交换。

JavaScript版

var moveZeroes = function(nums) {
    let slow=0,fast=0;
    while(fast<nums.length){
        //遇到非0元素，快指针指向的值就要与慢指针指向的值交换
        if(nums[fast]!==0){
            [nums[fast],nums[slow]]=[nums[slow],nums[fast]];
            slow++;
        }
        fast++;
    }
    return nums;
};

复杂度分析

时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)

844. 比较含退格的字符串

这题给了两个字符串，并说明#是退格键，要比较操作后的字符是否一样。

栈处理

如果是退格键#，那么将栈弹出
如果是普通字符，则压入

这个方法对于JS来说并不是最好的，因为要考虑数组是对象这个问题。

JS版

var backspaceCompare = function(s, t) {
    //因为数组是对象，他们只看引用地址判断
    //所有要toString转换成字符串
    return build(s).toString()===build(t).toString();
};

var build=function(str){
    let result=[];
    for(ch of str){
        if(ch!='#'){
            result.push(ch);
            //如果栈不为空
        }else if(result.length!==0){
            result.pop();
        }
    }
    return result;
}

复杂度分析

时间复杂度：\(O(N+M)\)，N与M分别是字符串\(s\)和\(t\)的长度
空间复杂度：\(O(N+M)\)

双指针

一个字符是否被删除，取决于字母后面的退格键，而与前面无关，所以我们可以弄双指针，分别指向字符串\(s\)和\(t\)的末尾，逆序遍历。

那么应该要弄各自的计数器skip，碰到#字符，则是计数+1，碰到普通字符则是-1。

当计数器为0，则说明遇到的该字符不用删
不为0，则删到对应的位置。

之后处理完就对能确定的一个字符进行比较，然后接着重复以上计数的过程。

JS版

var backspaceCompare = function(s, t) {
    //双指针指向字符串的末尾
    let i=s.length-1,j=t.length-1;
    //定义各自的计数器
    let skipS=0,skipT=0;

    //每次循环比较字符的条件
    while(i>=0 || j>=0){
        //逆序遍历计数
        while(i>=0){
            //找到退格键
            if(s[i]==='#'){
                skipS++,i--;
            //当不为退格键，但计数器不为0
            }else if(skipS>0){
                skipS--,i--;
            //当不为退格键，计数器为0
            }else{
                //退出遍历
                break;
            }
        }   

        while(j>=0){
            if(t[j]==='#'){
                skipT++,j--;
            }else if(skipT>0){
                skipT--,j--;
            }else{
                break;
            }
        }   

        //要开始比较普通字符
        if(i>=0 && j>=0){
            //如果出现字符不一致的情况
            if(s[i]!==t[j]){
                return false;
            }
        }else{
            //当任意一个已经没法遍历时
            if(i>=0 || j>=0){
                return false;
            }
        }  
        //都逆序遍历找普通字符
        i--,j--;
    }
    return true;
};

977. 有序数组的平方

给你个数组，求他们的平方，然后排序。

JS版

//版本一：暴力写法
var sortedSquares = function(nums) {
    for(let i=0;i<nums.length;i++){
        nums[i]*=nums[i];
    }
    return nums.sort((a,b)=>a-b);
};
//版本二：左右双指针
var sortedSquares = function(nums) {
    let n=nums.length;
    let ans=new Array(n).fill(0);
    let i=0,j=n-1,Index=n-1;
    while(i<=j){
        let left=nums[i]*nums[i],
        right=nums[j]*nums[j];
        if(left<right){
            ans[Index--]=right;
            j--;
        }else{
            ans[Index--]=left;
            i++;
        }
    }
    return ans;
};

Java版

//版本二的写法
class Solution {
    public int[] sortedSquares(int[] nums) {
        int right=nums.length-1,left=0;
        int [] result=new int[nums.length];
        int index=result.length-1;
        while(left<=right){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                result[index--]=nums[left]*nums[left];
                ++left;
            }else{
                result[index--]=nums[right]*nums[right];
                --right;
            }
        }
        return result;
    }
}

C++版

//版本二的写法
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        int k=right;
        vector<int> result(nums.size(),0);
        while(left<=right){
            if(nums[left]*nums[left]<=nums[right]*nums[right]){
                result[k--]=nums[right]*nums[right];
                right--;
            }else{
                result[k--]=nums[left]*nums[left];
                left++;
            }
        }
        return result;
    }
};

复杂度分析

时间复杂度：双指针\(O(n)\)，暴力则是\(O(n+nlogn)\)

滑动窗口

209. 长度最小的子数组

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

904. 水果成篮

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

76. 最小覆盖子串

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

模拟

59. 螺旋矩阵 II

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

54. 螺旋矩阵

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

剑指 Offer 29. 顺时针打印矩阵

C++版

//版本一：暴力写法


//版本二：二分查找

Java版

//版本二的写法

JavaScript版

//版本二的写法

总结

有关【代码随想录刷题笔记】——数组（持续更新中）的更多相关文章

ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2
给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？最佳答案在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru
ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2
我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代
ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
ruby - 多次弹出/移动 ruby 数组 - 2
我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。关于ruby-多次弹出/移动ruby数组，我们在StackOverflow上找到一
ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
ruby - 将数组的内容转换为 int - 2
我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]
ruby - 通过 erb 模板输出 ruby 数组 - 2
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
ruby - 检查数组是否在增加 - 2
这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife
ruby-on-rails - 使用 rails 4 设计而不更新用户 - 2
我将应用程序升级到Rails4，一切正常。我可以登录并转到我的编辑页面。也更新了观点。使用标准View时，用户会更新。但是当我添加例如字段:name时，它不会在表单中更新。使用devise3.1.1和gem'protected_attributes'我需要在设备或数据库上运行某种更新命令吗？我也搜索过这个地方，找到了许多不同的解决方案，但没有一个会更新我的用户字段。我没有添加任何自定义字段。最佳答案如果您想允许额外的参数，您可以在ApplicationController中使用beforefilter，因为Rails4将参数
ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2
我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

【代码随想录刷题笔记】——数组（持续更新中）

代码随想录——数组

二分查找

代码/思路

时间复杂度

代码/思路

暴力搜索

复杂度分析

二分查找

复杂度分析

代码/思路

复杂度分析

代码/思路

复杂度分析

袖珍计算器算法

复杂度分析

牛顿迭代法

复杂度分析

代码/思路

复杂度分析

双指针——左右、快慢

一、暴力法

复杂度分析

复杂度分析

三、左右双指针

复杂度分析

一、两次遍历

复杂度分析

二、快慢双指针

复杂度分析

栈处理

复杂度分析

双指针

复杂度分析

滑动窗口

模拟

总结

随机推荐