一、模拟牛牛的快递牛牛的快递_牛客题霸_牛客网解题思路先判断输入的数字是否大于1如果小于1这部分运费直接为20即sum20如果大于1超过1的部分使用Math.ceil( )进行向上取整),即sum20(int)Math.ceil(a-1)判断快递是否加急如果加急在原基础上加5元即sum5如不加急直接输出sum代码实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); double ain.nextDouble(); char cin.next().charAt(0); int sum0; if(a1){ sum20; }else{ sum20(int)Math.ceil(a-1); } if(cy){ sum5; } 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-32AtoUpperCase使用方法1.String 字符串调用 .toUpperCase ()String s1 hello123;String s2 s1.toUpperCase();System.out.println(s2); // HELLO1232.单个 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 readernew BufferedReader(new InputStreamReader(System.in)); //将读入的字符串转为int n int nInteger.parseInt(reader.readLine()); String[] strreader.readLine().split( ); //存下两个目标字符串 String s1str[0],s2str[1]; //将ret设为无穷大 //用两个变量 prev1、prev2分别记录上一次出现s1、s2的下标初始-1代表还没出现过 int prev1-1,prev2-1,ret0x3f3f3f3f; for(int i0;in;i){ String sreader.readLine(); if(s.equals(s1)){ //如果之前出现过s2计算当前i和上一次S2的距离 if(prev2 ! -1){ retMath.min(ret,i-prev2); } prev1i; } else if(s.equals(s2)){ if(prev1 ! -1){ retMath.min(ret,i-prev1); } prev2i; } } System.out.println(ret0x3f3f3f3f ? -1 :ret); } }注这道题 n 最大十万属于大数据输入Scanner 会超时所以竞赛标准写法一律用BufferedReader提速四、动态规划-线性dp最小花费爬楼最小花费爬楼梯_牛客题霸_牛客网解题思路动态规划定义 dp[i] 表示到达第 i 个台阶下标 i所需的最小花费。注意这里“到达”意味着站在该台阶上已经支付了从之前台阶跳上来的费用。初始化根据题意可以从下标 0 或 1 的台阶开始这意味着站在 0 或 1 台阶上时还没有支付任何费用所以 dp[0]0, dp[1]0。注意cost数组的长度为n楼梯顶部是下标 n所以 dp 数组长度应为 n1。所以计算是从 i2 开始递推到 in。状态转移方程要到达第 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 nin.nextInt(); int[] costnew int[n]; int[] dpnew int[n1]; //存入cost for(int i0;in;i){ cost[i]in.nextInt(); } //第0个台阶和第1个台阶cost为0 if(n 0|| n 1){ System.out.println(cost[0]); return; } //一直填到第n个位置 for(int i2;in;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长度为n1arr[0]未使用循环从 1 开始。import java.util.*; import java.io.*; //自己定义的输入类 class Read{ StringTokenizer stnew StringTokenizer(); BufferedReader bfnew BufferedReader(new InputStreamReader(System.in)); String next() throws IOException{ while(!st.hasMoreTokens()){ stnew 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 innew Read(); int nin.nextInt(),xin.nextInt(); int[] arrnew int[n1]; for(int i1;in;i){ arr[i]in.nextInt(); } int left1,right1,sum0; int retLeft-1,retRight-1,retLenn; while(rightn){ sumarr[right]; while(sumx){ if(right-left1retLen){ retLeftleft; retRightright; retLenright-left1; } sum-arr[left]; left; } right; } System.out.println(retLeft retRight); } }注写自定义Read快读类本质是封装 BufferedReaderStringTokenizer用来解决两个痛点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 innew Scanner(System.in); int nin.nextInt(),kin.nextInt(); PriorityQueueInteger heapnew PriorityQueue((a,b)-{return b-a;}); long sum0,x; for(int i0;in;i){ xin.nextLong(); sumx; if(x%20){ heap.add((int)x); } } while(!heap.isEmpty() k--!0){ long theap.poll()/2; sum-t; if(t%20){ heap.add((int)t); } } System.out.println(sum); } }注大根堆的创建前面博客有详细讲解如有不清楚可去看看哦七、Java输出方法总结print/println/printf7.1 print()输出内容后不自动换行多次输出会拼接在同一行仅原样打印传入数据无格式、无换行System.out.print(a);System.out.print(b);// 输出ab7.2 println()print line打印完成自动末尾换行不传参数时直接输出空一行System.out.println(a);System.out.println(b);/*输出ab*/7.3 printf()格式化输出支持占位符控制格式不会自动换行常用占位符:%s 字符串、%d 整数、%.2f 保留两位小数、%n 换行System.out.printf(数字%d小数%.2f%n, 10, 3.1415);// 输出数字10小数3.14方法是否自动换行核心用途print❌ 不换行连续拼接输出println✅ 自动换行日常普通打印、调试printf❌ 不换行控制格式、对齐、小数位数八、小结omg这是前几天写的题以为很快会整理好搞到这么晚了。今天还是很充实的写了算法还复习前面学的内容还往后面学新内容了美妙呢。算法题怎么说呢靠近了它就靠近了痛苦远离了它就远离了幸福。但是我们要知道终极目标——找到一份不错的工作挣很多很多钱就算再过几年ai让这碗饭吃不下去我也要在那之前进厂捞一笔哈哈哈哈。我明天要去逛超市我又想吃榴莲了我还想吃火锅炸鸡其实我一直觉得烤鸡比炸鸡好吃但是不知道为什么突然很想吃炸鸡。太晚了犯猪瘾了是这样的小结依旧碎碎念梦到那句说那句哈哈哈
牛客网算法题（第二期）
一、模拟牛牛的快递牛牛的快递_牛客题霸_牛客网解题思路先判断输入的数字是否大于1如果小于1这部分运费直接为20即sum20如果大于1超过1的部分使用Math.ceil( )进行向上取整),即sum20(int)Math.ceil(a-1)判断快递是否加急如果加急在原基础上加5元即sum5如不加急直接输出sum代码实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); double ain.nextDouble(); char cin.next().charAt(0); int sum0; if(a1){ sum20; }else{ sum20(int)Math.ceil(a-1); } if(cy){ sum5; } 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-32AtoUpperCase使用方法1.String 字符串调用 .toUpperCase ()String s1 hello123;String s2 s1.toUpperCase();System.out.println(s2); // HELLO1232.单个 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 readernew BufferedReader(new InputStreamReader(System.in)); //将读入的字符串转为int n int nInteger.parseInt(reader.readLine()); String[] strreader.readLine().split( ); //存下两个目标字符串 String s1str[0],s2str[1]; //将ret设为无穷大 //用两个变量 prev1、prev2分别记录上一次出现s1、s2的下标初始-1代表还没出现过 int prev1-1,prev2-1,ret0x3f3f3f3f; for(int i0;in;i){ String sreader.readLine(); if(s.equals(s1)){ //如果之前出现过s2计算当前i和上一次S2的距离 if(prev2 ! -1){ retMath.min(ret,i-prev2); } prev1i; } else if(s.equals(s2)){ if(prev1 ! -1){ retMath.min(ret,i-prev1); } prev2i; } } System.out.println(ret0x3f3f3f3f ? -1 :ret); } }注这道题 n 最大十万属于大数据输入Scanner 会超时所以竞赛标准写法一律用BufferedReader提速四、动态规划-线性dp最小花费爬楼最小花费爬楼梯_牛客题霸_牛客网解题思路动态规划定义 dp[i] 表示到达第 i 个台阶下标 i所需的最小花费。注意这里“到达”意味着站在该台阶上已经支付了从之前台阶跳上来的费用。初始化根据题意可以从下标 0 或 1 的台阶开始这意味着站在 0 或 1 台阶上时还没有支付任何费用所以 dp[0]0, dp[1]0。注意cost数组的长度为n楼梯顶部是下标 n所以 dp 数组长度应为 n1。所以计算是从 i2 开始递推到 in。状态转移方程要到达第 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 nin.nextInt(); int[] costnew int[n]; int[] dpnew int[n1]; //存入cost for(int i0;in;i){ cost[i]in.nextInt(); } //第0个台阶和第1个台阶cost为0 if(n 0|| n 1){ System.out.println(cost[0]); return; } //一直填到第n个位置 for(int i2;in;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长度为n1arr[0]未使用循环从 1 开始。import java.util.*; import java.io.*; //自己定义的输入类 class Read{ StringTokenizer stnew StringTokenizer(); BufferedReader bfnew BufferedReader(new InputStreamReader(System.in)); String next() throws IOException{ while(!st.hasMoreTokens()){ stnew 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 innew Read(); int nin.nextInt(),xin.nextInt(); int[] arrnew int[n1]; for(int i1;in;i){ arr[i]in.nextInt(); } int left1,right1,sum0; int retLeft-1,retRight-1,retLenn; while(rightn){ sumarr[right]; while(sumx){ if(right-left1retLen){ retLeftleft; retRightright; retLenright-left1; } sum-arr[left]; left; } right; } System.out.println(retLeft retRight); } }注写自定义Read快读类本质是封装 BufferedReaderStringTokenizer用来解决两个痛点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 innew Scanner(System.in); int nin.nextInt(),kin.nextInt(); PriorityQueueInteger heapnew PriorityQueue((a,b)-{return b-a;}); long sum0,x; for(int i0;in;i){ xin.nextLong(); sumx; if(x%20){ heap.add((int)x); } } while(!heap.isEmpty() k--!0){ long theap.poll()/2; sum-t; if(t%20){ heap.add((int)t); } } System.out.println(sum); } }注大根堆的创建前面博客有详细讲解如有不清楚可去看看哦七、Java输出方法总结print/println/printf7.1 print()输出内容后不自动换行多次输出会拼接在同一行仅原样打印传入数据无格式、无换行System.out.print(a);System.out.print(b);// 输出ab7.2 println()print line打印完成自动末尾换行不传参数时直接输出空一行System.out.println(a);System.out.println(b);/*输出ab*/7.3 printf()格式化输出支持占位符控制格式不会自动换行常用占位符:%s 字符串、%d 整数、%.2f 保留两位小数、%n 换行System.out.printf(数字%d小数%.2f%n, 10, 3.1415);// 输出数字10小数3.14方法是否自动换行核心用途print❌ 不换行连续拼接输出println✅ 自动换行日常普通打印、调试printf❌ 不换行控制格式、对齐、小数位数八、小结omg这是前几天写的题以为很快会整理好搞到这么晚了。今天还是很充实的写了算法还复习前面学的内容还往后面学新内容了美妙呢。算法题怎么说呢靠近了它就靠近了痛苦远离了它就远离了幸福。但是我们要知道终极目标——找到一份不错的工作挣很多很多钱就算再过几年ai让这碗饭吃不下去我也要在那之前进厂捞一笔哈哈哈哈。我明天要去逛超市我又想吃榴莲了我还想吃火锅炸鸡其实我一直觉得烤鸡比炸鸡好吃但是不知道为什么突然很想吃炸鸡。太晚了犯猪瘾了是这样的小结依旧碎碎念梦到那句说那句哈哈哈
