LeetCode刷题学习-数组篇

数组

二分查找

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

移除元素

提示：

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

双指针解法：

1. fast指针遍历数组元素

2. slow指针记录剩余的元素

3. 当fast指针指向的元素不等于目标值时，将fast指针的元素赋给slow指针，然后同时向后移动；

   若fast指针指向的元素等于目标值时，只需移动fast指针即可，slow指针原地不动

4. 最后slow的值即为数组剩余元素的长度

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

有序数组的平方

暴力解法：

1. 将原数组中所有元素平方后赋值给新数组
2. 给新数组进行排序

class Solution {
    public int[] sortedSquares(int[] nums) {
        int newArr[] = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            newArr[i] = nums[i] * nums[i];
            // newArr[i] = (int)Math.pow(nums[i], 2);  注意pow返回值是double，有类型转换问题需要考虑
        }
        Arrays.sort(newArr);
        return newArr;
    }
}

双指针解法：

1. 因原数组的元素均已有序（升序）。
2. 唯一的变数就是负数平方后可能会变最大值，则最大值肯定位于数组的左边或右边，而不可能在中间了
3. 利用双指针。原数组起始位置指针 low, 终止位置指针 high。
4. 新建一个数组接收平方后的元素。定义一个临时指针 temp 位于该数组的终止位置

class Solution {
    public int[] sortedSquares(int[] nums) {
        int newArr[] = new int[nums.length];
        int low = 0, high = nums.length - 1;
        int temp = newArr.length - 1;
        while(low <= high) {
            int lowNum = nums[low] * nums[low];
            int highNum = nums[high] * nums[high];
            if(lowNum < highNum) {
                newArr[temp--] = highNum;
                high--;
            } else {
                newArr[temp--] = lowNum;
                low++;
            }
        }
        return newArr;
    }
}

长度最小的子数组

滑动窗口法（双指针法的一种）。

滑动窗口法需要思考的问题：

1. 窗口内是什么
2. 如何移动窗口的起始位置
3. 如何移动窗口的结束位置

针对此题：

1. 窗口内就是可能的最小的子数组
2. 若窗口内元素和大于 target， 则初始位置向右移动
3. 若窗口内元素和小于 target， 则终止位置继续向右移动

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int end = 0;
        int sum = 0;
        int minLength = nums.length + 1;
        for(; end < nums.length; end++) {
            // 结束位置向右移动
            sum += nums[end];
            // 当大于或等于Target时，先记录下当前符合要求的子数组长度，然后初始位置再移动
            while(sum >= target) {
                int currentLength = end - start + 1;
                if(currentLength < minLength) {
                    minLength = currentLength;
                }
                sum -= nums[start++];
            }
        }
        return minLength == nums.length + 1 ? 0 : minLength;
    }
}

螺旋矩阵 II

1. 找准边界值
2. 建立一个二维数组，往里填充数据

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        // 左右
        int left = 0, right = n - 1;
        // 上下
        int top = 0, bottom = n - 1;
        int num = 1, target = n * n;
        // 填充
        while(num <= target) {
            // 从左往右
            for(int i = left; i <= right; i++){
                matrix[top][i] = num++;
            }  
            top++; // 最右边的一个已经被填充，边界往下移动
            // 从上往下
            for(int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--; // 最底下的一个已经被填充，边界往左移动
            // 从右往左
            for(int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--; // 最左边的一个已经被填充，边界往上移动
            // 从下往上
            for(int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++; // 最上边的一个已经被填充，边界往右移动
        }
        return matrix;
    }
}