首页 算法

作者：dabing🧁

记录一些 LeetCode 写过的题目及其解题思路

# 题目 1 两数之和 - 简单

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

# 1.1 官方解析：

方法一：暴力枚举

方法二：哈希表 (😍)

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O (N) 降低到 O (1)。

这样我们创建一个 哈希表 ，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

复杂度分析：

  • 时间复杂度：O (N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O (1) O (1) 地寻找 target - x。

  • 空间复杂度：O (N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

# 1.2 我的解法：

我是 暴力遍历 解决的，两次循环，时间复杂度 O (N^2)。最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            int tmp=target-nums[i];
            for(int j=i+1;j<nums.length;j++){
                if(tmp==nums[j]){
                    return new int[]{i,j};
                }
            }
        }
    return new int[0];
    }
}
复杂度分析：


    

  • 时间复杂度：O (N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
    • 

  • 空间复杂度：O (1)。
    • 



# 题目 2  二分查找 - 简单


20220423


给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


# 1.1 我的解法：


我是正好复习 Java 基础看到了二分查找，所以侥幸做出来了


class Solution {
    public int search(int[] nums, int target) {
        int low=0;  
        int height=nums.length-1;
        int mid=0;
        while(low<=height){
            mid=(low+height)/2;
            if(nums[mid]==target){
                return mid;
            }else if(target>nums[mid]){
                low=mid+1;
            }else{
                height=mid-1;
            }
        }
        return -1;
    }
}
复杂度分析：


    

  • 时间复杂度： O*(logn)，其中 N 是数组中的元素数量。
    • 



# 题目 3  搜索插入位置 - 简单


20220424


给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。


请必须使用时间复杂度为 O (log n) 的算法。


# 1.1 我的解法：


我感觉好笨笨，前面查询部分还是一样用二分查找。


但是后一部分，返回插入位置的，一直处理不好边界问题。


image-20220424174626183


看答案的。。。。


class Solution {
    public int search(int[] nums, int target) {
        int low=0;  
        int height=nums.length-1;
        int mid=0;
        while(low<=height){
            mid=(low+height)/2;
            if(nums[mid]==target){
                return mid;
            }else if(target>nums[mid]){
                low=mid+1;
            }else{
                height=mid-1;
            }
        }
        return right+1;
    }
}
复杂度分析：


    

  • 时间复杂度： O*(log*n)，其中 N 是数组中的元素数量。
    • 

  • 空间复杂度：O (1)
    • 

  • image-20220425163203583
    • 



# 1.2 代码随想解析


这道题目不难，但是为什么通过率相对来说并不高呢，我理解是大家对边界处理的判断有所失误导致的。


这道题目，要在数组中插入目标值，无非是这四种情况。


image-20220424175554165


    

  • 目标值在数组所有元素之前
    • 

  • 目标值等于数组中某一个元素
    • 

  • 目标值插入数组中的位置
    • 

  • 目标值在数组所有元素之后
    • 



这四种情况确认清楚了，就可以尝试解题了。


接下来我将从暴力的解法和二分法来讲解此题，也借此好好讲一讲二分查找法


暴力解法：


class Solution {
    public int searchInsert(int[] nums, int target) {
       for(int i=0;i<nums.length;i++){
           if(target<=nums[i]){
               return i;
           }     
       }
       return nums.length; 
    }
}
image-20220425164235614


时间复杂度：O (n)


空间复杂度：O (1)


# 题目 4  移除元素 - 简单


给你一个数组  nums  和一个值  val ，你需要  原地  移除所有数值等于 val 的元素，并返回移除后数组的新长度。


不要使用额外的数组空间，你必须仅使用 O (1) 额外空间并 原地 修改输入数组。


元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。


示例 1：


输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：


输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。



# 1.1 我的解法：


我是根据提示写出来的：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。


看了下官方解析，我的解法相当于官方的优化。image-20220425171040287


当遍历到有相同数据的时候，将该数据置换成尾部的数据，但我这里并没有修改尾部数据。置换之后目标指针 - 1，要再对比一次数据；尾部指针 - 1。


class Solution {
    public int removeElement(int[] nums, int val) {
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(val==nums[i]){
                nums[i]=nums[n-1];
                i--;
                n--;
            }
        }
        return n;
    }
}
复杂度分析：


    

  • 时间复杂度：O (N)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
    • 

  • 空间复杂度：O (1)。
    • 



