每周一练数组_数组的遍历

1. 最大连续1的个数

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

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

胡乱分析（假装有表情包

指针从左往右遍历，计算连续1的长度，存放最大的长度。

代码

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int temp=0,count=0;//temp记录当前连续1的个数，count记录当前最大连续1的个数

        for (int i=0;i<nums.length;i++){//指针右移
            if(nums[i]==1){
                temp++;//遇1累加1
            }else{
                if(count<temp){
                    count=temp;//记录目前最大连续1的个数
                }
                temp=0;//遇0倒置为0
            }
        }
        return (count>temp)? count:temp;
    }
}

2.提莫攻击

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。

胡乱分析

这道题我当初也想了好久(老年人太惨了），然后去看了官方解答。
就是中毒时间会被下次攻击刷新，因此以每次攻击之前算中毒时间为多少就可以了。一步步算脚踏实地很简单。

代码

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

3.第三大的数

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

胡乱分析

要求O(n)只能进行一次遍历。我这时候只考虑时间，那么可以存储三个变量a、b、c。遍历数组，然后将数据存放在变量中。

代码

 public int thirdMax(int[] nums) {
        //测试用例用了最小的数
        int first=Integer.MIN_VALUE;
        int second=Integer.MIN_VALUE;
        int thrid=Integer.MIN_VALUE;

        int flag=0;//flag是为了判断是否存在第三个数
        for(int i=0;i<nums.length;i++){
            if(nums[i]>first){
                thrid=second;
                second=first;
                flag++;
                first=nums[i];
            }else if(nums[i]>second){
                if(nums[i]==first){
                    continue;
                }
                thrid=second;
                second=nums[i];
                flag++;
            }else if(nums[i]>thrid){
                if(nums[i]==second)
                    continue;
                thrid=nums[i];
                flag++;
            }else if(nums[i]==Integer.MIN_VALUE){
                flag++;
            }
        }

        if(flag<3||first==second||second==thrid){
            return first;
        }
        
        return thrid;
    }

4.三个数的最大乘积

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

胡乱分析

3个数的组成是，最大数+{第二大数、第三大数|最小数、第二小数}。所以在有序数组中位置是确定的，让程序自己判断哪个大就返回吧。

代码

public int maximumProduct(int[] nums) {
        Arrays.sort(nums);//排序
        return nums[nums.length-1]*Math.max(nums[nums.length-2]*nums[nums.length-3],
            nums[0]*nums[1]);
 }

以上题目来源：leet-code

最后编辑于：2020.08.08 16:38:21