发表于 | 分类于 |
字数统计: 132

如何获取Resources目录下的文件

方式一

1
2
3
4
5
6
public void function(String fileName) throws IOException {
    String path = this.getClass().getClassLoader().getResource(fileName).getPath();
    System.out.println(path);
    String filePath = URLDecoder.decode(path, "UTF-8");//如果路径中带有中文会被URLEncoder,因此这里需要解码
    System.out.println(filePath);
}

方式二

1
2
3
public void function(String fileName) throws IOException {
    InputStream in = this.getClass().getClassLoader().getResourceAsStream(fileName);
}

方式三

1
2
3
public void function5(String fileName) throws IOException {
    InputStream in = this.getClass().getResourceAsStream(fileName);
}

方式四

这种方式要在SpringBoot环境下

1
2
3
public void function6(String fileName) throws IOException {
    InputStream inputStream = new ClassPathResource(fileName).getInputStream();
}

发表于 | 分类于 ， |
字数统计: 604

单调队列

这个技巧和单调栈一样，运用的场景比较少

它本质也是一个队列，只不过是运用了一些巧妙的逻辑

在内部维护了一个递增或者递减的序列

然后还保持了先进先出的特性

下面直接看题

滑动窗口最大值

这道题的描述不就是使用滑动窗口技巧吗，我们知道在滑动窗口技巧中

最重要的就是清楚在何时扩大窗口，在何时缩小窗口

但是这道题中，我没法根据出窗口的那个元素来判断是否需要更新最大值，如何更新

如果出窗口的就是最大值，那我就需要重新遍历一遍窗口找到最值，这样的时间复杂度是较高的

所以就需要使用到单调队列的技巧了

这里我们自己维护一个单调队列的类

1
2
3
4
5
6
7
8
public class MonotonousQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前单调队列中的最大值
    int max();
    // 队头元素如果是n的话就删除它
    void pop(int n);
}

在队尾添加元素的时候，需要将所有队尾元素比它小的元素都出队，直到遇到第一个比它大的元素或者队列为空的时候

最大值就是队列的队首元素

下面看这道题的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonousQueue window = new MonotonousQueue();
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 前k-1个元素直接入队
            if (i < k - 1){
                window.push(nums[i]);
            }else {
                // 第k个元素入队
                window.push(nums[i]);
                // 将窗口中的最大值放入结果集
                res.add(window.max());
                // 将窗口第一个元素出队
                window.pop(nums[i-k+1]);
            }
        }
        // 将res转换为数组返回
        int[] r = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }
}
class MonotonousQueue {
    LinkedList<Integer> queue = new LinkedList<>();
    // 在队尾添加元素 n
    void push(int n){
        // 维护递减的序列
        while (!queue.isEmpty()&&n>queue.getLast()){
            queue.removeLast();
        }
        queue.addLast(n);
    }
    // 返回当前单调队列中的最大值
    int max(){
        return queue.getFirst();
    }
    // 队头元素如果是n的话就删除它
    void pop(int n){
        if (queue.getFirst()==n){
            queue.removeFirst();
        }
    }
}

发表于 | 分类于 ， |
字数统计: 1k

单调栈

单调栈就是一种栈，只不过用了一种逻辑在内部维护了所有的栈内元素递增或者递减的序列

这种技巧用的不多，一般就是以下讲到的典型的题目

先来体会一下单调栈

技巧阐述

我们以题入技

题目如下

1
2
3
4
# 输入一个数组nums，然后返回一个等长的结果数组，结果数组中对应索引存储着nums数组中该索引后第一个比它大的元素，如果没有更大的元素，就存 -1。
例：
输入：[2,6,3,7,4]
输出：[6,7,7,-1,-1]

函数签名如下：int[] nextBigerElement(int[] nums);

题目很好理解，用暴力解的话就是在每一个元素向后面找第一个比它大的元素，时间复杂度是O(n^2)

现在我们使用单调栈的技巧来解决这道题

nums = [2,6,3,7,4]

