Java算法OJ（12）

---

目录

1.前言

2.正文

2.1Fib数列

2.2单词搜索

2.3杨辉三角

3.小结

---

1.前言

哈喽大家好吖，今天来分享几道的练习题，欢迎大家在评论区多多交流，废话不多说让我们直接开始吧。

2.正文

2.1Fib数列

题目：斐波那契数列_牛客题霸_牛客网

---

解法1：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int num = in.nextInt();int[] dp = new int[num + 1];dp[1] = 1;dp[2] = 1;for (int i = 3; i <= num; i++) {dp[i] = dp[i - 1] + dp[i - 2];}System.out.println(dp[num]);}
}

• 时间复杂度：O(n)，仅需一次遍历。

• 空间复杂度：O(n)，使用数组存储中间结果。

• 优化空间：若只需最终结果，可用两个变量替代数组，将空间复杂度降至O(1)。

• 注意事项：当num较大时，int可能溢出，可改用long或BigInteger。

---

解法2：

    public static void main(String[] args) {Scanner in = new Scanner(System.in);int num = in.nextInt();int first = 1;int second = 1;int temp;for (int i = 3; i <= num; i++) {temp = second;//先把变量second保存起来second = first + second;first = temp;}System.out.println(second);}

特性	说明
时间复杂度	O(n)，与动态规划方法相同
空间复杂度	O(1)，仅需3个变量，远优于动态规划的O(n)
边界处理	若输入 num = 1 或 2，直接输出初始值1，无需进入循环
溢出问题	当 num 较大时，int 可能溢出，可改用 long 或 BigInteger

2.2单词搜索

题目：单词搜索_牛客题霸_牛客网

---

import java.util.*;public class Solution {int[] dx = new int[]{-1, 1, 0, 0};int[] dy = new int[]{0, 0, -1, 1};public boolean exist (String[] board, String word) {// write code herechar[][] grid = new char[board.length][board[0].length()];for(int i = 0; i < board.length; i++){grid[i] = board[i].toCharArray();}boolean[][] visited = new boolean[grid.length][grid[0].length];for(int i = 0; i < grid.length; i++){for(int j = 0; j < grid[0].length; j++){if(word.charAt(0) == grid[i][j]){if(dfs(grid, word, 0, i, j, visited)) return true;}}}return false;}private boolean dfs(char[][] grid, String word, int depth, int x, int y, boolean[][] visited) {// 所有字符判断完了，返回trueif(depth == word.length()) {return true;}// 越界或访问过或字符不等，返回falseif(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y] || grid[x][y] != word.charAt(depth)){return false;}// 尝试4个方向，有一个成功就行visited[x][y] = true;for(int i = 0; i < 4; i++){if(dfs(grid, word, depth + 1, x + dx[i], y + dy[i], visited)){return true;}}// 回溯visited[x][y] = false;return false;}
}

1. 输入处理

• 将输入的字符串数组 board 转换为二维字符数组 grid，便于后续操作。

• 初始化一个与 grid 大小相同的 visited 数组，用于标记已访问的单元格。

---

2. 深度优先搜索（DFS）

• 目标：从矩阵的每个单元格出发，尝试匹配单词的每个字符。

• 步骤：

  1. 起点选择：遍历矩阵的每个单元格，如果当前单元格的字符与单词的第一个字符匹配，则从该位置开始 DFS。

  2. 递归匹配：

     • 如果当前字符匹配，标记该单元格为已访问。

     • 向四个方向（上下左右）递归搜索下一个字符。

     • 如果某个方向匹配成功，返回 true。

  3. 回溯：

     • 如果当前路径无法匹配完整单词，撤销当前单元格的访问标记（visited[x][y] = false），并返回 false。

---

3. 边界条件

• 成功条件：递归深度等于单词长度时，说明单词已完全匹配，返回 true。

• 失败条件：

  • 当前单元格越界。

  • 当前单元格已访问过。

  • 当前单元格字符与单词的当前字符不匹配。

2.3杨辉三角

题目：杨辉三角_牛客题霸_牛客网

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[][] array=new int[n][n];for(int i=0;i<n;i++){for(int j=0;j<=i;j++){if(j==0||j==i){array[i][j]=1;}else{array[i][j]=array[i-1][j-1]+array[i-1][j];}}}for(int i=0;i<n;i++){for(int j=0;j<=i;j++){System.out.printf("%5d",array[i][j]);}System.out.println();}}
}

1. 输入处理：

   • 读取用户输入的整数 n，表示要生成的杨辉三角的行数。

   • 创建一个大小为 n x n 的二维数组 array。

2. 填充杨辉三角：

   • 使用双重循环遍历每一行和每一列。

   • 根据杨辉三角的性质，计算每个位置的值：

     • 如果是行的开头或结尾，直接赋值为 1。

     • 否则，等于其左上方和右上方数字之和。

3. 打印杨辉三角：

   • 使用双重循环遍历数组，格式化输出每个数字。

   • 每行结束后换行。

3.小结

今天的分享到这里就结束了，喜欢的小伙伴点点赞点点关注，你的支持就是对我最大的鼓励，大家加油！