算法刷题整理合集（一）

算法刷题整理合集（一）

本篇博客旨在记录自已的算法刷题练习成长，里面注有详细的代码注释以及和个人的思路想法，希望可以给同道之人些许帮助。本人也是算法小白，水平有限，如果文章中有什么错误或遗漏之处，望各位可以在评论区指正出来，各位共勉💪。

1、砍竹子

这天, 小明在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 i 棵竹子的 高度为 hi。

他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么用一次魔法可以 把这一段竹子的高度都变为|√|H/2| +1|, 其中 ⌊x⌋ 表示对 x 向下取整。小明想 知道他最少使用多少次魔法可

让所有的竹子的高度都变为 1 。

用例规模：
对于 20% 的数据, 保证 n≤1000, hi≤10^6 。 对于 100% 的数据, 保证 n ≤ 2×10^5, hi ≤ 10^18 。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();  // 读取输入的整数n,代表竹子数量。long[][] num = new long[n + 1][10];// 创建一个二维数组num,用于存储每个竹子的高度序列。long[] std = new long[10];  //  创建一个一维数组刷std，用于存储每个主子在计算过程中的高度。long count = 0;  // 初始化计数器count，用于统计总高度序列的长度for (int i = 1; i <= n; i++) {  // 遍历每个竹子int top = 0;  // 初始化数组std的索引long h = sc.nextLong();  // 读取当前竹子的高度std[top] = h;  // 将高度存入std数组while (h > 1){  // 当高度大于1时继续循环top++;  // std数组索引递增h=sqrt(h/2+1); // 根据规则计算新的高度std[top]=h; // 将新的高度存入std数组}for(int j=0,k=top-1;k>=0;k--,j++){ // 将std数组逆序存入num数组的对应位置num[i][j]=std[k];}count+=top; // 将当前竹子的高度序列长度加到count上}// 遍历二维数组num，检查相邻竹子之间是否有相同的高度，如果有则减少countfor(int i=0;i<10;i++){ // 遍历高度序列的每一位for(int j=2;j<=n;j++){ // 从第二个竹子开始遍历if(num[j][i]>0&&num[j][i]==num[j-1][i])count--; // 如果当前竹子高度大于0且与前一个竹子相同，则减少count}}System.out.println(count); // 输出最终的count值，即所有竹子高度序列的总长度（去重后）}// 自定义的求平方根的函数，用于替代Math.sqrt，因为Math.sqrt不支持long类型public static long sqrt(long h){long x=0; // 初始化结果xlong start=1l,end=(long)1e9,mid=0; // 初始化二分查找的起始、结束和中间值while(start<=end){ // 二分查找平方根mid=(start+end)/2; // 计算中间值if(mid*mid<=h){ // 如果中间值的平方小于等于hx=mid; // 更新结果xstart=mid+1; // 缩小查找范围到右半部分}else end=mid-1; // 否则缩小查找范围到左半部分}return x; // 返回结果x}
}

2、01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

数据范围：

0<N, V ≤1000
0<vi, wi ≤1000

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) throws Exception{Scanner sc = new Scanner(System.in);int N = sc.nextInt();int V = sc.nextInt();// 表示物品数量和背包容积。int[] v = new int[N+1];int[] w = new int[N+1];// 第 i 件物品的体积和价值。for (int i = 1; i <= N; i++) {v[i] = sc.nextInt();w[i] = sc.nextInt();}sc.close();// ②01问题int[] dp = new int[V+1];dp[0] = 0;for(int i = 1; i <= N; i++){for(int j = V; j >= v[i]; j--){dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);}}System.out.println(dp[V]);}
}

3、蓝桥村的真相

在风景如画的蓝桥村，n名村民围坐在一张古老的圆桌旁，参与一场思想的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。
当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为 i 的村民提出了这样的断言：坐在他之后的两位村民—也就是编号i+1和i+2(注意，编号是环形的，所以如果i是最后一个，则i+1是第一个，以此类推)之中，一个说的是真话，而另一个说的是假话。
在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后?
请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，说谎者的总数。

用例规模：

对于 10% 的评测用例，T = 1，3 ≤ n ≤ 10。

