LeetCode-1.两数之和

思路:
(1)排序+双指针夹逼,O(NlogN)
(2)set,O(N)

LeetCode-4.寻找两个正序数组的中位数-困难

LeetCode-11.盛最多水的容器

思路:双指针(每次移动值较小的那个指针)+全局最大容量

  1. // 双指针, 每次移动较小的那一个, O(N)
  2. public int maxArea(int[] height) {
  3. int low = 0, high = height.length-1;
  4. int maxVolumn = 0;
  5. while(low<high){
  6. int volumn = (high-low)*Math.min(height[low], height[high]);
  7. maxVolumn = Math.max(maxVolumn, volumn);
  8. if(height[low]<=height[high]){
  9. low++;
  10. }else{
  11. high--;
  12. }
  13. }
  14. return maxVolumn;
  15. }

LeetCode-15.三数之和

思路:排序+双指针+去重 , 时间O(N*N)

    // 排序+双指针+去重(外循环去重+内循环去重), 时间O(N*N)
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3){
            return new ArrayList<>();
        }
        // 排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<nums.length-2;i++){
            // 外循环去重
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int low = i + 1, high = nums.length - 1;
            while(low<high){
                int sum = nums[low]+nums[high];
                if(sum == -nums[i]){
                    res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                    // 内循环low去重
                    while(low<high && nums[low]==nums[low+1]){
                        low++;
                    }
                    // 内循环high去重
                    while(low<high && nums[high]==nums[high-1]){
                        high--;
                    }
                    // 不能有重复则自增
                    low++;
                    high--;
                }else if(sum < -nums[i]){
                    low++;
                }else{
                    high--;
                }
            }
        }
        return res;
    }

LeetCode-16.最接近的三数之和

思路:排序+双指针+全局diff变量,时间O(N*N)

    // 存在唯一答案, 所以不需要去重
    // 排序+双指针+全局diff变量, 时间O(N*N)
    public int threeSumClosest(int[] nums, int target) {
        int diff = Integer.MAX_VALUE;
        int res = 0;
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            int low=i+1, high = nums.length - 1;
            while(low<high){
                int sum = nums[i]+nums[low]+nums[high];
                int currentDiff = Math.abs(sum-target);
                if(currentDiff<=diff){
                    diff  = currentDiff;
                    res = sum;
                }
                if(sum == target){
                    return target;
                }else if(sum>target){
                    high--;
                }else{
                    low++;
                }
            }
        }
        return res;
    }

LeetCode-18.四数之和

    // 排序+去重(两层外循环去重+内循环去重)+双指针夹逼,时间O(N*N*N)
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums.length<4){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<nums.length-3;i++){
            // 第一层外循环去重, 判断本次是否需要跳过
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.length-2;j++){
                // 第二层外循环去重, 判断本次是否需要跳过
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                int low = j+1, high = nums.length - 1;
                while(low<high){
                    int sum = nums[i]+nums[j]+nums[low]+nums[high];
                    if(sum==target){
                        res.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));
                        // 内循环low去重, 判断下次是否需要跳过
                        while(low<high && nums[low]==nums[low+1]){
                            low++;
                        }
                        while(low<high && nums[high]== nums[high-1]){
                            high--;
                        }
                        // 缩小区间
                        // 为什么要low++且high--呢?
                        //因为不能有重复值,一个指针向里靠近,另一个指针不动的话,和一定不等于target
                        low++;
                        high--;
                    }else if(sum<target){
                        low++;
                    }else{
                        high--;
                    }
                }
            }
        }
        return res;
    }

LeetCode-26.删除有序数组中的重复项

思路:插入法重建数组

    public int removeDuplicates(int[] nums) {
        if(nums.length<2){
            return nums.length;
        }
        int nextPointer = 1;
        for(int num:nums){
            if(nums[nextPointer-1]!=num){
                nums[nextPointer++] = num;
            }
        }
        return nextPointer;
    }

LeetCode-27.移除元素

