目录
- 1.薯券使用问题
- 2.笔记草稿
- 3.笔记精选
- 4.倒卖战利品
- 5.字符串倒序
- 6.迷宫游戏
1.薯券使用问题
某小红薯在小红书的活动中抽奖中了一定价值的薯券，这些薯券可以用来购买一批商品，求有多少种购买组合。其中一件商品可以买多件。
输 入:薯券金额、商品分别价格
输出 :组合数
输入描述:
输入薯券金额、商品分别价格 例如：10 [2,3,5] 10与[2,3,5]中间有空格
输出描述:
输出4，则结果集可以为:2,2,2,2,2；5,5；2,3,5；2,2,3,3共有4种组合
输入例子1:
10 [2,3,5]
输出例子1:
4
这是一道动态规划的题目，是一个背包问题，与leetcode518题属于一个类型的题目。
定义数组
dp[i][j]
表示金额为j的情况下，对于前i种商品，最多可以有多少种组合。
初始状态：
dp[...][0] = 1
表示在金额为0的情况下，无论有几种商品，只能有一种组合，那就是什么都不取这一种。
状态转移：
- 如果不选择当前第i个商品，组合的数目应该是
dp[i-1][j]
- 如果选择当前第i个商品，组合的数目应该是
dp[i][j-prices[i-1]]
当前组合数应该是两者的和：
dp[i][j] = dp[i-1][j] + dp[i][j - prices[i-1]]
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int sum = scanner.nextInt();
String next = scanner.next();
int length = next.length();
String subString = next.substring(1,length-1);
String[] split = subString.split(",");
int[] prices = new int[split.length];
for(int i = 0;i < split.length;i++){
prices[i] = Integer.parseInt(split[i]);
}
//定义dp[][]存储组合数
int[][] dp = new int[prices.length+1][sum+1];
//初始状态，在金额为零的情况下，只能选择什么都不选这一种组合
for(int i = 0;i < dp.length;i++){
dp[i][0] = 1;
}
for(int i = 1; i <= prices.length;i++){
for(int j = 1; j <= sum;j++){
//如果当前的金额小于总金额，可以选择选也可以选择不选
if(prices[i-1] <= j){
dp[i][j] = dp[i-1][j]+dp[i][j-prices[i-1]];
}else{
//如果当前的金额大于总金额，不可以选择
dp[i][j] = dp[i-1][j];
}
}
}
System.out.print(dp[prices.length][sum]);
}
}
2.笔记草稿
薯队长写了一篇笔记草稿，请你帮忙输出最后内容。
1.输入字符包括，"(" , “)” 和 "<“和其他字符。
2.其他字符表示笔记内容。
3.()之间表示注释内容，任何字符都无效。 括号保证成对出现。
4.”<“表示退格, 删去前面一个笔记内容字符。括号不受”<"影响 。
输入描述:
输入一行字符串。长度<=10000.
输出描述:
输出一行字符串，表示最终的笔记内容。
输入例子1:
Corona(Trump)USA<<
输出例子1:
CoronaVirus
本题目在leetcode有一道括号匹配的题目，leetcode使用的是栈来解决的，这道题可以不适用栈，更为简单。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.next();
char[] arr = str.toCharArray();
int count = 0;
String res = "";
for(int i=0;i<arr.length;i++){
if(arr[i] == '('){
count ++;
}else if(arr[i] == ')'){
count --;
}else if(arr[i] == '<' && count == 0 && res.length() > 0){
res = res.substring(0,res.length()-1);
}else{
if(count == 0){
res += arr[i];
}
}
}
System.out.print(res);
}
}
3.笔记精选
薯队长写了n篇笔记，编号从1~n,每篇笔记都获得了不少点赞数。
薯队长想从中选出一些笔记，作一个精选集合。挑选的时候有两个规则：
1.不能出现连续编号的笔记。
2.总点赞总数最多
如果满足1，2条件有多种方案，挑选笔记总数最少的那种
输入描述:
输入包含两行。第一行整数n表示多少篇笔记。 第二行n个整数分别表示n篇笔记的获得的点赞数。 （0<n<=1000,
0<=点赞数<=1000)
输出描述:
输出两个整数x,y。空格分割。 x表示总点赞数，y表示挑选的笔记总数。
输入例子1:
4
1 2 3 1
输出例子1:
4 2
这是一道动态规划类型的题目。与leetcode打家劫舍很相似。
首先这道题需要定义两个数组：
dp[i]:表示前i篇笔记，可以获取的最大点赞数；
flag[i]表示前i篇笔记，需要选取的笔记数；
状态转移矩阵：
dp[i] = Math.max(dp[i-1],dp[i-2]+books[i-1])
表示:由于笔记编号不能相连，当在前i篇笔记中进行选取，能获取的最大点赞数，要么是不选第i篇，取d[i-1]，要么是选第i篇，取dp[i-1]+nums[i-1];
初始条件：
dp[0]=0;dp[1]=books[0];
flag[0]=0;flag[1]=1;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); //获取所有的笔记数
int[] books = new int[n];//定义数组存储每一个笔记对应的点赞数
for(int i=0; i<n; i++){
books[i] = scanner.nextInt();
}
int[] dp = new int[n+1];//dp[i]表示选取前i篇笔记，总点赞数
int[] flag = new int[n+1];//flag[i]表示选取前i篇笔记，所选择的笔记数
flag[1] = 1; //当选择1篇的时候，只能选择第一篇
dp[1] = books[0];
for(int i = 2;i<=n;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+books[i-1]);
if(dp[i-1] == dp[i]){//说明没有选择第i篇
flag[i] = flag[i-1];
}else{//选择第i篇
flag[i] = flag[i-2]+1;
}
}
System.out.println(dp[n] + " " + flag[n]);
}
}
4.倒卖战利品
在游戏中，击败魔物后，薯队长获得了N件宝物，接下来得把这些宝物卖给宝物回收员来赚点小钱。这个回收员有个坏毛病，每次卖给他一件宝 物后，之后他就看不上比这件宝物差的宝物了。在这个世界中，衡量宝物的好坏有两个维度，稀有度X和实用度H，回收员在回收一个宝物A 后，下一个宝物的稀有度和实用度都不能低于宝物A。那么薯队长如何制定售卖顺序，才能卖给回收员宝物总个数最多。
输入描述:
第一行一个正整数N。 接下来N行。每行两个整数分别表示X 和 H
X1 H1
X2 H2
…
XN HN
输入限制：
对于70%的数据：
0<N<10^4
0<Xi<10^6
0<Hi<10^6
100%的数据：
0<N<10^6
0<Xi<10^6
0<Hi<10^6
输出描述:
一个整数，表示最多可以卖出的宝物数
示例1
输入
4
3 2
1 1
1 3
1 2
输出
3
按照一个维度排序后按照另一个维度寻找最长增加子序列即可.
方法一：使用两层循环，案例通过80%；
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] nums = new int[n][2];
for(int i = 0;i < n;i++){
nums[i][0] = scanner.nextInt();
nums[i][1] = scanner.nextInt();
}
Arrays.sort(nums,(a,b)->(a[0]==b[0]?a[1]-b[1]:a[0]-b[0]));
int[] dp = new int[n];
Arrays.fill(dp,1);
for(int i = 0;i < n;i++){
for(int j = 0;j < i;j++){
if(nums[i][1]>nums[j][1]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
}
int res = 1;
for(int i = 0;i < dp.length;i++){
res = Math.max(res,dp[i]);
}
System.out.print(res);
}
}
5.字符串倒序
薯队长带着小红薯参加密室逃脱团建游戏，首先遇到了反转游戏，小红薯们根据游戏提示收集了多个单词线索，并将单词按要求加一个空格组 成了句子，最终要求把句子按单词反转解密。 说明：收集的时候单词前后可能会有多个空格，反转后单词不能有多个空格，具体见输入输出样例。
输入描述:
输入一个字符串。包含空格和可见字符。长度<=100000。
输出描述:
输出一个字符串，表示反转后结果。
输入例子1:
the sky is blue!
输出例子1:
blue! is sky the
注意next() 和 nextLine()之间的区别：
abc def ghij
kl mno pqr st
uvw xyz
next()，第一次取的是abc，第二次取的是def，第三次取的是ghij
nextLine()，第一次取的是abc def ghij，第二次取的是kl mno pqr st，第三次取的是uvw xyz
前一个是以回车或空格为分隔符，一次取一个单词；
后一个是以回车为分隔符，一次取一行。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();//取一行
String[] strArr = str.trim().split(" +");//去掉前后的空格，并且以正则化表达式的形式分割
String res = "";
for(int i = strArr.length-1;i > 0;i--){
res = res+strArr[i]+" ";
}
res += strArr[0];
System.out.print(res);
}
}
6.迷宫游戏
薯队长最近在玩一个迷宫探索类游戏，迷宫是一个N*N的矩阵形状，其中会有一些障碍物禁止通过。这个迷宫还有一个特殊的设计，它的左右 边界以及上下边界是连通的，比如在(2,n)的位置继续往右走一格可以到(2,1)，在(1,2)的位置继续往上走一格可以到(n,2)。请问薯队长从起点位置S，最少走多少格才能到达迷宫的出口位置E。
输入描述:
第一行正整数N,接下来N行字符串
’.’表示可以通过
’#’表示障碍物
’S’表示起点（有且仅有一个）
’E’表示出口（有且仅有一个）
对于50%的数据N<10
对于100%的数据N<10^3
输出描述:
输出一个整数。表示从S到E最短路径的长度, 无法到达则输出 -1
示例1
输入
5
.#…
…#S.
.E###
…
…
输出
4
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
char[][] grid = new char[n][n];
int xStart = -1,yStart = -1;
int xEnd = -1, yEnd = -1;
//注意要换行
scanner.nextLine();
//每一行读取，一共n行
for(int i = 0; i < n; i++){
String str = scanner.nextLine();
char[] charArray = str.toCharArray();
//对一行的字符进行遍历，存入的二维数组中
for(int j = 0;j < n; j++){
grid[i][j] = charArray[j];
if(grid[i][j] == 'S'){
xStart = i;
yStart = j;
}
if(grid[i][j] == 'E'){
xEnd = i;
yEnd = j;
}
}
}
//如果不存在起始点，直接返回
if(xStart == -1 || yStart == -1 || xEnd == -1 || yEnd == -1){
System.out.println(-1);
return;
}
//定义一个队列存储每一层的节点
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{xStart,yStart});
//定义一个辅助数组，用来标记访问过的节点
boolean[][] isVisited = new boolean[n][n];
isVisited[xStart][yStart] = true;
//用来记录步数
int res = 0;
while(!queue.isEmpty()){
//记录当前层有多少节点
int currentSize = queue.size();
//依次遍历每一层
for(int i = 0;i < currentSize;i++){
int[] xy = queue.remove();
//如果是终点，返回。
if(xy[0] == xEnd && xy[1] == yEnd){
System.out.print(res);
return;
}
int x = -1,y =-1;
//向右移动，越界处理
if(xy[0]+1 == n){
x = 0;
y = xy[1];
}else{
x = xy[0]+1;
y = xy[1];
}
if(grid[x][y] != '#' && !isVisited[x][y]){
queue.add(new int[]{x,y});
isVisited[x][y] = true;
}
//向左移动，越界处理
if(xy[0]-1 == -1){
x = n-1;
y = xy[1];
}else{
x = xy[0]-1;
y = xy[1];
}
if(grid[x][y] != '#' && !isVisited[x][y]){
queue.add(new int[]{x,y});
isVisited[x][y] = true;
}
//向上移动，越界处理
if(xy[1]+1 == n){
x = xy[0];
y = 0;
}else{
x = xy[0];
y = xy[1]+1;
}
if(grid[x][y] != '#' && !isVisited[x][y]){
queue.add(new int[]{x,y});
isVisited[x][y] = true;
}
//向下移动，越界处理
if(xy[1]-1 == -1){
x = xy[0];
y = n-1;
}else{
x = xy[0];
y = xy[1]-1;
}
if(grid[x][y] != '#' && !isVisited[x][y]){
queue.add(new int[]{x,y});
isVisited[x][y] = true;
}
}
//如果遍历完一层,没有到达终点，步数加1
res++;
}
//最终都没到达终点，返回
System.out.print(-1);
return;
}
}
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)