【算法】实验室2024年二面纳新题复盘

2024-04-14 06:12

本文主要是介绍【算法】实验室2024年二面纳新题复盘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

实验室2024年二面纳新题复盘

P1258 小车问题

原题链接:

P1258 小车问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

小车问题

题目描述

甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车,可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样,且小于车的速度。问:怎样利用小车才能使两人尽快同时到达。

输入格式

仅一行,三个实数,分别表示 AB 两地的距离 s,人的步行速度 a,车的速度 b。

输出格式

两人同时到达 B 地需要的最短时间,保留 6 位小数。

样例 #1

样例输入 #1

120 5 25

样例输出 #1

9.600000

提示

数据规模与约定

对于 100% 的数据,保证 0 <= s, a, b <= 10^9。

首先确定最优解应该是让A与B同时开始走,开车带其中一人,而后走到一定时间再让车上的人下车,车返程去接另一人,然后再带着这一人前往终点,同时另一人步行,最终两人同时到达终点。

多说无益,上图:

这里B优先坐车,A步行为例。第一段时间B乘车走了S-X的路程,而A走了X的路程,车同时回到A所在的位置接到A,再带着A到终点,同时B也步行到了终点。

image-20240401165328481

根据上述过程,可以找到不变量s,a,b。同时,只要让 A步行的时间 等于车行走的时间,就可以求出两人到达时的最小时间。未知的变量是X与时间T。

可以列出方程如下图:

image-20240401172430975

解方程求出X,而后将X带入原式可以得出答案,这里贴出代码如下:

import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner sn = new Scanner(System.in);double s = sn.nextDouble();double a = sn.nextDouble();double b = sn.nextDouble();double x = (2 * a*s) /(3 *a+b);double t = x / a + (s - x) / b;System.out.printf("%f",t);}
}

值得注意的是:

本题中笔者首次接触到java的格式化输出,原来java里面是么得lf格式的(报错好久没发现问题)。此处贴出java f格式的用法,警钟长鸣。

f格式:用来输出实数(包括单、双精度),以小数形式输出。有以下几种用法:

%f:不指定宽度,整数部分全部输出并输出6位小数。

%m.nf:输出共占m列,其中有n位小数,如数值宽度小于m左端补空格。

%-m.nf:输出共占n列,其中有n位小数,如数值宽度小于m右端补空格。

P1125 [NOIP2008 提高组] 笨小猴

原题链接:

[P1125 NOIP2008 提高组] 笨小猴 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[NOIP2008 提高组] 笨小猴

题目描述

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!

这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn 是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。

输入格式

一个单词,其中只可能出现小写字母,并且长度小于 100 。

输出格式

共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出 Lucky Word,否则输出 No Answer

第二行是一个整数,如果输入单词是 Lucky Word,输出 \text{maxn}-\text{minn} 的值,否则输出 0 。

样例 #1

样例输入 #1

error

样例输出 #1

Lucky Word
2

样例 #2

样例输入 #2

olympic

样例输出 #2

No Answer
0

数组中找出最大的数和最小的数,相减判断质数即可。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String string = scanner.next();int[] hash = new int[26]; // 使用26来表示英文字母个数for (int i = 0; i < string.length(); i++) {char ch = string.charAt(i);if (Character.isLowerCase(ch)) { // 仅处理小写字母hash[ch - 'a']++;}}int max = 0;int min = 100;for (int i = 0; i < 26; i++) {if(hash[i] != 0){max = Math.max(max, hash[i]);min = Math.min(min, hash[i]);}}if (Check(max - min)) {System.out.println("Lucky Word");System.out.println(max - min);} else {System.out.println("No Answer");System.out.println(0);}}static boolean Check(int num) {if (num <= 1) {return false;}for (int i = 2; i * i <= num; i++) {if (num % i == 0) {return false;}}return true;}
}

P1506 拯救oibh总部

原题链接:

P1506 拯救oibh总部 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

拯救oibh总部

题目背景

oibh 总部突然被水淹没了!现在需要你的救援……

题目描述

