数组系列——数组的遍历

2023-12-25 16:24:28

895.最大连续的1.

给定一个二进制数组，计算其中最大连续 1 的个数。

示例：

输入：[1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.找到第一个1的位置 a [ i ]

2. a [ i ] 是否== a [ i+1 ] （等于的话返回 count，不等于的话开始找第二个1的位置，同时返回max。）

3.重复第二步

4.如果第二个max比第一个大，那么就返回新的max

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0; int count = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1) count++;
            else{
                if(count>max)max=count;
                count = 0;
            }
        }
        if(count>max)max=count;
        return max;
    }
}

关于代码优化：else这里是nums [ i ] == 0 的情况，这样就会导致一种情况，也就是如果最后一个元素是1的话，那就不会返回一个新的max值。所以才需要在for循环之外加一个if判断语句。

优化的话，在参考leetcode评论的基础上，可以把else去掉，这样就可以一并去掉for循环之外的判断语句。

时间复杂度是O(n),空间复杂度是O(1)

通过leetcode评论的研究，我发现还有利用双指针写的方法

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        if(nums.length == 0) return 0;
        int fast = 0,slow = 0;
        int num = 0;
        while(fast < nums.length){
            if(nums[fast]==0) {
                num = (fast - slow) > num ? fast - slow : num ;
                slow = fast + 1;
                fast++;
            }else{
                fast++;
            }
        }
        num = (fast - slow) > num ? fast - slow : num ;
        return num;
    }
}

这里把方法写在这里，也值得看一看。这个思路在写题目的一瞬间，脑子里也想到了，就是找数组中0的位置，然后用0的位置减去前一个0的位置，进行比较。

495.提莫攻击

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个非递减的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的总秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。
示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/teemo-attacking
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

返回中毒的总秒数

1.设两个变量时间总数和每轮要加的数量

2.对数组timeSeries进行一次for循环遍历

3.如果两个元素值的差比duration大，就返回duration作为加的数量

4.如果元素值的差比duration小，就返回元素差作为加的数量

5.最后return的值需要加上一个duration（因为最后一个元素的情况没有考虑进去）

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int timeSum = 0;
        int timeAdd = duration;
        for(int a=0;a<timeSeries.length-1;a++){
           if(timeSeries[a]+duration>timeSeries[a+1]) {
                timeAdd=timeSeries[a+1]-timeSeries[a]; 
                timeSum=timeSum+timeAdd;
                }
           else {timeAdd=duration;timeSum=timeSum+timeAdd;
            }
        }
        return timeSum+duration;
    }
}

leetcode的方法1

每次比较元素差与duration的大小，小的返回为加的值。（极其巧妙）

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 1) {
            return duration;
        }
        int ans = 0;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            ans += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        }
        return ans + duration;
    }
}

leetcode的方法2

先假设中毒时间拉满，然后减去重复的时间即可。

  public int findPoisonedDuration(int[] timeSeries, int duration) {
        int res = timeSeries.length * duration;
        for(int i = 1; i < timeSeries.length; i++){
            if(timeSeries[i] - timeSeries[i-1] < duration){
                res -=  duration - timeSeries[i] + timeSeries[i-1];
            }
        }
        return res;
    }

414.

给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。
示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/third-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.首先将数组进行排序，从小到大进行排序（这里理想状态下应该是从大到小）

2.for循环对数组进行遍历

3.比较nums[ i ]与num[ i-1 ]的大小

4.当相等的情况达到两次后，返回num[ i-1 ]

class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
             for(int i =nums.length-1,j =1;i>0;i--){
                 if(nums[i]!=nums[i-1]){
                     j++;
                     if(j==3) return nums[i-1];
            }
        }
        return nums[nums.length-1];
    }
    }

628.

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6
示例 2：

输入：nums = [1,2,3,4]
输出：24
示例 3：

输入：nums = [-1,-2,-3]
输出：-6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.先将数组进行排序，因为要找出三个数的最大乘积

2.如果数组排序后最大的那个数小于等于0，那么最大值就等于最后三个数相乘

3.如果数组排序后最大的那个数大于0，有以下两种情况：

（1）最大值=最后一个数乘以两个最小的负数

（2）最大值=最后三个数（皆为正数）相乘

4.完成算法

class Solution {
    public int maximumProduct(int[] nums) {
        int length = nums.length-1;
         Arrays.sort(nums);
         if(nums[length]>0)
         { 
             int max =nums[length]*nums[length-1]*nums[length-2];
            int min =nums[0]*nums[1]*nums[length];
        return Math.max(max,min);
         }
        else{
            return nums[length]*nums[length-1]*nums[length-2];
        }
        
    }
}

进行优化：

可以去掉if else这个情况判断，因为无论怎么比较，其实就是两种情况1---最后两个负数乘以最大的那个数 2---最大的三个数相乘

直接进行数学方法判断

class Solution {
    public int maximumProduct(int[] nums) {
        int length = nums.length-1;
         Arrays.sort(nums);
             int max =nums[length]*nums[length-1]*nums[length-2];
            int min =nums[0]*nums[1]*nums[length];
        return Math.max(max,min);
        
    }
}

时间复杂度O(nlogn) ，空间复杂度O(logn)

leetcode评论中看到的方法：一次遍历

class Solution {
    public int maximumProduct(int[] nums) {
        // 最小的和第二小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 最大的、第二大的和第三大的
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

        for (int x : nums) {
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } 
            else if (x < min2) {
                min2 = x;
            }
            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }

        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}

需要知道的新知识：if……else if ，每一个else都应有对应的if相配对，一个 if……else if为一个组合。

if (x < min1) {
min2 = min1;
min1 = x;
}
else if (x < min2) {
min2 = x;
}

这一段的意思是：如果 x<min1不成立，就执行else if（），如果成立就不执行。

其等于以下的代码

  if(x<min2){

                if(x<min1){

                    min2 = min1;

                    min1 = x;

                }

                else min2 = x;

            }

其实是一个if else if的组合，第二个if组合也是如此。

此为重写后的等价代码

class Solution {
        public int maximumProduct(int[] nums) {
            // 最小的和第二小的
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            // 最大的、第二大的和第三大的
            int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

            for (int x : nums) {
                if (x < min2) {
                    if (x < min1) {
                        min2 = min1;
                        min1 = x;
                    } else min2 = x;
                }

                if (x > max3) {
                    if (x > max2) {
                        if (x > max1) {
                            max3 = max2;
                            max2 = max1;
                            max1 = x;
                        } else {
                            max3 = max2;
                            max2 = x;
                        }
                    } else max3 = x;
                }

            }

            return Math.max(min1 * min2 * max1, max1 * max2 * max3);
        }
    }

至此，做完了刷题系列的第一个系列数组——数组的遍历

对应的leetcode题目是485、495、414、628

码农公寓

895.最大连续的1.

495.提莫攻击

相关文章