当前位置: 首页 > article >正文

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可能溢出,可改用longBigInteger


解法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)

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

  • 步骤

    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.小结

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


http://www.kler.cn/a/588426.html

相关文章:

  • Vue 3 组件库主题化与可扩展性深度剖析:设计模式与实现策略 - 构建灵活适应多场景的组件库架构
  • Java缓存String(字符串常量池)、Integer (-128 到 127 )
  • 计算机基础:二进制基础12,十进制数转换为十六进制
  • 联想台式电脑启动项没有U盘
  • 【医学影像 AI】大型语言模型生成 ROP 患者信息材料的能力
  • 编程题《牛牛的链表删除》的python可以用非链表的方式
  • 某省政务信创案例:3阶段实施×5类工具链选型经验分享
  • Word 小黑第18套
  • 用DasViewer的时候3Dtiles 转osgb 可以直接指定目标坐标系吗?
  • 【c++】【智能指针】什么情况下不适合智能指针
  • C++之stack_queue扩展
  • 【VUE】day04-组件的生命周期、组件之间的数据共享、ref引用、购物车案例
  • Axure高级功能深度解析一一高效原型设计的利器
  • 怎样用Java实现快速排序与找到数组中第k小的值?
  • AI第一天 自我理解笔记--微调大模型
  • L1-093 猜帽子游戏
  • fpga系列 HDL:ModelSim 波形绘制tips
  • 【软件】免费的PDF全文翻译软件,能保留公式图表的样式
  • ThinkPad T480s更换开机BIOS图片的详细步骤
  • windows系统,pycharm运行.sh文件