1、丢失报文的位置
某通信系统持续向外发送报文,使用数组 nums 保存 n个最近发送的报文,用于在报文未达到对端的情况下重发。报文使用序号 sn 表示,序号 sn 按照报文发送顺序从小到大排序,相邻报文 sn 不完全连续且有可能相同。报文使用循环覆盖的方式保存,即 nums 数组填满后,从头开始保存新的报文。假设需要重发序号为 sn 的报文。请找出序号为 sn的报文在数组中的开始位置和结束位置。
输入
第一行输入:数组 nums 的大小 n,取值范围 [0,10000]。
第二行输入:数组中的所有报文的序号 sn,sn 取值范围 [0,100000]。
第三行输入:需要重发的报文序号 sn,取值范围 [0,100000]。
输出
start end
说明:start 和 end 代表需要重发的报文序号 sn 在数组中的起始下标和结束下标。
样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
输入: 7 0 0 1 2 2 5 6 1 输出: 2 2 提示: nums数组大小为7。 保存了7个报文,sn分别是0 0 1 2 2 5 6。 sn为1的报文在数组中仅有1个,下标是2,因此输出2 2。 输入: 7 0 0 1 2 2 5 6 2 输出: 3 4 提示: nums数组大小为7。 保存了7个报文,sn分别是0 0 1 2 2 5 6。 sn为2的报文在数组中有2个,下标分别是3,4,因此输出3 4。 输入: 7 4 4 7 8 2 3 4 4 输出: 6 1 提示: nums数组大小为7。 保存了7个报文,sn分别是4 4 7 8 2 3 4。 sn为4的报文在数组中有3个,下标分别是0,1,6,说明数组存在记录满了从头开始记录的情况,输出6 1。 输入: 7 4 4 7 8 2 3 4 6 输出: -1 -1 提示: nums数组大小为7。 保存了7个报文,sn分别是4 4 7 8 2 3 4。 数组中不存在sn为6的报文,因此输出-1 -1。 输入: 5 5 5 5 5 5 5 输出: 0 4 提示: nums数组大小为5 保存了5个报文,sn分别是5 5 5 5 5 数组中所有报文sn都是5,这种情况下认为0是start,4是end,输出0 4。 |
思路
在本题中给定了保存的报文的需序号,这些序号是由发送顺序决定的,我们找到这段数组中最小的一个序号,然后从他开始遍历,标记开始的位置和结束的位置即可
代码
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
int x = scanner.nextInt();
int p = minElementIndex(a);
int l = -1, r = -1;
for (int i = 0; i < n; i++) {
int q = (p + i) % n;
if (a[q] == x) {
if (l == -1) {
l = q;
}
r = q;
}
}
System.out.println(l + " " + r);
}
public static int minElementIndex(int[] arr) {
int minIndex = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
}
2、快速传球
班级组织传球活动,男女同学随机排成 m 行 n 列队伍,第一列中的任意一个男同学都可以作为传球的起点,要求最终将球传到最后一列的任意一个男同学手里,求所有能够完成任务的传球路线中的最优路线(传球次数最少的路线)的传球次数。传球规则:
- 男同学只能将球传给男同学,不能传给女同学。
- 球只能传给身边前后左右相邻的同学。
- 如果游戏不能完成,返回 - 1.
说明:
- 传球次数最少的路线为最优路线。
- 最优路线可能不唯一,不同最优路线都为最少传球次数。
输入
班级同学随机排成的 m 行 n 列队伍,1 代表男同学,0 代表女同学。
输入第一行包含两个用空格分开的整数 m(m∈[1,30]) 和 n(n∈[1,30]),表示 m 行 n 列的队伍,接下来是 m 行每行包含 n 个用空格分开的整数 1 或 0。
输出
最优路线的传球次数(最少传球次数)。
样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
输入: 4 4 1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 输出: 5 提示: 图一 图二 图三 . . . 0 . . 1 0 1 1 1 0 1 1 . 0 1 . . 0 . . . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 1 . . 0 1 . . 0 1 . . 图一传球路线需要传球6次。 图二传球路线需要传球6次。 图三传球路线需要传球5次,传球次数最少,为最优传球路线。 输入: 3 4 1 0 1 1 1 1 0 0 0 0 1 0 输出: -1 提示: 选择第1行第1列的男同学作为起点,无法实现按规则将球到最后一列男同学手里。 选择第2行第1列的男同学作为起点,无法实现按规则将球到最后一列男同学手里。 |
解答
文章来源地址https://www.uudwc.com/A/0kjnA/
解答
声明一个d[][]去计算和存储到达最后一列男生的步数,d[][]同时也起到了记录该点位是否被访问的作用
在初始化阶段将第一列男生入队列,实现多元的bfs遍历。
最终打印最后一列所有男生中d[][]最小的那个值
代码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class test {
static final int N = 35;
static final int[] dx = {0,0,1,-1};
static final int[] dy = {1,-1,0,0};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] s = new int[N][N]; // 记录地图
int[][] d = new int[N][N]; // 计算到达最后一列男生的最小步
for(int i = 1;i<=n;i++){
for (int j = 1;j<=m;j++ ){
s[i][j] = in.nextInt();
d[i][j] = -1;
}
}
Queue<int []> q = new LinkedList<>();
for(int i=1;i<=n;i++){ // 初始化第一列,将第一列男生入队列
if (s[i][1] == 1){
d[i][1] = 0;
q.offer(new int[]{i,1});
}
}
while (!q.isEmpty()){ // bfs搜索
int[] front = q.poll();
int sx = front[0];
int sy = front[1];
for(int i=0;i<4;i++){
int x = sx+dx[i];
int y = sy+dy[i];
if((x < 1) || (y < 1) || (x > n) || (y > m) || d[x][y]!=-1 || s[x][y]==0){
continue;
}
d[x][y] = d[sx][sy]+1;
q.offer(new int[]{x,y});
}
}
int ans = Integer.MAX_VALUE;
for (int i = 1; i<=n;i++){
if(s[i][m] == 1){
ans = Math.min(ans,d[i][n]);
}
}
if(ans == Integer.MAX_VALUE){
ans = -1;
}
System.out.println(ans);
}
}
3、简易计算器
设计一款计算器软件,支持以下功能:
1支持 let
关键字。
2支持通过 let
赋值表达式定义变量并初始化。
例如:
1 2 |
let var1 = 123 let var = 123 |
3.变量需要先定义再引用,在表达式中引用未定义的变量,则表达式的结果也是未定义的。
例如:
1 2 3 4 |
let var1 = 1 let var2 = var1 + 1 // var1是定义的 let var3 = var4 + 1 // var4是未定义的 let var4 = 1 |
4.支持整数类型数据,整数数据的输入格式只需要支持十进制,支持负整数,整数取值范围 −2147483648≤≤2147483647。
例如:
1 2 |
let var3 = 10 let var3 = -10 |
5.支持整数的加 (+
)、减 (-
)、乘 (*
)、除 (/
) 四则运算,四则运算符之间没有优先级,运算数遵循左结合律,用例不考虑括号。
例如:
1 |
let var4 = 1 + 2 * var3 |
上述表达式的计算顺序是,先计算 1+2 结果为 3,再将 3 乘以 var3
得到表达式的结果。
6.支持通过 out
函数打印变量的值,函数参数只接受 1 个变量,不需要支持表达式。
例如:
1 2 |
let var4 = 12 out(var4) // 将会输出12 |
7.表达式中如果引用了未定义的变量,则表达式的结果是未定义的。
8.如果计算结果溢出,则表达式结果是溢出。
9.变量命名符合通用语言变量规范,必须是以下划线 (_
) 或者字母开头,遇到标点符号或者空格符时结束。
例如:
1 2 3 4 5 6 7 8 |
let _ = 1 // 变量名_是合法的 let _abc = 1 // 合法 let abc = 1 // 合法 let Abc_1 = 1 // 合法 let abc.x = 1 // 非法 let abc,x = 1 // 非法 let 12abc = 1 // 非法 let abc x = 1 // 非法 |
输入
- 每一行只有一个表达式。
- 最多支持 24 行输入。
- 每个用例输入至少有一个
out
输出表达式,可以有多个out
输出表达式。 - 每个变量只会赋值 1 次。
例如:
1 2 3 4 |
let var1 = 1 let var2 = 3 let var3 = var1 + var2 out(var3) |
输出
- 每遇到 1 个
out
输出表达式,则打印输出变量的值。 - 对于
out
行,只会输出一个out
表达式的值。 - 如果
out
输出的变量未定义,则打印<undefined>
- 如果表达式结果发生了整数上溢或者下溢,则对该变量的
out
输出表达式输出<underflow>
或者<overflow>
- 如果表达式非法,则打印
<syntax-error>
样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
输入: let var1 = 1 out(var1) 输出: 1 输入: out(var) 输出: <undefined> 提示: 输出的var变量未定义。 输入: let var1 = 1 let var2 = 3 let var3 = var1 + var2 out(var3) out(var2) out(var) let var4 = -2147483649 let var5 = 2147483648 out(var4) out(var5) let x.y = 1 输出: 4 3 <undefined> <underflow> <overflow> <syntax-error> |
解答
大型模拟,定义相关函数,校验各个字符的正确性之后进行相关运算,
在计算算式的时候采用跨越一个字符的方法遍历,实现计算
代码
# coding=utf-8
ls = []
mn = -(1<<31)
mx = (1<<31) - 1
inf = 10 ** 50
SYNTAX_ERROR = "<syntax-error>"
UNDEFINED = "<undefined>"
UNDERFLOW = "<underflow>"
OVERFLOW = "<overflow>"
mp = {}
try:
while True:
s = input()
ls.append(s)
except EOFError:
pass # ctrl+d结束输入
# 变量命名符合通用语言变量规范,必须是以下划线 (_) 或者字母开头,遇到标点符号或者空格符时结束。
def is_variable_name(name):
if len(name) == 0:
return False
if not (name[0].isalpha() or name[0]=='_'):
return False
for ch in name[1:]:
if not (ch.isalpha() or ch.isdigit() or ch == "_"):
return False
return True
# 支持整数类型数据,整数数据的输入格式只需要支持十进制,支持负整数,
def is_int(s):
try:
int(s)
return True
except ValueError:
return False
# 将字符串转化为数字,如果他本身就是数字,返回这个数字,如果他是字母,则返回字典中他对应的数据
def convert_int(s):
if is_int(s):
return int(s)
elif s in mp.keys():
return mp[s]
else:
return None
# 处理let后面的字符串
def parse_let(s):
s = s.strip() #消除空白字符
l,r = s.split('=')
l,r = l.strip(),r.strip()
if not is_variable_name(l):
return SYNTAX_ERROR
ls = r.split(' ')
if len(ls) % 2 == 0: # 如果右侧的元素个数为偶数,则说明有问题
return SYNTAX_ERROR
for i in range(0,len(ls),2): #校验右侧的字符
if not is_variable_name(ls[i]) and not is_int(ls[i]):
return SYNTAX_ERROR
for i in range(1,len(ls),2): #校验右侧的运算符
if not (len(ls[i])==1 and ls[i] in "+-*/"):
return SYNTAX_ERROR
v = convert_int(ls[0])
for i in range(1,len(ls),2): # 进行加减运算
op,w = ls[i],convert_int(ls[i+1])
if w is None:
return
if op == '+':
v += w
elif op == '-':
v -= w
elif op == '*':
v *= w
else:
v //= w
if v>mx:
v = inf
break
elif v<mn:
v = -inf
break
mp[l] = v
# 输出字符串对应的数字
def parse_out(s):
s = s[1:-1] # 去除括号
if s in mp.keys():
x = mp[s]
if x>mx:
return OVERFLOW
elif x<mn:
return UNDEFINED
return x
else:
return UNDEFINED
for s in ls:
if len(s) >= 3 and s[:3] == "let":
t = parse_let(s[3:])
if t is not None:
print(t) #报错处理
elif len(s) >= 3 and s[:3] == "out":
print(parse_out(s[3:]))
else:
print(SYNTAX_ERROR)
文章来源:https://www.uudwc.com/A/0kjnA/