LeetCode刷题之数组专栏

女爷i 2023-09-25 12:38 144阅读 0赞

--------------------

加油，不要过度焦虑(꒪ꇴ꒪(꒪ꇴ꒪ ;)

--------------------

*  [二分查找：https://leetcode.cn/problems/binary-search/][https_leetcode.cn_problems_binary-search]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 8:14
     * @Description:左闭右开时，思考为什么while(left <= right){}
     */
    public class Code01 {
        
        public int search(int[] nums, int target) {
        
            int left = 0;
            int rihgt = nums.length - 1;
            while (left <= rihgt) {
        
                int middle = left + ((rihgt - left) >> 1);
                if (nums[middle] == target)
                    return middle;
                else if (nums[middle] > target)
                    rihgt = middle - 1;
                else
                    left = middle + 1;
            }
            return -1;
        }
    }

*  [移除元素：https://leetcode.cn/problems/remove-element/][https_leetcode.cn_problems_remove-element]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 8:35
     * @Description:快慢指针
     */
    public class Code02 {
        
        public int removeElement(int[] nums, int val) {
        
            int slow = 0;
            int fast = 0;
            while (fast < nums.length) {
        
                if (nums[fast] == val) {
        
                    fast++;
                } else {
        
                    nums[slow] = nums[fast];
                    slow++;
                    fast++;
                }
            }
            return slow;
        }
    }

*  [有序数组的平方：https://leetcode.cn/problems/squares-of-a-sorted-array/][https_leetcode.cn_problems_squares-of-a-sorted-array]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 8:46
     * @Description:明白数组值的平方后的最大值一定在数组的两端
     */
    public class Code03 {
        
        public int[] sortedSquares(int[] nums) {
        
            int[] res = new int[nums.length];
            int left = 0;
            int right = nums.length - 1;
            int index = nums.length - 1;
            while (left <= right) {
        
                if (nums[left] * nums[left] <= nums[right] * nums[right]) {
        
                    res[index] = nums[right] * nums[right];
                    right--;
                    index--;
                } else {
        
                    res[index] = nums[left] * nums[left];
                    left++;
                    index--;
                }
            }
            return res;
        }
    }

*  [长度最小的子数组：https://leetcode.cn/problems/minimum-size-subarray-sum/][https_leetcode.cn_problems_minimum-size-subarray-sum]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 9:14
     * @Description:滑动窗口，当fast < nums.length成立时，一定要注意slow前移，
     * 并记录满足sum < target的最小长度，所以while中会再次嵌入while，但时间复杂度为O(n)
     */
    public class Code04 {
        
        public int minSubArrayLen(int target, int[] nums) {
        
            int slow = 0;
            int fast = 0;
            int sum = 0;
            int res = Integer.MAX_VALUE;
            while (fast < nums.length) {
        
                sum += nums[fast];
                while (sum >= target) {
        
                    res = Math.min(res, fast - slow + 1);
                    sum -= nums[slow];
                    slow++;
                }
                fast++;
            }
            return (res == Integer.MAX_VALUE) ? 0 : res;
        }
    }

*  [螺旋矩阵：https://leetcode.cn/problems/spiral-matrix-ii/][https_leetcode.cn_problems_spiral-matrix-ii]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 9:25
     * @Description:清楚明白各个变量的实际含义，遵循前闭后开的原则
     */
    public class Code05 {
        
        public int[][] generateMatrix(int n) {
        
            int x = 0, y = 0;
            int i, j;
            int middle = n / 2;
            int loop = n / 2;
            int offset = 1;
            int count = 1;
            int[][] res = new int[n][n];
            while ((loop--) > 0) {
        
                i = x;
                j = y;
                for (; j < n - offset; j++)
                    res[i][j] = count++;
                for (; i < n - offset; i++)
                    res[i][j] = count++;
                for (; j > y; j--)
                    res[i][j] = count++;
                for (; i > x; i--)
                    res[i][j] = count++;
                x++;
                y++;
                offset++;
            }
            if (n % 2 == 1)
                res[middle][middle] = count;
            return res;
        }
    }

*  [搜索插入位置：https://leetcode.cn/problems/search-insert-position/][https_leetcode.cn_problems_search-insert-position]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 11:55
     * @Description:思考为什么return的是right+1;
     */
    public class Code06 {
        
        public int searchInsert(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
        
                int middle = left + ((right - left) >> 1);
                if (nums[middle] == target)
                    return middle;
                else if (nums[middle] > target)
                    right = middle - 1;
                else
                    left = middle + 1;
            }
            return (right + 1);
        }
    }

*  [在排序数组中查找元素的第一个和最后一个位置：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/][https_leetcode.cn_problems_find-first-and-last-position-of-element-in-sorted-array]

/**
     * @Auther: sht2002
     * @Date: 2022-11-01 12:07
     * @Description:首先用二分查找，其次要弄明白searchRange()中两个while判断条件的含义！！！
     */
    public class Code07 {
        
          public int[] searchRange(int[] nums, int target) {
        
            int index = binary(nums, target);
            if (index == -1) return new int[]{
        -1, -1};
            int left = index;
            int right = index;
            while ((left - 1) >= 0 && nums[left - 1] == nums[index]) {
        
                left--;
            }
            while ((right + 1) < nums.length && nums[right + 1] == nums[index]) {
        
                right++;
            }
            return new int[]{
        left, right};
        }
        //二分查找
        private int binary(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
        
                int middle = left + ((right - left) >> 1);
                if (nums[middle] == target)
                    return middle;
                else if (nums[middle] > target)
                    right = middle - 1;
                else
                    left = middle + 1;
            }
            return -1;
        }
    }

*  [x的平方根：https://leetcode.cn/problems/sqrtx/][x_https_leetcode.cn_problems_sqrtx]

/**
     * @Auther: sht2002
     * @Date: 2022-11-02 5:35
     * @Description:
     */
    public class Code01 {
        
        public int mySqrt(int x) {
        
            int left = 0;
            int right = x;
            int res = -1;
            while (left <= right) {
        
                int middle = left + ((right - left) >> 1);
                if ((long) middle * middle <= x) {
        
                    res = middle;
                    left = middle + 1;
                } else {
        
                    right = middle - 1;
                }
            }
            return res;
        }
    }

*  [有效的完全平方：https://leetcode.cn/problems/valid-perfect-square/][https_leetcode.cn_problems_valid-perfect-square]

/**
     * @Auther: sht2002
     * @Date: 2022-11-02 5:54
     * @Description:
     */
    public class Code02 {
        
        public boolean isPerfectSquare(int num) {
        
            int left = 0;
            int right = num;
            while (left <= right) {
        
                int middle = left + ((right - left) >> 1);
                if ((long) middle * middle == num) {
        
                    return true;
                } else if ((long) middle * middle > num) {
        
                    right = middle - 1;
                } else {
        
                    left = middle + 1;
                }
            }
            return false;
        }
    }

*  [删除有序数组中的重复项：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/][https_leetcode.cn_problems_remove-duplicates-from-sorted-array]

/**
     * @Auther: sht2002
     * @Date: 2022-11-02 6:01
     * @Description:为了减少内存空间，可以从下标为1的地方开始，方法也是快慢指针
     */
    public class Code03 {
        
        public int removeDuplicates(int[] nums) {
        
            int slow = 0;
            int fast = 0;
            int flag = Integer.MAX_VALUE;
            while (fast < nums.length) {
        
                if (flag != nums[fast]){
        
                    nums[slow] = nums[fast];
                    slow++;
                    flag = nums[fast];
                }
                fast++;
            }
            return slow;
        }
    }

*  [移动零：https://leetcode.cn/problems/move-zeroes/][https_leetcode.cn_problems_move-zeroes]

/**
     * @Auther: sht2002
     * @Date: 2022-11-02 6:13
     * @Description:
     */
    public class Code04 {
        
        public void moveZeroes(int[] nums) {
        
            int slow = 0;
            int fast = 0;
            while (fast < nums.length) {
        
                if (nums[fast] != 0) {
        
                    swap(nums, slow, fast);
                    slow++;
                }
                fast++;
            }
        }
        //交换的方法千万不能使用异或运算！！
        private void swap(int[] nums, int left, int right) {
        
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }

[https_leetcode.cn_problems_binary-search]: https://leetcode.cn/problems/binary-search/
[https_leetcode.cn_problems_remove-element]: https://leetcode.cn/problems/remove-element/
[https_leetcode.cn_problems_squares-of-a-sorted-array]: https://leetcode.cn/problems/squares-of-a-sorted-array/
[https_leetcode.cn_problems_minimum-size-subarray-sum]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[https_leetcode.cn_problems_spiral-matrix-ii]: https://leetcode.cn/problems/spiral-matrix-ii/
[https_leetcode.cn_problems_search-insert-position]: https://leetcode.cn/problems/search-insert-position/
[https_leetcode.cn_problems_find-first-and-last-position-of-element-in-sorted-array]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[x_https_leetcode.cn_problems_sqrtx]: https://leetcode.cn/problems/sqrtx/
[https_leetcode.cn_problems_valid-perfect-square]: https://leetcode.cn/problems/valid-perfect-square/
[https_leetcode.cn_problems_remove-duplicates-from-sorted-array]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[https_leetcode.cn_problems_move-zeroes]: https://leetcode.cn/problems/move-zeroes/