目录
4. 一颗完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有109
5. 将N条长度均为M的有序链表合并,步骤是拿出N条链表的第一个元素建立小根堆,依次从堆顶取出元素,将链表其他元素依次放入堆中,进行向下调整
6. 循环队列中,f为队头元素位置,r为当前队尾元素的下一个位置(书上是这么说的),则元素个数为(r-f+Max) % Max
7. 快排确定第几趟排序结果,要看有几个数满足左边大右边小的条件
10. 方法区用于存储JVM加载的类信息,常量,静态变量,以及编译器编译后的代码等数据,是线程共享的
13. 接口中的变量都是全局常量,也就是被public static final修饰,
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)
上代码
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. 微信红包
题目要求：
题目分析：
找出现次数超过一半的数字
可以先给这个数组排个序,取这个排完序数字的中间值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. 双向链表修改,比如插入新的结点,一定要画图
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)
题目要求：
题目分析：
上代码
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)
题目要求：
题目分析：
上代码
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加载的类信息,常量,静态变量,以及编译器编译后的代码等数据,是线程共享的
通过这张图可以看出方法区是线程共享的,所以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修饰,
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. 星际密码
题目要求：
题目分析：
上代码
(这个里面用到了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. 数根
题目要求：
题目分析：
上代码
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);
}
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87306.html
