贪心算法练习day2

这篇具有很好参考价值的文章主要介绍了贪心算法练习day2。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

删除字符

1.题目及要求

贪心算法练习day2,贪心算法,算法

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类的一个方法

贪心算法练习day2,贪心算法,算法

 3)substring()

贪心算法练习day2,贪心算法,算法

搬砖

1.题目及要求

贪心算法练习day2,贪心算法,算法

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()方法

贪心算法练习day2,贪心算法,算法

2)i++,++i ;

贪心算法练习day2,贪心算法,算法

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 408复试day2(7大排序算法)

    7大排序算法总结: 首先排序分为内排序和外排序: 内排序是指待排序的记录放置在内存,而外排序是指排序的过程中需要对内存进行访问。其中稳定的排序有“插冒归”,即插入排序、冒泡排序、归并排序。 1.冒泡排序 算法原理: ①初始时有序区为空,即全部记录为无序

    2024年02月15日
    浏览(48)
  • 【算法】贪心算法练习一

    个人主页 : zxctscl 如有转载请先通知 一、贪心策略:解决问题的策略,局部最优-全局最优 把解决问题的过程分为若干步; 解决每一步的时候,都选择当前看起来“最优的”解法; 希望得到全局最优。 二、贪心策略的正确性 因为有可能“贪心策略”是一个错误的方法 正确

    2024年04月25日
    浏览(70)
  • 【大厂算法面试冲刺班】day2:合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 根据以上规律考虑本题目: 终止条件:当两个链表都为空时,表示我们对链表已合并完成。 如何递归:我们判断 l1 和 l2 头结点哪个更小,然后较小结点的 next 指针指向

    2024年01月23日
    浏览(44)
  • 贪心算法+练习

    正值国庆之际,祝愿祖国繁荣昌盛,祝愿朋友一生平安!终身学习,奋斗不息! 目录 1.贪心算法简介 2.贪心算法的特点 3.如何学习贪心算法 题目练习(持续更新) 1.柠檬水找零(easy) 算法原理 代码实现 证明(交换论证法) 贪心策略:解决问题的一种策略, 由局部最优-全

    2024年02月08日
    浏览(41)
  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(62)
  • 算法刷题营【Day2】:: 双指针算法应用:滑动窗口 :209. 长度最小的子数组

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:209. 长度最小的子数组 2. 题解参考 - - 2.1 方法一:暴力法 - - 2.2 方法二:滑动窗口 3. 方法思路点拨:滑动窗口 - - 3.1 直白解释 - - 3.2 本题思路点拨 4. 相关题集 1. 开篇例题:209. 长度

    2024年02月04日
    浏览(46)
  • 算法记录 | Day37 贪心算法

    思路: 1.一旦出现strNum[i - 1] strNum[i]的情况(非单调递增),首先想让strNum[i - 1]–,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。 2.向后遍历 从前向后遍历的话,遇到strNum[i - 1] strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能

    2023年04月22日
    浏览(31)
  • #算法记录 | Day33 贪心算法

    如果加油站提供的油总和大于等于消耗的汽油量,则必定可以绕环路行驶一周 假设先不考虑油量为负的情况,我们从「第 0 个加油站」出发,环行一周。记录下汽油量 gas[i] 和 cost[i] 差值总和 sum_diff,同时记录下油箱剩余油量的最小值 min_sum。 如果差值总和 sum_diff 0,则无论

    2023年04月18日
    浏览(39)
  • day 34 贪心算法

    1005.K次取反后最大化的数组和 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小 第二步:从前向后遍历,遇到负数将其变为正数,同时K– 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完 第四步:求和 134. 加油站 暴力求解, 从每一个位

    2024年02月11日
    浏览(33)
  • day27 贪心算法

    1.什么是贪心? 比如10张钞票,有1,5,20,100等面额,取五张,如何取得到数额最多的钱?每次取面额最大的那张钞票;就是每个阶段的局部最优;全局最优就是最后拿到的钞票数最大;局部最优推出全局最优; 题目描述 题目描述 题目描述 分析:摆动序列,就是前后相减保

    2024年02月16日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包