给定一个二维矩阵 matrix，以下类型的多个请求：

• 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -105 <= matrix[i][j] <= 105
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• 最多调用 104 次 sumRegion 方法

和另一个题目LeetCode刷题【1314】矩阵区域和基本一毛一样

同样的都是矩阵数据，都是求中间某个矩形部分的内的所有数字总和

求这里的红色区域内的数字总和的话，就是

红色区域的数字之和 = 蓝色区域的数字之和 – 黄色区域之和 – 紫色区域之和 + 黑色区域之和

黑色区域的和值之前重复减掉的

而求各个格子对应的左上区域的前缀和的方法

29的蓝色框线区域内的所有数字之和 = 23格子代表的紫色框线区域的所有数字之和 + 28代表的黄色框线区域数字之和 – 22代表的黑色框线区域的所有数字之和 + 29这个格子内的值

class NumMatrix {

    int[][] preSum;

    public NumMatrix(int[][] matrix) {
        preSum = new int[matrix.length][matrix[0].length];
        for (int row = 0; row < preSum.length; row++) {
            for (int col = 0; col < preSum[row].length; col++) {
                preSum[row][col] = getMatrixNum( preSum, row-1, col)
                        + getMatrixNum( preSum, row, col-1)
                        - getMatrixNum( preSum, row-1, col-1)
                        + matrix[row][col];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = getMatrixNum(preSum, row2, col2)
                + getMatrixNum(preSum, row1-1, col1-1)
                - getMatrixNum(preSum, row2, col1-1)
                - getMatrixNum(preSum, row1-1, col2);
        return sum;
    }

    public int getMatrixNum(int[][] matrix, int row, int col){
        if (row < 0 || col < 0){
            return 0;
        }
        return matrix[row][col];
    }
}

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

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

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

理解题意

根据题意：所求新数组answer[row][col]的值就是原数组的mat[row][col]位置上下左右下标距离k这个这个区域内的所有数字之和

若距离k为1,则answer[3][3]的值为周围距离k的矩形区域内的所有数字之和。
那么顺着题意，想要求这片红色区域的所有数字只有的话，我们有两个方法

遍历这个区域内的所有格子，求和处理
这片红色区域的数字之和 = 蓝色区域的数字之和 - 黄色区域之和 - 紫色区域之和 + 黑色区域之和
黑色区域的和值之前重复减掉的那么顺着这个和数组的前缀和非常像的思路，我们要怎么求这某个格子的所有左上格子内的数字之和呢？

右下角为29的蓝色区域的所有数字之和 = 23格子代表的紫色区域的所有数字之和 + 28代表的黄色区域数字之和 - 22代表的黑色区域的所有数字之和 + 29这个格子内的值

因为遍历的顺序是从上往下，从左往右，在第29这个格子的时候，前面的22,23,28的格子内的值都是已知的。

那么思路就很清楚了

一些边界情况

1. 在求前缀和的时候，如果是第0行或者是每行的第一个格子，他们的上一行或者前一个格子是不存在的，直接取值0
2. 当在求第一个图中红色区域的时候，如果红色区域超出了原本的数组的边界，应当取原本数组边界的位置

代码

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] preSum = new int[mat.length][mat[0].length];
        for (int row = 0; row < preSum.length; row++) {
            for (int col = 0; col < preSum[row].length; col++) {
                preSum[row][col] = getMatrixNum( preSum, row-1, col)
                        + getMatrixNum( preSum, row, col-1)
                        - getMatrixNum( preSum, row-1, col-1)
                        + mat[row][col];
            }
        }

        int[][] answer = new int[mat.length][mat[0].length];
        for (int row = 0; row < answer.length; row++) {
            for (int col = 0; col < answer[row].length; col++) {
                answer[row][col] = getPreSumMatrixNum(preSum, row+k, col+k)
                        + getPreSumMatrixNum(preSum, row-k-1, col-k-1)
                        - getPreSumMatrixNum(preSum, row+k, col-k-1)
                        - getPreSumMatrixNum(preSum, row-k-1, col+k);
            }
        }
        return answer;
    }

    public int getMatrixNum(int[][] matrix, int row, int col){
        if (row < 0 || col < 0){
            return 0;
        }
        return matrix[row][col];
    }

    public int getPreSumMatrixNum(int[][] matrix, int row, int col){
        if (row < 0 || col < 0){
            return 0;
        }
        row = row > matrix.length-1 ? matrix.length-1 : row;
        col = col > matrix[row].length-1 ? matrix[row].length-1 : col;
        return matrix[row][col];
    }

}

