首页 > 其他分享 >【Leetcode_Hot100】普通数组

【Leetcode_Hot100】普通数组

时间:2024-08-27 22:04:02浏览次数:13  
标签:nums int res sum length Hot100 数组 Leetcode

普通数组

53. 最大子数组和

56. 合并区间

189. 轮转数组

238. 除自身以外数组的乘积

41. 缺失的第一个正数

53. 最大子数组和

方法一:暴力解

依次遍历数组中的每个子数组,进而判断res的最大值

超时

class Solution {
    public int maxSubArray(int[] nums) {
        int res = 0;

        for(int i=0; i<nums.length; i++) {
            int sum = 0;
            for(int j=i; j<nums.length; j++) {
                sum += nums[j];
                res = Math.max(res, sum);
            }
        }

        return res;
    }
}

方法二:贪心算法

贪心算法,保证累加后的结果始终对当前结果存在增益效果即可

  1. sum用于记录前几项的元素和,动态更新;res用于记录最大的元素和,动态更新
  2. 求解的关键在于sum值的更新,假设不考虑nums[i]的值,此处仅关注nums[i-1]
    1. 如果nums[i-1]>0,那么对nums[i]均有增益作用
    2. 如果nums[i-1]<0,无论nums[i]为正还是负,对nums[i]均无增益作用;例如nums[i-1]=-1,nums[i]=-3,此时,重新累加的值为-3,而叠加后的值却为-4
  3. 那么何时应该累加sum?将上述思路扩展至前几项的和sum:如果sum值小于0,则sum再加上nums[i]值会更小,无有增益作用。因此此时sum应从0开始计算。
  4. 初始化,res = Integer.MIN_VALUEsum = 0表示从0开始累加
class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int sum = 0;

        for(int i=0; i<nums.length; i++) {
            // 如果 sum<0, 说明前几项无增益作用,重新累计sum
            if(sum<0) {
                sum = 0;
            }
            sum += nums[i];
            res = Math.max(res, sum);
        }

        return res;
    }
}

方法三:动态规划

与上述贪心算法的实现思路似乎比较类似,动态规划问题设计了一个状态转移方程,而贪心算法则侧重于取当前最优方案

  1. 状态转移方程:dp[i] = max(dp[i-1]+nums[i], nums[i]),如果加上nums[i]的元素后的值还小于nums[i],则舍弃之前的元素
  2. 优化上述方程,更新时只需要dp[i-1]dp[i],因此可采用变量sum进行更新
  3. 初始化,res = Integer.MIN_VALUEsum = 0表示从0开始累加
class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int sum = 0;

        for(int i=0; i<nums.length; i++) {
            sum = Math.max(sum+nums[i], nums[i]);
            res = Math.max(res, sum);
        }

        return res;
    }
}

56. 合并区间

先将给定数组按照左边界进行排序,之后依次比较右边界的值,即可确定合并区间。

变量定义:ArrayList<int[]> res存储结果

左边界leftBound,右边界rightBound

注意表达含义:

  1. Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
  2. res.add(new int[]{leftBound, rightBound});这句表述,以leftBoundrightBound为值,构建了一个int[],并将int[]存入ArrayList<int[]>
  3. res.toArray(new int[res.size()][]);List的toArray()方法_list.toarray-CSDN博客
class Solution {
    public int[][] merge(int[][] intervals) {
        // 将数组Intervals按照左边界排序,调用compare方法
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));

        ArrayList<int[]> res = new ArrayList<>();
		
        int leftBound = intervals[0][0];
        int rightBound = intervals[0][1];

        for(int i=1; i<intervals.length; i++) {
            if(intervals[i][0] > rightBound) {
                // 边界不重叠,将结果存入res中,并且同时更新左右边界
                res.add(new int[]{leftBound, rightBound});
                leftBound = intervals[i][0];
                rightBound = intervals[i][1];
            } else {
                // 边界重叠,更新右边界,大中取大
                rightBound = Math.max(rightBound, intervals[i][1]);
            }
        }

        // 上述循环最后一次更新右边界,结果未写入res中,将此次结果插入
        res.add(new int[]{leftBound, rightBound});
        
        return res.toArray(new int[res.size()][]);
    }
}