# 1.2 官方解析：


方法一：双指针


思路及算法：


由于题目要求删除数组中等于 val  的元素，我们可以把不等于 val  的数据直接写回到数组上。


可以使用双指针：右指针 right  指向当前将要处理的元素，左指针  left  指向下一个将要赋值的位置。(从 0 开始)


这样的算法在最坏情况下（输入数组中没有元素等于  val ），左右指针各遍历了数组一次。


代码:


就是把符合条件的数据丢进数组


class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;  
        int left = 0;
        for (int right = 0; right < n; right++) { // 遍历数组
            if (nums[right] != val) {   // 符合条件的数据
                nums[left] = nums[right];  // 符合条件的放回数组里去
                left++;
            }
        }
        return left;
    }
}
    

  • 时间复杂度：O (n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。
    • 

  • 空间复杂度：O (1)。我们只需要常数的空间保存若干变量。
    • 



方法二：双指针优化 (😍)


思路


如果要移除的元素恰好在数组的开头，例如序列  [1,2,3,4,5] ，当  val  为 1 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4] ，同样满足题目要求。这个优化在序列中  val  元素的数量较少时非常有效。


实现方面，我们依然使用 双指针 ，两个指针初始时分别位于数组的 首尾 ，向中间移动遍历该序列。


算法


如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。


当左指针  left  和右指针 right  重合的时候，左右指针遍历完数组中所有的元素。


这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。


代码


class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}
复杂度分析：


    

  • 时间复杂度：O (n)，其中 n 为序列的长度。我们只需要遍历该序列至多一次。
    • 

  • 空间复杂度：O (1)。我们只需要常数的空间保存若干变量。
    • 



# 题目 5 有序数组的平方 - 简单


给你一个按 非递减顺序 排序的整数数组  nums ，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。


# 1.1 我的解法


我真的是硬做的噢，就是遍历平方之后，用 Arrays 类来排序再输出。


class Solution {
    public int[] sortedSquares(int[] nums) {
        int j=0;
        for(int i:nums){
           nums[j]=i*i;
           j++; 
        }
        Arrays.sort(nums);
        return nums;
    }
}
效果也是蛮差的。


image-20220425180218021


复杂度分析


    

  • 

    时间复杂度：O (nlogn)，其中 n 是数组 nums 的长度。
    

    • 

  • 

    空间复杂度：O (logn)。除了存储答案的数组以外，我们需要 O (logn) 的栈空间进行排序
    

    • 



# 1.2 官方解析


方法一：直接排序


跟我做的一样


方法二：双指针

思路与算法


方法一没有利用「数组 nums 已经按照升序排序」这个条件。显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。


这样一来，如果我们能够找到数组 nums 中 负数 与 非负数 的分界线，那么就可以用类似 归并排序 的方法了。具体地，我们设 neg 为数组 nums 中负数与非负数的分界线，也就是说，nums [0] 到 nums [neg] 均为负数，而 nums [neg+1] 到 nums [n−1] 均为非负数。当我们将数组 nums 中的数平方后，那么 nums [0] 到 nums [neg] 单调递减，nums [neg+1] 到 nums [n−1] 单调递增。


由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置 neg  和 neg+1 ，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。


代码


class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }
        int[] ans = new int[n];
        int index = 0, i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {
                ans[index] = nums[j] * nums[j];
                ++j;
            } else if (j == n) {
                ans[index] = nums[i] * nums[i];
                --i;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                ans[index] = nums[i] * nums[i];
                --i;
            } else {
                ans[index] = nums[j] * nums[j];
                ++j;
            }
            ++index;
        }
        return ans;
    }
}
复杂度分析


    

  • 

    时间复杂度：O (n)，其中 nn 是数组 nums 的长度。
    

    • 

  • 

    空间复杂度：O (1)。除了存储答案的数组以外，我们只需要维护常量空间。
    

    • 



方法三：双指针

思路与算法


同样地，我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个 逆序 放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。


代码


class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            } else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
}
# 题目 6 长度最小的子数组 - 中等


给定一个含有  n  个正整数的数组和一个正整数  target  。


