LeetCode刷题第一周

数组：内存空间连续，数据类型统一，下标从0开始

二分查找

704

class Solution {
    public int search(int[] nums, int target) {
        // 方法一：暴力解法
        // for(int i = 0; i < nums.length; i++){
        //     if(nums[i] == target){//找到目标值
        //         return i;
        //     }
        // }
        // return -1;
        // 方法二：二分查找（元素有序且无重复元素），使用迭代，执行速度快，但是内存消耗大
        // return binarySearch(nums, target, 0, nums.length-1); 
        // 方法三：二分查找，参考代码随想录的左闭右闭区间
        // 上来先处理边界条件
        if(target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;//右闭区间
        int mid = (left + right) >> 1;
        while(left <= right){//因为取得数组区间左右都是闭的，所以取等号的时候也能满足条件，还不需要退出循环
            if(target == nums[mid]){
                return mid;
            }else if(target < nums[mid]){
                right = mid -1;//往左区间缩
            }else{
                left = mid +1;
            }
            mid = (left + right) >> 1;
        }
        return -1;
    }
    // public int binarySearch(int[] nums, int target, int start, int end){
    //     int mid = (start+end)/2;
    //     int find = -1;
    //     if(start > end){//没有找到
    //         return -1;
    //     }
    //     if(target == nums[mid]){
    //         return mid;
    //     }else if(target < nums[mid]){
    //         find = binarySearch(nums, target, start, mid-1);
    //     }else{
    //         find = binarySearch(nums, target, mid+1, end);
    //     }
    //     return find;
    // }
}

69x 的平方根

class Solution {
    public int mySqrt(int x) {
        // 使用二分查找
        int left = 0;
        int right = x;
        int ans = -1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if((long)mid*mid <= x){
                ans = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return ans;
    }
}

367有效的完全平方数

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0, right = num;
        while(left <= right){
            int mid = (left + right) >> 1;
            if((long) mid * mid == num){
                return true;
            }else if((long) mid * mid < num){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
}

移除元素

27

class Solution {
    public int removeElement(int[] nums, int val) {
// 原地移除，所有元素
// 数组内元素可以乱序
        // 方法一：暴力解法，不推荐，时间复杂度O(n^2)
        // int right = nums.length;//目标数组长度，右指针
        // for(int i = 0; i < right; i++){
        //     if(val == nums[i]){
        //         right--;//找到目标数值，目标数长度减一，右指针左移
        //         for(int j = i; j < right; j++){
        //             nums[j] = nums[j + 1];//数组整体左移一位（数组元素不能删除，只能覆盖）
        //         }
        //         i--;//左指针左移
        //     }
        // }
        // return right;
        // 方法二：快慢指针，时间复杂度O(n)
        // int solwPoint = 0;
        // for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
        //     if(nums[fastPoint] != val){
        //         nums[solwPoint] = nums[fastPoint];
        //         solwPoint++;
        //     }
        // }
        // return solwPoint;
        // 方法三：注意元素的顺序可以改变，使用相向指针，时间复杂度O(n)
        int rightPoint = nums.length - 1;
        int leftPoint = 0;
        while(rightPoint >= 0 && nums[rightPoint] == val){
            rightPoint--;
        }
        while(leftPoint <= rightPoint){
            if(nums[leftPoint] == val){
                nums[leftPoint] = nums[rightPoint--];
            }
            leftPoint++;
            while(rightPoint >= 0 && nums[rightPoint] == val){
                rightPoint--;
            }
        }
        return leftPoint;
    }
}

26删除排序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
// 相对顺序一致，所以不能使用相向指针。
// 考虑使用快慢指针
        if(nums.length == 1){
            return 1;
        }
        int slowPoint = 0;
        for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){
            if(nums[slowPoint] != nums[fastPoint]){
                nums[++slowPoint] = nums[fastPoint];
            }
        }
        return slowPoint + 1;
    }
}

283移动零

class Solution {
    public void moveZeroes(int[] nums) {
// 要保持相对顺序，不能用相向指针
        int slowPoint = 0;
        for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
            if(nums[fastPoint] != 0){
                nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左边
            }
        }
        for(; slowPoint < nums.length; slowPoint++){
            nums[slowPoint] = 0;//把数组末尾置零
        }
    }
}

844比较含退格的字符串