思路:插入法重建数组

    // 插入法原地重建数组
    public int removeElement(int[] nums, int val) {
        if(nums.length<1){
            return nums.length;
        }
        int nextPointer = 0;
        for(int num:nums){
            if(num!=val){
                nums[nextPointer++] = num;
            }
        }
        return nextPointer;

LeetCode-31.下一个排列

思路:

    // 把右边的较大的数和左边较小的数交换, 被交换的右边和左边的数尽量靠右(尽可能小)
    // 从右边向左循环第一个顺序对index为(x, y), 在区间[y ,n-1]从右向左需寻找第一个大于nums[x]的下标z
    // 交换nums[x]和nums[z],然后逆序[x+1, n-1]
    public void nextPermutation(int[] nums) {
        if(nums.length<2){
            return;
        }
        // flag为true说明数组需要翻转
        boolean flag = true;
        int x = 0, z = 0;
        // 寻找第一个顺序对(x,y)
        for(int i=nums.length-1;i>=1;i--){
            if(nums[i]>nums[i-1]){
                flag = false;
                x = i-1;
                break;
            }
        }
        // 没有找到顺序对
        if(flag){
            reverse(nums, 0, nums.length-1);
            return;
        }
        for(int i=nums.length-1;i>=x;i--){
            if(nums[i]>nums[x]){
                z = i;
                break;
            }
        }
        // 交换x和z位置
        swap(nums, x, z);
        // 逆序[x+1, n-1]
        reverse(nums, x+1, nums.length-1);
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums, int i, int j){
        while(i<j){
            swap(nums, i, j);
            i++;
            j--;
        }
    }

LeetCode-33.搜索旋转排序数组

思路:二分,[low , high]区间被mid分为两部分,有一部分为有序区间,通过判断有序区间是否包含target来排除一个区间达到二分,如果nums[mid]>=nums[low]则[low, mid]有序,否则 [mid, high]有序

    // 二分
    // [low,high]被mid分为两部分, 判断有序的部分, 并判断有序部分是否包含target来排除一半区间
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while(low<=high){
            int mid = (high-low)/2 + low;
            if(nums[mid]==target){
                return mid;
            }
            // [low, mid] 有序
            if(nums[mid]>=nums[low]){
                // target在[low, mid]里
                if(nums[low]<=target && target<=nums[mid]){
                    high = mid;
                }else{
                    low = mid + 1;
                }
            // [mid, high] 有序
            }else{
                if(nums[mid]<=target && target<=nums[high]){
                    low = mid;
                }else{
                    high = mid-1;
                }
            }
        }
        return -1;
    }

LeetCode-34.在排序数组中查找元素的第一个和最后一个位置

思路:二分
查找第一个元素:找到后也要向左找,既high—,最终high会落在第一个元素的左边,low落在第一个元素位置
查找最后一个元素:找到后也要向右找,既low++,最终low会落在最后一个元素的右边,high落在最后一个元素位置
注意:如果原数组中没有target元素则high和low无效.

LeetCode-35.搜索插入位置

思路:二分搜索等于target或大于target的第一个位置
注意:有可能数组中所有数都小于target,有可能输入只有一个数字

    // 数组中不存在大于target位置时, low+1
    public int searchInsert(int[] nums, int target) {
        if(nums.length==0){
            return 0;
        }
        int low = 0, high = nums.length - 1;
        while(low<=high){
            // 有可能数组所有元素都小于target 
            if(low==high){
                return nums[low]>=target?low:(low+1);
            }
            int mid = (high-low)/2 + low;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid]>target){
                high = mid;
            }else{
                low++;
            }
        }
        return low;
    }

LeetCode-39.组合总和

看 “回溯专栏”

LeetCode-40.组合总和 II

看 “回溯专栏”

LeetCode-41.缺失的第一个正数-困难

LeetCode-42.接雨水-困难

LeetCode-45.跳跃游戏 II

思路:贪心算法
(1)反向查找:从位置n-1向前查找上一个位置,要求上一个位置距离当前位置最远,而且上一个位置可以一步到达当前位置,时间O(N*N)

    // 贪心:反向查找下一个位置, 时间O(N*N)
    public int jump(int[] nums) {
        if(nums==null||nums.length<2){
            return 0;
        }
        // pos是当前位置, 从后向前查找, 上一个位置尽可能靠近位置0
        int step = 0, pos = nums.length - 1;
        while(pos>0){
            for(int i=0;i<nums.length;i++){
                if(i+nums[i]>=pos){
                    step++;
                    pos = i;
                    break;
                }
            }
        }
        return step;
    }

(2)正向查找:从位置0向后查找下一个位置,要求当前位置能一步到达下一个位置,而且从下一个位置能达到的距离最远,时间O(N)

    public int jump(int[] nums) {
        if(nums==null||nums.length<2){
            return 0;
        }
        // end是本轮能到达的最远距离, maxPos是下一轮能到达的最远距离
        int end = 0, maxPos = 0, step = 0;
        // 不访问最后一个元素, 因为如果最后恰好能到达最后一个位置就会多出来不必要的一步
        // 因为访问第一个位置就跳了一步
        for(int i=0;i<nums.length-1;i++){
            maxPos = Math.max(maxPos, i+nums[i]);
            if(i==end){
                step++;
                end = maxPos;
            }
        }
        return step;
    }

LeetCode-48.旋转图像

描述:矩阵顺时针旋转90度,要求空间O(1)
思路:(x,y) -> (y, n-1-x);先水平翻转(x,y)->(n-1-x, y),然后主对角线翻转(x, y)->(y,x),联立得(x,y)->(y, n-1-x)