本题和另外一题，LeetCode刷题【304】二维区域和检索 – 矩阵不可变基本一样，可以结合起来一起理解

写一个程序，输出从 1 到 n 数字的字符串表示。

1. 如果 n 是3的倍数，输出“Fizz”；

2. 如果 n 是5的倍数，输出“Buzz”；

3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

每日一题刷题打卡，15个一组，第3、5、6、9、10、12、15位对应字符串。
剩下的部分自行把int型转为String型，当然你也可以直接使用Integer.toString(num);来实现。
我这边的写法也是参考的Integer.toString(num);的源码来写的，中间省去了一些确定范围之类的逻辑，相对更加简单点。

class Solution {

    int [] sizeArray = { 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, Integer.MAX_VALUE };

    char[] numArray = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    boolean[] ifString = {false,false,false,true,false,true,true,false,false,true,true,false,true,false,false,true};

    String[] stringArray = new String[]{null,null,null,"Fizz",null,"Buzz","Fizz",null,null,"Fizz","Buzz",null,"Fizz",null,null,"FizzBuzz"};

    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        int num = 1;
        int idx = 1;
        while (num <= n){
            list.add( ifString[idx] ? stringArray[idx] : numToString(num) );
            num ++;
            idx = idx==15 ? 1 : idx+1;
        }
        return list;
    }

    public String numToString(int num){
        int size = stringSize(num);
        char[] chars = new char[size];
        while (num>0){
            chars[--size] = numArray[num%10];
            num = num/10;
        }
        return new String(chars);
    }

    public int stringSize(int num) {
        for (int i=0; ; i++)
            if (num <= sizeArray[i])
                return i+1;
    }
}

正常点来说，你可以选择依次遍历，余3输出”Fizz”、余5输出”Buzz”、都余输出”FizzBuzz”，其他的输出当前数字即可

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3],      [[2,1,3],
 [6,5,4],       [6,5,4],
 [7,8,9]]       [7,8,9]]

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
 [-40,-5]]

示例 3：

输入：matrix = [[-48]]
输出：-48

提示：

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

本题同LeetCode刷题【120】三角形最小路径和其实是一样的区别只是在于本题是数据是矩阵型的，120题是三角形的，在dp每个阶段所选取的决策参数的范围不同。

直接上代码了

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int path = Integer.MAX_VALUE;
        int row = 1;
        for (; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) {
                int left = col == 0 ? 101 : matrix[row-1][col-1];
                int right = col == matrix[row].length-1 ? 101 : matrix[row-1][col+1];
                matrix[row][col] = Math.min(matrix[row-1][col],Math.min(left,right)) + matrix[row][col];
            }
        }
        for (int num : matrix[--row]) {
            path = Math.min(path,num);
        }
        return path;
    }
}

 

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

 

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

 

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

结合上一篇LeetCode刷题【剑指 Offer 24】反转链表一起看，是同一个问题，不过这里不用迭代遍历了

class Solution {

    ListNode preNode;
    ListNode tail;
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        preNode = head;
        nextNode(head.next);
        head.next = null;
        return tail;
    }


    public void nextNode(ListNode node){
        if (node == null){
            tail = preNode;
            return;
        }
        ListNode next = node.next;
        node.next = preNode;
        preNode = node;
        nextNode(next);
    }
}

这是递归的方法，不过本质上还是和遍历迭代是一样的

• 在递归的过程中记录上一个递归到的节点preNode
• 把当前节点的next指向之前记录的preNode
• 把preNode指向当前节点
• 继续处理next节点
• 别忘了头结点的next指向也要清除掉

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        head.next = null;
        ListNode tmp;
        while (cur!=null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }

        return pre;
    }
}

一遍遍历，题目和LeetCode刷题【206】反转链表一样，这里是实现的迭代遍历的方法，在206题中实现的是递归的方法，两篇可以结合起来一起看下，其本质实现逻辑是一样的