找出该数组中满足 其和   ≥ target  的长度最小的 连续子数组  [numsl, numsl+1, ..., numsr-1, numsr]  ，并返回其长度。如果不存在符合条件的子数组，返回  0  。


# 1.1 我的解法


暴力解：从第一个开始遍历，两个指针。一个一个的往后加，看代码，但是代码写的非常不优雅


class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int sum=0;
       int res=0;
       int tmp=0;
       for(int i=0;i<nums.length;i++){
           sum=0;
           for(int j=i;j<nums.length;j++){
               sum+=nums[j];
               if(sum>=target){
                  tmp=j-i+1;
                  if(tmp==1) res=1;
                  if(res!=0){
                    res=res<tmp?res:tmp;  // 比原定的长度还大就不用继续遍历，进行下一次遍历
                    break;
                  }else{
                      res=tmp;
                  }   
               }
                
           }
       }
       return res; 
    }
}
image-20220507161946929


效率也很低啊，时间复杂度：O (n^2) 空间复杂度：O (1)


# 1.2 官方解析


方法一：暴力法

暴力法是最直观的方法。初始化子数组的最小长度为无穷大，枚举数组 nums  中的每个下标作为子数组的开始下标，对于每个开始下标  i ，需要找到大于或等于  i  的最小下标  j ，使得从 nums[i]  到 nums[j]  的元素和大于或等于  s ，并更新子数组的最小长度（此时子数组的长度是  j-i+1 ）。


class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
方法二：前缀和 + 二分查找

方法一的时间复杂度是  O(n^2) ，因为在确定每个子数组的开始下标后，找到长度最小的子数组需要  O(n)  的时间。如果使用二分查找，则可以将时间优化到 O(logn) 。


为了使用二分查找，需要额外创建一个数组 sums  用于存储数组 nums  的前缀和，其中  sums[i]  表示从  nums[0]  到 nums[i−1]  的元素和。得到前缀和之后，对于每个开始下标 i ，可通过二分查找得到大于或等于 i  的最小下标 bound ，使得  sums[bound]-sums[i-1] ≥s ，并更新子数组的最小长度（此时子数组的长度是  bound−(i−1) ）。


因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。


在很多语言中，都有现成的库和函数来为我们实现这里二分查找大于等于某个数的第一个位置的功能，比如 C++ 的 lower_bound，Java 中的 Arrays.binarySearch，C# 中的 Array.BinarySearch，Python 中的 bisect.bisect_left。


class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算，令 size = n + 1 
        //sums [0] = 0 意味着前 0 个元素的前缀和为 0
        //sums [1] = A [0] 前 1 个元素的前缀和为 A [0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
复杂度分析


    

  • 

    时间复杂度：O (nlogn)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 O (n)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O (logn)，因此总时间复杂度是 O (nlogn)。
    

    • 

  • 

    空间复杂度：O (n)，其中 n 是数组的长度。额外创建数组 sums 存储前缀和。
    

    • 



方法三：滑动窗口

在方法一和方法二中，都是每次确定子数组的开始下标，然后得到长度最小的子数组，因此时间复杂度较高。为了降低时间复杂度，可以使用   滑动窗口  的方法。


定义两个指针 start  和 end  分别表示子数组（滑动窗口）的开始位置和结束位置，维护变量  sum  存储子数组中的元素和（即从 nums[start]  到  nums[end]  的元素和）。


初始状态下， start  和 end  都指向下标  0 ， sum  的值为  0 。


每一轮迭代，将 nums[end]  加到  sum ，如果 sum≥s ，则更新子数组的最小长度（此时子数组的长度是 end−start+1 ），然后将 nums[start]  从 sum  中减去并将 start  右移，直到  sum<s ，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将  end  右移。


class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
复杂度分析


    

  • 

    时间复杂度：O (n)，其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。
    

    • 

  • 

    空间复杂度：O (1)。
    

    • 



# 题目 7 螺旋矩阵 II- 中等


给你一个正整数  n  ，生成一个包含  1  到  n2  所有元素，且元素按顺时针顺序螺旋排列的  n x n  正方形矩阵  matrix  。


image-20220507232645315


输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]



# 1.1 我的解法


救命，做不出来，我看还有螺旋矩阵 I , 先去做做 I


下一题


经过了 I 做出来的，稍稍改了下而已：


