一、模拟（牛牛的快递）

牛牛的快递_牛客题霸_牛客网

解题思路：

• 先判断输入的数字是否大于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，并在满足条件时尽量缩小窗口以找到最短的满足条件的子数组。
• 步骤：
  1. 初始化left = 1,right = 1,sum = 0（题目数组下标从 1 开始）。
  2. 用变量retLeft,retRight记录当前找到的最优子数组的左右端点，retLen记录其长度，初始化为n（最大可能长度）。
  3. 外层循环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++继续扩大窗口。
  4. 循环结束后，输出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 的操作。因为减少一个大的数对总和的减小效果最明显。
• 算法步骤：
  1. 读入所有数，计算初始总和sum。
  2. 遍历数组，将所有偶数加入大根堆heap。
  3. 进行k次操作：
     • 如果堆为空，说明没有偶数可操作，直接结束循环。
     • 从堆中弹出当前最大偶数t = heap.poll()。
     • 计算操作后的值t / 2（整数除法，自动向下取整）。
     • 总和减少：sum -= t / 2。
     • 如果操作后的新值t/2仍然是偶数，则将其重新加入堆中，以备后续操作。
  4. 输出最终的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

八、小结

omg这是前几天写的题，以为很快会整理好，搞到这么晚了。今天还是很充实的，写了算法，还复习前面学的内容，还往后面学新内容了，美妙呢。算法题怎么说呢，靠近了它就靠近了痛苦，远离了它就远离了幸福。但是我们要知道终极目标——找到一份不错的工作，挣很多很多钱，就算再过几年ai让这碗饭吃不下去，我也要在那之前进厂捞一笔，哈哈哈哈。我明天要去逛超市，我又想吃榴莲了，我还想吃火锅，炸鸡，其实我一直觉得烤鸡比炸鸡好吃，但是不知道为什么突然很想吃炸鸡。太晚了犯猪瘾了是这样的（小结依旧碎碎念，梦到那句说那句，哈哈哈）