Home Tags Posts tagged with "Leetcode"

Leetcode

数组的遍历 485、495、414、628
统计数组中的元素 645、697、448、442、41、274
数组的改变、移动 453、665、283

485:

难度简单131收藏分享切换为英文接收动态反馈给定一个二进制数组, 计算其中最大连续1的个数。

示例 1:

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

class Solution {
  public int findMaxConsecutiveOnes(int[] nums) {
      int maxC=0;
      int C=0;
      for(int i=0;i<nums.length;i++){
          if(nums[i]==1){
              C++;//记录个数;
          }
          else{
              maxC=Math.max(maxC,C);//取到大数;
              C=0;//遇到0则清零;
          }
      }
      return  Math.max(maxC,C);//最后的连续1未在比较;
  }
}
495:

难度中等114收藏分享切换为英文接收动态反馈在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。现在,给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间,你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。

示例1:
输入: [1,4], 2
输出: 4
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
第 4 秒初,提莫再次攻击艾希,使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。
示例2:
输入: [1,2], 2
输出: 3
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
但是第 2 秒初,提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加,提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
所以最终输出 3 。
提示:
你可以假定时间序列数组的总长度不超过 10000。
你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数,并且不超过 10,000,000。
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        //前元素起始+中毒时长<=后元素,则时长为duration*元素个数;
        //前元素起始+中毒时长>后元素,则时长为<=的个数*duration+大于的时长;
        int i=0,end=0,add=duration;
        if(timeSeries.length==0){
            return 0;
        }
        if(timeSeries.length==1){
            return duration;
        }
        for(i=1;i<timeSeries.length;i++){
            end=timeSeries[i-1]+duration;
            if(end<=timeSeries[i]){
                add+=duration;
            }
            else{
                add+=(timeSeries[i]+duration-end);
            }
        }
        return add;
    }
}
414:

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

示例 1:
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意,要求返回第三大的数,是指第三大且唯一出现的数。
存在两个值为2的数,它们都排第二。
class Solution {
    private long MIN = Long.MIN_VALUE;    // MIN代表没有在值
    public int thirdMax(int[] nums) {
 if (nums == null || nums.length == 0) throw new RuntimeException(“nums is null or length of 0”);//特殊判断;
int n=nums.length;
int one =nums[0];
long two=MIN;
long three=MIN;
for(int i=1;i<n;i++){
      int now=nums[i];
      if(now==one||now==two||now==three)continue;
      if(now>one){
             three=two;
             two=one;
            one=now;
      }
     if(now>two){
            three=two;
            two=now;
     }
     if(now>threee){
            three=now;
     }
}
if(three==MIN)return one//不存在三个不相同的数;
return (int )three;
}
}
628:

难度简单181收藏分享切换为英文接收动态反馈给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。

示例 1:
输入: [1,2,3]
输出: 6
示例 2:
输入: [1,2,3,4]
输出: 24
注意:
给定的整型数组长度范围是[3,104],数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
//排序;
public class Solution {
    public int maximumProduct(int[] nums) {
         Array.sort(nums);
         return    (nums[0]*nums[1]*nums[length-1],nums[length-3]*nums[length-2]*nums[length-3]);//要么是最小的负数*第二小的负数*最大的正数,要么是最大的正数*第二大的正数*第三大的正数;
}
}

645:

错误的集合难度简单127收藏分享切换为英文接收动态反馈集合 S 包含从1到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个元素复制了成了集合里面的另外一个元素的值,导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。
 给定的数组是无序的。
//哈希表;
class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] counter = new int[nums.length+1];
        for (int i: nums) {
            counter[i]++;
        }
        int[] result = new int[2];
        for (int i = 1; i<counter.length; i++) {
            if (counter[i] == 0) {
                result[1] = i;
            } else if (counter[i] == 2) {
                result[0] = i;
            }
        }
        return result;
    }
}
//排序;
public class Solution {
    public int[] findErrorNums(int[] nums) {
        Arrays.sort(nums);
        int dup = -1, missing = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i – 1])
                dup = nums[i];
            else if (nums[i] > nums[i – 1] + 1)
                missing = nums[i – 1] + 1;
        }
        return new int[] {dup, nums[nums.length – 1] != nums.length ? nums.length : missing};
    }
}
//位运算;
697:

数组的度难度简单175收藏分享切换为英文接收动态反馈给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。

示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2,因为元素1和2的出现频数最大,均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2,所以返回2.
示例 2:
输入: [1,2,2,3,1,4,2]
输出: 6
注意:
nums.length 在1到50,000区间范围内。
nums[i] 是一个在0到49,999范围内的整数。
//哈希表的思想,边遍历边记录,次数=度数的可能不止一个,应当注意选取其中最小的
int findShortestSubArray(int* nums, int numsSize){
    int mark[50000]={0},start[50000]={0},end[500000]={0};
    int i;
    int count=0,min;
    for(i=0;i<numsSize;i++)
    {
        mark[nums[i]]++;//记录度
        if(mark[nums[i]]>count)
        count=mark[nums[i]];//记下最大的度
        if(mark[nums[i]]==1)//第一次出现,需要设置起点
        {
            start[nums[i]]=i;
            end[nums[i]]=i;
        }
        else if(mark[nums[i]]>1)//非第一次出现
        end[nums[i]]=i;
    }
    min=50000;//寻找最大
    for(i=0;i<50000;i++)
    {
        if(mark[i]==count)//判断符合要求的
            if(end[i]-start[i]<min)
                min=end[i]-start[i];
    }
        min++;
    return min;
}
448.

找到所有数组中消失的数字难度简单479收藏分享切换为英文接收动态反馈给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
//标记出现了的元素,与未出现的分开,并且利用下标从0到n-1,而值为1到n此条件;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for(int i=0;i<nums.length;i++){
            int newIndex = Math.abs(nums[i]) – 1;
            if(nums[newIndex]>0)
            nums[newIndex]*=-1;//将值-1作为对应的下标;
        }
        List<Integer> result = new LinkedList<Integer>();
        // Iterate over the numbers from 1 to N and add all those
        // that have positive magnitude in the array
        for (int i = 1; i <= nums.length; i++) {  
            if (nums[i – 1] > 0) {
                result.add(i);
            }
        }
        return result;
    }

}

442:

数组中重复的数据难度中等286收藏分享切换为英文接收动态反馈给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
//使用额外空间则哈希表,不允许的话则使用下标条件;
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0)
                res.add(Math.abs(index+1));
            nums[index] = -nums[index];
        }
        return res;
    }
}
41. 缺失的第一个正数难度困难820收藏分享切换为英文接收动态反馈给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
//不允许使用额外空间,并且时间复杂度要控制在O(n),只能使用下标这个条件,以及元素自我标记;
/*class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num – 1] = -Math.abs(nums[num – 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}*/
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && 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 < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}