刷题，让我燃起斗志！

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的使用及其原理