先来看这张图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int[] nextBigerElement(int[] nums) {
    int[] res = new int[nums.length];
    Stack<Integer> stack = new Stack<>();
    // 倒着遍历
    for (int i = nums.length - 1; i >= 0; i--) {
        // 如果栈顶元素比nums[i]小，则出栈，直到栈顶元素比nums[i]大或者栈为空
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return res;
}

496.下一个更大元素Ⅰ

题目意思有点绕，这里解释一下。

首先，nums1是nums2的子集

其次，题目要求返回的是nums1的每一个元素在nums2中的位置后的比它大的元素的值

那么题目意思明白了之后，这道题就很简单了

我只需要对nums2的每一个元素找到其后面第一个比它大的元素的数组

然后使用一个hash表存起来，再遍历nums1，用nums1[1]在map中取得结果将其放入结果集中，最后返回

下面看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    int[] nextBigerElement(int[] nums){
        int[] res = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = nums.length-1; i >= 0; i--) {
            // 如果栈顶元素比nums[i]小，则出栈，直到栈顶元素比nums[i]大或者栈为空
            while (!stack.isEmpty()&&stack.peek()<=nums[i]){
                stack.pop();
            }
            res[i] = stack.isEmpty()?-1:stack.peek();
            stack.push(nums[i]);
        }
        return res;
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = nextBigerElement(nums2);
        // key是nums的值，value是其后面第一个比它大的数
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[i],res[i]);
        }
        int[] r = new int[nums1.length];
        for (int i = 0; i < r.length; i++) {
            r[i] = map.get(nums1[i]);
        }
        return r;
    }
}

503.下一个更大元素 II

这一题是循环数组，很简单的一个技巧，那就是将数组复制一遍放到原数组后面，这样不就实现了循环数组找到下一个元素了吗

但是这里我们不新建一个两倍长的数组然后拷贝数组

这里我们使用%符号来巧妙地完成逻辑上扩一倍地效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] nextGreaterElements(int[] nums) {
    int len = nums.length;
    int[] res = new int[len];
    Stack<Integer> stack = new Stack<>();
    // 一样的从最后一个元素开始
    for (int i = len * 2 - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        // 这里的索引都需要对len取余
        res[i % len] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i % len]);
    }
    return res;
}

739.每日温度

这道题目其实和我们一开始的技巧阐述的思想是一样的

但是这里返回的数组中存储的是索引而已

这道题直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = temperatures.length - 1; i >= 0; i--) {
            // 如果栈顶元素比当前元素小，则一直出栈，直到出现第一个比它大的数或者栈空
            while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
                stack.pop();
            }
            // 注意:题目需要的是几天后，所以是stack.peek()-i而不是stack.peek();
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return res;
    }
}

发表于 | 分类于 ， |
字数统计: 1.4k

区间问题

区间问题是什么，其实就是给了你一组区间，比如[[2,6],[9,13],[6,8],[1,4],[3,5],[9,11]]

然后让你有多少区间是被覆盖的，合并所有可以合并的区间等等操作

这种题目就两个步骤

第一步排序，按照左边界升序排序，右边界降序排序

第二步画图，画出两个边界之间的关系的所有可能的情况

1288.删除被覆盖的区间

然后我们按照以上两个步骤来解决这道题

排序

以[[2,6],[9,13],[6,8],[1,4],[3,5],[9,11]]作为测试数据

将其按照左边界升序排序，右边界降序排序后

变为[[1,4],[2,6],[3,5],[6,8],[9,13],[9,11]]

用图像来表示就是这样

画图

然后我们来画图将所有出现的区间关系画出来

​ 其中①②③这三种情况都是属于覆盖的情况，所以我只要将这些情况记录到res中，最后intervals.length-res就是需要删除的被覆盖的区间个数

​ ④⑦都是属于区间相交的情况

​ ⑤⑥⑧⑨属于区间交错的情况

心中有图，代码我有！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // 按照左边界升序排序，有边界降序排序
        Arrays.sort(intervals,(a,b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
        // 记录被覆盖的区间个数
        int res = 0;
        // 记录左边界
        int left = intervals[0][0];
        // 记录右边界
        int right = intervals[0][1];
        // 从第二组边界开始遍历
        for(int i = 1; i < intervals.length;i++){
            // 拿到这组边界
            int[] interval = intervals[i];
            int a1 = interval[0];
            int b1 = interval[1];
            // 如果这组的边界的左边界大于等于left并且有边界小于right，则说明这组边界被[left,right]覆盖，res自增
            if (a1 >= left && b1 <= right) {
                res++;
            }
            // 如果这组边界的左边界大于等于right说明两者相错开，更新left和right
            if (a1 >= right) {
                left = a1;
                right = b1;
            }
            // 如果right在这组边界的中间，说明两组边界🍌相交吗，更新right
            // 这一步更新right其实就是合并这两个区间
            if (right >= a1 && right <= b1) {
                right = b1;
            }
        }
        return intervals.length-res;
    }
}

56.合并区间

