@TOC

一、消失的数字

数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。在 O(n)时间内完成

1.异或运算:

 public int missingNumber(int[] nums) {
        int[] arr = new int[nums.length + 1];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum ^= i;
        }
        for (int i = 0; i < nums.length ; i++) {
            sum ^= nums[i];
        }
        return sum;
    }

2.空间换时间:

public int missingNumber1(int[] nums) {
        int[] arr = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]] = 1;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != 1) {
                return i;
            }
        }
        return -1;
    }

二、轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

这是之前写过一篇专门是旋转数组的:旋转数组三种方式
上面的思路是针对于左旋数组，对右旋数组只需要稍加修改即可

public static void reverse(int[] arr,int left,int right) {
        while(left < right) {
            int ret = arr[left];
            arr[left] = arr[right];
            arr[right] = ret;
            left++;
            right--;
        }
    }
    public static void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);

        System.out.println(Arrays.toString(nums));
    }

三、存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false

public boolean containsDuplicate(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) {
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }

四、寻找峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = -\infty−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？

public static int findPeakElement (int[] nums) {
        if(nums == null || nums.length == 0) {
            return -1;
        }
        if(nums.length == 1) {
            return 0;
        }
        if(nums[0] > nums[1]) {
            return 0;
        }
        if(nums[nums.length-1] > nums[nums.length-2]) {
            return nums.length - 1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] < nums[mid+1]) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

五、珠玑妙算游戏

计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。

public static int[] masterMind(String solution, String guess) {
        int[] arr = new int[2];
        char[] ch = solution.toCharArray();
        char[] c = guess.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if(c[i] == ch[i]) {
                arr[0]++;
                ch[i] = 0;
                c[i] = 1;
            }
            }
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < guess.length(); j++) {
                if(c[i] == ch[j]) {
                    ch[j] = 0;
                    arr[1]++;
                    break;
                }
            }
        }
        return arr;
    }