Leetcode《图解数据结构》刷题日志【第三周】（2022/10/31-2022/11/06）

1. 剑指Offer 59 -II.队列的最大值

1.1 题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value需要返回 -1

示例 1：
输入: 
    ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
    [[],[1],[2],[],[],[]]
输出:
    [null,null,null,2,1,2]
示例 2：
输入: 
    ["MaxQueue","pop_front","max_value"]
    [[],[],[]]
输出:
    [null,-1,-1]
限制：
    1 <= push_back,pop_front,max_value的总操作数?<= 10000
    1 <= value <= 10^5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2 解题思路

因为题目里面要求的是max_value()、pop_front()、push_back()的平均时间复杂度都是O(1)，因此在查找队列最大值的时候需要一个辅助的数据结构，以空间换时间，这一题的思路和剑指 Offer 30. 包含 min 函数的栈还有剑指 Offer 59 - I. 滑动窗口的最大值的思路类似。
我们需要维护一个辅助队列，将最大的元素存储在首位，维护过程如下

• 加入元素：在push_back()里面，从队列尾部添加元素，如果队列尾部元素小于待插入的元素值value，将若干个小于value的元素从队列中取出
• 删除元素：在pop_front()里面，从队列头部取出元素，如果这个头部元素是辅助队列的最大元素，则在辅助队列中也需要将头部元素删除。
  从而维护一个递减的辅助队列，原始队列中的最大元素永远在辅助队列的首位。
  PS：这个维护过程是不是和剑指 Offer 59 - I. 滑动窗口的最大值的辅助队列一样？其实感觉这两题思路类似而这题还要稍微简单一点。

1.3 数据类型功能函数总结

//LinkedList相关操作
LinkedList<> LL_Name = new LinkedList<>();//定义一个链表，可根据头尾操作模拟队列或者栈
LinkedList.add/get/remove First/Last();//添加、获取、删除 头部/尾部元素
LinkedList.size();//获得链表长度
1
2
3
4

1.4 java代码

class MaxQueue {
    LinkedList<Integer> maxQueue;
    LinkedList<Integer> subMaxQueue;
    public MaxQueue() {//初始化
        maxQueue=new LinkedList<Integer>();
        subMaxQueue=new LinkedList<Integer>();
    }

    public int max_value() {
        if(subMaxQueue.size()==0){
            return -1;
        }
        return subMaxQueue.getFirst();
    }
    
    public void push_back(int value) {
        maxQueue.addLast(value);
        while(subMaxQueue.size()!=0 && subMaxQueue.getLast()<value){
            subMaxQueue.removeLast();
        }
        subMaxQueue.addLast(value);
    }
    
