用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列 - 力扣（Leetcode）

题目要求

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

例子：

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

提示：

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

思路分析

我们使用到两个栈stack1和stack2，利用栈的先进后出原则：

  • 当需要入队列，就将需要入队的元素放入stack1；
  • 当需要出队列，先判断stack2中是否有元素，如果有就先将stack2中的元素弹出，然后再将stack1中的所有元素放入stack2，最后从stack2中弹出即可；如果stack2中没有元素那么直接将stack1中的所有元素放入stack2，最后从stack2中弹出；
  • 如果stack1和stack2都为空，那么返回-1；

代码实现

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
class CQueue {
    // 构建两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        // 初始化
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        // 入队列
        stack1.push(value);
    }
    
    public int deleteHead() {
        // 出队列
        // 判断stack2是否为空
        if(!stack2.isEmpty()){
            // 弹出stack2中的元素
            return stack2.pop();
        }
        // 判断stack1是否为空
        if(!stack1.isEmpty()){
            // 将stack1中的所有元素放入stack2
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            // 弹出stack2中的元素
            return stack2.pop();
        }
        // 两个栈都为空
        return -1;
    }
}

斐波那契数列

剑指 Offer 10- I. 斐波那契数列 - 力扣（Leetcode）

题目要求

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

1
2
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

例子：

1
2
3
4
5
输入：n = 2
输出：1

输入：n = 5
输出：5

提示：

  • 0 <= n <= 100

思路分析

解题方法

  1. 递归+优化 时间O(n)，空间O(n)
  2. 自下而上迭代 时间O(n)，空间O(1)

分析

递归＋优化思路：

  • 递归公式 F(N) = F(N - 1) + F(N - 2) ，(N > 1)
  • 优化思路：因为在递归的时候，很多值都是被重复计算了多次，我们需要将计算过的结果保存，在递归时判断传入的值是否被计算过，如果计算过直接返回我们保存的值，否则再进行递归计算；
  • 可以使用Map或者数组来保存值；

自下而上迭代思路：

image-20221211123651884

代码实现

递归解法

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 {
    int arr[];
    public int fib(int n) {
        // 初始化数组，大小为n+1
        arr = new int[n+1];
        // 将数组默认值初始化为-1
        for(int i=0;i<=n;i++){
            arr[i] =-1;
        }
        return f(n);
    }
    int f(int n){
        // 结束条件
        if(n<=1){
            return n;
        }
        // 如果不为-1，说明被计算过，直接返回保存的值
        if(arr[n] != -1){
            return arr[n];
        }
        // 递归计算(结果需要取模)
        int sum = (f(n-1)+f(n-2)) % 1000000007;
        arr[n] = sum; // 记录计算结果
        return sum;
    }
}

自下而上迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int fib(int n) {
        if(n<=1){
            return n;
        }
        int a = 0,b = 1,c = 0;
        for(int i=2; i<= n;i++){
            // 计算c=a+b，取模
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }
}

青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（Leetcode）

题目要求

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

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

例子：

1
2
3
4
5
6
7
8
输入：n = 2
输出：2
    
输入：n = 7
输出：21
    
输入：n = 0
输出：1

提示：

  • 0 <= n <= 100

思路分析

青蛙一次可以跳1格或2格；

image-20221211130324287

公式：f(n) = f(n-2) + f(n-1)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numWays(int n) {
        // 公式：f(n) = f(n-2) + f(n-1)
        if(n<=1){
            return 1;
        }
        int a=1,b=1,c=0;

        for(int i=2;i<=n;i++){
            // 计算并取模
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }
}

旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字 - 力扣（Leetcode）

题目要求

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

例子：

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

提示：

  • n == numbers.length
  • 1 <= n <= 5000
  • -5000 <= numbers[i] <= 5000
  • numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路分析

步骤分析：

极端情况：旋转点在最开头

  1. 旋转点就是我们要找的最小数字；旋转点将数组分为左右两部分，左边的值大于右边的值；
  2. 我们要通过不断减少左右边的值，直到最后剩下的哪个值就是旋转点；

使用二分查找：

时间O(logn)，空间O(1)

image-20221212122614863

  1. 中间值：mid=(left+right)/2
  2. mid和left进行比较：
    • mid>left => left=mid+1; （砍掉最左边的元素）
    • mid<left => right=mid; （砍掉最右边的元素）
    • mid=left => left=left+1; (砍掉最左边的元素)
  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
class Solution {
    public int minArray(int[] numbers) {
        // 定义left right
        int left = 0;
        int right = numbers.length-1;
        while(left<right){
            // 极端情况
            if(numbers[left]<numbers[right]){
                return numbers[left];
            }
            // 计算中间值
            int mid = (left + right) / 2;
            // 不断删除两边元素，直到直到旋转点
            if(numbers[mid] > numbers[left]){
                left = mid+1;
            }else if(numbers[mid] < numbers[left]){
                right = mid;
            }else{
                left++;
            }
        }
        // 返回最后剩余的元素
        return numbers[left];
    }
}

矩阵中的路径

剑指 Offer 12. 矩阵中的路径 - 力扣（Leetcode）

题目要求

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

image-202212121144639

例子：

1
2
3
4
5
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
    
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和word仅由大小写英文字母组成

思路分析

深度优先进行搜索：

  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
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    // 定义全局变量
    int m,n,len;
    boolean[][] visited; // 标记元素是否被访问
    public boolean exist(char[][] board, String word) {
        this.n = board.length; // 二维数组行
        this.m = board[0].length; // 二维数组列
        this.len = word.length(); // 字符串长度
        this.visited = new boolean[n][m]; //初始化visited

        // 进行搜索
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(dfs(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
    // 深度优先搜索
    boolean dfs(char[][] board,int i,int j,String word,int k){
        // 判断是否需要搜索
        if(i<0 || i>=n || j<0 || j>=m || visited[i][j] || board[i][j] != word.charAt(k)){
            return false;
        }
        // 字符串匹配完毕
        if(k==len-1){
            return true;
        }
        // 标记被访问
        visited[i][j] = true;
        // 开始搜索  顺序：右->下->左->上
        boolean res = dfs(board,i,j+1,word,k+1) ||
                      dfs(board,i+1,j,word,k+1) ||
                      dfs(board,i,j-1,word,k+1) ||
                      dfs(board,i-1,j,word,k+1);
        // 重置visited为false
        visited[i][j] = false;
        // 返回搜索结果
        return res;
    }
}