class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res=new int[n][n];
        int up=0;
        int down=n-1;
        int left=0;
        int right=n-1;
        int index=1;
        while(true){
            // 第一行
            for(int i=left;i<=right;i++){
                res[up][i]=index;
                index++;
            }
            up++;
            if(up>down) break;
            // 最后一列
            for(int i=up;i<=down;i++){
                res[i][right]=index;
                index++;
            }
            right--;
            if(right<left) break;
            // 最后一行
            for(int i=right;i>=left;i--){
                res[down][i]=index;
                index++;
            }
            down--;
            if(down<up) break;
            // 第一列
            for(int i=down;i>=up;i--){
                res[i][left]=index;
                index++;
            }
            left++;
            if(left>right) break;
        }
        return res;
    }
}
image-20220509174944303


复杂度分析


    

  • 时间复杂度：O (m*n)
    • 

  • 空间复杂度：O (1) , 除了输出数组以外，空间复杂度是常数。
    • 



# 题目 8 螺旋矩阵 - 中等


给你一个  m  行  n  列的矩阵  matrix  ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。


示例：


image-20220508175209465


输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]



# 1.1 我的解法


嘻嘻，看评论区兄弟说的才做出来的。果然中等题就能把我碾压了


image-20220508190037544


感谢老哥～


class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 对于这种螺旋遍历的方法，重要的是要确定上下左右四条边的位置，那么初始化的时候
        // 上边 up 就是 0, 下边 down 就是 m-1，左边 left 是 0，右边 right 是 n-1。然后我们进行 while 循环，
        // 先遍历上边，将所有元素加入结果 res，然后上边下移一位，如果此时上边大于下边，
        // 说明此时已经遍历完成了，直接 break
        int m=matrix.length;;
        int n=matrix[0].length;
        int up=0;
        int down=m-1;
        int left=0;
        int right=n-1;
        List res=new ArrayList();
        // 问题是啥时候可以停止遍历呢？
        while(true){
            for(int i=left;i<=right;i++){ // 遍历第 1 行
                res.add(matrix[up][i]);      
            }
            // 遍历完第一行，up 下移一行
            up++;
            if(up>down) break;
            for(int i=up;i<=down;i++){ // 遍历最后 1 列
                res.add(matrix[i][right]);
            
            }
            // 遍历完最后一列，right 右边左移一列
            right--;
            if(right<left) break;
            for(int i=right;i>=left;i--){ // 遍历最后 1 行
                res.add(matrix[down][i]);
                  
            }
            // 遍历完最后一行，down 上移一行
            down--;
            if(down<up) break;
            for(int i=down;i>=up;i--){ // 遍历第 1 列
                res.add(matrix[i][left]);
                   
            }
            // 遍历完第 1 列，left 右移一行
            left++;
            if(left>right) break;
        }
        return res;
    }
}
但是好像还是不够优雅，可以加上一个如果传空数组，直接返回空。


虽然也没啥区别。


if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return new LinkedList<>();
image-20220508185544414


复杂度分析


    

  • 时间复杂度：O (m*n)
    • 

  • 空间复杂度：O (1) , 除了输出数组以外，空间复杂度是常数。
    • 



# 1.2 官方解析


方法一：模拟

可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。


判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵  visited ，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将  visited  中的对应位置的元素设为已访问。


如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。


class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = <!--swig0-->;
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}
看不懂，不想看了～～～


复杂度分析


    

  • 

    时间复杂度：O (mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
    

    • 

  • 

    空间复杂度：O (mn)。需要创建一个大小为 m×n  的矩阵 visited  记录每个位置是否被访问过。
    

    • 



方法二：按层模拟


这个跟我做的是一个意思。


可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。


定义矩阵的第  k  层是到最近边界距离为  k  的所有顶点。例如，下图矩阵最外层元素都是第 1  层，次外层元素都是第 2  层，剩下的元素都是第  3  层。


[[1, 1, 1, 1, 1, 1, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 2, 3, 3, 3, 2, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 1, 1, 1, 1, 1, 1]]
对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于  (top,left) ，右下角位于  (bottom,right) ，按照如下顺序遍历当前层的元素。


从左到右遍历上侧元素，依次为 (top,left)  到 (top,right) 。


从上到下遍历右侧元素，依次为 (top+1,right)  到 (bottom,right) 。


如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为  (bottom,right−1)  到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left)  到  (top+1,left) 。