    public int pop_front() {
        if(maxQueue.size()==0){
            return -1;
        }
        int ele=maxQueue.removeFirst();
        if(subMaxQueue.size()!=0 &&  subMaxQueue.getFirst()==ele){
            subMaxQueue.removeFirst();
        }
        return ele;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */
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

2. 剑指Offer 67.将字符串转换成整数

2.1 题目

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为?[?231,? 231?? 1]。如果数值超过这个范围，请返回 ?INT_MAX (231?? 1) 或?INT_MIN (?231) 。

示例?1:
输入: "42"
输出: 42

示例?2:
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例?3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例?4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。

示例?5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (?231) 。

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

2.2 解题思路

解题思路主要就是按照字符串的顺序进行遍历，并且进行一些缝缝补补。

• 如果字符串是空串，直接返回0;
• 如果字符串有若干空格，跳过这些空格；
• 如果第一个非空格字符是正负号，存储这个字符，继续向下遍历
• 如果第一个非空格字符是数字，开始查找连续数字，将单个字符转为整数并加入结果中
  • 由于结果可能会超过int的范围，我们将结果定义为long型，在最后再返回
  • 在结果不断累计的过程中，查看它和对应的INT_MAX、INT_MIN的关系，如果超过，字符串之后的字符不必考虑，直接将结果转为特殊值并退出遍历。
• 如果第一个非空格字符不是正负号也不是数组，跳过结果的处理，返回初值0；

2.3 数据类型功能函数总结

//string相关操作
string.length();//获得字符串长度
string.charAt(index);//获得指定下标的字符
//int型相关操作
Integer.INT_MAX;//int型最大值
Integer.INT_MIN;//int型最小值
整数类型：int/long;//注意：没有c语言里面的long long
1
2
3
4
5
6
7

2.4 java代码

class Solution {
    public int strToInt(String str) {
        long re=0;
        int i=0;
        if(str.length()==0){//空串
            return 0;
        }
        while(i < str.length() && str.charAt(i)==' '){//跳过空格
            i++;
        }
        char temp=' ';
        if(i<str.length() && (str.charAt(i)=='+'||str.charAt(i)=='-')){//如果是正负号，存起来，最后处理
            temp=str.charAt(i);
            i++;
        }
        while(i<str.length() && str.charAt(i)>='0'&&str.charAt(i)<='9'){//数字部分
            re=re*10+(str.charAt(i)-'0');
            if(temp=='-'){
                if(-re < Integer.MIN_VALUE){
                    re = Integer.MIN_VALUE;
                    break;
                }
            }
            else{//整数
                if(re > Integer.MAX_VALUE){
                    re = Integer.MAX_VALUE;
                    break;
                }
            }
            i++;
        }
        if(temp=='-'){
            if(re>0){
                re=-re;
            }
        }
        return (int)re;
    }
}
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

2.5 踩坑类型

2.5.1 “reached end of file while parsing”

错误原因：括号不匹配，仔细检查代码。

2.5.2 “java.lang.StringIndexOutOfBoundsException”

错误原因：遍历字符串的过程中超过了字符串的实际范围，访问越界。需要检查自己的代码，在遍历的时候注意不要超过范围。
比如我这里的错误点就在于：

//错误版本
if(i<str.length() && str.charAt(i)=='+'||str.charAt(i)=='-'){//如果是正负号，存起来，最后处理
    temp=str.charAt(i);
    i++;
}
//之所以错误是因为||所导致的运算逻辑。
//先判断i是不是小于字符串长度，如果越界，不判断条件2，但是还是会判断条件3“str.charAt(i)=='-'”，
//就会导致i越界的情况下依然访问str元素的操作。
//正确版本
if(i<str.length() && (str.charAt(i)=='+'||str.charAt(i)=='-')){//如果是正负号，存起来，最后处理
    temp=str.charAt(i);
    i++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 剑指 Offer 10- I. 斐波那契数列

3.1 题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0,? ?F(1)?= 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    输入：n = 2 
    输出：1

示例 2：
    输入：n = 5 
    输出：5

提示：
    0 <= n <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2 解题思路

我无意中写出来的竟然是“动态规划”的思路，哈哈哈确实给我学习动态规划提供了很好的自信，good start!
一开始我想要用递归法，但是递归法解决这道题还需要涉及到取模问题，并且递归实际上也存在性能问题，因此我舍弃了递归的做法。
因为题目进入n>1的时候，只需要f(n-1),f(n-2)的值就能够求出f(n)的值，然后f(n-2)=f(n-1),f(n-1)=f(n),通过循环求解出新的f(n)的值。
并且，对于递归中的取模问题，实际上仔细想想也不是什么问题，先求和最后取模和每次计算出f(n)之后取模的效果是一样的，考虑到1e9+7这个数字非常大，而且斐波那契数列也因为变态的数据增长而出名，所以为了避免数据的溢出，选择“每次计算出f(n)之后取模的效果”显然更加稳妥。

3.3 数据类型功能函数总结

//取余运算
(int)n1%(int)n2;
1
2

3.4 java代码

class Solution {
    public int fib(int n) {
        int fn_1=1,fn_2=0;
        int sum=0;
        if(n==1){
            sum=1;
        }
        for(int i=2;i<=n;i++){
            sum=fn_1+fn_2;
            sum%=1e9+7;
            fn_2=fn_1;
            fn_1=sum;
        } 
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.5 动态规划学习笔记

学习官方题解的一些笔记

https://leetcode.cn/leetbook/read/illustration-of-algorithm/m5zfc1/
1

1. 动态规划和递归的区别
   递归和动态规划都适用于“子问题分解”这样的问题。
   但是不同的是，递归中不会保留曾经出现的子问题的结果，而是每次求解的时候分别重新计算所有的子问题，这也是递归算法性不高的原因。
   而动态规划除了将问题分解为子问题之外，还需要将后续计算所需要的子问题结果存储起来，这样在后续的计算中不会重复计算，存储结果的数组也是一种“以空间换时间”的做法【重叠子问题】。
   动态规划求解的问题涉及到“最优子结构”问题，也就是说，该问题不仅能够分解为多个子问题，而且问题的结果也由子问题的最优解组成。【最优子结构】

2. 动态规划的应用
   一般用在“最值”等问题中

   普遍来看，求最值的问题一般都具有「重叠子问题」和「最优子结构」特点，因此此类问题往往适合用动态规划解决

3. 动态规划的解题思路

   1. 状态定义：问题能够分解的子问题，问题结果指的是什么，计算问题结果需要哪些变量
   2. 初始状态：最基本的子问题最优解是什么样的？（起点）
   3. 转移方程：最优解和子问题最优解的关系。子问题最优解如何组合获得问题的最优解
   4. 返回值：终止条件是什么？终止的时候应该返回的结果是什么？（一般终止条件和问题规模有关）

4. 剑指 Offer 10- II. 青蛙跳台阶问题

4.1 题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n?级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    输入：n = 2
    输出：2

示例 2：
    输入：n = 7
    输出：21

示例 3：
    输入：n = 0
    输出：1

提示：
    0 <= n <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.2 解题思路

这一题和上一题斐波那契数列很类似，只要利用动态规划将问题分解成子问题，而原始问题的答案由子问题的答案所构成。
要想跳上n个台阶，可以从n-1个台阶上跳1，也可以从n-2个台阶上跳2，因此，n的台阶的跳法f(n)由n-1个台阶的跳法f(n-1)和n-2个台阶的跳法f(n-2)组成，因此有公式f(n)=f(n-1)+f(n-2)，因此n从2开始可以用这个公式，而题目也给出了初始条件的结果，f(0)=1,f(1)=1，所以我们还是设置三个变量，形成滚动数组，为了避免int型结果溢出，我们每次求出当前f(i)之后都进行取模。

4.3 数据类型功能函数总结

无
1

4.4 java代码

class Solution {
    public int numWays(int n) {
        //规律：f[n]=f[n-1]+f[n-2];
        //f[0]=1,f[1]=1,f[2]=2;
        //f[3]=3,f[4]=5,f[5]=8,f[6]=13,f[7]=21
        if(n==1||n==0){
            return 1;
        }
        else{
            int fn_2=1,fn_1=1;
            int fn=0;
            for(int i=2;i<=n;i++){
                fn=(fn_2+fn_1);
                fn%=1e9+7;
                fn_2=fn_1;
                fn_1=fn;
            }
            return fn;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

忙忙的一周，周四到周日一塌糊涂，希望下周刷题能按天完成呜呜呜。