算法刷题整理合集（四）

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

1、反转字符串中的字符

实现一个算法来实现反转字符数组的功能。反转的要求如下：

1. 将字符数组的字符进行反转，例如 [‘b’, ’ ', ‘a’, ‘r’] 变成 [‘r’, ‘a’, ’ ', ‘b’]。
2. 将字符数组替换为反转后的数组。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String S = sc.nextLine();for (int i = S.length()-1; i >= 0; i--) {System.out.print(S.charAt(i));}}
}

2、最大化股票交易的利润

实现一个算法寻找最大化股票交易利润的策略。介绍如下：

• 股票价格每天都在变化，以数组的索引表示交易日，以数组的元素表示每天的股票价格。
• 可以通过买入和卖出获得利润。一天只能进行一次买入或卖出操作，一次买入加卖出操作称为一次交易次数。
• 你只能交易一次，求使得利润最大的交易策略。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] arr = new int[N];for (int i = 0; i < N; i++) {arr[i] = sc.nextInt();}sc.close();int max = -888;for (int i = 0; i < arr.length-1; i++) {for (int j = i+1; j < arr.length; j++) {int count = arr[j] - arr[i];if (count > max){max = count;}}}System.out.println(max);}
}

3、求解台阶问题

现一个算法求解台阶问题。介绍如下：

• 对于高度为 n 的台阶，从下往上走，每一步的阶数为 1，2，3 中的一个。问要走到顶部一共有多少种走法。

输入描述：

输入一个数字 N (1≤N≤35)N (1≤N≤35)，表示台阶的高度。

输出描述：

输出一行，为走法总数。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();System.out.println(reque(N));}// 迭代法public static int reque(int n){if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;int n1 = 1;int n2 = 2;int n3 = 4;int count = 0;for (int i = 4; i <= n; i++) {count = n1+n2+n3;n1 = n2;n2= n3;n3 = count;}return count;}
}

4、用杂志拼接信件

实现一个算法确定能否由杂志构成信件。介绍如下：

影视剧中信件大多是从报纸或杂志上的字符剪下来拼接而成的。

杂志和信件均由字符串构成，对于给定的杂志和信件，确定信件是否可以由杂志上的字符构成。

例如杂志为 ab，信件为 aa，则不能构成。杂志为 aab，信件为 aa，则可以构成。

输入描述：

输入两行字符串，长度均不超过 100。

第一行为杂志字符串，第二行为信件字符串。

输出描述：

输出一行，若信件可由杂志构成则输出 YES，否则输出 NO。

解题代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str1 = sc.nextLine();String str2 = sc.nextLine();boolean flag = true;for (int i = 0,j=0; i < str1.length()&&j < str2.length(); i++,j++) {if (str1.charAt(i) != str2.charAt(j)) {System.out.println("NO");flag = false;break;}}if (flag) System.out.println("YES");}
}

5、机器人的运动范围

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

注意:

1. 0<=m<=50
2. 0<=n<=50
3. 0<=k<=100

解题代码（BFS）：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main_BFS {// Node类作为点的封装，包含x，y横纵坐标的属性static class Node {int x;int y;public Node(int x,int y) {this.x = x;this.y = y;}}// 返回res 表示最终结果public static int MovingOn(int threshold, int rows, int cols) {if (rows == 0 && cols == 0) return 0;int res = 1;// move数组表示向右，下，左，上前进一格。int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};// book数组，0表示没走出，1表示走过。int[][] book = new int[rows][cols];// 机器人从(0,0)开始出发book[0][0] = 1;// 创建新的队列，用于记录机器人的坐标Queue<Node> queue = new LinkedList<>();queue.offer(new Node(0,0));// 当队列不为空时，也就是说机器人还有符合条件未抵达的坐标while (!queue.isEmpty()) {Node node = queue.poll();// 遍历上下左右四个方向，nx和ny记录坐标for (int i = 0; i < 4; i++) {int nx = node.x + move[i][0];int ny = node.y + move[i][1];// 判断坐标是方格内的，且未到达过，且行列的数位之和<=kif (nx >= 0 && ny >= 0 && nx < rows && ny < cols && book[nx][ny] == 0 && check(threshold,nx,ny)){res++;queue.offer(new Node(nx,ny));book[nx][ny] = 1;}}}return res;}// 判断行列坐标的每位数之和是否大于k，是就返回ture，反之falsestatic boolean check(int k, int i, int j) {int res = 0;while (i != 0) {res+= (i % 10);i /= 10;}while (j != 0){res += (j % 10);j /= 10;}return res <= k;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入格子大小m,n，以及横纵坐标之数位和小于等于kint k = sc.nextInt();int m = sc.nextInt();int n = sc.nextInt();System.out.println(MovingOn(k,m,n));}
}

解题代码（DFS）：

import java.util.Scanner;public class Main_DFS {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int k = sc.nextInt();int m = sc.nextInt();int n = sc.nextInt();System.out.println(movingOn(k,m,n));}// 确定机器人到达的格子public static int movingOn(int threshold, int rows, int cols) {// 标记机器人已经走过的格子boolean[][] flag = new boolean[rows][cols];int ans = dfs(threshold, rows, cols, 0, 0, flag);return ans;}// 深度优先搜索public static int dfs(int threshold, int rows, int cols, int x, int y, boolean[][] flag) {if (x < 0 || y < 0 || x >= rows || y >= cols || sum(x,y) > threshold || flag[x][y]) {return 0;}// 上+下+左+右+起始点flag[x][y] = true;int up = dfs(threshold, rows, cols, x -1, y, flag);int down = dfs(threshold, rows,cols, x  +1, y, flag);int left = dfs(threshold, rows, cols, x, y -1, flag);int right= dfs(threshold, rows, cols, x, y + 1, flag);return up + down + left + right + 1;}// 横纵坐标的数位之和public static int sum(int x, int y){int ans = 0;while (x > 0 || y > 0) {int n1 = x % 10;int n2 = y % 10;ans += n1 + n2;x /= 10;y /= 10;}return ans;}
}

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