消失的数字

一、消失的数字
数组 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;
}

1
2
3
4
5
6
7
8
9
10
11
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
二、轮转数组
给你一个数组，将数组中的元素向右轮转 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));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
三、存在重复元素
给你一个整数数组 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;
}

1
2
3
4
5
6
7
8
9
10
四、寻找峰值
给定一个长度为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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
五、珠玑妙算游戏
计算机有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]++;