java数据结构与算法刷题-----LeetCode304：二维区域和检索 - 矩阵不可变

1. 思路分析
2. 二维前缀和，从左上角，不断扩大矩形区间，算出每个区间的和。具体看代码。
3. 代码
   

class NumMatrix {
    int sum[][] = null;
    /**
        方法二：二维前缀和 sum[][]
        0   0   0   0   0   0
        0   3   3   4   8   10
        0   8   14  18  24  27  
        0   9   17  21  28  36  
        0   13  22  26  34  49
        0   14  23  30  38  58
        ==========
        0
        ==========
        0   0
        0   3
        ==========
        0   0   0
        0   3   3
        0   8   14
        把每一个数字都看成对角线，它的和就是 
        我上面的和 sum[i-1][j]
        0           0
        3(被重复加)  3
        我左边的和sum[i][j-1]
        0   3(被重复加)
        0   8
        可见 有一个3被重复加了sum[i-1][j-1] 需要减去
        最终加上自己本身就得到了最终的和
     */
     public NumMatrix(int[][] matrix) {
        sum = new int[matrix.length+1][matrix[0].length+1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + matrix[i][j];
            }
        }
    }

    /**
        算区间时
        0   0   0   0   0   0
        0   3   3   4   8   10
        0   8   14  18  24  27  
        0   9   17  21  28  36  
        0   13  22  26  34  49
        0   14  23  30  38  58
        假设要 
        14  18
        17  21  这个区间
        那就需要将前面加的去掉，而14,18,21直接忽略即可，因为21这个值算出来，就包括了它们，不用去掉，直接忽视
        0(去掉)   0(去掉)   0(去掉)   0(去掉) 
        0(去掉)   3(去掉，被重复减去)   3(去掉)   4(去掉)  
        0(去掉)   8(去掉)   14(忽略)  18(忽略)  
        0(去掉)   9(去掉)   17(忽略)  21
        同样的，先去上面 ，也就是4
        然后去左面，也就是9
        同样的，他俩都会减去3，最后结果也需要加回来
     */
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1] + sum[row1][col1];//减上，减左，把删了两次的加回来
    }

        /**
        方法一：一维前缀和，找的比二维前缀和慢
     */
    // public NumMatrix(int[][] matrix) {
    //     //0,5,11,14,16,17
    //     //0,1,3,3,4,9
    //     sum = new int[matrix.length][];
    //     for (int i = 0; i < matrix.length; i++) {
    //         sum[i] = new int[matrix[i].length+1];
    //         for (int j = 0; j < matrix[i].length; j++) {
    //             sum[i][j+1] = sum[i][j]+matrix[i][j];
    //         }
    //     }
    // }

    // public int sumRegion(int row1, int col1, int row2, int col2) {
    //     int result = 0;
    //     for (int i = row1; i <= row2; i++) {
    //         result += sum[i][col2+1] - sum[i][col1];
    //     }
    //     return result;
    // }
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

刷题一定要坚持，总结套路，不单单要把题做出来，要举一反三，也要参考别人的思路，学习别人解题的优点，找出你觉得可以优化的点。

1. 单链表解题思路：双指针、快慢指针、反转链表、预先指针

1. 双指针：对于单链表而言，可以方便的让我们遍历结点，并做一些额外的事
2. 快慢指针：常用于找链表中点，找循环链表的循环点，一般快指针每次移动两个结点，慢指针每次移动一个结点。
3. 反转链表：通常有些题，将链表反转后会更好做，一般选用三指针迭代法，递归的空间复杂度有点高
4. 预先指针：常用于找结点，比如找倒数第3个结点，那么定义两个指针，第一个指针先移动3个结点，然后两个指针一起遍历，当第一个指针遍历完成，第二个指针指向的结点就是要找的结点

2. 数组解题思路：双指针、三指针，下标标记

1. 双指针：多用于减少时间复杂度，快速遍历数组
2. 三指针：多用于二分查找，分为中间指针，左和右指针
3. 下标标记：常用于在数组范围内找东西，而不想使用额外的空间的情况，比如找数组长度为n，元素取值范围为[1,n]的数组中没有出现的数字，遍历每个元素，然后将对应下标位置的元素变为负数或者超出[1,n]范围的正数，最后没有发生变化的元素，就是缺少的值。
4. 差分数组：用差值，作为下标，节省空间找东西。比如1900年到2000年，就可以定义100大小的数组，每个数组元素下标的查找为1900。
5. 前缀和：假设有一个数组arr[1,2,3,4]。然后创建一个前缀和数组sum，记录从开头到每个元素区间的和。第一个元素是0。第二个元素，保存第一个和sum[1] = sum[0]+arr[0]，第二个元素，保存第二个和sum[2] = sum[1]+arr[1]

3. 栈解题思路：倒着入栈，双栈

1. 倒着入栈：适用于出栈时想让输出是正序的情况。比如字符串’abc’，如果倒着入栈，那么栈中元素是（c,b,a）。栈是先进后出，此时出栈，结果为abc。
2. 双栈：适用于实现队列的先入先出效果。一个栈负责输入，另一个栈负责输出。