1. 记下上一个节点，和下一个节点
2. 把当前节点的next指向上一个节点，
3. 把上一个节点pre指向当前节点
4. 跳转处理下一个节点
5. 记得清除头结点的next指向

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹,  2³¹ − 1]。本题中，如果除法结果溢出，则返回 2³¹ − 1。

今天每一题，先理清思路

首先，除法的本质，从我们小时候刚开始学习除法的时候老师们最直接的说明是这样的：6 ÷ 2 = 3

表示6可以由3个2加起来组成。而这里的3，就是我们这题需要求得的数字。那么最直观的，换一个角度来做的话，我们可以让6来减去2，看能减去多少个，得到的结果也是同样的答案了。

写代码前的一点问题

按照正常思路，肯定是正数操作更顺手，不过我们知道
Integer.MAX_VALUE = 2147483647
Integer.MIN_VALUE = -2147483648
是的，负的值比正的多一个（按照我们一般理解的数字分为[负，零，正]这三个区间来理解的话）
所以我这里选择了都变为负数来处理。如果把-2147483648取绝对值变成正的话就是溢出。至于为什么是这个区间是另外一个话题了

另外一些一些特殊情况：
被除数如果是1的话则直接返回除数本身
除数是Integer.MIN_VALUE，被除数如果是-1的话，是溢出的情况原因就是上面说的
如果被除数是-1的话直接取反返回（这个一开始忘了写）

好了，代码

class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor==1){
            return dividend;
        }
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean flag = true;
        if ((dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0) ){
            flag = false;
        }
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? - divisor : divisor;
        int res = 0;
        while (dividend <= divisor){
            dividend -= divisor;
            res++;
        }
        return flag?res:-res;
    }
}

跑一下看看

解答成功:
执行耗时:1146 ms,击败了7.76% 的Java用户
内存消耗:35.3 MB,击败了94.94% 的Java用户

嚯，果然，直接硬刚的结果就是这样

再想想

举个栗子，拿100依次减3，这样我们需要减33次，有没有办法加速呢？有的，

• 我们可以第一次尝试减3 = 97 1个3
• 尝试减6 = 91 3个3
• 尝试减12 = 79 7个3
• 尝试减24 = 55 15个3
• 尝试减48 = 7 31个3
• 尝试减96 不够
• 再次尝试从3开始减 = 4 32个3
• 尝试减6 不够
• 再次尝试从3开始减 = 1 33个3

这是这样的思想来加速处理或者说，好像叫倍增？这个我不太确定。不过如果换个角度来看的话，比较像是二分法的逆向运用。
除了和二分法有点相关的之外，还有另外一个方法有点类似，哈希表中用来解决哈希冲突用到的平方探测法：当哈希结果发生冲突的时候以增量序列[1,4,9,16……]循环试探下一个地址，这些值分别是1的平方、2的平方、3的平方、4的平方。
扯得有点多了。回到代码，这样我们在现在的代码中while循环内再加一层尝试的逻辑

以及加亿点点比较一眼就能看出来的结果的分支判断

代码

class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor==1){
            return dividend;
        }
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        if (divisor == Integer.MIN_VALUE){
            return dividend> divisor?0:1;
        }
        if (divisor == -1){
            return -dividend;
        }
        if (divisor == 2){
            return dividend>>1;
        }
        if (divisor == -2){
            return -dividend>>1;
        }
        boolean flag = true;
        if ((dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0) ){
            flag = false;
        }
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? - divisor : divisor;
        int res = 0;
        while (dividend <= divisor){
            int tmpDivisor = divisor;
            int tmpCount = 1;
            while (dividend <= tmpDivisor && tmpDivisor<=0){
                res += tmpCount;
                dividend -= tmpDivisor;
                tmpCount += tmpCount;
                tmpDivisor += tmpDivisor;//会越界,所以上面还加了判负条件，不过可能还有问题
            }
        }
        return flag?res:-res;
    }
}

还有一点问题，这里tmpDivisor虽然为负数，再加自己一次的时候还是可能会越界变成小于Integer.MIN_VALUE然后导致变成一个正数。
所以还是加了一个tmpDivisor<=0的判断，不过感觉还是有点问题。 也许应该用 tmpDivisor>=-1073741824来判断？就是Integer.MIN_VALUE/2的值

最后跑下看下结果，看起来海星

执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:35.3 MB,击败了89.65% 的Java用户