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

素颜马尾好姑娘i 2023-09-25 12:53 37阅读 0赞

**目录**

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)][_nowcoder.com]

**题目要求：**

![22d10a7c448441fdb4b580bdf949ada1.png][]

![c9a3849d7b0a4580b15af829ff5f8c7b.png][]

**题目分析：**

问题:字符串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)

**上代码**

import java.io.*;
    import java.lang.*;
    
    
    public class Main{
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str1;
            String str2 = "";
            if((str1 = br.readLine()) != null) {
                   str2 = br.readLine();
            }
    
            int len1 = str1.length();
            int len2 = str2.length();
            int[][] count = new int[len1+1][len2+1];
            count[0][0] = 0;
            for (int i = 1; i <= len1; i++) {
                count[i][0] = i;
            }
            for (int i = 1; i <= len2; i++) {
                count[0][i] = i;
            }
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if(str1.charAt(i-1) == str2.charAt(j-1)) {
                        count[i][j] = count[i-1][j-1];
                    }else {
                        count[i][j] = Math.min(Math.min(count[i-1][j],count[i][j-1]),count[i-1][j-1])+1;
                    }
                }
            }
            System.out.println(count[len1][len2]);
        }
    }

--------------------

## 2. 微信红包 ##

**题目链接：**[微信红包\_\_牛客网 (nowcoder.com)][_nowcoder.com 1]

**题目要求：**

![06d1ccdb30da4bb0ad2390bbdaf05cd4.png][]

![17254784acaa45d6b6f612c0e7dfe907.png][]

**题目分析：**

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

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

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

如果没有就返回0

**上代码**

import java.util.*;
    
    public class Gift {
        public int getValue(int[] gifts, int n) {
            Arrays.sort(gifts);
            //中间值
            int mid = gifts[n/2];
            int count = 0;
            for (int g : gifts) {
                if(g == mid) {
                    count++;
                }
            }
            if(count > n/2) {
                return mid;
            }
            return 0;
        }
    }

--------------------

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

![c322cc25e5394d8bb33b1155e5217f62.png][]

![04dc5a701bd94daa972fed9061b3797f.png][]

--------------------

## 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条链表的第一个元素建立小根堆,依次从堆顶取出元素,将链表其他元素依次放入堆中,进行向下调整 ##

![73f7687859734b0cb031f7052173ffb6.png][]

> 合并步骤:
> 
> 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 ##

![5e284bbf9449403c8a164dc4c986df4a.png][]

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

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

![994ef7b2f73e4fcaa5e5f2b059fbd159.png][]

--------------------

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

![e1063282a1b248c8a850f217512386f5.png][]

快排有个特点是,

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

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

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

![3622861e25294d5c9c4936ffd8e7d16a.png][]

--------------------

## 8. 年终奖 ##

**题目链接：**[年终奖\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 2]

**题目要求：**![9f0469b57b2d4d118f279415e04f9331.png][]

**题目分析：**

![ac8502199ebb4065a1858e6d767c34dc.png][]

**上代码**

public int getMost(int[][] board) {
            int row = board.length;
            int col = board[0].length;
            //第一行 和第一列
            for (int i = 1; i < col; i++) {
                board[0][i] += board[0][i-1];
            }
            for (int i = 1; i < row; i++) {
                board[i][0] += board[i-1][0];
            }
            //处理剩余位置
            for (int i = 1; i < row; i++) {
                for (int j = 1; j < col; j++) {
                    board[i][j] += Math.max(board[i-1][j],board[i][j-1]);
                }
            }
            return board[row-1][col-1];
        }

--------------------

## 9. 迷宫问题 ##

**题目链接：**[迷宫问题\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 3]

**题目要求：**

![88e8fc9ecd304ce5998ac9d27418db2e.png][]

![d4a51b30b1984e5fa407dba3741385e5.png][]

**题目分析：**

![63fd457f6fc541c4a3111efd982a7809.png][]

**上代码**

