推广型网站建设公司,宿迁房产信息公示网,电子贺卡制作,帮人做项目的网站#x1f389;#x1f389;#x1f389;点进来你就是我的人了博主主页#xff1a;#x1f648;#x1f648;#x1f648;戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔#x1f93a;#x1f93a;#x1f93a; 目录
一、选择题
二、编程题 #x1f525;年终奖 … 点进来你就是我的人了博主主页戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔 目录
一、选择题
二、编程题 年终奖 迷宫问题 一、选择题
1、将N条长度均为M的有序链表进行合并合并以后的链表也保持有序时间复杂度为()? A O(N * M * logN) B O(NM) C O(N) D O(M)正确答案 A 参考答案 1.建立一个长度为N的最大/最小堆 将这N条链表的第一个元素拿出来建立最小堆时间复杂度为O(N) 2.依次从最小堆中取出元素(堆顶)此时堆顶就是当前集合的最小值将链表的其他元素放入堆中。调整堆的时间复杂度(siftDown-O(logN))总共还需要入堆的元素个数O(NMloqN) 3.总共:建堆不断调整堆(不断取出堆顶元素)O(N)O(NM*loqN)2、下设栈S的初始状态为空元素a,b,c,d,e,f依次入栈S出栈的序列为b,d,c,f,e,a则栈S的容量至少为 A 6 B 5 C 4 D 3正确答案 D3、大小为MAX的循环队列中f为当前对头元素位置r为当前队尾元素位置(最后一个元素的位置)则任意时刻队列中的元素个数为 A r-f B (r-fMAX1)%MAX C r-f1 D (r-fMAX)%MAX正确答案 B 数组长度和最多存放的元素个数(MAX) 数组长度 MAX-1(判断队列满浪费一个空间)4、HASH 函数冲突处理方式不包括以下哪一项 A 开放定址法 B 链地址法 C 插入排序法 D 公共溢出区法正确答案 C5、若一棵二叉树具有12个度为2的结点6个度为1的结点则度为0的结点个数是。 A 10 B 11 C 13 D 不确定正确答案 C 度为2的节点个数1度为0的结点个数(叶子结点)度为0的结点度为1的结点度为2的结点 总结点个数边长总节点个数-1。6、二叉排序树可以得到一个从小到大的有序序列。 A 先序遍历 B 中序遍历 C 后序遍 D 层次遍历正确答案 B7、已知小根堆为8,15,10,21,34,16,12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 。 A 1 B 2 C 3 D 4正确答案C 8、已知某个哈希表的n个关键字具有相同的哈希值如果使用二次探测再散列法将这n个关键字存入哈希表至少要进行____次探测。 A n-1 B n C n1 D n(n1) E n(n1)/2 F 1n(n1)/2正确答案 E n个关键字入哈希表的过程 第一个元素入哈希表,1 第二个元素入哈希表,2 第三个元素入哈希表,3 … 第N个元素入哈希表n 123…n(1n)*n/29、下列选项中不可能是快速排序第2趟排序结果的是 A 2,3,5,4,6,7,9 B 2,7,5,6,4,3,9 C 3,2,5,4,7,6,9 D 4,2,3,5,7,6,9正确答案 C 每进行一次快排标定点一定处在最终位置 进行了两次快排则至少有两个元素到达最终位置。10、堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是 A O(N2)和O(1) B O(Nlog2N)和O(1) C O(Nlog2N)和O(N) D O(N2)和O(N)正确答案 B 二、编程题 年终奖 年终奖_牛客题霸_牛客网 【解题思路】 本题需要使用动态规划求解。 定义f(i,j)表示从左上角走到坐标(ij)处能获得的最大奖励。 搜索所有从左上角走到右下角的路径找到最优路径。 f(i,j)分三种情况 第一列f(i, 0) f(i-1, 0) board(i, 0) 第一行f(0,j) f(0, j - 1) b(0, j) 其它位置f(i, j) max{f(i-1, j), f(i, j - 1)} board(i, j) 最后返回右下角的值。
import java.util.*;
public class Bonus {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){//F(i, j) max(F(i - 1, j), F(i, j - 1)) board[i][j]board[i][j] Math.max(board[i - 1][j], board[i][j - 1]);}}return board[row - 1][col - 1];}
}迷宫问题
迷宫问题_牛客题霸_牛客网 【解题思路】 本题可用回溯法求解 具体步骤为
首先将当前点加入路径并设置为已走判断当前点是否为出口是则输出路径保存结果跳转到4依次判断当前点的上、下、左、右四个点是否可走如果可走则递归走该点当前点推出路径设置为可走
import java.util.*;
import java.io.*;
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) throws Exception{BufferedReader reader new BufferedReader(new InputStreamReader(System.in));String str;while((str reader.readLine()) ! null){String[] arr str.split( );int row Integer.parseInt(arr[0]);int col Integer.parseInt(arr[1]);//创建迷宫矩阵int[][] mat new int[row][col];//读入迷宫数据for(int i 0; i row; i){str reader.readLine();arr str.split( );for(int j 0; j col; j){mat[i][j] Integer.parseInt(arr[j]);}}//搜索最短路径ArrayListNode path new ArrayList();ArrayListNode 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 ));}}}//mat: 迷宫矩阵, row, col//x, y: 当前位置//book: 标记矩阵标记当前位置是否走过//path: 保存当前路径的每一个位置//minPath: 保存最短路径public static void getMinPath(int[][] mat, int row, int col,int x, int y, int[][] book, ArrayListNode path, ArrayListNode 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;}
}
