代码随想录算法训练营，29日 | 704. 二分查找，27. 移除元素，977.有序数组的平方，209.长度最小的子数组，59.螺旋矩阵II

数组基础
文档讲解︰代码随想录(programmercarl.com)
1.连续空间、相同类型元素
2.元素只能覆盖
3.二维数组的地址连续吗（C++连续，Java不连续）

704. 二分查找
题目链接：704. 二分查找
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰二分查找
日期：2024-08-29

思路：第一反应是想到二分查找的前提：数组升序，无重复元素；第二点是，确定区间是左闭右开还是左闭右闭，这样才能确定是左右大小比较是<、还是<=。
Java代码如下：

//左闭右闭
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

//左闭右开
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return -1;
    }
}

代码随想录给出一个优化的版本：

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid - 1;
            }
        }
        // 未找到目标值
        return -1;
    }
}

总结：还要再熟悉下更新mid，寻找区间是左闭右开区间，right更新为mid而不是mid - 1，即：下一个查询区间不会去比较nums[middle]。

27. 移除元素
题目链接：27. 移除元素
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰移除元素
日期：2024-08-29

思路：1.暴力解法，两层for，一层遍历数组找要移除的目标值，另一层是找到移除的值后，将其后面的值移前一位；2.快慢指针：快指针快在它会先走，遍历整个数组，慢指针：如果快指针遇到目标值了，它就不动了，否则将快指针的值给它，这样的好处就是，两个指针都从开头起步，能很方便的找到目标值并用后面的值覆盖。
Java代码如下：

//暴力
class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for(int i = 0; i < size; i++){
            if(nums[i] == val){
                for(int j = i + 1; j < size; j++){
                    nums[j - 1] = nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
}

//快慢指针
class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.length; fast++){
            if(nums[fast] != val){
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

代码随想录还提供了用相向双指针的算法，我用的是同向的：

//相向双指针法
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}

总结：第一次用双指针的地方，之前面试有被问过什么时候用双指针的地方，后面遇到多了再总结。总的来说就是一边循环里干两遍循环的事。

977.有序数组的平方
题目链接：977.有序数组的平方
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰有序数组的平方
日期：2024-08-29

思路：1.暴力思路，平方后再快排； 2.注意到数组是有序的，那么对于平方后的最大数只会在头或者尾产生，所有两个指针一个在头一个在尾平方比大小，把较大的值放到一个新数组的末尾就行了。
Java代码如下：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int i = nums.length - 1;
        while(left <= right){
            if(nums[left] * nums[left] <= nums[right] * nums[right]){
                result[i--] = nums[right] * nums[right];
                right--;
            }else{
                result[i--] = nums[left] * nums[left];
                left++;
            }
        }
        return result;
    }
}

总结：注意一定要是有序的数组才能这么操作，面试被坑过（

209.长度最小的子数组
题目链接：209.长度最小的子数组
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰长度最小的子数组
日期：2024-08-29

思路：看题第一眼就是滑动窗口（总算记住了），数组跟着前指针的移动逐加，直到和大于等于目标，记录此时子数组长度，此时移动一位后指针，前指针再接着走，接着加，再出现大于等于目标时比较之前的长度和这一次的，取最小值，最后返回时还要判断到底存不存在这个子数组
Java代码如下：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int i = 0, sum = 0;
        for(int j = 0; j < nums.length; j++){
            sum += nums[j];
            while(sum >= target){
                result = Math.min((j - i + 1), result);
                sum -= nums[i++];
            }
        }
        return result == Integer.MAX_VALUE? 0: result;
    }
}

总结：不熟悉Java语法，Integer.MAX_VALUE，Math.min，滑动窗口这名字还是很形象的，主要用在早最小区间。

59.螺旋矩阵II
题目链接：59.螺旋矩阵II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰螺旋矩阵II
日期：2024-08-29

思路：首先是找不变量，在本题中就是区间的划分，上下左右都得是同样的区间（左闭右开）才能清楚明白的写下去，还有就是完成这套题需要一些什么值要搞清楚，循环起始位置（怎么调整它：需要一个调整值），循环次数，填的数（从1开始），最后就是这个二维矩阵的中心有没有，确定了这些思路就清楚了
Java代码如下：

class Solution {
    public int[][] generateMatrix(int n) {
        int result[][] = new int[n][n];
        int startx = 0, starty = 0;
        int loop = n / 2;
        int mid = n / 2;
        int offset = 1;
        int count = 1;
        while(loop-- > 0){
            int i = startx;
            int j = starty;
            for(; j < n - offset; j++){
                result[i][j] = count++;
            }
            for(; i < n - offset; i++){
                result[i][j] = count++;
            }
            for(; j > 0; j--){
                result[i][j] = count++;
            }
            for(; i > 0; i--){
                result[i][j] = count++;
            }
            startx++;
            starty++;
            offset++;
        }
        if(n % 2 != 0) result[mid][mid] = n * n;
        return result;
    }
}

总结：错在了对二维数组两个角标的理解上，还有这里每个值的意义要搞明白。