遍历完当前层的元素之后，将 left  和 top  分别增加 1，将  right  和 bottom  分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。


class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}
复杂度分析


    

  • 

    时间复杂度：O (mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
    

    • 

  • 

    空间复杂度：O (1)。除了输出数组以外，空间复杂度是常数。
    

    • 



方法三、削头旋转


有一个在评论区看到的，削头（拿第一行），逆时针旋转 90°，继续削头


也很厉害


class Solution {
    // 旋转削头的做法
      public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        while (matrix.length>=1){
            for (int num : matrix[0]) {  // 第一行削头
                res.add(num);
            }
            matrix=reversalArr(matrix);  // 数组去掉第一行并逆时针旋转 90°
        }
        return res;
    }
    private int[][] reversalArr(int[][] matrix) {
        int m = matrix[0].length;
        int n = matrix.length - 1;
        int[][] reArr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                reArr[i][j]=matrix[j+1][m-i-1];// 从第二行开始遍历即去掉第一行
            }
        }
        return reArr;
    }
}
# 数组 - 总结


# 1. 数组理论基础


    

  1. 

    数组是存放在 连续内存 空间上的相同类型数据的集合。
    

    2. 

  2. 

    数组可以通过 下标索引 获取数据。（从 0 开始）
    

    3. 

  3. 

    因为数组的在内存空间的地址是连续的，所以我们在 删除 或者 增添 元素的时候，就难免要移动其他元素的地址。
    

    4. 

  4. 

    Java 数组的大小是固定的，数组的元素是不能删的，只能覆盖。
    

    5. 

  5. 

    如果要删除，得转化成集合 list 类型
    

    6. 

  6. 

    而对于二维数组：
    

    7. 



image-20230315204501224


所以二维数据在内存中不是 3*4 的连续地址空间，而是四条连续的地址空间组成！


根据上面的算法练习，总结出以下数组相关的思想方法：


# 2. 二分法


详看第二题：二分查找


二分查找是数组的基本操作，一定要会的。


一般的查找可以采用暴力解法，即逐个遍历。如果算法中需要使用到查找，且该数组又符合有序，且数组无重复元素，（因为一旦有重复元素，使用二分查找返回的元素可能不是唯一的）可以考虑使用二分查找降低时间复杂度。


    

  • 暴力解法时间复杂度：O (n)
    • 

  • 二分法时间复杂度：O (logn)
    • 



注意二分法里的循环不变量原则，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。


区间一般分为两种：左闭右闭 [left,right]，左闭右开 [left,right)


根据区别就有两种写法，像我上边写的就是 左闭右闭[left,right]  的写法。


    

  1. 左闭右闭 [left,right]
    2. 



right=nums.length-1;


while(left<=right)


right=middle-1;


left=middle+1;


image-20230315204526021


    

  1. 左闭右开 [left,right)
    2. 



right=nums.length;


while(left<right)


right=middle;


left=middle+1;


image-20230315204548765


# 3. 双指针法


详细可见：第四题 - 移除元素


双指针法（快慢指针法、首位指针）：很多考察数组、链表、字符串等操作的面试题，都使用双指针法。


    

  • 暴力解法时间复杂度：O (n^2)
    • 

  • 双指针时间复杂度：O (n)
    • 



# 4. 滑动窗口


详细可见：第六题 - 长度最小的子数组


滑动窗口，即不断的调节子序列的起始位置和终止位置（也是双指针），从而得出我们想要的结果。


    

  • 暴力解法时间复杂度：O (n^2)
    • 

  • 滑动窗口时间复杂度：O (n)
    • 



如题目 6，s=7 , 数组是 2，3，1，2，4，3，来看一下查找的过程：


img


当要使用滑动窗口时，我们要考虑：


    

  • 窗口内是什么？
    • 

  • 如何移动窗口的起始位置？
    • 

  • 如何移动窗口的结束位置？
    • 



时间复杂度：O (n)   空间复杂度：O (1)


主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2 × n 也就是 O (n)。


# 5. 模拟行为


详细可见：题目 7、8 - 螺旋矩阵（官方解法）


# 链表 - 理论基础


首先我们要知道，什么是链表？


链表，是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是 数据域 ，一个是 指针域  (存放指向下一个节点的指针)。最后一个节点的指针域指向 null（空指针）


