第一题：485. 最大连续1的个数
给定一个二进制数组， 计算其中最大连续1的个数。
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
注意：
输入的数组只包含 0 和1。 输入数组的长度是正整数，且不超过 10,000。
思路：
正确的思路： 先遍历这个目标数组，然后设置count变量去记录连续1出现的次数 然后巧妙的使用maxCount来接纳count和maxCount中的最大值，因为出现一次0之后，就需要将count重新置为0，不知道下次连续1的次数，所以用maxCount来记录，这个地方很巧妙！ 结尾的时候，需要再次取下最大值，不然只输入一个1的情况不满足。
我的错误思路： 整体思路是正确的，但是我没想到引入另外一个变量去记录最大值，所以我一直在找连续和连续被打断，这个count怎么办，我总想着这个i存在一个关系关联，把问题想复杂了。
代码：
public int findMaxConsecutiveOnes(int[] nums) {
int count = 0;
int maxCount = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
count ++;
}else {
maxCount = Math.max(count,maxCount);
count = 0;
}
}
return maxCount;
}第二题：495. 提莫攻击
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
示例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。
思路：
正确的思路：
说实话，这个题目为中等难度，实属不应该（小声bb哈）
首先不要被示例误导，这个数组的长度不止两个哦，是一个未知长度的数组呢！
然后我们就化繁为简，就从两个看起，很容易看出，这个第一次攻击和第二次攻击之间的时差，与伤害持续时间是存在一个关系的：
1)相邻两个攻击时间点 A[i] 和 A[i + 1] 以及中毒持续时间 t
2)如果 A[i + 1]-A[i] >= t ，那么在第 i + 1 次攻击时，第 i 次攻击造成的中毒的持续时间已经结束，即第i次的持续时间为 t；(那我们总时间就可以用第一次持续时间加上这次的时间：t + duration)
3)如果 A[i + 1]-A[i] < t，那么在第 i + 1 次攻击时，第 i 次攻击的中毒仍然在持续，由于中毒状态不可叠加，因此第 i 次持续时间为 A[i + 1] - A[i]。(那我们总时间就是A[i + 1] - A[i] +duration)
注意：这个代码实现过程中有一个循环的问题需要控制;
一般来说，我们遍历都是 for (int i = 0; i < nums.length; i++) {}
但是我们在这里有一个操作 timeSeries[i+1] - timeSeries[i];所以就会数组越界，所以就改为for (int i = 0; i < nums.length-1; ++i) {} 我的错误思路： 整体思路是正确的，分析也分析对了，就以为和示例一样，只存在两个攻击时间点，这是第一个问题 要先判断好是不是中毒还在持续，然后前一次的时间不用管，就是持续时间duration，我们只要找出后面一次的中毒时间，当中毒已经失效了，那就还会中毒一个周期duration，那如果还在生效，那就要少算一段时间，那就是A[i + 1] - A[i]。
代码：
public int findPoisonedDuration(int[] timeSeries, int duration) {
int n = timeSeries.length;
if (n == 0) {
return 0;
}
int total = 0;
int sub = 0;
for (int i = 0; i < n-1; ++i) {
sub = timeSeries[i+1] - timeSeries[i];
if(sub >= duration){
total += duration;
}else {
total += sub;
}
}
return total + duration;
}第三题：414. 第三大的数
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1: 输入: [3, 2, 1] 输出: 1 解释: 第三大的数是 1.
示例 2: 输入: [1, 2] 输出: 2 解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3: 输入: [2, 2, 3, 1] 输出: 1 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。
思路：
正确的思路1： ·找出第三大的数，那我们就设置三个变量分别去保存，然后循环比较就能得出三个值，最后输出（想不通的话，你就尝试着想找出最大值怎么找，其实是一样的） ·本体的亮点在于，通过案例中有一组是：[1,2,-2147483648]，所以我们就只能用Long类型，一定要这个敏感性的嗅觉 ·关于数组只有最大值和第二大值，总结经验就可以最后使用三目运算符来输出即可。
方法一：
public int thirdMax(int[] nums) {
long first = Long.MIN_VALUE;
long second = Long.MIN_VALUE;
long third = Long.MIN_VALUE;
for(int num : nums){
if(num >first){
third = second;
second = first;
first = num;
}else if (num > second && num <first){
third = second;
second = num;
}else if(num >third && num <second){
third = num;
}
}
return (int) (third == Long.MIN_VALUE?first:third);
}正确的思路2： 使用java特有的集合：treeSet，我们需要记住两个特点：自动排序和唯一不重复 ·维护一个只有3个元素的TreeSet，如果大于三个元素就就把Set中的最小最小值remove掉。 ·最后如果Set中元素小于3就返回Set最大值，否则返回最小值。
方法二：
public int thirdMax3(int[] nums) {
TreeSet<Integer> set = new TreeSet<>();
for(Integer num : nums){
set.add(num);
if(set.size() > 3){
set.remove(set.first());
}
}
return set.size() >3 ?set.last():set.first();
}我的错误思路： ·做题想得出方法，但是实现起来或多或少都会存在缺陷或者问题 ·我是想循环一次找出最大的，再循环一次找出第二大的，再循环一次找出第三大的，这样时间复杂度也是O(n) ·但最终发现，我还要保存最大值和第二大值得下标，保证下次不去找这个值了，想的很细，也想的很复杂，发现自己每次都往复杂的方向搞，搞的自己都写不出了，难受~
第四题：628. 三个数的最大乘积
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1: 输入: [1,2,3] 输出: 6
示例 2: 输入: [1,2,3,4] 输出: 24
注意:
给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
思路：
正确的思路1： ·将数组进行升序排序 ·如果数组中所有的元素都是非负数，那么答案即为最后三个元素的乘积 ·如果数组中出现了负数，那么我们还需要考虑乘积中包含负数的情况，显然选择最小的两个负数和最大的一个正数是最优的，即为前两个元素与最后一个元素的乘积。 ·两个结果中的较大值就是答案。
方法一：
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
return Math.max(nums[0]*nums[1]*nums[nums.length-1],nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3]);
}正确的思路2： 求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。 具体比较就是类似于上面那题，不断的比较就好了
方法二：
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;
// min1 min2 max1 max2 max3
for (int n: nums) {
if (n <= min1) {
min2 = min1;
min1 = n;
} else if (n <= min2) { // n lies between min1 and min2
min2 = n;
}
if (n >= max1) { // n is greater than max1, max2 and max3
max3 = max2;
max2 = max1;
max1 = n;
} else if (n >= max2) { // n lies betweeen max1 and max2
max3 = max2;
max2 = n;
} else if (n >= max3) { // n lies betwen max2 and max3
max3 = n;
}
}
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
京公网安备 11010502036488号