import java.util.*;
    
    
    class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public class Main {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int row = scan.nextInt();
            int col = scan.nextInt();
            //创建迷宫
            int[][] mat = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    mat[i][j] = scan.nextInt();
                }
            }   
            //搜索路径
            ArrayList<Node> path = new ArrayList<>();
            ArrayList<Node> minPath = new ArrayList<>();
            int[][] book = new int[row][col];
            getMinPath(mat,row,col,0,0,book,path,minPath);
            
            //打印路径
            for(Node n : minPath) {
                System.out.println("(" + n.x + ',' + n.y + ")");
            }
        }
    
        //matL迷宫矩阵: row行 row列
        // x,y:当前位置
        // book:标记矩阵,标记当前位置是否走过
        // path:保存当前路径的每一个位置
        // minPath:保存最短路径
        private static void getMinPath(int[][] mat, int row, int col, int x, int y, int[][] book, ArrayList<Node> path, ArrayList<Node> minPath) {
            // 判断(x,y):是否越界,是否走过,是否有障碍
            if(x < 0 || x >= row || y < 0 || y >= col || book[x][y] == 1 || mat[x][y] == 1) {
                return;
            }
            //把当前位置存入路径中
            path.add(new Node(x,y));
            //标记当前位置
            book[x][y] = 1;
            //判断当前位置是否为出口
            if(x == row-1 && y == col-1) {
                //一条新的路径产生了
                //判断是否为更短路径
                if(minPath.isEmpty() || path.size() < minPath.size()) {
                    //更新为更短路径
                    minPath.clear();
                    for(Node n : path) {
                        minPath.add(n);
                    }
                }
            }
            //如果不是出口,继续搜索(x,y)的上下左右四个方向
            getMinPath(mat,row,col,x+1,y,book,path,minPath);//下
            getMinPath(mat,row,col,x-1,y,book,path,minPath);//上
            getMinPath(mat,row,col,x,y+1,book,path,minPath);//右
            getMinPath(mat,row,col,x,y-1,book,path,minPath);//左
            //把当前位置从路径中删除,寻找新的路径
            path.remove(path.size()-1);
            book[x][y] = 0;//回退了,表示没有走过,改为0
        }
    }

--------------------

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

![6b3958d908684af7a0aa53f396efdad2.png][]

通过这张图可以看出方法区是线程共享的,所以C错![7ceb67907e41446d85b2c932d0f8a060.png][]

--------------------

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

![c5ca1422c28e4b129ca40b8d2f81d608.png][]

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

![46067425945a4de98b0677397d52f89c.png][]

其次这道题就是考察的是 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修饰, ##

public interface IService {
            String NAME = "default";
        }

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

A.    public String NAME = "default";
        B.    public static String NAME = "default";
        C.    public static final String NAME = "default";
        D.    private String NAME = "default";

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

--------------------

## 14. 星际密码 ##

**题目链接：**[星际密码\_\_牛客网 (nowcoder.com)][_nowcoder.com 4]

**题目要求：**

![3d07d53dbab5495c874d924c07126692.png][]

![a40b8d92764f47f1a0ec65edee64ef3f.png][]

**题目分析：**

![4b58b3fa32d94ae084b47ecdf79aa535.png][]

**上代码**

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

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while(scan.hasNext()) {
                int n = scan.nextInt();
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = scan.nextInt();
                }
    
                //斐波那契数组
                int[] F = new int[10001];
                F[0] = 1;
                F[1] = 1;
                for (int i = 2; i < F.length; i++) {
                    F[i] = (F[i-1] + F[i-2])%10000;
                }
    
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < n; i++) {
                    sb.append(String.format("%04d", F[i]));
                }
                System.out.println(sb);
            }
        }
    }

--------------------

## 15. 数根 ##

**题目链接：**[数根\_\_牛客网 (nowcoder.com)][_nowcoder.com 5]

**题目要求：**

![14927facbd934b86925f46c424d686b4.png][]

**题目分析：**

![2ada33632cd34b10b8053ecfba8517f2.png][]

**上代码**

import java.util.*;
    class Main {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while(scan.hasNext()) {
                String str = scan.nextLine();
                while(str.length() != 1) {
                    int sum = 0;
                    for(int i = 0; i < str.length(); i++) {
                        sum += str.charAt(i) - '0';
                    }
                    str= String.valueOf(sum);
                }
                System.out.println(str);
            }
        }
    }

--------------------

