leetcode算法

蹉跎良久，终于开始刷题

2023年，研一上修了高级算法与设计，对贪心，分治，动态规划，网络流，np问题，npc问题（规约），近似算法有了一定的了解。

以上只是算法层面，真正实际代码层面，并没有经过一个完整的过程。期间刷过一段时间，但后面又耽搁了。还有一年的时间，将时间段定在寒假结束之前，看这段时间能不能按照代码随想录的顺序完整地刷一遍算法，然后将过程心得记录下来，不管题目是多简单或者多难，将方法，思想，注释完善下。

一、数组

引入：

二维数组在内存的空间地址是连续的么？

不同的编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的，下面是代码随想录提供的测试实验：

#include <iostream>

using namespace std;

void test_arr() {
    int array[2][3] = {
        {0, 1, 2},
        {3, 4, 5}
    };

    // 打印每个元素的地址
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
    return 0;
}

运行结果如下：

可以看出地址是16进制，并且相邻两个数组元素相差4个字节（int占用4个字节）

题外话：

Q：一个字等于多少个字节？

A：与系统硬件（总线、cpu命令字位数等）有关，不应该毫无前提地说一个字等于多少位。

正确的说法：

①：1字节（byte） = 8位（bit）

②：在16位的系统中（比如8086微机） 1字 （word）= 2字节（byte）= 16（bit）

​ 在32位的系统中（比如win32） 1字（word）= 4字节（byte）=32（bit）

​ 在64位的系统中（比如win64）1字（word）= 8字节（byte）=64（bit）

JAVA:

Java 与 C++ 在内存管理和对程序员的暴露程度上的不同。在 Java 中，指针的概念被隐藏，而且程序员通常无法直接访问或操作对象的内存地址,寻址操作完全交给虚拟机。这是 Java 设计的一部分，旨在提供更安全的编程环境。

public class test1 {
    public static void main(String[] args) {
        test_arr();
    }

    public static void test_arr() {
        int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9, 9, 9}};

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();  // 新的一行
            System.out.print(arr[i] + " ");
            System.out.println();  // 新的一行
        }
    }
}

运行结果如下：

当尝试打印一个数组对象（如 arr[0]），Java 默认打印对象的引用地址，通常是一个哈希码或者一种内部表示，而不是内存中的具体地址。这是因为 Java 的安全性和抽象层次，它隐藏了底层的内存管理细节。

如果想查看数组中各个元素的值，需要遍历数组并打印每个元素，而不是直接打印数组对象本身。

二、数组Leetcode题

1. 二分查找

https://leetcode.cn/problems/search-insert-position/

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

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

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

有些公司的算法题可能会是acm输入输出模式的，现提供手动输入输出版本如下：

import java.util.ArrayList;
import java.util.Scanner;