189. 轮转数组

方法一:模拟

  1. 向后移动k位,可利用取余操作(i+k)%len,计算更新后的元素位置

  2. 数组复制相关知识:深入解析Java中的数组复制:System.arraycopy、Arrays.copyOf和Arrays.copyOfRange - 知乎 (zhihu.com)

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        // 复制数组int[] nums,到int[] temp
        int[] temp = Arrays.copyOf(nums, len);
        int count = 0;

        for(int i=0; i<len; i++) {
            // 使用取余运算,判断nums中的值
            nums[(i+k) % len] = temp[i];
        }

    }
}

方法二:反转数组

将数组进行三次反转即可,例如:nums = [1,2,3,4,5,6,7], k=3

  1. 第一次反转,从0到nums.length-1:nums = [7,6,5,4,3,2,1]
  2. 第二次反转,从0到k-1:nums = [5,6,7,4,3,2,1]
  3. 第三次反转,从k到nums.length:nums = [5,6,7,1,2,3,4]
class Solution {
    public void rotate(int[] nums, int k) {
        // 注意此处应该取余,处理nums=[1,2], k=3的情况
        k %= nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);
    }

    private void reverse(int[] nums, int left, int right) {
        while(left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

方法三:环状替代

【待补充】

238. 除自身以外数组的乘积

方法一:前缀积 + 后缀积

为了避免重复计算,可将nums[i]的前缀积和后缀积均计算出来,则数组中除nums[i]的乘积则为前缀积 * 后缀积;计算时应注意边界条件

初始化:前缀积leftMul[0] = 1,从左向右计算;后缀积rightMul[nums.length - 1] = 1从右向左计算

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int[] leftMul = new int[nums.length];
        int[] rightMul = new int[nums.length];

        leftMul[0] = 1;
        rightMul[nums.length - 1] = 1;

        // 计算时,最后一个元素不用计算,假如取到最后一个元素,其乘积不用计算自己
        for(int i=0; i<nums.length-1; i++) {
            leftMul[i+1] = leftMul[i] * nums[i];
            // System.out.print(leftMul[i] + ",");
        }

        for(int i=nums.length-1; i>0; i--) {
            rightMul[i-1] = rightMul[i] * nums[i];
            // System.out.print(rightMul[i-1] + ",");
        }

        for(int i=0; i<nums.length; i++) {
            res[i] = leftMul[i] * rightMul[i];
        }

        return res;
    }
}

方法二:优化

上述实现方法中,leftMulrightMul中的值仅在计算res[]时使用一次,并未重复使用,因此可以直接将计算结果写入res数组中,利用变量R记录后缀积,将空间复杂度从O(n)降为O(1)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];

        res[0] = 1;

        // 先计算前缀乘积
        for(int i=0; i<nums.length-1; i++) {
            res[i+1] = res[i] * nums[i];
            // System.out.print(res[i+1] + ",");
        }

        // 再乘以后缀乘积
        int R = 1;
        for(int i=nums.length-1; i>=0; i--) {
            res[i] = res[i] * R;
            // 更新后缀乘积
            R *= nums[i];
            // System.out.print(res[i-1] + ",");
        }

        return res;
    }
}

41. 缺失的第一个正数

方法一:HashSet

先将正数放入HashSet中,之后枚举正整数,判断其是否在HashSet中

时间复杂度为O(n),符合要求;空间复杂度为O(1),不符合要求

class Solution {
    public int firstMissingPositive(int[] nums) {
        int res = -1;
        HashSet<Integer> set = new HashSet<>();

        // 将nums中符合要求的数放入hashSet中
        for(int i=0; i<nums.length; i++) {
            if(nums[i] > 0) {
                set.add(nums[i]);
            }
        }
		
        // 从1开始遍历,判断哪个i不在hashSet中
        for(int i=1; i<Integer.MAX_VALUE; i++) {
            if(!set.contains(i)) {
                res = i;
                break;
            }
        }

        return res;

    }
}

方法二:置换

