月度归档： 2021年10月

写一个程序，输出从 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用户

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

• 1 <= values <= 10000
• 最多会对 appendTail、deleteHead 进行 10000 次调用

【此时你需要两个薯片桶】有点意思的设计题

来啊，先去超时买两罐薯片再来解这题呢！~

我们把两个薯片桶当做两个栈，先进后出非常的完美符合。这两个桶分别为A和B

按照如图的这样把两桶桶放好，而薯片就是你要放入的数字了，此时往A桶里放入标记了1,2,3的三个薯片

现在我觉得标记1号的薯片可能味道比较好一点，我想吃那个1号薯片，那么我就把两个桶口相接，把A桶里的薯片都倒入B桶，这样我就可以轻松拿到原先A桶最底部的1号薯片了

此时我还想再往3号薯片后面放一个4号薯片，但是我只想把这个4号薯片放到3号薯片后面，呢么就把B桶里的薯片再都倒入A桶

然后我们继续往A桶里放入第4号薯片

好了，到这里你想吃薯片了没？

class CQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        //把stack2全都倒入stack中，然后再往顶部压入数据
        while (!stack2.isEmpty()){
            int num = stack2.pop();
            stack1.push(num);
        }
        stack1.push(value);
    }
    
    public int deleteHead() {
        if (stack1.isEmpty() && stack2.isEmpty()){
            return -1;
        }
        while (!stack1.isEmpty()){
            int num = stack1.pop();
            stack2.push(num);
        }
        return stack2.pop();
    }
}

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> rowList = new ArrayList<>();
        rowList.add(1);
        res.add(rowList);
        for (int row = 1; row < numRows; row++) {
            List<Integer> tmpRowList = new ArrayList<>();
            for (int col = 0; col <= row; col++) {
                int leftUp = col== 0 ? 0 :res.get(row-1).get(col-1);
                int rightUp = col == row? 0 :res.get(row-1).get(col);
                tmpRowList.add(leftUp+rightUp);
            }
            res.add(tmpRowList);
        }
        return res;
    }
}

把原来的题目中的图全部往左靠了偏移，然后我们再在左右两边都加上不存在的虚拟出来的0

方法直接呼之欲出

dp[i][n] = dp[i-1][n] + dp[i-1][n-1]

更多相关可以参考LeetCode刷题【119】杨辉三角 II