LeetCode-53.最大子序和

描述:
思路:

LeetCode-54.螺旋矩阵

描述:给你一个m行n列的矩阵 matrix,请按照顺时针螺旋顺序,返回矩阵中的所有元素。
思路:模拟
方法1:螺旋模拟
右->下->左->上,注意记录被访问过的位置,不要重复访问

        public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        // 右->下->左->上
        int[][] directions= new int[][]{{0,1}, {1, 0}, {0,-1}, {-1, 0}};
        // 记录(x,y)是否被访问过
        boolean[][] visited = new boolean[m][n];
        // 遍历横、纵坐标
        int x = 0, y = 0;
        // 方向数组变量
        int diretP = 0;
        // 一共有m*n个元素需要加入res
        for(int i=0;i<m*n;i++){
            visited[x][y] = true;
            res.add(matrix[x][y]);
            // 下一个位置是否存在
            if(!isLegal(x+directions[diretP][0], y+directions[diretP][1], m, n, visited)){
                diretP = (diretP+1)%directions.length;
            }
            x += directions[diretP][0];
            y += directions[diretP][1];
        }
        return res;
    }
    public boolean isLegal(int x, int y, int m, int n, boolean[][] visited){
        return x>=0 && x<m && y>=0 && y<n &&!visited[x][y];
    }

方法2:按层模拟
从外层到内层:左上角 (topX, topY),右下角 (bottomX, bottomY)
上边:i=[topY,bottomY]的[topX,i] 加入结果集
右边:i=[topX+1, bottomX] [i, bottomY]加入结果集
topX下边:i=[bottomY-1, topY], [bottomX, i] 加入结果集
左边:i=[bottomX-1, topX+1], [i, topY] 加入结果集

    // 方法2: 按层模拟
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        // 左上角 (topX, topY)
        int topX = 0, topY = 0;
        // 右下角 (bottomX, bottomY)
        int bottomX= m-1, bottomY = n-1;
        while(topX<=bottomX && topY<=bottomY){
            // 上边: 左->右
            for(int i=topY; i<=bottomY;i++){
                res.add(matrix[topX][i]);
            }
            // 右边: 上->下
            for(int i=topX+1; i<=bottomX;i++){
                res.add(matrix[i][bottomY]);
            }
            // 可能最后只剩一行或一列
            if(topX<bottomX && topY<bottomY){
                // 下边: 右->左
                for(int i=bottomY-1;i>=topY;i--){
                    res.add(matrix[bottomX][i]);
                }
                // 左边: 下->上
                for(int i=bottomX-1;i>=topX+1;i--){
                    res.add(matrix[i][topY]);
                }
            }
            // 向内走一圈
            topX++;topY++;
            bottomX--;bottomY--;
        }
        return res;
    }

LeetCode-55.跳跃游戏

描述:给一个非负整数数组 nums ,最初位于数组的 第一个下标 ,数组中的每个元素的值代表你在该位置可以跳跃的最大长度,判断你是否能够到达最后一个下标。
思路:贪心
维护一个全局可到达的最远位置maxPos,初始maxPos=0
遍历数组每个下标i:
若i>maxPos则不能到达最后一个位置
若maxPos>=n-1则能到达最后一个位置
更新maxPos=max(maxPos, i+nums[i])
时间O(N)

    // 贪心
    public boolean canJump(int[] nums) {
        int maxPos = 0;
        int n = nums.length;
        for(int i=0;i<n;i++){
            if(i>maxPos){
                return false;
            }
            if(maxPos>=n-1){
                return true;
            }
            maxPos = Math.max(maxPos, i + nums[i]);
        }
        return true;
    }

LeetCode45-跳跃游戏 II 延申题

描述:给定一个非负整数数组,你最初位于数组的第一个位置,数组中的每个元素代表你在该位置可以跳跃的最大长度,目标是使用最少的跳跃次数到达数组的最后一个位置,有可能到达不了最后一个位置,判断是否达到最后一个位置并且如果能到达就输出最少需要跳跃的步数。

LeetCode-56.合并区间