[_nowcoder.com]: https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&tqId=21275&ru=/exam/oj
[22d10a7c448441fdb4b580bdf949ada1.png]: https://img-blog.csdnimg.cn/22d10a7c448441fdb4b580bdf949ada1.png
[c9a3849d7b0a4580b15af829ff5f8c7b.png]: https://img-blog.csdnimg.cn/c9a3849d7b0a4580b15af829ff5f8c7b.png
[_nowcoder.com 1]: https://www.nowcoder.com/questionTerminal/fbcf95ed620f42a88be24eb2cd57ec54
[06d1ccdb30da4bb0ad2390bbdaf05cd4.png]: https://img-blog.csdnimg.cn/06d1ccdb30da4bb0ad2390bbdaf05cd4.png
[17254784acaa45d6b6f612c0e7dfe907.png]: https://img-blog.csdnimg.cn/17254784acaa45d6b6f612c0e7dfe907.png
[c322cc25e5394d8bb33b1155e5217f62.png]: https://img-blog.csdnimg.cn/c322cc25e5394d8bb33b1155e5217f62.png
[04dc5a701bd94daa972fed9061b3797f.png]: https://img-blog.csdnimg.cn/04dc5a701bd94daa972fed9061b3797f.png
[73f7687859734b0cb031f7052173ffb6.png]: https://img-blog.csdnimg.cn/73f7687859734b0cb031f7052173ffb6.png
[5e284bbf9449403c8a164dc4c986df4a.png]: https://img-blog.csdnimg.cn/5e284bbf9449403c8a164dc4c986df4a.png
[994ef7b2f73e4fcaa5e5f2b059fbd159.png]: https://img-blog.csdnimg.cn/994ef7b2f73e4fcaa5e5f2b059fbd159.png
[e1063282a1b248c8a850f217512386f5.png]: https://img-blog.csdnimg.cn/e1063282a1b248c8a850f217512386f5.png
[3622861e25294d5c9c4936ffd8e7d16a.png]: https://img-blog.csdnimg.cn/3622861e25294d5c9c4936ffd8e7d16a.png
[_nowcoder.com 2]: https://www.nowcoder.com/practice/72a99e28381a407991f2c96d8cb238ab?tpId=134&tqId=33854&ru=/exam/oj
[9f0469b57b2d4d118f279415e04f9331.png]: https://img-blog.csdnimg.cn/9f0469b57b2d4d118f279415e04f9331.png
[ac8502199ebb4065a1858e6d767c34dc.png]: https://img-blog.csdnimg.cn/ac8502199ebb4065a1858e6d767c34dc.png
[_nowcoder.com 3]: https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&ru=/exam/oj
[88e8fc9ecd304ce5998ac9d27418db2e.png]: https://img-blog.csdnimg.cn/88e8fc9ecd304ce5998ac9d27418db2e.png
[d4a51b30b1984e5fa407dba3741385e5.png]: https://img-blog.csdnimg.cn/d4a51b30b1984e5fa407dba3741385e5.png
[63fd457f6fc541c4a3111efd982a7809.png]: https://img-blog.csdnimg.cn/63fd457f6fc541c4a3111efd982a7809.png
[6b3958d908684af7a0aa53f396efdad2.png]: https://img-blog.csdnimg.cn/6b3958d908684af7a0aa53f396efdad2.png
[7ceb67907e41446d85b2c932d0f8a060.png]: https://img-blog.csdnimg.cn/7ceb67907e41446d85b2c932d0f8a060.png
[c5ca1422c28e4b129ca40b8d2f81d608.png]: https://img-blog.csdnimg.cn/c5ca1422c28e4b129ca40b8d2f81d608.png
[46067425945a4de98b0677397d52f89c.png]: https://img-blog.csdnimg.cn/46067425945a4de98b0677397d52f89c.png
[_nowcoder.com 4]: https://www.nowcoder.com/questionTerminal/34f17d5f2a8240bea661a23ec095a062
[3d07d53dbab5495c874d924c07126692.png]: https://img-blog.csdnimg.cn/3d07d53dbab5495c874d924c07126692.png
[a40b8d92764f47f1a0ec65edee64ef3f.png]: https://img-blog.csdnimg.cn/a40b8d92764f47f1a0ec65edee64ef3f.png
[4b58b3fa32d94ae084b47ecdf79aa535.png]: https://img-blog.csdnimg.cn/4b58b3fa32d94ae084b47ecdf79aa535.png
[_nowcoder.com 5]: https://www.nowcoder.com/questionTerminal/e2422543519249f292d8435394ab82fe
[14927facbd934b86925f46c424d686b4.png]: https://img-blog.csdnimg.cn/14927facbd934b86925f46c424d686b4.png
[2ada33632cd34b10b8053ecfba8517f2.png]: https://img-blog.csdnimg.cn/2ada33632cd34b10b8053ecfba8517f2.png