day01

数组理论基础

● 思维不难，主要是考察对代码的掌控能力
● 内存中的存储方式：存放在连续内存空间上的相同类型数据的集合
● 数组可以通过下标索引获取到下标对应的数据
● 数组下标从0开始
● 因为内存空间地址连续，因此删除或增加元素的时候，难免移动其他元素地址
● Java中的二维数组，每一行连续，头结点地址没有规则

704.二分查找

● 力扣题目链接
● 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路

● 二分查找逻辑，两种方式，左闭右闭或者左闭右开
● 时间复杂度O(n) 空间复杂度O(logn)
● 为什么不是 m = (i + j) / 2？
○ 因为 i + j 可能很大，二进制表示的数字高位一旦变成1，就变成负数了，做除法无法改变符号，而无符号右移可以，就是除掉二后还是int，但不除可能最高位是1，就导致符号问题
○ Java中,整数都是有符号的,最高位是符号位,0表示正数,1表示负数

代码

// 方法一：左闭右闭写法
class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1; // 这里右边闭，因此在r处的也可能是答案
        int m;
        while (l <= r) { // 因为r处的可能是答案，所以l=r时还要再看看，不能返回-1
            m = (l + r) >>> 1;
            if (nums[m] < target) {
                l = m + 1; // m处元素小，那继续往右找
            } else if (nums[m] > target) {
                r = m - 1; //m处元素大，那继续往左找
            } else {
                return m; // 找到了
            }
        }
        return -1; // 没找到，返回-1
    }
}

// 方法二：左闭右开写法
class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length; // 这里r取到了数组末尾的后一位，因此r的位置一定不是答案
        int m;
        while (l < r) { // 不用管l=r，因为r的位置一定不是答案，l=r时可以直接结束循环
            m = (l + r) >>> 1;
            if (nums[m] < target) {
                l = m + 1; // m处元素小，和之前一样
            } else if (nums[m] > target) {
                r = m; // m处元素大，让r=m即可，如果这里r=m-1，可能导致原来m-1处的元素少判定一次，有问题
                // -1 0 3 7 9 12 找7，m=3 l=7 m=9 然后r需要是9，不能是7，不然返回-1了
            } else {
                return m;
            }
        }
        return -1;
    }
}

27. 移除元素

● 力扣题目链接
● 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
● 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
● 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路

● 双指针法，一个指针遍历数组，如果遇到不等于tar，就更换元素

代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int res = 0; // 初始长度为0
        for (int i = 0; i < nums.length; i++) { // 遍历一遍数组
            if (nums[i] != val) { // 如果不等于val
                nums[res++] = nums[i]; // 把i处元素放到res的位置，然后res+1
            }
        }
        return res; // 最后返回res
    }
}
// 优化为相向双指针，避免要删除的元素在最右侧导致要移动很多元素
class Solution {
    public int removeElement(int[] nums, int val) {
        int l = 0; int r = nums.length - 1;
        while (l <= r) { // 等于也要看，用l遍历，要么自己走，要么是r交换过来的
            if (nums[l] == val) {
                nums[l] = nums[r];
                r--; // 移动r，因为这个一定是val，看过了，继续走
            } else {
                l++; // 不是val，移动l
            }
        }
        return l; // 最后返回l，就是新数组的长度
    }
}