Find All Duplicates in an Array(442)
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
思路：
on的时间复杂度，肯定是一个遍历。主要难点是不使用额外的存储空间。想办法标记已经访问过的元素。
遇到这种情况，可以通过下表标记，因为数组中的元素师1-n的。 当找到一个i，把位置i-1标记为负的。表明i被访问过一次。每次判断该元素是不是负的，负的说明下表代表的（数字+1）被访问过。
// when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 is already negative, i is the number that occurs twice.
public 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(index+1);
}else{
nums[index]=-nums[index];
}
}
return res;
}
}
Find All Numbers Disappeared in an Array(448)
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
Subscribe to see which companies asked this question.
思路：
套路同442.
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res=new ArrayList<>();
for(int i=0;i<nums.length;i++){
int index=Math.abs(nums[i])-1;
nums[index]=-Math.abs(nums[index]);
}
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
res.add(i+1);
}
}
return res;
}
}
Max Consecutive Ones(485)
Given a binary array, find the maximum number of consecutive 1s in this array.
Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.
Note:
- The input array will only contain
0and1. - The length of input array is a positive integer and will not exceed 10,000
Subscribe to see which companies asked this question.
思路：
先读懂题意，求连续1最大的个数。采用一个for循环，每次记录连续1的个数，遇到0重置。ps；最后返回的时候先比较一次max和count。为了防止出现【1】这种情况。max没有置为count。
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int count=0;
int max=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
max=max>count?max:count;
count=0;
}else{
count++;
}
}
max=max>count?max:count;
return max;
}
}
Teemo Attacking(495)
In LLP world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo's attacking ascending time series towards Ashe and the poisoning time duration per Teemo's attacking, you need to output the total time that Ashe is in poisoned condition.
You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.
Example 1:
Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately.
This poisoned status will last 2 seconds until the end of time point 2.
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds.
So you finally need to output 4.
Example 2:
Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned.
This poisoned status will last 2 seconds until the end of time point 2.
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status.
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3.
So you finally need to output 3.
Note:
- You may assume the length of given time series array won't exceed 10000.
- You may assume the numbers in the Teemo's attacking time series and his poisoning time duration per attacking are non-negative integers, which won't exceed 10,000,000.
Subscribe to see which companies asked this question.
思路：
考虑每一次攻击都会增加固定的时常。总共n次，就是n*duration。 现在需要考虑的是重复时常的部分。如果每两次攻击之间的时间大于duration，那么没有重复。如果每两次攻击之间时间小于前一次时间加上duration，那么需要减去该值。
public class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int i=0;
int d=0;
int count=0;
while(i<timeSeries.length-1){
d=timeSeries[i]+duration-timeSeries[i+1];
if(d<=0){
count+=0;
}else{
count-=d;
}
i++;
}
count+=duration*timeSeries.length;
return count;
}
}