oibh 被突来的洪水淹没了,还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示,而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域,每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图,问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 x,y 。

接下来 x 行,每行 y 个整数,由 *0 组成,表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

样例 #1

样例输入 #1

4 5
00000
00*00
0*0*0
00*00

样例输出 #1

1

样例 #2

样例输入 #2

5 5
*****
*0*0*
**0**
*0*0*
*****

样例输出 #2

5

笔者对DFS暂且理解不深,就不献丑了,贴上题解代码,日后深入学习了DFS,再将本题拿出来拷打。

import java.util.*;
public class Main{static Scanner sc=new Scanner(System.in);static int N=sc.nextInt();static int M=sc.nextInt();static char a[][]=new char[501][501];static int dx[]= {0,1,0,-1};static int dy[]= {1,0,-1,0};public static void main(String[] args) {// TODO Auto-generated method stubfor(int i=1;i<=N;i++){String s=sc.next();for(int j=1;j<=M;j++){a[i][j]=s.charAt(j-1);}}//本质上就是外围的0全部被淹没,里面被包围的0幸存 因此从外围开始dfs,把外围的0全都染色了for(int i=1;i<=M;i++)  //这里的N和M搞错了!固定行,求列应该用M{//第一行if(a[1][i]=='0') dfs(1,i);//最后一行if(a[N][i]=='0') dfs(N,i);}for(int j=1;j<=N;j++){//第一列if(a[j][1]=='0') dfs(j,1);//最后一列if(a[j][M]=='0') dfs(j,M);}int count=0;for(int i=1;i<=N;i++){for(int j=1;j<=M;j++){if(a[i][j]=='0') count++;}}System.out.println(count);}public static void dfs(int x,int y){a[x][y]=3;  //先染色for(int i=0;i<4;i++){int newx=x+dx[i];int newy=y+dy[i];if(newx>=1&&newx<=N&&newy>=1&&newy<=M&&a[newx][newy]=='0'){//不越界且为0,则继续给这些外围的0染色dfs(newx,newy);}}}}

P1160 队列安排2

原题链接:

P1160 队列安排 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

队列安排

题目描述

一个学校里老师要将班上 N 个同学排成一列,同学被编号为 1 ~ N ,他采取如下的方法:

  1. 先将 1 号同学安排进队列,这时队列中只有他一个人;

  2. 2 ~ N 号同学依次入列,编号为 i 的同学入列方式为:老师指定编号为 i 的同学站在编号为 1 ~ i - 1 中某位同学(即之前已经入列的同学)的左边或右边;