这一题也是按照上述两个步骤做就行了，这里直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[][] merge(int[][] intervals) {
        // 排序
        Arrays.sort(intervals,(a,b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
        // 因为不确定最后会保留几个区间，所以这里使用List来暂时保存结果
        List<int[]> res = new LinkedList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1;i < intervals.length;i++){
            int[] interval = intervals[i];
            int a1 = interval[0];
            int b1 = interval[1];
            // 如果区间完全相错，直接将[left,right]区间加入结果集中，更新left和right
            if(a1>right){
                res.add(new int[]{left,right});
                left = a1;
                right = b1;
                continue;
            }
            // 如果这个区间被[left,right]区间覆盖，不用管
            if(a1>=left&&b1<=right){
                continue;
            }
            // 这个区间和[left,right]区间相交，更新right为b1
            if(right>=a1&&right<b1){
                right = b1;
            }
        }
        // 将最后一个区间加入结果集
        res.add(new int[]{left,right});
        // 转换list为二维矩阵返回
        int[][] r = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }
}

或者使用以下的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
        List<int[]> res = new LinkedList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        // 手动控制i的增长
        for(int i = 0;i < intervals.length;){
            int[] interval = intervals[i];
            int a1 = interval[0];
            int b1 = interval[1];
            // 如果相交或者覆盖
            if (a1>=left&&a1<=right){
                right = Math.max(right,b1);
                i++;
                // 当i小于intervals.length
                // 左边界在[left,right]之间
                // 则一直往后找最大的right
                while (i < intervals.length){
                    int[] temp = intervals[i];
                    if (temp[0] >= left && temp[0] <= right) {
                        right = Math.max(right,temp[1]);
                        i++;
                    }else {
                        break;
                    }
                }
                res.add(new int[]{left,right});
                // 如果找到了最后一个则直接退出循环
                if (i==intervals.length){
                    break;
                }
                left = intervals[i][0];
                right = intervals[i][1];
            }else {
                // 区间相错了，直接将区间[left,right]加入集合然后i++，更新jleft和right
                res.add(new int[]{left,right});
                left = a1;
                right = b1;
                i++;
            }
        }
        int[][] r = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }
}

986.区间列表的交集

这道题和上述思路一致的，只需要将交集的部分放入res中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> res = new LinkedList<>();
        int firstIndex = 0;
        int secondIndex = 0;
        while(firstIndex<firstList.length&&secondIndex<secondList.length){
            int[] firstInterval = firstList[firstIndex];
            int[] secondInterval = secondList[secondIndex];
            // 相交
            if(firstInterval[1]>=secondInterval[0]&&firstInterval[0]<=secondInterval[1]){
                // 取两个左边最大的作为交集的左边界，取两个右边界最小的作为交集的右边界
                res.add(new int[]{
                    Math.max(secondInterval[0],firstInterval[0]),
                    Math.min(firstInterval[1],secondInterval[1])
                });
            }
            // 如果第二个区间的右边界比第一个区间的右边界大
            // 则firstIndex自增，因为第一个区间的右边界到第二个区间的左边界有可能被firstList的下一个区间相交的
            if(secondInterval[1]>firstInterval[1]){
                firstIndex++;
            }else {
                secondIndex++;
            }
        }
        int[][] r = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }
}

发表于 | 分类于 ， |
字数统计: 211

子序列问题

子序列问题是很常见的一类问题，与之类似的还有子串问题，这两者有什么区别呢？

子序列是不需要连续的，但是字串是需要连续的。

"abcd"

子序列是["a","b","c","d","ab","ac","ad","bc","bd","cd"]

字串是["a","b","c","d","ab","bc","cd"]

观察一下两者之间的区别。

这类子序列问题一般使用动态规划来做，一般有以下两种思路

一维dp数组

1
2
# int[] dp = new int[str.length()];
dp[i]的意思是在字符串str[0,i]中，以str[i]结尾的目标子序列的长度是dp[i]

栗题：力扣300最长递增子序列

发表于 | 分类于 ， |
字数统计: 512

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

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

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

Related Topics

  • 数组
  • 分治
  • 动态规划

暴力递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(maxSubArray(nums, i), res);
        }
        return res;
    }

    // 函数i当以：返回以nums[index]结尾的连续子数组的最大和
    private int maxSubArray(int[] nums, int index) {
        if (index == 0) {
            return nums[0];
        }
        int max = nums[index];
        max = Math.max(maxSubArray(nums, index - 1) + nums[index], max);
        return max;
    }
}

