刷题,让我燃起斗志!

摘要

七彩罗马,流转千年。I、V、X、L、C、D、M,代表着不同的数字。它们如同历史的印记,记录着古老的文明和辉煌的过去。让我们一起感受这些神秘符号所蕴含的深刻内涵吧!

正文

2021.5.15刷题

题目一: 103.罗马数字转整数(Roman to Integer)来源:力扣(LeetCode)

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

 总体思路:题目中给出:通常情况下,罗马数字中小的数字在大的数字的右边。那么所允许的几种特例都是小的数字在大的右边,那么在我们转整数的时候,我们只需要比对当前数字与下一个数字的大小关系,就可以知道当前数字是需要加上去还是减去。

题解:

       public int romanToInt(String s) {
            int sum = 0;
            int prenum = Translate(s.charAt(0));
            int num = 0;
            for(int i = 1 ; i < s.length() ;i++) {
                num = Translate(s.charAt(i));
                if(prenum >= num) {
                    sum += prenum;
                }else if(prenum < num) {
                    sum -= prenum;
                }
                prenum = num;
            }
            sum += prenum;
            return sum;
        }
        public  int Translate(char ch) {
            switch(ch){
            case ('I'): return 1;
            case ('V'): return 5;
            case ('X'): return 10;
            case ('L'): return 50;
            case ('C'): return 100;
            case ('D'): return 500;
            case ('M'): return 1000;
            default: return 0;
            }
        }

该题解中,我是通过switch语句实现对罗马数字的数值转化,而这种一一对应的数值转化让我想到了java中的map接口,所以我又用map接口重写了一下:

 

       public int romanToInt(String s) {
           
            Map<Character,Integer> map = new HashMap<>();
            map.put('I', 1);
            map.put('V', 5);
            map.put('X', 10);
            map.put('L', 50);
            map.put('C', 100);
            map.put('D', 500);
            map.put('M', 1000);
            
            int sum = 0;
            int prenum = 0 , num = 0;
            prenum = map.get(s.charAt(0));
            
            for(int i = 1 ; i < s.length() ; i++) {
                num=map.get(s.charAt(i));
                if(prenum >= num) {
                    sum += prenum;
                }else if(prenum < num) {
                    sum -= prenum;
                }
                prenum = num;
            }
            return sum+prenum;
        }

收获:对比两次提交,我发现两种写法在用时上有微乎其微的差距,我去搜索相关问题,找到了一篇文章:switch与map的性能比较,在该文章中我了解到:

    switch语句被编译后,对应得是jvm的tableswitch指令,执行起来也就几条指令就完成了;而HashMap的get操作所执行的jvm指令肯定是要比tableswitch要多的(引自原文)

    但是在该文章中,该作者在自己电脑上测试时发现,map.get会比switch语句来得快,原来是JIT中对map.get进行了优化,从而得出Java的性能测试受环境的影响很大(详情大家可以自行查看该文章)

 

题目二:1833. 雪糕的最大数量(Maximum Ice Cream Bars)来源:力扣(LeetCode)

 

夏日炎炎,小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕,用长度为 n 的数组 costs 表示雪糕的定价,其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费,他想要买尽可能多的雪糕。

给你价格数组 costs 和现金量 coins ,请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

注意:Tony 可以按任意顺序购买雪糕。

总体思路:思路一:排序+贪心:在该题中,要用coins买到最大数量的雪糕,那就肯定要从金额小的雪糕先开始,那么就对costs数组进行排序之后再用贪心算法解决问题。
     思路二:大顶堆:该思路来源于jexing的题解,就是通过java中的优先级队列PriortyQueue实现将数组排序的功能

题解:

排序+贪心

    public int maxIceCream(int[] costs, int coins) {
        //利用java中的排序方法
        Arrays.sort(costs);
        //贪心算法
        int sum=0;
        for(int j:costs) {
            if(coins < j) {
                break;
            }
            coins-=j;
            sum++;
        }
        return sum;

    }

大顶堆

    public int maxIceCream(int[] costs, int coins) {
    //利用java中的优先级队列PriortyQueue实现
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    int sum = 0;
    for(int item : costs){
        int val = sum + item;
        if(val <= coins){
            //如果当前项加上之前项之和小于coins,将该项直接放入队列中
            sum += item;
            queue.offer(-1 * item);
            /*
             * 因为优先级队列PriortyQueue默认升序排列
             * 所以放入PriortyQueue时需乘上-1实现降序排列
             */
        }else if(!queue.isEmpty()&&(queue.peek() * -1 ) > item){
            //如果当前项加上之前项之和大于coins,将当前项与队列中最大项替换
            sum += queue.poll();
            queue.offer(-1 * item);
            sum += item;
        }
    }
    return queue.size();
    }

收获:在这次刷题中,我学习到了优先级队列PriortyQueue的使用及其原理

关注不迷路

扫码下方二维码,关注宇凡盒子公众号,免费获取最新技术内幕!

温馨提示:如果您访问和下载本站资源,表示您已同意只将下载文件用于研究、学习而非其他用途。
文章版权声明 1、本网站名称:宇凡盒子
2、本站文章未经许可,禁止转载!
3、如果文章内容介绍中无特别注明,本网站压缩包解压需要密码统一是:yufanbox.com
4、本站仅供资源信息交流学习,不保证资源的可用及完整性,不提供安装使用及技术服务。点此了解
5、如果您发现本站分享的资源侵犯了您的权益,请及时通知我们,我们会在接到通知后及时处理!提交入口
0

评论0

请先

站点公告

🚀 【宇凡盒子】全网资源库转储中心

👉 注册即送VIP权限👈

👻 全站资源免费下载✅,欢迎注册!

记得 【收藏】+【关注】 谢谢!~~~

立即注册
没有账号?注册  忘记密码?

社交账号快速登录