狂暴复习之路20160610 Array I

因为马上要去面试了，虽然说LeetCodeOJ上面已经刷了200道算法题，但是我打算再复习一遍，从今天开始。

1. Array

283

Move Zeroes

public void moveZeroes(int[] nums) {
    int nonZeroIndex = 0;
    int zeroIndex = 0;
    int len = nums.length;

    while(nonZeroIndex < len)
    {
        if(nums[nonZeroIndex] == 0)
        {
            nonZeroIndex++;
            continue;
        }

        if(nonZeroIndex != zeroIndex)
        {
            nums[zeroIndex] = nums[nonZeroIndex];
            nums[nonZeroIndex] = 0;
        }
        zeroIndex++;
        nonZeroIndex++;
    }
}

不断地找出非0 与为0的点 交换他们的值

238
Product of Array Except Self

从前向后一遍乘法 再从后向前一遍乘法

public int[] productExceptSelf(int[] nums) {
    int[] result = new int[nums.length];
    result[0] = 1;
    for (int i = 1; i <nums.length ; i++) {
        result[i] = result[i-1] * nums[i-1];
    }
    int temp = 1;
    for (int i = nums.length-1; i >=0 ; i--) {
        result[i] *= temp;
        temp *= nums[i];
    }
    return result;
}


121
Best Time to Buy and Sell Stock





public int maxProfit(int[] prices) {
    int profit = 0;
    int min = Integer.MAX_VALUE;
    for(int i=0; i<prices.length; i++){
        profit = Math.max(profit, prices[i]-min);
        min = Math.min(min, prices[i]);
    }
    return profit;
}
动态规划，每次加入一个数字，计算加入这个数字之后对结果的影响


122
Best Time to Buy and Sell Stock II



public int maxProfit(int[] prices) {
    int result = 0;
    int benefit = 0;
    for (int i = 1; i <prices.length ; i++) {
        benefit = prices[i] - prices[i-1];
        if (benefit>0)
            result += benefit;
    }
    return result;
}
因为买卖是时间线性的，直接贪心，大于0就算利润。



169
Majority Element


public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}
排序，返回中位数。



217
Contains Duplicate

public boolean containsDuplicate(int[] nums) {
    if (nums==null|| nums.length==0)
        return false;
    HashSet hs = new HashSet();
    for (int num: nums)
        if (hs.add(num)==false)
            return true;
    return false;
}

挨个扔HashSet里面，如果添加失败，返回true，如全部添加成功返回false。

268
Missing Number

public int missingNumber(int[] nums) {
    int len = nums.length;
    int sum = (len*(len+1))/2;
    for(int i = 0 ; i < len; i++){
        sum -= nums[i];
    }
    return sum;
}
因为所有的数字都是连续且独一无二的，算一下他们的和，从头到尾挨个减一遍，剩下的值，就是缺省值。



287
Find the Duplicate Number


public int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;
    do    {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);
    int find = 0;
    while (find!=slow)
    {
        slow = nums[slow];
        find = nums[find];
    }
    return find;
}
迪杰斯特拉算法找环路


35
Search Insert Position


public int searchInsert(int[] nums, int target) {
    if (nums==null||nums.length==0)
        return 0;
    int len = nums.length;
    int left = 0;
    int right = len-1;

    while (left <= right)
    {
        if (target < nums[left])
            return left;
        if (target > nums[right])
            return (right+1);
        int mid = (left + right)>>1;
        if (target < nums[mid])
            right = mid-1;
        else if (target > nums[mid])
            left = mid+1;
        else            return mid;
    }
    return 0;
}
二分查找，使用右移代替除2.


53
Maximum Subarray



public int maxSubArray(int[] nums) {
    int max = nums[0];
    int[] sum = new int[nums.length];
    sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++)
    {
        sum[i] = Math.max(nums[i], sum[i - 1] + nums[i]);
        max = Math.max(max, sum[i]);
    }

    return max;
}
动态规划，最优子结构result = max（nums[i],sum[i-1]+nums[i]）