【面试突击算法第二天】剑指offer + Leetcode Hot100

2022年6月25日亮剑计划正式启动，直到8月初，每天回顾5道算法题，我选择的题目是剑指offer和leetcodehot100，因为这些题目基本上都是面试常考题，后面在面试之前可以多看看面经，熟悉一下每个公司对应的考过的算法题就行了

剑指 Offer 09. 用两个栈实现队列

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

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

• 思路：一个栈作为输入，还有一个栈作为输出，也就是先将元素写入一个栈中，然后再从该栈中出栈写入另外一个栈中，这样就可以实现先进先出的特性
• 代码：

  class CQueue {
      Deque<Integer> stack1;
      Deque<Integer> stack2;
      public CQueue() {
          stack1 = new LinkedList<>();
          stack2 = new LinkedList<>();
      }   
      public void appendTail(int value) {
      	// 添加元素的时候，只需要使用输入栈
          stack1.push(value);
      }
      public int deleteHead() {
          if (stack2.isEmpty()) {// 如果不为空,那么直接出栈就行了
              while (!stack1.isEmpty()) {// 如果为空,就说明没有输入元素或者元素全部已经出栈
                  stack2.push(stack1.pop());
              }
          }
          return stack2.isEmpty() ? -1 : stack2.pop();
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

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

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

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

  斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
• 示例：

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

• 思路：本题如果归类到动态规划题目的话，那么这个递推公式是很容易写出来的，还有初始化部分都是很容易的，但是难点在哪呢？就是答案需要取模 1e9+7，所以需要在递推的过程中对状态取模
• 代码：

  class Solution {
      public int fib(int n) {
          if (n <= 1)
              return n;
          int[] dp = new int[n + 1];
          dp[0] = 0;
          dp[1] = 1;
          for (int i = 2; i <= n; i++) {
              dp[i] = dp[i - 1] + dp[i - 2];
              dp[i] %= 1000000007;
          }
          return dp[n];
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

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

• 题意：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
• 示例：

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

• 思路：跟斐波那契数列递推公式一样，唯一的不同就是初始化的时候
• 代码：

  class Solution {
      public int numWays(int n) {
          if (n <= 1)
              return 1;
          int[] dp = new int[n + 1];  
          dp[0] = 1;
          dp[1] = 1;
          for (int i = 2; i <= n; i++) {
              dp[i] = dp[i - 1] + dp[i - 2];
              dp[i] %= 1000000007;
          }
          return dp[n];
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

剑指 Offer 11. 旋转数组的最小数字

• 题意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
• 示例：

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

• 思路：第一种想法，我们观察这个旋转后的序列有一个特点，就是转折点之前是递增序列，转折点之后是递增序列，那么该转折点其实是极小值点，因此一次遍历过程中就可以找到最小值；第二种想法，一看是一个半有序序列，联想到了二分查找 较难
• 代码：

  class Solution {
  	public int minArray(int[] numbers) {
          int l = 0, r = numbers.length - 1;
          while (l <= r) {
              int mid = l + (r - l) / 2;
              if (numbers[mid] > numbers[r])   // 排除左边部分  
                  l = mid + 1;
              else if (numbers[mid] < numbers[r])  // 排除右边部分  但是mid可能就是最小值
                  r = mid;
              else    
                  r -= 1;      // 因为这个时候最小值有可能在mid左边，也有可能在mid右边，所以只能排除r
          }
          return numbers[l];
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

剑指 Offer 12. 矩阵中的路径

• 题意：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
• 示例：

  输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  输出：true
  1
  2

• 思路：套岛屿面积的模板
• 代码：

  class Solution {
      public boolean exist(char[][] board, String word) {
          int m = board.length, n = board[0].length;
          boolean[][] visited = new boolean[m][n];   // 防止死循环
          // 从每一个位置进行递归搜索
          for (int i = 0; i < m; i++) {
              for (int j = 0; j < n; j++) {
                  if (dfs(board, word, visited, i, j, 0))
                      return true;
              }
          }
          return false;
      }
      
      private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
          int m = board.length, n = board[0].length;
          if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j])
              return false;
          if (board[i][j] != word.charAt(index))
              return false;
          if (index == word.length() - 1)
              return true;
          visited[i][j] = true;
          boolean result = dfs(board, word, visited, i - 1, j, index + 1) ||
          dfs(board, word, visited, i + 1, j, index + 1) ||
          dfs(board, word, visited, i, j - 1, index + 1) ||
          dfs(board, word, visited, i, j + 1, index + 1);
          visited[i][j] = false;
          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