  3. 从队列中去掉 M 个同学,其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 N ,表示了有 N 个同学。

第 2 ~ N 行,第 i 行包含两个整数 k,p ,其中 k 为小于 i 的正整数, p 为 0 或者 1 。若 p 为 0 ,则表示将 i 号同学插入到 k 号同学的左边, p 为 1 则表示插入到右边。

第 N+1 行为一个整数 M ,表示去掉的同学数目。

接下来 M 行,每行一个正整数 x ,表示将 x 号同学从队列中移去,如果 x 号同学已经不在队列中则忽略这一条指令。

输出格式

一行,包含最多 N 个空格隔开的整数,表示了队列从左到右所有同学的编号。

样例 #1

样例输入 #1

4
1 0
2 1
1 0
2
3
3

样例输出 #1

2 4 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;class Node {int value;Node prev, next;Node(int value) {this.value = value;}
}public class Main {static BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {int N = Integer.parseInt(scan.readLine());Map<Integer, Node> nodeLookup = new HashMap<>();Node head = new Node(1);nodeLookup.put(1, head);//首先读取一个整数N,然后读取N行输入。每一行都包含一个整数X和一个标志B。//它在列表中查找值为X的元素,然后在其之前(如果B为0)或者之后(如果B为1)插入新的元素。//新元素的值为当前的循环次数(从2开始)。如果找不到值为X的元素,那么新元素将不会被插入。for (int i = 2; i <= N; i++) {String[] input = scan.readLine().split(" ");int X = Integer.parseInt(input[0]);int B = Integer.parseInt(input[1]);Node newNode = new Node(i);Node oldNode = nodeLookup.get(X);if (B == 0) {newNode.next = oldNode;newNode.prev = oldNode.prev;if (oldNode.prev != null) {oldNode.prev.next = newNode;}oldNode.prev = newNode;if (oldNode == head) {head = newNode;}} else {newNode.prev = oldNode;newNode.next = oldNode.next;if (oldNode.next != null) {oldNode.next.prev = newNode;}oldNode.next = newNode;}nodeLookup.put(i, newNode);}//然后,读取一个整数M,然后读取M行输入。每一行包含一个整数,表示需要从列表中删除的元素。int M = Integer.parseInt(scan.readLine());for (int i = 0; i < M; i++) {int data = Integer.parseInt(scan.readLine());Node nodeToRemove = nodeLookup.get(data);if (nodeToRemove != null) {if (nodeToRemove.prev != null) {nodeToRemove.prev.next = nodeToRemove.next;}if (nodeToRemove.next != null) {nodeToRemove.next.prev = nodeToRemove.prev;}if (nodeToRemove == head) {head = nodeToRemove.next;}nodeLookup.remove(data);}}for (Node node = head; node != null; node = node.next) {System.out.print(node.value + " ");}}
}

B3640 T3 句子反转

原题链接:

B3640 T3 句子反转 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

T3 句子反转

题目背景

请尽量在 30min 之内写完题目。这是指「写代码」的时间;「读题」时间不计算在内。

题目描述

给定一行句子,每个词之间用空格隔开,要么是全小写英文单词,要么是全大写英文单词,要么是自然数。

要求将这些单词倒序输出。而且对于每个单词,如果是小写词,应当转为大写;如果是大写词,应当转为小写;如果是自然数,应该倒转输出。

举一个例子:

we choose TO go 2 the 123 moon

程序应当输出:

MOON 321 THE 2 GO to CHOOSE WE

输入格式

仅一行,即需要反转的句子。

输出格式

仅一行,表示程序对句子的处理结果。

样例 #1

样例输入 #1

we choose TO go 2 the 123 moon

样例输出 #1

MOON 321 THE 2 GO to CHOOSE WE

提示

样例解释

首先应当按单词逆序,即:

moon 123 the 2 go TO choose we

小写变大写、大写变小写、倒转自然数之后,得到最终结果:

MOON 321 THE 2 GO to CHOOSE WE
数据规模与约定

对于 100% 的数据,句子中包含的单词数量不超过 1000 ,每个单词长度不超过 6 。

字符串反转并不陌生,但如果加上一些限制条件呢?

其实也不难,笔者做的时候居然在获取字符串的地方犯难了,罪过罪过,后来查资料才知道java应该如何获取字符串,而后对字符串进行一些操作:

先介绍思路,再贴上一些没用过的方法吧~

首先将整个字符串反转,然后用快慢指针找到每个单词,分别对这些单词进行操作即可。

import java.util.Scanner;
public class Main{static void Reverse(char[] string,int left,int right){while(left <= right) {char temp = string[left];string[left] = string[right];string[right] = temp;left++;right--;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();char[] string = s.toCharArray();int len = string.length;int slow = 0;int fast = len;//先将整体翻转Reverse(string,slow,fast-1);//fast指向某个单词的结尾,slow指向某个单词的开始for(fast = 0;fast < len;fast++){//fast指针停在某个单词后的空格处while(fast < len && string[fast] != ' '){fast++;}Reverse(string,slow,fast-1);int left = slow;int right = fast -1;//按照题目要求分别处理if (Character.isLowerCase(string[left])) {while (left <= right) {string[left] = Character.toUpperCase(string[left]);left++;}} else if (Character.isUpperCase(string[left])) {while (left <= right) {string[left] = Character.toLowerCase(string[left]);left++;}} else {while (left <= right) {char t = string[left];string[left] = string[right];string[right] = t;left++;right--;}}// 继续向后移动slow = fast + 1;}System.out.println(string);}
}

这里贴上笔者写题的时候不会用或者比较陌生的方法:

Character 类

序号方法与描述
1isLetter() 是否是一个字母
2isDigit() 是否是一个数字字符
3isWhitespace() 是否是一个空白字符
4isUpperCase() 是否是大写字母
5isLowerCase() 是否是小写字母
6toUpperCase() 指定字母的大写形式
7toLowerCase() 指定字母的小写形式
8toString() 返回字符的字符串形式,字符串的长度仅为1

P1059 [NOIP2006 普及组] 明明的随机数

原题链接:

[P1059 NOIP2006 普及组] 明明的随机数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[NOIP2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N\leq100) ,对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行,第 1 行为 1 个正整数,表示所生成的随机数的个数 N。

第 2 行有 N 个用空格隔开的正整数,为所产生的随机数。

输出格式

输出也是两行,第 1 行为 1 个正整数 M,表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

10
20 40 32 67 40 20 89 300 400 15

样例输出 #1

8
15 20 32 40 67 89 300 400

​ 全部放到数组中,两次遍历代替去重操作,然后sort排序即可。

import java.util.Scanner;import static java.util.Arrays.sort;public class Main{public static void main(String[] args) {int num = 0;Scanner s = new Scanner(System.in);num = s.nextInt();int[] hash = new int[1001];for(int i = 0;i < num;i++){int tmp = 0;tmp = s.nextInt();hash[tmp]++;}int j = 0;for(int i = 0;i <= 1000;i++){if(hash[i] > 0){j++;}}int[] arr = new int[j];int cnt = 0;for(int i = 0;i <= 1000;i++){if(hash[i] > 0){arr[cnt++] = i;}}sort(arr);System.out.println(j);for(int i = 0;i < arr.length;i++){System.out.printf("%d ",arr[i]);}}
}

P3817 小A的糖果

原题链接:

P3817 小A的糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

小A的糖果

题目描述

小 A 有 n 个糖果盒,第 i 个盒中有 a_i 颗糖果。

小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 x ,至少得吃掉几颗糖。

输入格式

输入的第一行是两个用空格隔开的整数,代表糖果盒的个数 n 和给定的参数 x 。

第二行有 n 个用空格隔开的整数,第 i 个整数代表第 i 盒糖的糖果个数 a_i 。

输出格式

输出一行一个整数,代表最少要吃掉的糖果的数量。

样例 #1

样例输入 #1

3 3
2 2 2

样例输出 #1

1

样例 #2

样例输入 #2

6 1
1 6 1 2 0 4

样例输出 #2

11

样例 #3

样例输入 #3

5 9
3 1 4 1 5

样例输出 #3

0

提示

样例输入输出 1 解释

吃掉第 2 盒中的一个糖果即可。


样例输入输出 2 解释

第 2 盒糖吃掉 6 颗,第 4 盒吃掉 2 颗,第 6 盒吃掉 3 颗。

import java.util.Scanner;
public class Main{public static void main(String[] args) {long sum = 0;Scanner sc = new Scanner(System.in);int n = sc.nextInt();int x = sc.nextInt();long[] a = new long[n + 1];a[1] = sc.nextInt();if(a[1] > x){sum += a[1] - x;a[1] = x;}for(int i = 2;i <= n;i++){a[i] = sc.nextInt();if(a[i] + a[i-1] > x){sum += a[i] + a[i-1] - x;a[i] = x - a[i-1];}}System.out.println(sum);}
}

Sp. 低洼地

image-20240402133325740

先去重再遍历,没啥好说的,放代码~

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = scanner.nextInt();}int newIndex = 0;for (int i = 0; i < n; i++) {if (i == 0 || arr[i] != arr[i - 1]) {arr[newIndex++] = arr[i];}}n = newIndex;int cnt = 0;for (int i = 1; i < n - 1; i++) {if (arr[i] < arr[i + 1] && arr[i] < arr[i - 1]) {cnt++;}}System.out.println(cnt);}
}

这篇关于【算法】实验室2024年二面纳新题复盘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/902277

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费