【刷题册】2024.10.13 - 2024.10.15
目录
一、2024.10.13
1.1 BC153 [NOIP2010]数字统计
题目链接：BC153 [NOIP2010]数字统计
题目描述：
解题思路：
- 枚举，直接循环对两数字之间的所有数拆分看每个数的含2个数。
- 拆分方法：数字取余10，看个位数是否为2，然后让数字除10，直到数字小于0为止。
解题代码：
public static void main(String[] args) {
//输入
Scanner in = new Scanner(System.in);
int first = in.nextInt();
int last = in.nextInt();
int ret = 0;
for(int i = first; i <= last; i++) {
ret += count(i);
}
System.out.println(ret);
}
//记录数中2个数
private static int count(int num) {
int ret = 0;
while(num > 0) {
if(num % 10 == 2) ret++;
num = num / 10;
}
return ret;
}
1.2 NC313 两个数组的交集
题目链接：NC313 两个数组的交集
题目描述：
题目分析：就是找出两数组的相同元素，且结果数组中元素是不能重复的。
1.2.1 思路一：暴力O(N^2)
直接使用两层for循环，第一个for拿到nums1中的每一个数，与第二个中的所有元素进行比较，相同存入结果数组（注意结果数组中是否已经有了该数，如nums1 = {2,2}，nums2 = {2,2}）。
解题代码
public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
ArrayList<Integer> ret = new ArrayList<Integer>();
for(int i = 0; i < nums1.size(); i++) {
Integer cur = nums1.get(i);
for( int j = 0; j < nums2.size(); j++) {
if(cur.equals( nums2.get(j) )) {
//注意排除已经有的值
if(!ret.contains(cur)) ret.add(cur);
break;
}
}
}
return ret;
}
1.2.2 思路二：hash
将第一个数组存入hash表中，然后遍历第二个数组看hash表中是否有这个数。
但是由于数据范围是1000，是很小的，我们就不使用集合类HashMap，
直接使用一个布尔数组来表示，
- 遍历nums1数组，将nums1数组中元素作为布尔数组中true值的下标，其余为false；
- 在遍历nums2数组，看nums2数组中元素作为下标的布尔数组中只是不是true；
- 是true就将该元素存入结果数组中，并将布尔数组置为false（防止重复数据）。
public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
boolean[] hash = new boolean[1010];
ArrayList<Integer> ret = new ArrayList<Integer>();
for(int i = 0; i < nums1.size(); i++) {
hash[nums1.get(i)] = true;
}
for(int i = 0; i < nums2.size(); i++) {
if(hash[nums2.get(i)]) {
ret.add(nums2.get(i));
hash[nums2.get(i)] = false;
}
}
return ret;
}
1.3 AB5 点击消除
题目链接：AB5 点击消除
题目描述：
解题思路：
- 我们使用栈来模拟操作，拿到一个字母就与栈顶元素比较，相同就出栈，不同就进栈。
- 但是使用Stack类的话，我们最后拿到的栈顶到栈尾的，toString方法也不行。我们就使用StringBuilder来模拟实现。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.next();
StringBuilder ret = new StringBuilder("");
for(int i = 0; i <str.length(); i++) {
char ch = str.charAt(i);
if(ret.length() != 0 && ch == ret.charAt(ret.length()-1) ) {
//出栈
ret.deleteCharAt(ret.length()-1);
} else {
//进栈
ret.append(str.charAt(i));
}
}
//注意判断栈是否为空
System.out.println(ret.length() == 0? 0 : ret.toString());
}
二、2024.10.14
2.1 BC64⽜⽜的快递
题目链接：BC64 ⽜⽜的快递
题目描述：
题目解析：一道小学数学题，只介绍对小数的处理：
- 法1：直接调用Math类中的ceil()库方法向上取整；
- 法2：使用a-(int)a与0进行比较，看是否有小数，有就结果加1。
代码：
//法1：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
float a = in.nextFloat();
char b = in.next().charAt(0);
int ret = 20;
if(b == 'y') ret += 5;
if(a > 1.0) {
ret = ret - 1 + (int)Math.ceil(a);
}
System.out.println(ret);
}
//法二：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//输入处理
float a = in.nextFloat();
String str = in.nextLine();
char b = str.charAt(1);
int ret = 20;
//是否加急
if(b == 'y') ret += 5;
//是否超出1
if(a > 1) {
float temp = a - (int)a ;
//是否有小数
if(temp != 0.0) ret += 1;
ret = ret + (int)a - 1;
}
System.out.println(ret);
}
2.2 DP4 最⼩花费爬楼梯
题目链接：DP4 最⼩花费爬楼梯
题目描述：
题目分析：
这是一道简单的动态规划题目，看题目给出的实例终点是走出数组。
- 动态方程
dp[i] = Math.min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2]);
代码：
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] cost = new int[n];
cost[0] = in.nextInt();
int[] dp = new int[n+1];
for(int i = 2; i <= n; i++) {
cost[i-1] = in.nextInt();
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
System.out.println(dp[n]);
}
}
2.3 数组中两个字符串的最⼩距离
链接找不到，下架了
题目描述：
题目解析：
题目给得很明确，在strs数组中找str1和str2之间的最小距离。
解题思路：
- 法1：使用两层for循环，找到一个str1，就从当前开始找str2，如果结果ret更小，就更新。
- 法2：对法1的优化，我们只需要使用两个变量flag0和flag1分别表示当前找到的str1和str2的位置，在找到一个str1或者str2的时候与最近的相减（也就是flag1-flag0的绝对值）再与结果ret比较，小就更新。
import java.io.*;
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int len = Integer.parseInt(reader.readLine());
String[] strs = reader.readLine().split(" ");
String str1 = strs[0], str2 = strs[1];
String[] strs = new String[len];
for(int i = 0; i < len; i++) strs[i] = in.next();
int ret = 0x3f3f3f3f;
int flag0 = 0;
int flag1 = 0;
for(int i = 2; i < len ; i++) {
if(strs[i].equals(str1) ) {
flag0 = i;
}
if(strs[i].equals(str2)) {
flag1 = i;
}
if(ret == 0 || ret > Math.abs(flag1 - flag0)) ret = Math.abs(flag1 - flag0);
}
if(flag0 == 0 || flag1 == 0) System.out.println(-1);
else System.out.println(ret);
}
三、2024.10.15
3.1 BC149 简写单词
题目链接： BC149 简写单词
题目描述：
简单题不用解析。
代码：
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
char ch = in.next().charAt(0);
System.out.print((ch <= 'z'&& ch >= 'a') ? (char)(ch - 32) : ch);
}
}
}
3.2 dd爱框框
题目链接：dd爱框框
题目描述：
题目解析：题目要求我们找出最小区间中的数组元素和大于等于x的左右下标值。
解题思路：
- 暴力解法：使用两层for循环，一层i代表左下标，第二层j循环从i下标开始去求右下标，找到最小区间长度即可，但是数组长度n的值很大，这样是会超时的。
- 对暴力解法优化，滑动窗口/同向双指针：
2.1. 数组中的数据全是大于1的正数，证明当我们找到一个区间的数是大于x的时候left左指针向后走一位的时候，right–不会出现区间数组和变大的情况。
2.2 直接使用Scannner由于数据量大，会出现超时，要使用自定义快读类。
代码：
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
Read in = new Read();
int n = in.nextInt();
int x = in.nextInt();
int[] arr = new int[n+1];
for(int i = 1; i <= n; i++) {
arr[i] = in.nextInt();
}
int left = 1, right = 1,sum = 0;
int retLeft = 0, retRight = 0, retLen = 0X3f3f3f3f;
while(right <= n) {
//进窗口
sum += arr[right];
//更新结果
while(sum >= x) {
if(retLen > right - left + 1) {
retLeft = left;
retRight = right;
retLen = retRight - retLeft + 1;
}
//出窗口
sum -= arr[left++];
}
right++;
}
System.out.println(retLeft + " " + retRight);
}
}
class Read {
StringTokenizer st = new StringTokenizer("");
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String next() throws IOException {
while(!st.hasMoreTokens()) {
st = new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
3.3 除2！
题目链接：除2！
题目描述：
题目解析：这道题目就是给你最多k次让偶数除2操作，使最后数组元素和最小。
解题思路：
- 因为是对偶数除2，并且要让最后数组和尽可能小，那么我们就可以使用大根堆来存储偶数。
- 注意k只是最多可以操作的次数，有可能最后数组中已经没有偶数，而k的次数还没执行完；
- 我们先将给的数据和加起来，每出一次大根堆就减去，在判断除2后是不是还是偶数，是就进堆。
代码：
import java.util.Scanner;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
int k = in.nextInt();
PriorityQueue<Long> heap = new PriorityQueue<>((a,b) -> {
return (int)(b - a);
});
long sum = 0;
while(in.hasNextLong()) {
long temp = in.nextInt();
sum += temp;
if(temp % 2 == 0) {
heap.add(temp);
}
}
while(!heap.isEmpty() && k > 0) {
long temp = heap.poll() / 2;
sum -= temp;
if(temp % 2 == 0) {
heap.add(temp);
}
k--;
}
System.out.println(sum);
}
}
原文地址：https://blog.csdn.net/yj20040627/article/details/142905015
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！