描述:数组 intervals 表示若干个区间的集合,单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
思路:排序+ 逐项合并
将二维数组intervals按照第一维度升序排序,然后遍历intervals的每个元素intervals[i]:
i=0,将intervals[i]尾插法插入结果集顺序表res
i>0,若intervals[i]和res的tail元素没有交叉,就直接插入,如果有交叉则先从res删除tail然后将interval[i]和tail合并再插入res

    // 排序 + 逐项
    public int[][] merge(int[][] intervals) {
        // 二维数组升序排序
        Arrays.sort(intervals, (a, b)->a[0]-b[0]);
        List<int[]> res = new ArrayList<>();
        for(int i=0;i<intervals.length;i++){
            if(i==0){
                res.add(intervals[i]);
                continue;
            }
            int[] resTail = res.get(res.size()-1);
            // intervals[i]和resTail无交叉
            if(resTail[0]>intervals[i][1] || resTail[1]<intervals[i][0]){
                res.add(intervals[i]);
            }else{
                // 只需要修改resTail的左右端点即可
                resTail[0] = Math.min(resTail[0], intervals[i][0]);
                resTail[1] = Math.max(resTail[1], intervals[i][1]);
            }
        }
        //List转数组
        return res.toArray(new int[res.size()][]);
    }

LeetCode-57.插入区间

描述:给你一个无重叠的按照区间起始端点排序的区间列表,在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
思路:
原始区间列表可以分为:在newInterval 左边的区间,和newInterval 有交叉的区间,在newInterval 右边的区间
左边区间:intervals[i][1]右边区间: intervals[i][0]>newInterval[1]
交叉区间: 不是左边也不是右边的区间, 所有的交叉区间和newInterval会融合为一个新融合区间
新融合区间需要在第一个右区间加入结果集之前加入结果集,所以如果不存在右区间, 就需要扫描完数组后加入结果集,设置一个标识flag,如果有右区间则置flag为true。

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        boolean isExistRightIntervalFlag = false;
        int n = intervals.length;
        // 新融合区间 左、右 端点
        int mergeLeft = newInterval[0];;
        int mergeRight = newInterval[1];
        for(int i = 0;i<n;i++){
            // 左区间
            if(intervals[i][1]<newInterval[0]){
                res.add(intervals[i]);
            // 右区间    
            }else if(intervals[i][0]>newInterval[1]){
                // 将新融合区间插入到第一个右区间左边
                if(!isExistRightIntervalFlag){
                    isExistRightIntervalFlag = true;
                    res.add(new int[]{mergeLeft, mergeRight});
                }
                res.add(intervals[i]);
            // 交叉区间    
            }else{
                mergeLeft = Math.min(mergeLeft, intervals[i][0]);
                mergeRight = Math.max(mergeRight, intervals[i][1]);
            }
        }
        // 如果没有一个右区间
        if(!isExistRightIntervalFlag){
            res.add(new int[]{mergeLeft, mergeRight});
        }
        // List转数组
        return res.toArray(new int[res.size()][]);
    }

LeetCode-59.螺旋矩阵 II

LeetCode-62.不同路径

LeetCode-63.不同路径 II

LeetCode-64.最小路径和

LeetCode-66.加一

LeetCode-73.矩阵置零

LeetCode-74.搜索二维矩阵

LeetCode-75.颜色分类

LeetCode-78.子集

LeetCode-79.单词搜索

LeetCode-80.删除有序数组中的重复项 II

LeetCode-81.搜索旋转排序数组 II

LeetCode-84.柱状图中最大的矩形

LeetCode-85.最大矩形-困难

LeetCode-88.合并两个有序数组-困难

LeetCode-105.从前序与中序遍历序列构造二叉树

LeetCode-106.从中序与后序遍历序列构造二叉树

LeetCode-118.杨辉三角

LeetCode-119.杨辉三角 II

LeetCode-120.三角形最小路径和

LeetCode-121.买卖股票的最佳时机

LeetCode-122.买卖股票的最佳时机 II

LeetCode-123.买卖股票的最佳时机 III-困难

LeetCode-126.单词接龙 II-困难

LeetCode-128.最长连续序列-困难

LeetCode-152.乘积最大子数组

LeetCode-153.寻找旋转排序数组中的最小值

LeetCode-154.寻找旋转排序数组中的最小值 II

LeetCode-162.寻找峰值

LeetCode-167.两数之和 II - 输入有序数组

LeetCode-169.多数元素

LeetCode-189.旋转数组链接

LeetCode-209.长度最小的子数组

LeetCode-216.组合总和 III

LeetCode-217.存在重复元素

LeetCode-219.存在重复元素 II

LeetCode-228.汇总区间

LeetCode-229.求众数 II

LeetCode-238.除自身以外数组的乘积

LeetCode-268.丢失的数字

LeetCode-283.移动零

LeetCode-287.寻找重复数

LeetCode-289.生命游戏

LeetCode-380.常数时间插入、删除和获取随机元素

LeetCode-381.O(1) 时间插入、删除和获取随机元素 - 允许重复

LeetCode-414.第三大的数

LeetCode-442.数组中重复的数据

LeetCode-448.找到所有数组中消失的数字

LeetCode-457.环形数组是否存在循环

LeetCode-485.最大连续1的个数

LeetCode-495.提莫攻击

LeetCode-509.斐波那契数