删除字符
1.题目及要求
2.解题思路
1)初始化最小字母为‘Z’,确保任何字母都能与之比较
2)遍历单词,找到当前未删除字母中的最小字母
3)获取当前位置的字母 current = word.charAt(i);
4)删除最小字母之前的所有字母 word=word.substring(index+1);
5) 将最小字母添加到结果字符,更新剩余可删除字母数量 t -= index ;
3.详细代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String word=scan.next();
int t=scan.nextInt();//删除字母的数量
char min;
char current;//存储当前遍历到的字母
int index=0;//从左到右t个字母中最小字母的位置,找到将其保存,并且删除它之前的所有字母,之后的字母去它后面寻找
String result="";//存储结果单词
while(t>0){
min='Z';
for (int i = 0; i < word.length(); i++) {
current=word.charAt(i);
if(current<min){
min=current;
index=i;
}
}
//获取到t个字母里面的最小字母之前的字母数,删除操作
word= word.substring(index+1);//第一趟确定第一小的字母,第二趟第二小,以此类推
result+=min;
t-=index;//还能删除的字母数量
}
System.out.println(result+word);//记得把word剩余的字母补上哦
scan.close();
}
}
4.学习要点
1)读取用户输入的字符,字符串,整数...等等
Scanner scan = new Scanner(System.in);
String s = scan.nextLine();
char a = scan.next().charAt(0);
int a = scan.nextInt();
2)charAt(int index) String类的一个方法
3)substring()
搬砖
1.题目及要求
2.解题思路
贪心+01背包+排序
先循环输入每件物品的重量,价值,以及重量价值之和,存放到二维数组里。
然后依据数组里的某一特性进行排序,用到Arraya.sort()方法
外层循环遍历每件物品。内层循环从背包的最大容量到当前物品的重量。
3.详细代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
final int count = scan.nextInt();
int[][] structs = new int[count + 1][3]; // 这里用数组。注意:Record类(类似C语言结构体)是Java14特性,不能用
int capacity = 0;
for (int i = 1; i <= count; ++i) {
int wi = scan.nextInt(), vi = scan.nextInt();
capacity += wi;
structs[i][0] = wi;
structs[i][1] = vi;
structs[i][2] = wi + vi;
}
scan.close();
Arrays.sort(structs, Comparator.comparingInt(struct -> struct[2])); // 根据sum排序(lambda表达式,相当于匿名内部类)
// 这里用滚动数组更方便,因为是倒序遍历,0-1背包滚动数组详解:https://www.bilibili.com/video/BV1BU4y177kY/
int[] dp = new int[capacity + 1];
for (int i = 1; i <= count; ++i) {
int wi = structs[i][0], vi = structs[i][1];
for (int j = capacity; j >= wi; --j)
if (j - wi <= vi)
dp[j] = Math.max(dp[j - wi] + vi, dp[j]);
}
Arrays.sort(dp);
System.out.println(dp[capacity]);
}
}
4.学习要点
1)Arrays.sort()方法
2)i++,++i ;
文章来源:https://www.toymoban.com/news/detail-829164.html
3)循环输入每个物品的信息文章来源地址https://www.toymoban.com/news/detail-829164.html
for (int i = 1; i <= count; ++i) {
int wi = scan.nextInt(), vi = scan.nextInt();
capacity += wi;
structs[i][0] = wi;
structs[i][1] = vi;
structs[i][2] = wi + vi;
}
到了这里,关于贪心算法练习day2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!