常见的企业网站有哪些,wordpress 标签,洛阳最新通告今天,网站开发难度和小程序开发难度蓝桥杯刷题——day3 题目一题干题目解析代码 题目二题干题目解析代码 题目一
题干
每张票据有唯一的 ID 号#xff0c;全年所有票据的 ID 号是连续的#xff0c;但 ID 的开始数码是随机选定的。因为工作人员疏忽#xff0c;在录入 ID 号的时候发生了一处错误#xff0c;造… 蓝桥杯刷题——day3 题目一题干题目解析代码 题目二题干题目解析代码 题目一
题干
每张票据有唯一的 ID 号全年所有票据的 ID 号是连续的但 ID 的开始数码是随机选定的。因为工作人员疏忽在录入 ID 号的时候发生了一处错误造成了某个 ID 断号另外一个 ID 重号。你的任务是通过编程找出断号的 ID 和重号的 ID。数据保证断号不可能发生在最大和最小号。 输入格式 一个整数 N(N100) 表示后面数据行数接着读入N行数据每行数据长度不等是用空格分开的若干个不大于100个正整数不大于10的5次方每个整数代表一个 ID 号。 输出格式 要求程序首先输入要求程序输出1 行含两个整数mn用空格分隔其中m表示断号 IDn表示重号 ID。 示例一 输入 2 5 6 8 11 9 10 12 9 输出 7 9 示例二 输入 6 164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196 172 189 127 107 112 192 103 131 133 169 158 128 102 110 148 139 157 140 195 197 185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190 149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188 113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119 输出 105 120 题目链接错误票据
题目解析
这道题目挺有意思的其实不难输入部分我们就不过多介绍我们可以创建一个Arraylist用作存储没输入一个数字就将数字存储到Arraylist中去然后用排序将Arraylist从小到大进行排序从后往前遍历当发现两个数字相等的时候则该数字就是重复的ID当发现两个数字相差大于1的时候就发现该数字为丢失的数字。下面为完整代码
代码
import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 输入行数int line scanner.nextInt();ArrayListInteger list new ArrayList();// 读取所有 IDfor (int i 0; i line; i) {while (scanner.hasNextInt()) {list.add(scanner.nextInt());}}// 排序 IDCollections.sort(list);// 找出断号和重号int missing 0, duplicate 0;for (int i 1; i list.size(); i) {if (list.get(i).equals(list.get(i - 1))) {duplicate list.get(i); // 找到重号} else if (list.get(i) list.get(i - 1) 1) {missing list.get(i - 1) 1; // 找到断号}}// 输出结果System.out.println(missing duplicate);}
}
题目二
题干
小青蛙住在一条河边它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线小青蛙每次跳跃必须落在一块石头或者岸上。不过每块石头有一个高度每次小青蛙从一块石头起跳这块石头的高度就会下降1当石头的高度下降到0时小青蛙不能再跳到这块石头上某次跳跃后使石头高度下降到0 是允许的)。小青蛙一共需要去学校上x 天课所以它需要往返2x 次。当小青蛙具有一个跳跃能力y 时它能跳不超过y 的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。 输入格式 输入的第一行包含两个整数n,x, 分别表示河的宽度和小青蛙需要去学校的天数。请注意2x 才是实际过河的次数。第二行包含n−1 个非负整数 表示在河中与 小青蛙的家相距i的地方有一块高度为h的石头h0则表示没有石头。 输出格式 输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。 示例一 输入 5 1 1 0 1 0 输出 4 题目链接青蛙过河
题目解析
这是一个典型的二分查找加模拟的问题。小青蛙需要在有限的石头高度和跳跃能力的限制下完成往返 2x 次。以下是解决问题的详细思路
最小跳跃能力y 的范围是从 1 到n我们可以用二分查找找到最小的y使得小青蛙能够完成2x 次过河。给定一个跳跃能力y模拟小青蛙的跳跃过程检查是否能完成2x 次过河。然后每次跳跃时石头高度减 1不能跳到高度为 0 的石头上。判断是否满足条件的方法用模拟实现。如果当前 y 能够完成2x 次过河则尝试更小的 y否则增加 y。
下面是完整代码
代码
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 输入河宽度和需要去学校的天数int n scanner.nextInt();int x scanner.nextInt();// 输入石头高度int[] stones new int[n];for (int i 1; i n; i) {stones[i] scanner.nextInt();}// 二分查找最低跳跃能力int left 1, right n, result n;while (left right) {int mid (left right) / 2;if (canCross(stones.clone(), mid, 2 * x)) {result mid; // 当前跳跃能力可行尝试更小值right mid - 1;} else {left mid 1; // 当前跳跃能力不足增加跳跃能力}}// 输出结果System.out.println(result);}// 判断是否能完成指定次数的过河public static boolean canCross(int[] stones, int jump, int trips) {int n stones.length;for (int t 0; t trips; t) {int position 0; // 从起点出发while (position n - 1) {int next position;// 找到能跳到的最远位置for (int j position 1; j n j position jump; j) {if (stones[j] 0) {next j;}}if (next position) {// 无法前进跳跃失败return false;}// 跳到 next石头高度减 1stones[next]--;position next;}}return true; // 成功完成所有 trips}
}
main函数其实很好理解就是一个二分查找的问题我们看canCross函数在这个函数模拟小青蛙从起点出发经过石头跳到对岸的过程。外层循环 for (int t 0; t trips; t)循环模拟小青蛙过河的过程。因为小青蛙需要往返2x 次所以我们要模拟trips 次跳跃while (position n - 1)循环则检查小青蛙是否跳到了对岸for (int j position 1; j n j position jump; j) 循环则是找小青蛙能跳到的最远距离当我们发现next position时就表明小青蛙一动不动也就是跳跃失败否则石头的高度减去1并且更新position。这段代码我并没有完全通过编译器其出现的问题我也不太清楚如果发现问题欢迎私信和评论感谢各位的点赞。