带备忘录的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxSubArray(int[] nums) {
        int[] meno = new int[nums.length];
        System.arraycopy(nums, 0, meno, 0, nums.length);
        maxSubArray(nums, nums.length - 1, meno);
        int res = Integer.MIN_VALUE;
        for (int t : meno) {
            res = Math.max(res, t);
        }
        return res;
    }

    // 函数定义：返回以nums[index]结尾的连续子数组的最大和
    private int maxSubArray(int[] nums, int index, int[] meno) {
        if (index == 0) {
            return nums[0];
        }
        if (meno[index] != nums[index]) {
            return meno[index];
        }
        int max = nums[index];
        max = Math.max(maxSubArray(nums, index - 1, meno) + nums[index], max);
        meno[index] = max;
        return max;
    }
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxSubArray(int[] nums) {
        // dp[i]是nums的[0,i]形成的最大子数组的和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(
                    // i不加入nums的[0,i-1]形成的子数组
                    nums[i],
                    // i加入nums的[0,i-1]形成的子数组
                    dp[i - 1] + nums[i]
            );
        }
        // 取最大值
        int res = Integer.MIN_VALUE;
        for (int t : dp) {
            res = Math.max(res, t);
        }
        return res;
    }
}

发表于 | 分类于 ， |
字数统计: 2.5k

遍历二维矩阵的各种花样

PS：干货很多，建议分多次食用

常规遍历

1
# 输出以下序列: [1 2 3 4...15 16]

这个就是按行遍历即可

示例代码

1
2
3
4
5
6
int len = matrix.length;
for (int i = 0; i < len; i++) {
    for (int j = 0; j < len; j++) {
        System.out.print(matrix[i][j]+" ");
    }
}

旋转遍历

PS：本遍历方法使用生成以下矩阵来讲述，生成会了，遍历自然也会了

示意图

遍历思路

1
2
3
4
5
# [0,0] [0,1] [0,2] [0,3]	👉向右
# [0,4] [1,4] [2,4] [3,4]	👇向下
# [4,4] [4,3] [4,2] [4,1]	👆向上
# [4,0] [3,0] [2,0]	[1,0]	👈向左
# ......

圈圈法

第一个思路就是一圈一圈的遍历

将每一个圈拆为四个部分

第一个循环用来生成水平向左的数据

第二个循环用来生成垂直向下的数据

第三个循环用来生成水平向右的数据

第四个循环用来生成垂直向上的数据

流程图

粉红色的是标注为每次大循环的开始处

PS：图片很多，过程很详细

示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int[][] rotateNumber(int n) {
    int[][] matrix = new int[n][n];
    int counter = 1;
    // n / 2即这个矩阵有几个圈
    for (int i = 0; i < n / 2; i++) {
        // end即本次这个圈的宽-1
        int end = n - i - 1;
        // →
        for (int j = i; j < end; j++) {
            matrix[i][j] = counter++;
        }
        // ↓
        for (int j = i; j < end; j++) {
            matrix[j][end] = counter++;
        }
        // ←
        for (int j = end; j > i; j--) {
            matrix[end][j] = counter++;
        }
        // ↑
        for (int j = end; j > i; j--) {
            matrix[j][i] = counter++;
        }
    }
    // 如果是奇数，单独处理中间那一格数据
    if (n % 2 != 0) {
        matrix[n / 2][n / 2] = n * n;
    }
    return matrix;
}

横平竖直法（推荐）

这种方法是通过四个边界来辅助生成矩阵

四个边界的示意图

示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public int[][] rotateNumber(int n){
    // 用来存放生成的旋转数字矩阵
    int[][] matrix = new int[n][n];
    // 计数器
    int counter = 1;
    // 上边界
    int up = 0;
    // 下边界
    int down = n-1;
    // 左边界
    int left = 0;
    // 右边界
    int right = n-1;
    // 当 counter 比 n * n 小就一直循环
    while (counter <= n * n) {
        // 遍历上边界的那一行
        for (int j = left; j <= right; j++) {
            matrix[up][j] = counter++;
        }
        // 上边界向下移动一行
        up++;
        // 遍历右边界的那一行
        for (int i = up; i <= down; i++) {
            matrix[i][right] = counter++;
        }
        // 右边界向左移动一行
        right--;
        // 遍历下边界的那一行
        for (int j = right; j >= left; j--) {
            matrix[down][j] = counter++;
        }
        // 下边界向上移动一行
        down--;
        // 遍历左边界的那一行
        for (int i = down; i >= up; i--) {
            matrix[i][left] = counter++;
        }
        // 左边界向右移动那一行
        left++;
    }
    // 返回结果数组
    return matrix;
}

斜遍历

1
# 输出所有由左上向右下方向的对角线: [13 9 14 5 10 15 1 6 11 16 2 7 12 3 8 4]

偏移X法

和往常一样遍历第一行，[0,0] [0,1] [0,2] [0,3] [0,4]