class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 从前往后的话不确定下一位是不是"#"，当前位需不需要消除，所以采用从后往前的方式
        int countS = 0;//记录s中"#"的数量
        int countT = 0;//记录t中"#"的数量
        int rightS = s.length() - 1;
        int rightT = t.length() - 1;
        while(true){
            while(rightS >= 0){
                if(s.charAt(rightS) == "#"){
                    countS++;
                }else{
                    if(countS > 0){
                        countS--;
                    }else{
                        break;
                    }
                }
                rightS--;
            }
            while(rightT >= 0){
                if(t.charAt(rightT) == "#"){
                countT++;
                }else{
                    if(countT > 0){
                        countT--;
                    }else{
                        break;
                    }
                }
                rightT--;
            }
            if(rightT < 0 || rightS < 0){
                break;
            }
            if(s.charAt(rightS) != t.charAt(rightT)){
                return false;
            }
            rightS--;
            rightT--;
        }
        if(rightS == -1 && rightT == -1){
            return true;
        }
        return false;
    }
}

有序数组的平方

977

class Solution {
    public int[] sortedSquares(int[] nums) {
// 用相向的双指针
        int[] arr = new int[nums.length];
        int index = arr.length - 1;
        int leftPoint = 0;
        int rightPoint = nums.length - 1;
        while(leftPoint <= rightPoint){
            if(Math.pow(nums[leftPoint], 2) > Math.pow(nums[rightPoint], 2)){
                arr[index--] = (int)Math.pow(nums[leftPoint], 2);
                leftPoint++;
            }else{
                arr[index--] = (int)Math.pow(nums[rightPoint], 2);
                rightPoint--;
            }
        }
        return arr;
    }
}

长度最小的子数组

209

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
// 注意是连续子数组
        // 使用滑动窗口，实际上还是双指针
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for(int right = 0; right < nums.length; right++){
            sum += nums[right];
            while(sum >= target){
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

904水果成篮

class Solution {
    public int totalFruit(int[] fruits) {
// 此题也可以使用滑动窗口
        int maxNumber = 0;
        int left = 0;
        Map<Integer, Integer> map = new HashMap<>();//用哈希表记录被使用的篮子数量，以及每个篮子中的水果数量
        for(int right = 0; right < fruits.length; right++){
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);//往篮子里面放水果
            while(map.size() > 2){//放进去的水果不符合水果类型
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if(map.get(fruits[left]) == 0){
                    map.remove(fruits[left]);
                }
                left++;
            }
            maxNumber = Math.max(maxNumber, right - left + 1);
        }
        return maxNumber;
    }
}

螺旋矩阵 II

59

class Solution {
    public int[][] generateMatrix(int n) {
        // 方法一：直接按序输出
        int[][] arr = new int[n][n];
         int top = 0;
         int buttom = n - 1;
         int left = 0;
         int right = n - 1;;
         int index = 1;
         while(left <= right && top <= buttom && index <= n*n){
             for(int i = left; i <= right; i++){
                 arr[top][i] = index++;
             }
             top++;
             for(int i = top; i <= buttom; i++){
                 arr[i][right] = index++;
             }
             right--;
             for(int i = right; i >= left; i--){
                 arr[buttom][i] = index++;
             }
             buttom--;
             for(int i = buttom; i >= top; i--){
                 arr[i][left] = index++;
             }
             left++;
         }
         return arr;
    }
}

54

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int top = 0;
        int buttom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        List<Integer> list = new ArrayList<Integer>();
        while(left <= right && top <= buttom){
            for(int i = left; i <= right; i++){
                if(top <= buttom)
                list.add(matrix[top][i]);
            }
            top++;
            for(int i = top; i <= buttom; i++){
                if(left <= right)
                list.add(matrix[i][right]);
            }
            right--;
            for(int i = right; i >= left; i--){
                if(top <= buttom)
                list.add(matrix[buttom][i]);
            }
            buttom--;
            for(int i = buttom; i >= top; i--){
                if(left <= right)
                list.add(matrix[i][left]);
            }
            left++;
        }
        return list;
    }
}

29 顺时针打印矩阵

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0){
            return new int[0];
        }
        int top = 0;
        int buttom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        int[] arr = new int[matrix.length*matrix[0].length];
        int index = 0;
        while(left <= right && top <= buttom){
            for(int i = left; i <= right; i++){
                if(top <= buttom)
                arr[index++] = matrix[top][i];
            }
            top++;
            for(int i = top; i <= buttom; i++){
                if(left <= right)
                arr[index++] = matrix[i][right];
            }
            right--;
            for(int i = right; i >= left; i--){
                if(top <= buttom)
                arr[index++] = matrix[buttom][i];
            }
            buttom--;
            for(int i = buttom; i >= top; i--){
                if(left <= right)
                arr[index++] = matrix[i][left];
            }
            left++;
        }
        return arr;
    }
}