• 刷题笔记之十一 (计算字符串的编辑距离+微信红包+年终奖+迷宫问题+星际密码+数根)

    目录

    1. 计算字符串的编辑距离

    2. 微信红包

    3. 双向链表修改,比如插入新的结点,一定要画图

    4. 一颗完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有109

    5. 将N条长度均为M的有序链表合并,步骤是拿出N条链表的第一个元素建立小根堆,依次从堆顶取出元素,将链表其他元素依次放入堆中,进行向下调整

    6. 循环队列中,f为队头元素位置,r为当前队尾元素的下一个位置(书上是这么说的),则元素个数为(r-f+Max) % Max

    7. 快排确定第几趟排序结果,要看有几个数满足左边大右边小的条件

    8. 年终奖

    9. 迷宫问题

    10. 方法区用于存储JVM加载的类信息,常量,静态变量,以及编译器编译后的代码等数据,是线程共享的

    11. for循环表达式中()位置可以放方法

    12. java在运行时才进行翻译指令

    13. 接口中的变量都是全局常量,也就是被public static final修饰,

    14. 星际密码

    15. 数根

    1. 计算字符串的编辑距离

    题目链接：计算字符串的编辑距离_牛客题霸_牛客网 (nowcoder.com)

    题目要求：

      题目分析：

    问题:字符串A转换成字符串B的编辑距离

    子问题:字符串A的子串转换成字符串B的子串的一部分的编辑距离

    状态F(i,j):字符串A的前i个字符转换成字符串B的前j个字符的编辑距离

    如果当前字符相等,直接那就等于前一个位置的情况也就是F[i,j] = F[i-1][j-1]

    如果不相等,

    如果不相等，要么B字符串插入A中i位置对应字符即dp[i][j]=dp[i-1][j]+1

    要么A字符串插入B中j位置对应字符即dp[i][j]=dp[i][j-1]+1，要么s1字符串

    i位置字符被s2字符串j位置字符替换，即dp[i][j]=dp[i-1][j-1]+1

    状态转义方程:F（i,j）=min{F(i,j-1)+1，F(i-1,j)+1，F(i-1,j-1) +1

    初始化:F（0，j）=j          F（i，0）=i

    返回值F(ALen,Blen)

    上代码

    1. import java.io.*;
    2. import java.lang.*;
    3.  
    4.  
    5. public class Main{
    6.     public static void main(String[] args) throws IOException {
    7.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    8.         String str1;
    9.         String str2 = "";
    10.         if((str1 = br.readLine()) != null) {
    11.                str2 = br.readLine();
    12.         }
    13.  
    14.         int len1 = str1.length();
    15.         int len2 = str2.length();
    16.         int[][] count = new int[len1+1][len2+1];
    17.         count[0][0] = 0;
    18.         for (int i = 1; i <= len1; i++) {
    19.             count[i][0] = i;
    20.         }
    21.         for (int i = 1; i <= len2; i++) {
    22.             count[0][i] = i;
    23.         }
    24.         for (int i = 1; i <= len1; i++) {
    25.             for (int j = 1; j <= len2; j++) {
    26.                 if(str1.charAt(i-1) == str2.charAt(j-1)) {
    27.                     count[i][j] = count[i-1][j-1];
    28.                 }else {
    29.                     count[i][j] = Math.min(Math.min(count[i-1][j],count[i][j-1]),count[i-1][j-1])+1;
    30.                 }
    31.             }
    32.         }
    33.         System.out.println(count[len1][len2]);
    34.     }
    35. }
    36.

    2. 微信红包

    题目链接：微信红包__牛客网 (nowcoder.com)

    题目要求：

     题目分析：

    找出现次数超过一半的数字

    可以先给这个数组排个序,取这个排完序数字的中间值mid

    遍历数组,统计mid出现的次数是否超过一半,如果有一半就返回这个mid

    如果没有就返回0

    上代码

    1. import java.util.*;
    2.  
    3. public class Gift {
    4.     public int getValue(int[] gifts, int n) {
    5.         Arrays.sort(gifts);
    6.         //中间值
    7.         int mid = gifts[n/2];
    8.         int count = 0;
    9.         for (int g : gifts) {
    10.             if(g == mid) {
    11.                 count++;
    12.             }
    13.         }
    14.         if(count > n/2) {
    15.             return mid;
    16.         }
    17.         return 0;
    18.     }
    19. }

    3. 双向链表修改,比如插入新的结点,一定要画图

     

    4. 一颗完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有109

    一颗完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有(D)

    A. 112     B. 111      C. 107         D. 109

    第六层有9个叶子结点,求最大结点个数,那就存在第7层,并且第六层是满的

    前六层  1+2+4+8+16+32=63

    第六层本身有2^5=32,除去9个叶子结点,还剩23个结点的度为2

    所以第七层 23*2 = 46,总共63+46 = 109

    5. 将N条长度均为M的有序链表合并,步骤是拿出N条链表的第一个元素建立小根堆,依次从堆顶取出元素,将链表其他元素依次放入堆中,进行向下调整

    合并步骤:

    1. 建立一个长度为N的最大/最小堆

    将这N条链表的第一个元素拿出来建立最小堆,时间复杂度O(N)

    2. 依次从最小堆中取出元素(堆顶),此时堆顶就是当前集合的最小值,将链表的其他元素放入堆中.

    调整堆的时间复杂度(siftDown - O(logN)),总共还需要入堆的元素个数,O(N*M*logN)

    3. 总共:建堆 + 不断调整堆(不断取出堆顶元素) O(N) + O(N*M*logN)

    所以答案选A 

    6. 循环队列中,f为队头元素位置,r为当前队尾元素的下一个位置(书上是这么说的),则元素个数为(r-f+Max) % Max

    针对这道题,力扣上有一个图非常清楚,可以解释答案为啥选B 

    需要注意的是本道题中r为当前队尾元素位置(最后一个元素的位置)

    7. 快排确定第几趟排序结果,要看有几个数满足左边大右边小的条件

    快排有个特点是,

    每进行一次快排,标定点一定处在最终位置上

    进行了两次快排,则至少有两个元素到达最终位置

    也就是说第2趟排序结果肯定满足至少有2个数字其左边比它小右边比它大。所以选C

    8. 年终奖

    题目链接：年终奖_牛客题霸_牛客网 (nowcoder.com)

    题目要求：

     题目分析：

     上代码

    1.     public int getMost(int[][] board) {
    2.         int row = board.length;
    3.         int col = board[0].length;
    4.         //第一行 和第一列
    5.         for (int i = 1; i < col; i++) {
    6.             board[0][i] += board[0][i-1];
    7.         }
    8.         for (int i = 1; i < row; i++) {
    9.             board[i][0] += board[i-1][0];
    10.         }
    11.         //处理剩余位置
    12.         for (int i = 1; i < row; i++) {
    13.             for (int j = 1; j < col; j++) {
    14.                 board[i][j] += Math.max(board[i-1][j],board[i][j-1]);
    15.             }
    16.         }
    17.         return board[row-1][col-1];
    18.     }

    9. 迷宫问题

    题目链接：迷宫问题_牛客题霸_牛客网 (nowcoder.com)

    题目要求：

    题目分析：

    上代码

    1. import java.util.*;
    2.  
    3.  
    4. class Node {
    5.     int x;
    6.     int y;
    7.     public Node(int x, int y) {
    8.         this.x = x;
    9.         this.y = y;
    10.     }
    11. }
    12.  
    13. public class Main {
    14.     public static void main(String[] args) {
    15.         Scanner scan = new Scanner(System.in);
    16.         int row = scan.nextInt();
    17.         int col = scan.nextInt();
    18.         //创建迷宫
    19.         int[][] mat = new int[row][col];
    20.         for (int i = 0; i < row; i++) {
    21.             for (int j = 0; j < col; j++) {
    22.                 mat[i][j] = scan.nextInt();
    23.             }
    24.         }   
    25.         //搜索路径
    26.         ArrayList path = new ArrayList<>();
    27.         ArrayList minPath = new ArrayList<>();
    28.         int[][] book = new int[row][col];
    29.         getMinPath(mat,row,col,0,0,book,path,minPath);
    30.         
    31.         //打印路径
    32.         for(Node n : minPath) {
    33.             System.out.println("(" + n.x + ',' + n.y + ")");
    34.         }
    35.     }
    36.  
    37.     //matL迷宫矩阵: row行 row列
    38.     // x,y:当前位置
    39.     // book:标记矩阵,标记当前位置是否走过
    40.     // path:保存当前路径的每一个位置
    41.     // minPath:保存最短路径
    42.     private static void getMinPath(int[][] mat, int row, int col, int x, int y, int[][] book, ArrayList path, ArrayList minPath) {
    43.         // 判断(x,y):是否越界,是否走过,是否有障碍
    44.         if(x < 0 || x >= row || y < 0 || y >= col || book[x][y] == 1 || mat[x][y] == 1) {
    45.             return;
    46.         }
    47.         //把当前位置存入路径中
    48.         path.add(new Node(x,y));
    49.         //标记当前位置
    50.         book[x][y] = 1;
    51.         //判断当前位置是否为出口
    52.         if(x == row-1 && y == col-1) {
    53.             //一条新的路径产生了
    54.             //判断是否为更短路径
    55.             if(minPath.isEmpty() || path.size() < minPath.size()) {
    56.                 //更新为更短路径
    57.                 minPath.clear();
    58.                 for(Node n : path) {
    59.                     minPath.add(n);
    60.                 }
    61.             }
    62.         }
    63.         //如果不是出口,继续搜索(x,y)的上下左右四个方向
    64.         getMinPath(mat,row,col,x+1,y,book,path,minPath);//下
    65.         getMinPath(mat,row,col,x-1,y,book,path,minPath);//上
    66.         getMinPath(mat,row,col,x,y+1,book,path,minPath);//右
    67.         getMinPath(mat,row,col,x,y-1,book,path,minPath);//左
    68.         //把当前位置从路径中删除,寻找新的路径
    69.         path.remove(path.size()-1);
    70.         book[x][y] = 0;//回退了,表示没有走过,改为0
    71.     }
    72. }

    10. 方法区用于存储JVM加载的类信息,常量,静态变量,以及编译器编译后的代码等数据,是线程共享的

     通过这张图可以看出方法区是线程共享的,所以C错

    11. for循环表达式中()位置可以放方法

     首先明白for(表达式1;表达式2;表达式3) {}  这个表达式的位置是可以放入方法的,我在做题时以为不可以,就直接选了C,     可以看到我把代码放入idea中是没有报错的

    其次这道题就是考察的是    for循环中表达式的执行顺序问题

    先执行表达式1和表达式2,如果满足就执行for循环中的语句,然后再执行表达式3,选A

    12. java在运行时才进行翻译指令

    下面关于程序编译说法正确的是 (C)

    A. java语言是编译型语言,会把java程序编译成二进制机器指令直接放行

    B. java编译出来的目标文件与具体操作系统有关

    C. java在运行时才进行翻译指令

    D. java编译出来的目标文件,可以运行在任意jvm上

    A. java是半编译半运行的语言,A错

    B. java编译出来的目标文件,是class它是与操作系统无关的,面向JVM的二进制文件,B错

    C.编译阶段: javac 会把  *.java 编译为 *.class(与系统无关的,面向JVM的二进制文件)

    运行阶段: java    JVM实际上此时会把class文件翻译成操作系统运行的机器码

    D.JVM也是有版本的,JDK11的class文件  JDK8的JVM是无法运行的,D错

    13. 接口中的变量都是全局常量,也就是被public static final修饰,

    1.     public interface IService {
    2.         String NAME = "default";
    3.     }

    默认类型等价表示是哪一项    (C)

    1.     A.    public String NAME = "default";
    2.     B.    public static String NAME = "default";
    3.     C.    public static final String NAME = "default";
    4.     D.    private String NAME = "default";

    答案选C,这是因为接口中的变量都是全局常量,也就是被public static final修饰,

    14. 星际密码

    题目链接：星际密码__牛客网 (nowcoder.com)

    题目要求：

     题目分析：

     上代码

    (这个里面用到了String.format方法,这个方法是给第二参数(Object类型)传一个变量,然后根据第一个参数格式来进行打印)

    1. import java.util.Scanner;
    2.  
    3. public class Main {
    4.     public static void main(String[] args) {
    5.         Scanner scan = new Scanner(System.in);
    6.         while(scan.hasNext()) {
    7.             int n = scan.nextInt();
    8.             int[] arr = new int[n];
    9.             for (int i = 0; i < n; i++) {
    10.                 arr[i] = scan.nextInt();
    11.             }
    12.  
    13.             //斐波那契数组
    14.             int[] F = new int[10001];
    15.             F[0] = 1;
    16.             F[1] = 1;
    17.             for (int i = 2; i < F.length; i++) {
    18.                 F[i] = (F[i-1] + F[i-2])%10000;
    19.             }
    20.  
    21.             StringBuffer sb = new StringBuffer();
    22.             for (int i = 0; i < n; i++) {
    23.                 sb.append(String.format("%04d", F[i]));
    24.             }
    25.             System.out.println(sb);
    26.         }
    27.     }
    28. }

    15. 数根

    题目链接：数根__牛客网 (nowcoder.com)

    题目要求：

     题目分析：

     上代码

    1. import java.util.*;
    2. class Main {
    3.     public static void main(String[] args) {
    4.         Scanner scan = new Scanner(System.in);
    5.         while(scan.hasNext()) {
    6.             String str = scan.nextLine();
    7.             while(str.length() != 1) {
    8.                 int sum = 0;
    9.                 for(int i = 0; i < str.length(); i++) {
    10.                     sum += str.charAt(i) - '0';
    11.                 }
    12.                 str= String.valueOf(sum);
    13.             }
    14.             System.out.println(str);
    15.         }
    16.     }
    17. }

  • 相关阅读:
    Element UI组件安装使用会了吗?
    [【linux_centOS】]没有javac 编译命令，安装它的时候又没dnf命令，真搞人心态啊！！！
    Yolov5-Deepsort-Fastreid windows10环境配置详细过程
    激光位移传感器的原理及信号处理方式
    计算机病毒
    Flutter 应用程序更新
    i.MX 8M Plus-集成专用神经处理引擎（NPU）
    YTU数据结构作业三
    【QT】信号与槽
    Matplotlib格式化轴
  • 原文地址：https://blog.csdn.net/m0_58761900/article/details/127802993