可以发现中间那个对角线是这一行向下偏移的结果，但是不同的位置在 X 方向上的偏移量是不一样的

遍历第二行[1,0] [1,1] [1,2] [1,3] [1,4]

可以看到和刚刚第一行一样，每一列向下偏移一定量就可以得到主对角线下面的那个对角线了

（这里先不要管越界的问题，先把思路理清楚，再在代码里面解决越界问题）

先写出遍历每一行的初始代码，然后我们在这个上面改造

1
2
3
4
5
for (int i = 0; i < len; i++) {
    for (int j = 0; j < len; j++) {
        System.out.println(matrix[i][j]);
    }
}

在遍历每一行的情况，向下偏移就是对角线了

每一列的偏移量都是不一样的，接下来要解决的就是如何算出每一列的偏移量

经过观察可以发现，当前这一列的偏移量就是当前的列值，那么就好办了直接用j就可以了

1
2
3
4
5
for (int i = 0; i < len; i++) {
    for (int j = 0; j < len; j++) {
        System.out.println(matrix[i + j][j]);
    }
}

现在还有一个问题，就是得到的对角线是部分不合法的，那么接下来就是如何截取合法的对角线部分

因为对角线是由每一行向下偏移而来，对角线越界的根本原因是每一行遍历多了

那么只要逐渐减少每一行的遍历长度即可，每一行少遍历 i 的长度即可

1
2
3
4
5
for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i; j++) {
        System.out.println(matrix[i + j][j]);
    }
}
完整示例代码

PS：注意右上角

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = len - 1; i >= 0; i--) {
    for (int j = 0; j < len - i; j++) {
        System.out.println(matrix[i + j][j]);
    }
}
for (int i = len - 2; i >= 0; i--) {
    for (int j = len - 1 - i; j < len; j++) {
        // 偏移量
        int offset = len - 1 - j;
        System.out.println(matrix[i - offset][j]);
    }
}

偏移Y法

这个方法和偏移 X 法有异曲同工之妙

只不过从遍历每一行变成了遍历每一列

和刚刚一样，先写出遍历每一列

1
2
3
4
5
for (int j = 0; j < len; j++) {
    for (int i = 0; i < len; i++) {
        System.out.println(matrix[i][j]);
    }
}

然后向右边偏移

1
2
3
4
5
for (int j = 0; j < len; j++) {
    for (int i = 0; i < len; i++) {
        System.out.println(matrix[i][j + i]);
    }
}

对角线不合法，截取合法部分

1
2
3
4
5
for (int j = 0; j < len; j++) {
    for (int i = 0; i < len - j; i++) {
        System.out.println(matrix[i][j + i]);
    }
}
完整示例代码

PS：注意左下角

1
2
3
4
5
6
7
8
9
10
11
for (int j = 0; j < len; j++) {
    for (int i = len - 1 - j; i < len; i++) {
        int offset = len - 1 - i;
        System.out.println(matrix[i][j - offset]);
    }
}
for (int j = 1; j < len; j++) {
    for (int i = 0; i < len - j; i++) {
        System.out.println(matrix[i][i + j]);
    }
}

偏移对角线法（推荐）

可以发现偏移 X 法和偏移 Y 法都比较麻烦

所以我比较推荐这种方法，根据对角线来做偏移就会简单很多

从左上顶角到右下顶角的那条对角线如下[0,0] [1,1] [2,2] [3,3]

@表示越界舍弃

整体往下偏移 1 位，就是[1,0] [2,1] [3,2] [4,3](@)

整体往下偏移 2 位，就是[2,0] [3,1] [4,2](@) [5,3](@)

整体往下偏移 3 位，就是[3,0] [4,1] [5,2](@) [6,3](@)

整体往上偏移 1 位，就是[-1,0](@) [0,1] [1,2] [2,3]

整体往上偏移 2 位，就是[-2,0](@) [-1,1](@) [-1,0][0,2] [1,3]

整体往上偏移 3 位，就是[-3,0](@) [-2,1](@) [-1,2](@) [0,3]

如何解决越界

既然完整的对角线偏移会出现越界，那就偏移部分的对角线不就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int len = matrix.length;
// 输出部分对角线，从完整开始逐渐变短
for (int offset = 0; offset < len; offset++) {
    for (int i = 0; i < len - offset; i++) {
        System.out.println(matrix[i][i]);
    }
}
// 这时候输出的依次是
// [0,0] [1,1] [2,2] [3,3]	(offset=0)
// [0,0] [1,1] [2,2]		(offset=1)
// [0,0] [1,1]				(offset=2)
// [0,0]					(offset=3)
// 那么只需要根据部分的对角线向下偏移即可
for (int offset = 0; offset < len; offset++) {
    for (int i = 0; i < len - offset; i++) {
        System.out.println(matrix[i + offset][i]);
    }
}
// 这样的输出结果就是
// [0,0] [1,1] [2,2] [3,3]	(offset=0)
// [1,0] [2,1] [3,2]		(offset=1)
// [2,0] [3,1]				(offset=2)
// [3,0]					(offset=3)

