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 here
char[][] 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) {
// 所有字符判断完了,返回true
if(depth == word.length()) {
return true;
}
// 越界或访问过或字符不等,返回false
if(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)
目标:从矩阵的每个单元格出发,尝试匹配单词的每个字符。
步骤:
起点选择:遍历矩阵的每个单元格,如果当前单元格的字符与单词的第一个字符匹配,则从该位置开始 DFS。
递归匹配:
如果当前字符匹配,标记该单元格为已访问。
向四个方向(上下左右)递归搜索下一个字符。
如果某个方向匹配成功,返回
true
。回溯:
如果当前路径无法匹配完整单词,撤销当前单元格的访问标记(
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();
}
}
}
输入处理:
读取用户输入的整数
n
,表示要生成的杨辉三角的行数。创建一个大小为
n x n
的二维数组array
。填充杨辉三角:
使用双重循环遍历每一行和每一列。
根据杨辉三角的性质,计算每个位置的值:
如果是行的开头或结尾,直接赋值为
1
。否则,等于其左上方和右上方数字之和。
打印杨辉三角:
使用双重循环遍历数组,格式化输出每个数字。
每行结束后换行。
3.小结
今天的分享到这里就结束了,喜欢的小伙伴点点赞点点关注,你的支持就是对我最大的鼓励,大家加油!