链表的入口节点称为头节点，即 head


image-20230315204744565


优点：不需要使用地址连续的存储单元，插入和删除操作不需要移动元素，只需要修改指针即可。


缺点：失去顺序表可随机存取的优点（数组）


image-20230315204835870


链表的分类:


单链表：就是上面那个


双链表：两个指针，一个指前一个，一个指后一个


!!image-20230315205018607


循环链表：跟单链表的区别就是，最后一个节点的 next 不是指向 null，是指向头节点。就是成一个闭环的。


image-20230315205036099


链表的定义：


我搁 LinkedList 里复制过来的，LinkedList 底层是 双向链表 ，要求会手写


public class Node<E> {
        E item;  // 节点上存储的元素
        Node<E> next;  // 指向后继节点
        Node<E> prev;  // 指向前驱节点
        
        public Node(){}  // 无参
        public Node(Node<E> prev, E element, Node<E> next) {  // 双向链表构造器
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
链表的操作：


删除：


image-20230315205056182


增加：


image-20230315205111115


# 题目 1 移除链表元素 - 简单


给你一个链表的头节点  head  和一个整数  val  ，请你删除链表中所有满足  Node.val == val  的节点，并返回 新的头节点 。


示例 1：


image-20230315205127901


** 输入：**head = [1,2,6,3,4,5,6], val = 6


输出：[1,2,3,4,5]


示例 2：


** 输入：**head = [], val = 1


输出：[]


示例 3：


** 输入：**head = [7,7,7,7], val = 7


输出：[]


救命，我做不出来！感觉就是一个修改指向的问题而已，我搞了一个小时没写出来，要吐了～


偷摸看了下答案，看有用递归的，害，递归我也用的很菜。


硬生生给我做出来了，但是似乎不太优雅：


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head!=null){
            if(head.val==val){
                head=head.next;
            }else{
                break;
            }
        } // 头节点就是要删除的情况
        if(head==null) return head;
        ListNode node=head;
        while(node.next!=null){
            if(node.next.val==val){
                node.next=node.next.next;
            }else{
                node=node.next;
            }
        }
        return head;
    }
}
image-20230315205145307


明天再继续整理吧，头疼……


我的处理方法是，先把头节点是不是也等于 val  的情况先处理了，不设置虚拟头节点


还可以设置一个虚拟的头节点。学到了～～


class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead=new ListNode(-1);// 虚拟的头节点
        dummyHead.next=head;   
        ListNode node=dummyHead;
        while(node.next!=null){
            if(node.next.val==val){
                node.next=node.next.next;
            }else{
                node=node.next;
            }
        }
        return dummyHead.next;
    }
}
不整理官方解析了，只记录自己解法


官方有一个递归的方法，递归一向给我感觉就是很高贵不是一般人用的。


看是能看懂，但是我自己写不出来。


方法一：递归


链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。


对于给定的链表，首先对除了头节点 head  以外的节点进行删除操作，然后判断  head  的节点值是否等于给定的 val 。如果 head  的节点值等于 val ，则  head  需要被删除，因此删除操作后的头节点为  head.next ；如果 head  的节点值不等于 \textit {val} val，则  head  保留，因此删除操作后的头节点还是  head 。上述过程是一个递归的过程。


递归的终止条件是  head  为空，此时直接返回  head 。当  head  不为空时，递归地进行删除操作，然后判断  head  的节点值是否等于  val  并决定是否要删除  head


class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}
# 题目 2  设计链表 - 中等


设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针 / 引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。


在链表类中实现这些功能：


    

  • get(index)：获取链表中第  index  个节点的值。如果索引无效，则返回 - 1。
    • 

  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。 (头插法)
    • 

  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。 (尾插法)
    • 

  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果 index 小于 0，则在头部插入节点。
    • 

  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
    • 



单链表：


