数组简单题| 盛最多水的容器、买卖股票的最佳时机、只出现一次的数字、多数元素、移动零、找到所有数组中消失的数字

数组简单题| 盛最多水的容器、买卖股票的最佳时机、只出现一次的数字、多数元素、移动零、找到所有数组中消失的数字

11 盛最多水的容器

public class $11 {
    public int maxArea(int[] height) {
        int len = height.length;
        int ans = 0;
        int l = 0;
        int r = len-1;

        while (l < r) {
            int min = Math.min(height[l], height[r]);
            int area = min * (r-l);
            //更新area
            ans = Math.max(ans, area);

            //移动数字较小的指针，认为该指针不能作为容器的边界了
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

121 买卖股票的最佳时机

/**
 * 买卖股票的最佳时机
 * 法一：双重遍历，超出时间限制
 * 法二：遍历数组，
 * 当price[i]<minPrice，更新minPrice
 * 当price[i]>minPrice+maxProfit，更新maxProfit
 */
public class $121 {
    //法二：
    public int maxProfit2(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        //遍历数组
        for (int i = 0; i < prices.length; i++) {
            //当price[i]<minPrice
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) { //当price[i]>minPrice+maxProfit
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
}

136 只出现一次的数字

/**

• 法一：遍历数字，并保存到map中，key对应nums[i]，value对应个数
• 法二：全部数字异或，最终结果就是只出现一次的数字
  */

import java.util.HashMap;
import java.util.Map;

/**
 * 只出现一次的数字
 * 法一：遍历数字，并保存到map中，key对应nums[i]，value对应个数
 * 法二：全部数字异或，最终结果就是只出现一次的数字
 */
public class $136 {
    //法一：map
    public static int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int x : nums) {
            int count = map.getOrDefault(x,0);
            map.put(x, count+1); //为什么count++错了
        }
        //遍历map，找到count为 1 的key
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return 0;
    }
}

import java.util.HashMap;
import java.util.Map;

/**
 * 只出现一次的数字
 * 法一：遍历数字，并保存到map中，key对应nums[i]，value对应个数
 * 法二：全部数字异或，最终结果就是只出现一次的数字
 */
public class $136 {
    //法二：异或
    public int singleNumber2(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

169 多数元素

import java.util.Arrays;

/**
 * 多数元素
 * 法一：排序后取中间元素
 * 法二：投票算法
 */
public class $169 {
    //法一：排序后，中间的元素一定是多数元素
    public int majorityElement(int[] nums) {
        //1.排序
        Arrays.sort(nums);
        //2.中间的元素
        return nums[nums.length/2];
    }
}

import java.util.Arrays;

/**
 * 多数元素
 * 法一：排序后取中间元素
 * 法二：投票算法
 */
public class $169 {
    //法二：投票算法
    public int majorityElement2(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += num == candidate ? 1 : -1;
        }
        return candidate;
    }
}

283 移动零

/**
 * 移动零
 * 法一：把非零元素移到前面，空的位置补0
 * 法二：利用快排交换思想，但注意不要改变原!0元素顺序
 */
public class $283 {
    //法一：
    public void moveZeroes(int[] nums) {
        if (nums == null) {
            return;
        }

        //把非零元素移到前面
        int j = 0;
        int i = 0;
        while (i < nums.length) {
            while (nums[i] == 0) {
                i++;
            }
            nums[j++] = nums[i++];
        }

        //把末尾元素用0填补
        for (int k = j; k < nums.length; k++) {
            nums[k] = 0;
        }
    }

    //法一改写
    public void moveZeroes4(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (int k = j; k < nums.length; k++) {
            nums[k] = 0;
        }
    }
}

/**
 * 移动零
 * 法一：把非零元素移到前面，空的位置补0
 * 法二：利用快排交换思想，但注意不要改变原!0元素顺序
 */
public class $283 {
    //法二：利用快排思想
    public void moveZeroes3(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j++;
            }
        }
    }

    //法二：错误，0移到末尾，但是改变了!0元素的顺序
    public void moveZeroes2(int[] nums) {
        int pivot = 0;
        int left = 0;
        int right = nums.length;

        while (left < right) {
            while (left < right && nums[right] == 0) {
                right--;
            }
            while (left < right && nums[left] != 0) {
                left++;
            }
            swap(nums, left, right);
        }
    }
}

448 找到所有数组中消失的数字

import java.util.ArrayList;
import java.util.List;

/**
 * 找到所有数组中消失的数字
 */

public class $448 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int len = nums.length;

        for (int num : nums) {
            int x = (num-1) % len; //找到num应该在数组的哪个位置，哪怕该数字已经修改过，也能找到同一个位置
            nums[x] += len; //修改该位置上的数字
        }

        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= len) {
                ret.add(i+1);
            }
        }
        return ret;
    }
}