刪除字符

1.題目及要求

2.解題思路

1）初始化最小字母為‘Z’，確保任何字母都能與之比較

2）遍歷單詞，找到當(dāng)前未刪除字母中的最小字母

3）獲取當(dāng)前位置的字母? current = word.charAt(i)；

4）刪除最小字母之前的所有字母? word=word.substring(index+1);

5)? 將最小字母添加到結(jié)果字符，更新剩余可刪除字母數(shù)量 t -= index ；

3.詳細(xì)代碼

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();//刪除字母的數(shù)量
        char min;
        char current;//存儲(chǔ)當(dāng)前遍歷到的字母
        int index=0;//從左到右t個(gè)字母中最小字母的位置，找到將其保存，并且刪除它之前的所有字母，之后的字母去它后面尋找
        String result="";//存儲(chǔ)結(jié)果單詞
        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個(gè)字母里面的最小字母之前的字母數(shù),刪除操作
            word= word.substring(index+1);//第一趟確定第一小的字母，第二趟第二小，以此類(lèi)推
            result+=min;
            t-=index;//還能刪除的字母數(shù)量
        }
        System.out.println(result+word);//記得把word剩余的字母補(bǔ)上哦
        scan.close();
    }
}

4.學(xué)習(xí)要點(diǎn)

1）讀取用戶(hù)輸入的字符，字符串，整數(shù)...等等

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類(lèi)的一個(gè)方法

?3）substring()

搬磚

1.題目及要求

2.解題思路

貪心+01背包+排序

先循環(huán)輸入每件物品的重量，價(jià)值，以及重量?jī)r(jià)值之和，存放到二維數(shù)組里。

然后依據(jù)數(shù)組里的某一特性進(jìn)行排序，用到Arraya.sort()方法

外層循環(huán)遍歷每件物品。內(nèi)層循環(huán)從背包的最大容量到當(dāng)前物品的重量。

3.詳細(xì)代碼

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]; // 這里用數(shù)組。注意：Record類(lèi)（類(lèi)似C語(yǔ)言結(jié)構(gòu)體）是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])); // 根據(jù)sum排序（lambda表達(dá)式，相當(dāng)于匿名內(nèi)部類(lèi)）
        // 這里用滾動(dòng)數(shù)組更方便，因?yàn)槭堑剐虮闅v，0-1背包滾動(dòng)數(shù)組詳解：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.學(xué)習(xí)要點(diǎn)

1）Arrays.sort()方法

2）i++,++i ;

3）循環(huán)輸入每個(gè)物品的信息文章來(lái)源地址http://www.zghlxwxcb.cn/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;
        }

到了這里，關(guān)于貪心算法練習(xí)day2的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！