在理解了上述的方法后，修改下来完成第一部分的遍历，即这一块的遍历

这个和刚刚不同的地方在于它的偏移量是从大到小的，上面那个理解了，这个应该也不难

1
2
3
4
5
6
7
8
9
10
11
// [3,0]
// [2,0] [3,1]
// [1,0] [2,1] [3,2]
// [0,0] [1,1] [2,2] [3,3]
// offset是对角线在x方向的偏移量
for (int offset = len - 1; offset >= 0; offset--) {
    for (int i = 0; i < len - offset; i++) {
        // 向下偏移
        System.out.println(matrix[i + offset][i]);
    }
}
完整示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void tiltPrint(int[][] matrix){
    int len = matrix.length;
    for (int offset = len - 1; offset >= 0; offset--) {
        for (int i = 0; i < len - offset; i++) {
            // 向下偏移
            System.out.println(matrix[i + offset][i]);
        }
    }
    for (int offset = 1; offset < len; offset++) {
        for (int i = offset; i < len; i++) {
            // 向上偏移
            System.out.println(matrix[i - offset][i]);
        }
    }
}

螺旋遍历

1
# 输出螺旋遍历顺序: [1 2 3 4 5 6 7 8 9 10 11 ... 21]

拆解法

将这个路径拆解开

拆解如下

1
2
3
# [0,0] -- [0,1] [1,0]
# [2,0] [1,1] [0,2] --- [0,3] [1,2] [2,1] [3,0]
# [4,0] [3,1] [2,2] [1,3] [0,4] --- [0,5] [1,4] [2,3] [3,2] [4,1] [5,0]
流程图

粉红色的是标注为每次大循环的开始处

标注内层循环初始化的是该循环刚要开始时候的数据

PS：图片很多，过程很详细

示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// i记录了次数和每一次输出开始的点的row
// 0 2 4
for (int i = 0; i < matrix.length; i+=2) {
    // 第一个输出的数字的column坐标开头都是0
    // [0,0][2,0][4,0]
    int j = 0;
    // 第一个内循环是左下角往右上角方向的
    // k（row）从i自减
    // j（column）自增到row到0
    for (int k = i; k >= 0; k--) {
        System.out.print(matrix[k][j++]+" ");
    }
    // 记录结束位置
	int end=j;
    // 如果n是奇数，在最后一次大循环中就不会有这个小循环了
    if(j >= matrix.length){
        break;
    }
    // 第二个内循环是右上角往左下角方向的
    // k（row）从0开始自增到end
    // j（column）自减到k到end
    for (int k = 0; k <= end; k++) {
        System.out.print(matrix[k][j--]+" ");
    }
}

连续法

把这些路径当作是连续的

维护一个[rowIndex,columnIndex]来走这一条连续的路径

示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int row = matrix.length;
int column = matrix[0].length;
int whole = row * column;
int counter = 0;
int rowIndex = 0;
int columnIndex = 0;
// 只要计数器比一半少，就说明还没走完
while (counter < whole / 2) {
    while (rowIndex >= 0) {
        System.out.println(matrix[rowIndex--][columnIndex++]);
        counter++;
    }
    // 复位
    rowIndex = 0;
    while (columnIndex >= 0) {
        System.out.println(matrix[rowIndex++][columnIndex--]);
        counter++;
    }
    // 复位
    columnIndex = 0;
}

发表于 | 分类于 ， |
字数统计: 422

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

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

示例 2：

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

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Related Topics

  • 数组
  • 数学
  • 矩阵

解法

这种要求原地修改数组的题目一般都需要观察

目标是将所有数字顺时针旋转90°

可以先将矩阵镜面翻转，接着对每一行进行逆转

最后就得到了顺时针旋转90°的矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public void rotate(int[][] matrix) {
        // 镜像翻转
        mirror(matrix);
        for (int[] row : matrix) {
            reverseRow(row);
        }
    }

    private void mirror(int[][] matrix) {
        int width = matrix.length;
        for (int i = 0; i < width; i++) {
            for (int j = i; j < width; j++) {
                // 将matrix[i][j]和matrix[j][i]交换
                swap(i, j, j, i, matrix);
            }
        }
    }


    /**
     * 逆转数组arr
     * 利用双指针技巧原地修改原数组
     *
     * @param arr
     */
    private void reverseRow(int[] arr) {
        // [left,right]
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    /**
     * 交换matrix[x1][y1]和matrix[x2][y2]
     *
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @param matrix
     */
    private void swap(int x1, int y1, int x2, int y2, int[][] matrix) {
        int temp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = temp;
    }
}