public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}
class MyLinkedList {
  int size;
  ListNode head; 
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
  }
 
  public int get(int index) {
    if (index < 0 || index >= size) return -1;
    ListNode curr = head;
    for(int i = 0; i < index + 1; ++i) curr = curr.next;
    return curr.val;
  }
  
  public void addAtHead(int val) {
    addAtIndex(0, val);
  }
  public void addAtTail(int val) {
    addAtIndex(size, val);
  }
 
  public void addAtIndex(int index, int val) {
    if (index > size) return;
    if (index < 0) index = 0;
    ++size;
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;
    ListNode toAdd = new ListNode(val);
    toAdd.next = pred.next;
    pred.next = toAdd;
  }
  public void deleteAtIndex(int index) {
    
    if (index < 0 || index >= size) return;
    size--;
   
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;
    
    pred.next = pred.next.next;
  }
}
# 题目 3  反转链表 - 简单


给你单链表的头节点  head  ，请你反转链表，并返回反转后的链表。


示例 1：


image-20230315205208814


** 输入：**head = [1,2,3,4,5]


输出：[5,4,3,2,1]


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node=null;
        while(head!=null){
            node=addAtHead(node,head.val);
            head=head.next;
        }
        return node;
    }
    // 将 val 头插到 node 链表中去
    public ListNode addAtHead(ListNode node,int val){
        return new ListNode(val,node);
    }
}
image-20230315205229625


简单题重拳出击，中等题跪地求饶🙂


方法二：指针反转


因为新创建一个链表会造成空间浪费，其实反转链表只是指针的方向反转了一下而已。看下面的动图可以使用快慢指针修改结点的下节点。


img


这个是看代码随想录动图才想到的方法，果然我是一个懒得思考的人，做出来之后就不会去想想还有没有其他做法了。如果面试的时候，做出来了，但是人家说，还有更加优化的方法吗？我不就完蛋了？


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        ListNode nextNode=null;
        while(cur!=null){
            nextNode=cur.next;// 记住下一步
            cur.next=pre;// 修改 cur 的指向
            pre=cur;
            cur=nextNode;    
        }
        return pre;
    }
}
# 题目 4 两两交换链表中的节点 - 中等


给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。


示例 1：


!!image-20230315205259032


** 输入：**head = [1,2,3,4]


输出：[2,1,4,3]


示例 2：


** 输入：**head = []


输出：[]


示例 3：


** 输入：**head = [1]


输出：[1]


我第一反应就是用两个指针，一前一后，交换数值，然后再继续往下：


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null) return head;
        ListNode pre=head;
        ListNode nxt=head.next;
        while(nxt!=null){
            int tmp=pre.val;
            pre.val=nxt.val;
            nxt.val=tmp;
            if(nxt.next==null) break;
            pre=nxt.next;
            nxt=nxt.next.next;
        }
        return head;
    }
}
image-20230315205320315


复杂度分析：


    

  • 时间复杂度 ：O（n）
    • 

  • 空间复杂度 ：O（1）
    • 



第一反应一般都是模拟行为的一种方法，也是最直观的方法，所以我还是要多思考，多想想有没有其他方法。递归行不行呢？用递归写了，但是不对，果然我还是对递归不够理解。


看了下官方对递归的写法，我感觉那些人脑子真好用。


class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
# 题目 5 删除链表的倒数第 N 个结点 - 中等


给你一个链表，删除链表的倒数第 n  个结点，并且返回链表的头结点。


示例 1：


image-20230315205334474


** 输入：**head = [1,2,3,4,5], n = 2


输出：[1,2,3,5]


示例 2：


** 输入：**head = [1], n = 1


输出：[]


示例 3：


** 输入：**head = [1,2], n = 1


输出：[1]


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return head;
        }
        if(head.next==null && n==1){
            return null;
        }
        
        // 算总数 m
        int m=1;
        ListNode sumNode=head.next;
        while(sumNode!=null){
            m++;
            sumNode=sumNode.next;
        }
        if(m==n){
           return head.next; 
        } 
        // 删除第 m-n+1 位的数
        if(m>n){
            ListNode deleteNode=head;
            ListNode beforeNode=new ListNode(-1);
            beforeNode.next=deleteNode;
            for(int i=1;i<=(m-n);i++){
                beforeNode=beforeNode.next;
                deleteNode=deleteNode.next;
            }
            // 删除：
            beforeNode.next=deleteNode.next;
            
        }
        return head;
          
    }
}

      

          
      

  


   


    

  
    
      
    
    更新于
    
  
  
      
        
      
      阅读次数
      
      次
  



      


  
  
请我喝[茶]~(￣▽￣)~*

  

      
      

        Dabing-He 微信支付
        
微信支付