0304leetcode-array

561. Array Partition I

class Solution {
    public int arrayPairSum(int[] nums) {
        int[] count = new int[20001];
        for(int i = 0; i < nums.length; i++){
            count[nums[i] + 10000]++;
        }
        
        int sum = 0;
        int odd = 0;
        for(int i = count.length - 1; i >= 0; i--){
            if(count[i] > 0){
                sum += (i - 10000) * ((count[i] + odd) / 2);
                if((count[i] + odd) % 2 == 0){
                    odd = 0;
                } else {
                    odd = 1;
                }
            }
        }
        
        return sum;
    }
}  

485. Max Consecutive Ones

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

283. Move Zeroes

public class Solution {
    public void moveZeroes(int[] nums) {
        int i=0,index=0,count=0;
        
        for(i=0;i<nums.length;i++){
            if(nums[i]==0) 
                count++;
            else{
                nums[index]=nums[i];
                index++;
            }
        }
        
        for(i=nums.length-1;i>nums.length-count-1;i--) nums[i]=0;
    }
}  

448. Find All Numbers Disappeared in an Array

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new LinkedList<>();
        
        int n = nums.length;
        boolean[] num = new boolean[n+1];
        
        for(int i=0; i<n; i++)
            num[nums[i]] = true;
        
        for(int i=1; i<n+1; i++)
            if(num[i] == false)
                list.add(i);
        
        return list;
    }
}  

169. Majority Element

class Solution {
    public int majorityElement(int[] nums) {
        int count=0, ret = 0;
        for (int num: nums) {
            if (count==0)
                ret = num;
            if (num!=ret)
                count--;
            else
                count++;
        }
        return ret;
    }
}

122. Best Time to Buy and Sell Stock II

class Solution {
    public int maxProfit(int[] prices) {
        int[] deltas = new int[prices.length];
        
        for (int i = 0; i < prices.length - 1; i++) {
            deltas[i] = prices[i+1] - prices[i];
        }
        
        int ret = 0;
        
        for (int v : deltas) {
            if (v > 0)
                ret += v;
        }
        
        return ret;
    }
}   

167. Two Sum II - Input array is sorted

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if(target < numbers[0])
            return null;
        int result[] = new int[2];
        int i = 0, j = numbers.length-1;
        while(i < j) {
            if(numbers[i]+numbers[j] < target)
                i++;
            else if(numbers[i]+numbers[j] > target)
                j--;
            else {
                result[0] = i+1;
                result[1] = j+1;
                break;
            }
        }
        return result;
    }
}  

217. Contains Duplicate

class Solution {
    public boolean containsDuplicate(int[] nums) {
        //当数组不存在，或者长度小于2时，不可能存在重复数据
        if(nums == null || nums.length <= 1 ){
            return false;
        }

        //找出数组中的最大数和最小数
        int min = nums[0];
        int max = nums[0];
        for(int i = 1, size = nums.length; i < size; i++){
            if(nums[i] < min){
                min = nums[i];
            }else if(nums[i] > max){
                max = nums[i];
            }
        }

        //若最大最小数的区间小于数组长度，必定存在重复数据
        if((max - min + 1 ) < nums.length){
            return true;
        }
        boolean[] results = new boolean[max - min + 1];
        for(int i = 0,size = nums.length; i < size; i++){
            //减去最小数，保证偏移量为整数
            int index = nums[i] - min;

            //若boolean数组该位置被置为true，表示该数已经出现过
            if(results[index]){
                return true;
            }
            //将boolean该偏移位置设置为true
            results[index] = true;
        }
        return false;
    }
}

268. Missing Number

class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for(int i = 0; i < nums.length; i++) {
            res ^= i;
            res ^= nums[i];
        }
        return res;
    }
}