牛客网算法题（第二期）
一、模拟（牛牛的快递）
牛牛的快递_牛客题霸_牛客网
解题思路：
- 先判断输入的数字是否大于1（如果小于1，这部分运费直接为20，即sum=20；如果大于1，超过1的部分使用Math.ceil( )进行向上取整),即sum=20+(int)Math.ceil(a-1)
- 判断快递是否加急，如果加急在原基础上加5元，即sum+=5；如不加急直接输出sum
代码实现：
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); double a=in.nextDouble(); char c=in.next().charAt(0); int sum=0; if(a<1){ sum=20; }else{ sum=20+(int)Math.ceil(a-1); } if(c=='y'){ sum+=5; } System.out.println(sum); } }二、模拟（简写单词）
简写单词_牛客题霸_牛客网
解题思路：
- 用while循环获取每个单词首字母
- 如果是小写字母，转为大写输出；大写字母则直接输出
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); //hasNext判断输入流里是否还有下一个由空白（空格 / 回车 / Tab）隔开的单词 while (in.hasNext()) { char ch = in.next().charAt(0); if (ch >= 'a' && ch <= 'z') { //转大写 //System.out.print(Character.toUpperCase(ch)); System.out.print((char)(ch - 32)); } else { System.out.print(ch); } } } }注：ASCII 码规律：小写字母比对应大写字母大 32，如'a'-32='A'；
toUpperCase使用方法：
1.String 字符串调用 .toUpperCase ()
String s1 = "hello123";
String s2 = s1.toUpperCase();
System.out.println(s2); // HELLO123
2.单个 char 字符转大写：Character.toUpperCase (ch)
char 大写字符 = Character.toUpperCase(小写char变量);
三、模拟+贪心（数组中两个字符串最小距离）
数组中两个字符串的最小距离
解题思路（模拟 + 贪心）：
- 在一次遍历中，动态维护两个变量 pre1 和 pre2，分别记录 s1 和 s2最近一次出现的下标。同时用一个变量 ret 记录当前找到的最小距离。
- 遍历过程：
遍历数组下标 i（从 0 到 n-1）：
如果当前字符串
strs[i]等于s1：
检查
prev2 != -1（即s2之前是否出现过）。如果出现过，计算当前距离
i - prev2，并用Math.min(ret, i - prev2)更新最小距离。更新
prev1 = i（记录s1的最新位置）。如果当前字符串
strs[i]等于s2：
检查
prev1 != -1（即s1之前是否出现过）。如果出现过，计算当前距离
i - prev1，并用Math.min(ret, i - prev1)更新最小距离。更新
prev2 = i（记录s2的最新位置）。遍历结束后，如果
ret仍然是初始的无穷大值，说明两个字符串从未同时出现过，返回 -1；否则返回ret。贪心正确性：因为要求的是最近一次出现的距离，所以只需要维护最近一次出现的位置。当遇到一个目标字符串时，它只需要与另一个目标字符串最近一次出现的位置计算距离，这个距离一定是到当前为止、以该对位置为端点的最小可能距离。
import java.util.*; import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws Throwable{ BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); //将读入的字符串转为int n int n=Integer.parseInt(reader.readLine()); String[] str=reader.readLine().split(" "); //存下两个目标字符串 String s1=str[0],s2=str[1]; //将ret设为无穷大 //用两个变量 prev1、prev2分别记录上一次出现s1、s2的下标，初始-1代表还没出现过； int prev1=-1,prev2=-1,ret=0x3f3f3f3f; for(int i=0;i<n;i++){ String s=reader.readLine(); if(s.equals(s1)){ //如果之前出现过s2，计算当前i和上一次S2的距离 if(prev2 != -1){ ret=Math.min(ret,i-prev2); } prev1=i; } else if(s.equals(s2)){ if(prev1 != -1){ ret=Math.min(ret,i-prev1); } prev2=i; } } System.out.println(ret==0x3f3f3f3f ? -1 :ret); } }注：这道题 n 最大十万，属于大数据输入，Scanner 会超时，所以竞赛标准写法一律用BufferedReader提速
四、动态规划-线性dp（最小花费爬楼）
最小花费爬楼梯_牛客题霸_牛客网
解题思路（动态规划）：
- 定义 dp[i] 表示到达第 i 个台阶（下标 i）所需的最小花费。注意，这里“到达”意味着站在该台阶上，已经支付了从之前台阶跳上来的费用。
- 初始化：
- 根据题意，可以从下标 0 或 1 的台阶开始，这意味着站在 0 或 1 台阶上时，还没有支付任何费用，所以 dp[0]=0, dp[1]=0。
- 注意：cost数组的长度为n，楼梯顶部是下标 n，所以 dp 数组长度应为 n+1
。所以计算是从 i=2 开始递推到 i=n。- 状态转移方程：
- 要到达第 i 个台阶，可以从第
i-1个台阶爬 1 步上来，花费为dp[i-1] + cost[i-1]（到达 i-1 的最小花费 + 从 i-1 向上爬的费用）。- 也可以从第
i-2个台阶爬 2 步上来，花费为dp[i-2] + cost[i-2]。- 取两者最小值：
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。- dp[ n ] 即为到达楼梯顶部的最小花费。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n=in.nextInt(); int[] cost=new int[n]; int[] dp=new int[n+1]; //存入cost for(int i=0;i<n;i++){ cost[i]=in.nextInt(); } //第0个台阶和第1个台阶cost为0 if(n == 0|| n== 1){ System.out.println(cost[0]); return; } //一直填到第n个位置 for(int i=2;i<=n;i++){ dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } System.out.println(dp[n]); } }五、滑动窗口（dd爱框框）
dd爱框框
解题思路（滑动窗口）：
- 使用同向双指针（滑动窗口）维护一个区间
[left, right]，使得区间和sum满足sum ≥ x，并在满足条件时尽量缩小窗口以找到最短的满足条件的子数组。- 步骤：
- 初始化
left = 1,right = 1,sum = 0（题目数组下标从 1 开始）。- 用变量
retLeft,retRight记录当前找到的最优子数组的左右端点，retLen记录其长度，初始化为n（最大可能长度）。- 外层循环
while(right <= n)：
- 将
arr[right]加入sum。- 内层循环
while(sum >= x)：
- 此时窗口
[left, right]满足条件。计算当前窗口长度len = right - left + 1。- 如果
len < retLen，更新retLen,retLeft,retRight（因为right从左向右移动，相同长度下先遇到的窗口自然左端点更小，满足“最靠左”要求）。- 尝试缩小窗口：将
arr[left]从sum中减去，left++。right++继续扩大窗口。- 循环结束后，输出
retLeft和retRight。- 关键点：
- 单调性：由于数组元素均为正整数，当
right固定时，sum随left增大而单调递减。因此内层while可以安全地收缩窗口，不会错过更优解。- 时间复杂度：
O(n)，每个元素最多被加入和移出窗口各一次。- 下标处理：题目输入数组下标从 1 开始，代码中
arr长度为n+1，arr[0]未使用，循环从 1 开始。
import java.util.*; import java.io.*; //自己定义的输入类 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(); } String nextLine() throws IOException{ return bf.readLine(); } int nextInt() throws IOException{ return Integer.parseInt(next()); } long nextLong() throws IOException{ return Long.parseLong(next()); } double nextDouble() throws IOException{ return Double.parseDouble(next()); } } public class Main{ public static void main(String[] args) throws IOException{ Read in=new Read(); int n=in.nextInt(),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=-1,retRight=-1,retLen=n; while(right<=n){ sum+=arr[right]; while(sum>=x){ if(right-left+1<retLen){ retLeft=left; retRight=right; retLen=right-left+1; } sum-=arr[left]; left++; } right++; } System.out.println(retLeft+" "+retRight); } }注：写自定义Read快读类，本质是封装 BufferedReader+StringTokenizer，用来解决两个痛点：
1.BufferedReader每次只能读一整行，读数字、单词要自己切割、转类型，代码重复繁琐；
2.原生Scanner速度慢，大数据（1e5 级别输入）会超时，竞赛必须用更快的缓冲流。
Read 类就是对高速输入流的工具封装：提速 + 简化代码 + 复用，不用每次做题重复写 IO 切割、类型转换的重复代码。
六、贪心+堆（除2！）
除2！
解题思路
- 贪心策略：为了最小化总和，每次操作都应该选择当前最大的偶数进行除以 2 的操作。因为减少一个大的数对总和的减小效果最明显。
- 算法步骤：
- 读入所有数，计算初始总和
sum。- 遍历数组，将所有偶数加入大根堆
heap。- 进行
k次操作：
- 如果堆为空，说明没有偶数可操作，直接结束循环。
- 从堆中弹出当前最大偶数
t = heap.poll()。- 计算操作后的值
t / 2（整数除法，自动向下取整）。- 总和减少：
sum -= t / 2。- 如果操作后的新值
t/2仍然是偶数，则将其重新加入堆中，以备后续操作。- 输出最终的
sum。
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); int n=in.nextInt(),k=in.nextInt(); PriorityQueue<Integer> heap=new PriorityQueue<>((a,b)->{return b-a;}); long sum=0,x; for(int i=0;i<n;i++){ x=in.nextLong(); sum+=x; if(x%2==0){ heap.add((int)x); } } while(!heap.isEmpty() && k--!=0){ long t=heap.poll()/2; sum-=t; if(t%2==0){ heap.add((int)t); } } System.out.println(sum); } }注：大根堆的创建前面博客有详细讲解，如有不清楚可去看看哦
七、Java输出方法总结（print/println/printf）
7.1 print()
- 输出内容后不自动换行，多次输出会拼接在同一行
- 仅原样打印传入数据，无格式、无换行
System.out.print("a");
System.out.print("b");
// 输出：ab
7.2 println()
- print + line，打印完成自动末尾换行
- 不传参数时，直接输出空一行
System.out.println("a");
System.out.println("b");
/*输出
a
b
*/
7.3 printf()
- 格式化输出，支持占位符控制格式，不会自动换行
- 常用占位符:%s 字符串、%d 整数、%.2f 保留两位小数、%n 换行
System.out.printf("数字：%d，小数：%.2f%n", 10, 3.1415);
// 输出：数字：10，小数：3.14
| 方法 | 是否自动换行 | 核心用途 |
|---|---|---|
| ❌ 不换行 | 连续拼接输出 | |
| println | ✅ 自动换行 | 日常普通打印、调试 |
| printf | ❌ 不换行 | 控制格式、对齐、小数位数 |
八、小结
omg这是前几天写的题，以为很快会整理好，搞到这么晚了。今天还是很充实的，写了算法，还复习前面学的内容，还往后面学新内容了，美妙呢。算法题怎么说呢，靠近了它就靠近了痛苦，远离了它就远离了幸福。但是我们要知道终极目标——找到一份不错的工作，挣很多很多钱，就算再过几年ai让这碗饭吃不下去，我也要在那之前进厂捞一笔，哈哈哈哈。我明天要去逛超市，我又想吃榴莲了，我还想吃火锅，炸鸡，其实我一直觉得烤鸡比炸鸡好吃，但是不知道为什么突然很想吃炸鸡。太晚了犯猪瘾了是这样的（小结依旧碎碎念，梦到那句说那句，哈哈哈）