对于 40% 的评测用例，1 ≤ T ≤ 10^2，3 ≤ n ≤ 3 x 10^3

对于所有评测用例，1 ≤ T ≤ 10^5，3 ≤ n ≤ 10^18

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 表示数据的组数。int T = sc.nextInt();long[] Result = new long[T];for (int i = 0; i < T; i++) {// 表示村落的人数long k = sc.nextLong();// 当取余3不等于0时，则村落人数即为所有真假组合中，说谎者的总数if (k%3 != 0) {Result[i] = k;}else {long s = k/3;Result[i] = k+s*3;}}// 所有真假组合中，说谎者的总数for (int i = 0; i < T; i++) {System.out.println(Result[i]);}}
}

4、商品库存管理

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从1至 n。初始时，每种商品的库存量均为 0。

为了高效地监控和调整库存量，小蓝的管理团队设计了m个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围(例如区间 [L，R] )。执行这些操作时，区间内每种商品的库存量都将增加 1。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，每个操作未执行时，库存量为0 的商品的种类数。

用例规模：

对于20%的评测用例，1 ≤ n，m ≤ 5×10^3，1 ≤ L ≤ R ≤ n 。

对于所有评测用例，1≤ n，m≤ 3*10^5，1 ≤ L ≤ R ≤ n。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] operate = new int[m][2]; // 记录每次的操作区间int[] d = new int[n + 2]; // 差分数组，索引范围 0 到 n+1// 读取操作并更新差分数组for (int i = 0; i < m; i++) {int L = scan.nextInt();int R = scan.nextInt();operate[i][0] = L;operate[i][1] = R;// 更新差分数组d[L]++;if (R + 1 <= n) {d[R + 1]--;}}// 计算每个商品的库存操作次数总和int[] sum = new int[n + 1];for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + d[i];}// 预处理前缀和数组，统计库存为 0 和 1 的商品数量int[] preZero = new int[n + 1]; // 前缀和数组，统计库存为 0 的商品数量int[] preOne = new int[n + 1];  // 前缀和数组，统计库存为 1 的商品数量for (int i = 1; i <= n; i++) {preZero[i] = preZero[i - 1];preOne[i] = preOne[i - 1];if (sum[i] == 0) {preZero[i]++;} else if (sum[i] == 1) {preOne[i]++;}}// 计算未进行任何撤回操作时库存为 0 的商品数量int zeroCount = preZero[n];// 处理每个操作for (int i = 0; i < m; i++) {int L = operate[i][0];int R = operate[i][1];// 计算区间内库存为 0 和 1 的商品数量int cntZero = preZero[R] - preZero[L - 1];int cntOne = preOne[R] - preOne[L - 1];// 计算结果int res = (zeroCount - cntZero) + cntOne;System.out.println(res);}}
}

5、神奇闹钟

小蓝发现了一个神奇的闹钟，从纪元时间(1970年1月1日00:00:00)开始，每经过 x 分钟，这个闹钟便会触发一次闹铃(纪元时间也会响铃)。这引起了小蓝的兴趣，他想要好好研究下这个闹钟。

对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss 的时间小蓝想要知道在这个时间点之前(包含这个时间点)的最近的一次闹铃时间是哪个时间?
注意，你不必考虑时区问题。

用例规模：

对于所有评测用例，1 ≤ T ≤ 10，1 ≤ x ≤ 1000，保证所有的时间格式都是合法的。

解题代码：

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Scanner;public class Main06 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt();sc.nextLine();DateTimeFormatter ft = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss");// 定义自定义格式LocalDateTime startTime = LocalDateTime.of(1970,1,1,0,0,0);// LocalDateTime.of()用于创建一个指定年月日时分秒的LocaldateTime对象for (int i = 0; i < T; i++) {String input = sc.nextLine(); // 读取输入String[] parts = input.split(" "); // 将输入的字符串分为三部分String dateTimeStr = parts[0]+" "+parts[1]; // 1，2部分为时间int x = Integer.parseInt(parts[2]);//3部分为闹铃时间间隔LocalDateTime dateTime = LocalDateTime.parse(dateTimeStr, ft); // format将字符串转为时间// LocalDateTime.parse()将字符串解析为LocalDateTime对象，需要指定格式long delteMin = java.time.Duration.between(startTime, dateTime).toMinutes();//获取总的时间间隔// Duration.between 用于计算时间间隔，toMinutes()转换为分钟数long n = delteMin / x; // 求有多少个闹铃间隔时间xLocalDateTime result = startTime.plusMinutes(n*x); System.out.println(result.format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));}}
}