public class Solution704 {
    public int search(int[] nums, int target) {
        if (target < nums[0]||target > nums[nums.length-1]){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while (left<=right){
            int mid = left + ((right-left)>>2);
            if (nums[mid]>target){
                right = mid-1;
            }
            else if(nums[mid]<target){
                left = mid+1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入数组的长度:");
        int n = scanner.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入 " + n + " 个升序整数:");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        System.out.println("请输入目标值:");
        int target = scanner.nextInt();
        Solution704 solution = new Solution704();
        int result = solution.search(nums, target);
        if (result != -1) {
            System.out.println("元素 " + target + " 的索引为: " + result);
        } else {
            System.out.println("元素 " + target + " 不在数组中");
        }
        scanner.close();
    }
}

如果不想要限制输入数据长度，可以采用可变数组的方法：

import java.util.ArrayList;
import java.util.Scanner;

public class BinarySearchWithArrayList {
    public static int search(ArrayList<Integer> nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums.get(mid) == target) {
                return mid;
            } else if (nums.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> nums = new ArrayList<>();

        System.out.println("请输入升序整数（输入非数字字符结束输入）:");

        // 循环读取整数，直到非数字输入
        while (scanner.hasNextInt()) {
            nums.add(scanner.nextInt());
        }

        System.out.println("请输入目标值:");
        scanner.nextLine();  // 清除输入流中的非数字字符
        int target = scanner.nextInt();

        int result = search(nums, target);
        if (result != -1) {
            System.out.println("元素 " + target + " 的索引为: " + result);
        } else {
            System.out.println("元素 " + target + " 不在数组中");
        }

        scanner.close();
    }
}

相似题目：

• 35.搜索插入位置(opens new window)
• 34.在排序数组中查找元素的第一个和最后一个位置(opens new window)
• 69.x 的平方根(opens new window)
• 367.有效的完全平方数

35.搜索插入位置

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

```

**367.有效的完全平方数**

给你一个正整数 `num` 。如果 `num` 是一个完全平方数，则返回 `true` ，否则返回 `false` 。

**完全平方数** 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 `sqrt` 。

**示例 1：**

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

**示例 2：**

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

**提示：**

- `1 <= num <= 2^31 - 1`

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

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

    public static void main(String[] args) {
        Solution367 solution = new Solution367();
        boolean result = solution.isPerfectSquare(808201);
        System.out.println(result);
    }
}

int 类型在 Java 中是一个 32 位的有符号整数类型。其取值范围从 -2,147,483,648（即 -2^31）到 2,147,483,647（即 2^31 - 1）。这意味着 int 类型可以存储的最大正整数是 2,147,483,647。

虽然 int 类型的最大值是 2,147,483,647，这确实足够大，但是代码中，当计算 mid * mid 时，即使 mid 本身是一个有效的 int 值，乘积仍然可能超过 int 类型的最大值。

举个例子，假设 mid 是 50,000，那么 mid * mid 将是 2,500,000,000，这个值已经超出了 int 类型的最大范围（2,147,483,647）。这就是为什么在计算平方时可能发生溢出的原因。

为了避免这个问题，我们需要使用一个更大的数据类型来存储平方的结果。在 Java 中，long 类型是一个 64 位的整数，它的最大值远大于 int，所以使用 long 类型可以防止在计算大数平方时发生溢出。

二、移除元素

27. 移除元素

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 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,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

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

在使用双指针方法移除数组中的特定元素后，慢指针（在这个例子中是指针 i）之后的元素实际上是不需要关心的。这是因为函数返回的新长度（i 的值）标志着数组有效部分的结束。在这个新长度之后的元素，即便它们仍然存储在数组中，也被视为“无效”或“不可见”。

重要的是要理解，数组的物理大小（即数组能够容纳的元素数量）并没有改变，因为Java数组的大小在创建后是固定的。这个方法只是改变了数组的“有效”大小。

例如，如果原数组是 [3, 2, 2, 3]，val 是 3，那么在调用 removeElement 方法后，数组可能看起来像 [2, 2, 2, 3]，但方法返回的长度是 2。因此，尽管物理上数组中还有四个元素，只有前两个元素（[2, 2]）是有效的或被认为是数组的新内容。

在实际应用中，通常只关心数组的这个“有效”部分。如果需要在某些情况下消除数组剩余部分的混淆，可以选择将其余部分填充为一个特定的值（如零或某个不可能出现的值），但这通常是不必要的。

相似题目：

• 26.删除排序数组中的重复项(opens new window)
• 283.移动零(opens new window)
• 844.比较含退格的字符串(opens new window)
• 977.有序数组的平方

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

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

class Solution {
    public int removeDuplicates(int[] nums) {
        int shortIndex = 0;
        for (int longIndex = 0;longIndex < nums.length;longIndex++){
            if(nums[longIndex]!=nums[shortIndex]){
                shortIndex++;
                nums[shortIndex]=nums[longIndex];
            }
        }
        return shortIndex+1;
    }
}

通过快慢指针的方法，快指针找到第一个与慢指针指向的不同元素，替换慢指针的下一个元素，最后返回慢指针加1；

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

class Solution {
    public void moveZeroes(int[] nums) {
        int slowIndex = 0;
        for (int longIndex = 0 ; longIndex < nums.length; longIndex++){
            if(nums[longIndex]!=0){
                nums[slowIndex]=nums[longIndex];
                slowIndex++;
            }
        }
        while(slowIndex<nums.length){
            nums[slowIndex]=0;
            slowIndex++;
        }
    }
}

844.比较含退格的字符串(opens new window)

三、有序数组的平方

977.有序数组的平方

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

class Solution {
    public int[] sortedSquares(int[] nums) {
        int fastIndex = nums.length-1;
        int slowIndex = 0;
        int [] result = new int [nums.length];
        int n = nums.length-1;
        while (fastIndex >= slowIndex){
            if(nums[fastIndex]*nums[fastIndex]>=nums[slowIndex]*nums[slowIndex]){
                result[n--]=nums[fastIndex]*nums[fastIndex];
                fastIndex--;
            }else{
                result[n--]=nums[slowIndex]*nums[slowIndex];
                slowIndex++;
            }
        }
        return result;
    }
}

题意中的非递减顺序排列的数组是解题要点，由于由正负数，所以两端的平方肯定有最大数；

四、长度最小的子数组

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

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

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

方法一：o(n)时间复杂度，滑动窗口（快慢指针方法）
    class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int shortIndex = 0;
        int sum = 0;
        int tag = 0;
        for (int longIndex = 0;longIndex < nums.length;longIndex++ ){
            sum += nums[longIndex];
            while(sum>=target){
                sum-=nums[shortIndex];
                // tag = longIndex-shortIndex+1;
                // if (tag<=result){
                //     result = longIndex-shortIndex+1;
                // }
                result = Math.min(result,longIndex-shortIndex+1);
                shortIndex++;
            }
        }
        return result==Integer.MAX_VALUE ? 0 :result;
    }
}

方法二：o(nlogn)的fang'f

904.水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int maxFruits = 0, left = 0;

        for (int right = 0; right < fruits.length; right++) {
            countMap.put(fruits[right], countMap.getOrDefault(fruits[right], 0) + 1);

            while (countMap.size() > 2) {
                countMap.put(fruits[left], countMap.get(fruits[left]) - 1);
                if (countMap.get(fruits[left]) == 0) {
                    countMap.remove(fruits[left]);
                }
                left++;
            }

            maxFruits = Math.max(maxFruits, right - left + 1);
        }

        return maxFruits;
    }
}

76.最小覆盖子串(opens new window)

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

```





#### 五、螺旋矩阵II

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

**示例 1：**

![img](https://shjpic.oss-cn-chengdu.aliyuncs.com/spiraln.jpg)

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

**示例 2：**

输入：n = 1
输出：[[1]]

**提示：**

- `1 <= n <= 20`

第一种方法：模拟

```java
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int num = 1;
        int startRow = 0, endRow = n - 1;
        int startCol = 0, endCol = n - 1;

        while (startRow <= endRow && startCol <= endCol) {
            // 从左到右填充顶部行
            for (int col = startCol; col <= endCol; col++) {
                matrix[startRow][col] = num++;
            }
            startRow++;

            // 从上到下填充右侧列
            for (int row = startRow; row <= endRow; row++) {
                matrix[row][endCol] = num++;
            }
            endCol--;

            // 从右到左填充底部行
            if (startRow <= endRow) {
                for (int col = endCol; col >= startCol; col--) {
                    matrix[endRow][col] = num++;
                }
                endRow--;
            }

            // 从下到上填充左侧列
            if (startCol <= endCol) {
                for (int row = endRow; row >= startRow; row--) {
                    matrix[row][startCol] = num++;
                }
                startCol++;
            }
        }
        return matrix;
    }
}

相似题目：

• 54.螺旋矩阵
• 剑指Offer 29.顺时针打印矩阵

54.螺旋矩阵

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

示例 1：

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

示例 2：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int startRow = 0, endRow = matrix.length-1;
        int startCol = 0, endCol = matrix[0].length-1;
        while (startRow <= endRow && startCol <= endCol ){

            for (int col = startCol; col <= endCol; col++){
                result.add(matrix[startRow][col]);
            }
            startRow++;

            for (int row = startRow; row <= endRow; row++){
                result.add(matrix[row][endCol]);
            }
            endCol--;

            if(startCol<=endCol && startRow<=endRow){
                for (int col = endCol;col >= startCol;col--){
                    result.add(matrix[endRow][col]);
                }
                endRow--;
            }

            if(startRow<=endRow && startCol<=endCol){
                for (int row = endRow;row >=startRow;row--){
                    result.add(matrix[row][startCol]);
                }
                startCol++;
            }
        }
        return result;
    }
}

剑指Offer 29.顺时针打印矩阵

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

示例 1：

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

示例 2：

输入：array  = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

限制：

• 0 <= array.length <= 100
• 0 <= array[i].length <= 100

class Solution {
    public int[] spiralArray(int[][] array) {
        if (array.length==0){
            return new int[0];
        }
        int [] result = new int[array.length*array[0].length];
        int num = 0;
        int startRow = 0, endRow = array.length-1;
        int startCol = 0, endCol = array[0].length-1;
        while (startRow<=endRow && startCol<=endCol){
            for(int col = startCol ; col<=endCol; col++){
                result[num++]=array[startRow][col];
            }
            startRow++;
            for(int row = startRow; row<=endRow; row++){
                result[num++]=array[row][endCol];
            }
            endCol--;
            if(startCol<=endCol && startRow<=endRow){
                for(int col = endCol;col>=startCol;col--){
                    result[num++]= array[endRow][col];
                }
                endRow--;
            }
            if(startRow<=endRow && startCol<=endCol){
                for(int row = endRow;row>=startRow;row--){
                    result[num++]= array[row][startCol];
                }
                startCol++;
            }
        }
        return result;
    }
}

六、总结篇