发表于 | 分类于 ， |
字数统计: 1.2k

算法-子集、排列、组合问题

子集

输入一个不包含重复元素的数组，求它的子集，函数签名如下

1
public List<List<Integer>> subsets(int[] nums);

比如输入了[1,2,3]

返回以下数据

1
2
3
4
5
6
7
8
9
10
[
    [],
    [1],
    [2],
    [3],
    [1,2],
    [1,3],
    [2,3],
    [1,2,3]
]

递归

第一个解法就是我们可以通过小规模问题推导出大规模问题的，即分治的方式来解决

空数组的子集

subsets([])=[[]]

1的子集

subsets([1])=[[],[1]]

2的子集

subsets([1,2])=[[],[1],[2],[1,2]]

3的子集

subsets([1,2,3])=[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]

通过数学归纳法，我们可以发现，大规模的求子集问题可以通过小规模的求子集问题中推导得知

2的子集可以由1的子集再加上1的子集中每一个元素加上2求得

3的子集可以由2的子集再加上2的子集中每一个元素加上3求得

这不就是典型的递归和分治的思想吗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> subsets(int[] nums){
    return subsets(nums,0);
}

/**
     * 返回到[index,nums.length)的所有数字的子集
     * @param nums
     * @param index
     * @return
     */
public List<List<Integer>> subsets(int[] nums,int index){
    if(index == nums.length){
        List<List<Integer>> res = new LinkedList<>();
        res.add(new LinkedList<>());
        return res;
    }
    List<List<Integer>> subPro = subsets(nums, index + 1);
    int size = subPro.size();
    // 将当前元素加入到之前求得的每一个子集中，并加入这个子集，求得[index,nums.length)的子集
    for (int i = 0; i < size; i++) {
        // 这里要复制一份，不然最后的结果会有问题
        LinkedList<Integer> append = new LinkedList<>(subPro.get(i));
        append.add(nums[index]);
        subPro.add(append);
    }
    return subPro;
}

回溯

还可以使用回溯的思想来解决这道题，直接套用回溯的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> subsets(int[] nums) {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    backTrack(nums, 0, track, res);
    return res;
}
// 路径：track
// 选择列表：[start,nums.length)
// 结束条件：没有，就是要穷举每一种可能，将每一次选择都记录下来
private void backTrack(int[] nums, int index, LinkedList<Integer> track, LinkedList<List<Integer>> res) {
    res.add(new LinkedList<>(track));
    for (int i = index; i < nums.length; i++) {
        track.addLast(nums[i]);
        backTrack(nums, index + 1, track, res);
        track.removeLast();
    }
}

nums=[1,2,3]的决策树如下

绿色的数组代表的是选择列表

组合

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合，方法签名如下

1
List<List<Integer>> combine(int n, int k);

这是一个很典型的回溯的问题

n限制了树的宽度，k限制了树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> track = new LinkedList<>();
    combine(n, k, 1, track, res);
    return res;
}

// 路径：track
// 选择列表：[start,n]
// 结束条件：k==track.size()
private void combine(int n, int k, int start, List<Integer> track, List<List<Integer>> res) {
    if (k == track.size()) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int i = start; i <= n; i++) {
        track.add(i);
        combine(n, k, i + 1, track, res);
        track.remove(track.size() - 1);
    }
}

n = [1,2,3]的时候的决策树是这样的

绿色的数组代表的是选择列表

可以发现这张决策树长得和求子集的时候的决策树很像

是这样的，求子集的时候是将每一个节点的选择都记录下来了

而求组合问题的时候，其实就是只要叶子节点的选择

排列

输入一个数组nums，返回这个数组的所有排列方式，函数签名如下

1
public List<List<Integer>> permute(int[] nums);

nums=[1,2,3]的决策树如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        permute(nums, track, res);
        return res;
    }

    // 路径：track中的数字
    // 选择列表：通过track和nums推得
    // 结束条件：track的长度等于nums的长度
    private void permute(int[] nums, LinkedList<Integer> track, List<List<Integer>> res) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (track.contains(nums[i])) {
                continue;
            }
            track.add(nums[i]);
            permute(nums, track, res);
            track.removeLast();
        }
    }
}