6、拉马车

小的时候，你玩过纸牌游戏吗？

有一种叫做"拉马车"的游戏，规则很简单，却很吸引小朋友。

其规则简述如下：

假设参加游戏的小朋友是 A 和 B ，游戏开始的时候，他们得到的随机的纸牌序列如下：

AA 方：[K,8,X,K,A,2,A,9,5,A]

BB 方：[2,7,K,5,J,5,Q,6,K,4]

其中的 XX 表示 “10”，我们忽略了纸牌的花色。

从 A 方开始，A、B双方轮流出牌。

当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。

此例中，游戏过程：

A出K，B出2，A出8，B出7，A出X，此时桌上的序列为:K,2,8,7,X

当轮到 B 出牌时，他的牌 K 与桌上的纸牌序列中的 K 相同，则把包括 K 在内的以及两个 K 之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。

此时，A、B双方的手里牌为：

A 方：[K,A,2,A,9,5,A]

B 方：[5,J,5,Q,6,K,4,K,X,7,8,2,K]

赢牌的一方继续出牌。也就是 B接着出5，A出K，B出J，A出4，B 出5，又赢牌了。此时桌上的序列为：

5, K ,J ,A ,5

此时双方手里牌：

A 方：[2,A,9,5,A]

B 方：[Q,6,K,4,K,X,7,8,2,K,5,A,J,K,5]

注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。

当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。

对于本例的初始手牌情况下，最后 A 会输掉，而 B 最后的手里牌为：

9K2A62KAX58K57KJ5

本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出 -1。

输入描述

输入为 2 行，2 个串，分别表示 A*、*B 双方初始手里的牌序列。我们约定，输入的串的长度不超过 30。2J9A7QA6Q6889977

输出描述

输出为 1 行，1 个串，表示 A 先出牌，最后赢的一方手里的牌序。

解题代码：

import java.util.Scanner;public class Main {public static boolean isflagA = true;public static boolean isflagB = false;public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 1.定义A,B,桌面的牌String a = sc.nextLine();String b = sc.nextLine();// A ,B, 桌面StringBuilder A = new StringBuilder(a);StringBuilder B = new StringBuilder(b);StringBuilder C = new StringBuilder();sc.close();while (true){// 判断是否继续出牌if (isflagA){play(A,C, true);// A手中牌为空时，则B赢，游戏结束if (A.length() == 0){System.out.println(B);break;}} else if (isflagB) {// B手中牌为空时，则A赢，游戏结束play(B,C,false);if (B.length() == 0){System.out.println(A);break;}}}}// 2.当你出的牌与桌面上有相同的牌，则将其之间的牌倒序收回到自己的牌堆，并继续出牌//当A,B其中一方手中为空时，则游戏结束，当游戏无法结束输出-1.// 出牌阶段public static void play(StringBuilder x, StringBuilder y, boolean isflag){if (x.length() == 0) return; // 判断手牌是否为空// 查找手牌中第一张，在牌堆里是否有相同的char front = x.charAt(0);int pos = y.indexOf(String.valueOf(front));// 当牌堆里不存在时，则下一个人出牌if (pos == -1){y.insert(0,front);isflagA = !isflag;isflagB = isflag;}else {// 当存在时，则将其包含在内的牌倒叙收回手牌里x.append(front);for (int i = 0; i <= pos; i++) {x.append(y.charAt(i));}// 去掉桌面上收回的牌y.delete(0,pos+1);// 收回后，继续出牌if (isflag){isflagA = true;isflagB = false;}else {isflagA = false;isflagB = true;}}x.deleteCharAt(0);}
}

有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~✨️✨️✨️