class Solution {
    public int firstMissingPositive(int[] nums) {
        int res = -1;

        // 从i开始遍历,一次操作后,nums[i]中元素置换完成
        for(int i=0; i<nums.length; i++) {
            // 只有当元素的值位于[0, nums.length]时才开始交换
            // 并且当交换的值恰好在当前位置时则不进行交换
            while(nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1] != nums[i]) {
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp; 
            }
        }

        for(int i=0; i<nums.length; i++) {
            if(nums[i] != i+1) {
                return i+1;
            }
        }

        return nums.length+1;

    }
}

方法三:哈希表

  1. 将数组中的非正数修改为N+1
  2. 将小于等于N的元素值修改为负数
  3. 遍历数组,确定第一个正数的位置

image-20240827153233205

标签:nums,int,res,sum,length,Hot100,数组,Leetcode
From: https://www.cnblogs.com/syr463/p/18383637

相关文章

  • 135. 分发糖果(leetcode)
    https://leetcode.cn/problems/candy/description/贪心,策略是确定一侧的正确性,再确定另一侧的正确性,最后综合作为正确答案,其中先确定一侧的正确性是局部最优,确定两侧的正确性的局部最优,且找不到反例就可以推出全局最优答案classSolution{publicintcandy(int[]ra......
  • 数组学习
    1.概念数组是相同类型数据的有序集合每一个数据都称为数组元素2.数组的使用1.声明一个数组:可以在类型后加[](首选)或者在名称后加[](为了方便c和c++语言而设计)2.创建一个数组,并设置内存3.给数组赋值总览3.使用数组长度来计算数组总和如果想计算数组里的数的总和,可......
  • 合并两个排序的数组
     输入:nums1=[1,2,3,0,0,0],m=3nums2=[2,5,6],n=3输出:[1,2,2,3,5,6] publicvoidmergeArray(int[]nums1,intm,int[]nums2,intn){inti=m-1;intj=n-1;intindex=m+n-1;while(index>=0){......
  • GET传递数组参数
    前端通过HTTPGET请求向后端传递List类型参数。方法一、直接以数组形式传递id=[2,4,6]后端:以数组类型接收,再转换为List类型。//请求URLhttp://127.0.0.1:8080/getTeachers?name=王五,刘麻子//后台接口代码@RestController@RequestMapping("/")publicclassSpringM......
  • 【C#】数组转置
    【需求】现有一个需求,3行4列的从左到右从上到下的数组,转成4行3列,如图所示: 【实现方法】通过C#编码实现,两种方法:第一种方法:publicdouble[]transpose(double[]src,intw,inth){double[]dst=null;if(src==null||src.Length!=w*h||w==0......
  • 程序员必备的的5个刷题网站。大厂面试稳了 力扣 https://leetcode.cn
    程序员必备的的5个刷题网站。大厂面试稳了力扣https://leetcode.cn1、leetcode力扣。网址:https://leetcode.cnLeetCode是一个定位为求职的刷题网站,其中又以算法题为主。很多大厂在面试的时候,都会考算法。有空就刷一刷这里面的算法题,你的算法水平肯定会有大幅的提升,不管是求职,......
  • 探索C语言中数组作为函数参数的奥秘
    在C语言的世界里,数组是一种基础且强大的数据结构,它允许我们存储相同类型的数据集合。然而,在处理函数和数组的关系时,尤其是在数组作为函数参数传递时,初学者往往会感到困惑。今天,我们就来深入探讨这一话题,通过具体的代码示例来揭开其神秘面纱。数组作为函数参数的两种形式在C语......
  • LeetCode 算法:爬楼梯 c++
    原题链接......
  • 搜索二维矩阵 II(LeetCode)
    题目编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。解题"""时间复杂度为O(m+n),其中m是矩阵的行数,n是矩阵的列数。"""defsearchMatrix(matrix,t......
  • 每日一题:Leetcode-47 全排列
    力扣题目解题思路java代码力扣题目:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。示例1:输入:nums=[1,1,2]输出:[[1,1,2],[1,2,1],[2,1,1]]示例2:输入:nums=[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]解......