排列问题中通过 contains 方法来排除在 track 中已经选择过的数字，从而得到选择列表，因为维护一个选择列表比较麻烦，所以用了这种推导的方式

组合问题通过维护一个 start 参数，来排除 start 索引之前的数字，从而得到选择列表，因为组合中[1,2]和[2,1]是算重复的

发表于 | 分类于 ， |
字数统计: 1.6k

解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

1
2
3
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

Related Topics

  • 数组
  • 回溯
  • 矩阵

回溯

这里需要关注一下题目给的提示，我们来一一分析

第一条和第二条告诉我们，传入的数组是一个固定9 * 9的矩阵

第三条告诉我们'.'指的是空位

第四条告诉我们题目传入的数独只有一个答案，这就代表着我最后穷举出来解满足条件的只有一个

回溯三要素

1、路径：填上的数字，就是棋盘上的数字

2、选择列表：'1'-'9'

3、结束条件：穷举到最后一个格子（由第四条提示可得）

下面直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public void solveSudoku(char[][] board) {
        // 辅助函数
        solveSudoku(board,0,0);
    }
    
    // 路径：已经被填上数字的棋盘，即row之前
	// 对每一个格子的选择列表: 1 - 9
	// 结束条件：穷举到最后一行
    private boolean solveSudoku(char[][] board, int row, int column) {
        // 返回true，结束递归
        // 到了最后一行
        if (row==board.length){
            return true;
        }
        // 到了这一行的结尾了，换行
        if (column==board[0].length){
            return solveSudoku(board,row+1,0);
        }
        // 如果已经有数字了，直接下一列
        // 因为给出的棋盘中有的格子中是有数字的
        if (board[row][column]!='.'){
            return solveSudoku(board,row,column+1);
        }
        // 穷举
        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果要填写的数字不合法，直接跳过此次选择
            if (!valid(board,row,column,ch)){
                continue;
            }
            // 做出选择
            board[row][column] = ch;
            // 如果已经得到答案，直接结束穷举，返回true
            if(solveSudoku(board,row,column+1)){
                return true;
            }
            // 撤销选择
            board[row][column] = '.';
        }
        // [row][column]这个格子填1-9都不合法，回退上一个格子，撤销上一次的选择
        return false;
    }
    
    // 判断要填入[row,column]的这个key是否符合规则
    private boolean valid(char[][] board, int row, int column, char key) {
        for (int i = 0; i < board.length; i++) {
            // 这一列不能有重复数字
            if (board[i][column]==key){
                return false;
            }
            // 这一行不能用重复数字
            if (board[row][i]==key){
                return false;
            }
            // 九宫格不能有重复数字
            // 这里要斟酌一下的
            if (board[(row / 3) * 3 + i / 3][(column / 3) * 3 + i % 3]==key){
                return false;
            }
        }
        return true;
    }
}

我们来看下这个valid函数中判断九宫格内是否有重复数字的代码

1
2
3
if (board[(row / 3) * 3 + i / 3][(column / 3) * 3 + i % 3]==key){
    return false;
}
1
2
3
4
5
row/3 可以将其映射到其对应的九宫格行
column/3 可以将其映射到其对应的九宫格列
i	->	[0,1,2,3,4,5,6,7,8]
i/3	->	[0,0,0,1,1,1,2,2,2]
i%3	->	[0,1,2,0,1,2,0,1,2]

进阶

如果我将提示的第四条，即只有一个正确答案这个条件删除，那这道题该怎么做？

其实也不难，只要改变结束条件即可，上述代码是直接将可以穷举到最后的答案返回

因为题目说了只有唯一解，所以我不需要再对其进行判断

既然删除了只有唯一解这个条件，那我就要对穷举到最后的答案进行验证

怎么验证呢，那就是验证每一行每一列对角线加起来都是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private boolean valid(int[][] board){
    int sum = Arrays.stream(board[0]).sum();
    int row = 0;
    int column = 0;
    int downCatercorner = 0;
    int upCatercorner = 0;
    // 计算行列和对角线的和
    for (int i = 0; i < board.length; i++) {
        row = 0;
        for (int j = 0; j < board[0].length; j++) {
            row += board[i][j];
            column += board[j][i];
            // 从左上角到右下角的对角线
            if (i==j){
                downCatercorner+=board[i][j];
            }
            // 从左下角到右上角的对角线
            if (i+j==board.length-1){
                upCatercorner += board[i][j];
            }
        }
        // 每一次循环中对比行和列的和
        if (row!=sum||column!=sum){
            return false;
        }
        row = 0;
        column=0;
    }
    // 最后对比对角线的和
    return downCatercorner == sum && upCatercorner == sum;
}