Leetcode 12,452,455-贪心算法
2024-10-08 10:23:28
Leetcode第12题，整数转罗马数字，难度中等
整个题目比较好理解，难度也不大，就算不过脑子，用一串if也基本上可以解决问题，比如
/** 执行用时:6ms,在所有 Java 提交中击败了52.61%的用户 内存消耗:40.3 MB, 在所有 Java 提交中击败了5.00%的用户 */
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
if(num < 1 || num > 3999) return "";
int n = 0;
if(num >= 1000){
n = num / 1000;
num = num - n * 1000;
for(int i = 0; i < n; i++) sb.append("M");
}
if(num >= 900){
sb.append("CM");
num = num - 900;
}
if(num >= 500){
sb.append("D");
num = num - 500;
}
if(num >= 400){
sb.append("CD");
num = num - 400;
}
if(num >= 100){
n = num / 100;
num = num - n * 100;
for (int i = 0; i < n; i++) sb.append("C");
}
if(num >= 90){
sb.append("XC");
num = num - 90;
}
if(num >= 50){
num = num - 50;
sb.append("L");
}
if(num >= 40){
sb.append("XL");
num = num - 40;
}
if(num >= 10){
n = num / 10;
num = num - n * 10;
for (int i = 0; i < n; i++) sb.append("X");
}
if(num >= 9){
sb.append("IX");
num = num - 9;
}
if(num >= 5){
num = num - 5;
sb.append("V");
}
if(num >= 4){
sb.append("IV");
num = num - 4;
}
if(num >= 1){
n = num / 1;
for (int i = 0; i < n; i++) sb.append("I");
}
return sb.toString();
}
不过这样写if太多了，篇幅太长，整理成数组会好很多：
/**
执行用时:6 ms, 在所有Java提交中击败了52.61%的用户
内存消耗:40.6 MB, 在所有 Java 提交中击败了5.00%的用户
*/
public String intToRoman2(int num) {
StringBuilder sb = new StringBuilder();
String[][] list = {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
{"", "M", "MM", "MMM"}};
sb.append(list[3][num/1000]);
sb.append(list[2][num%1000/100]);
sb.append(list[1][num%100/10]);
sb.append(list[0][num%10]);
return sb.toString();
}
这里要注意数组第一位是空字符串，因为有个0，我写的时候忘了这茬，还是看来网友的解题思路才想起的，
那么这两个解题思路都是比较局限性的解题思路，看了题解里大神的分析，想起来原来这题适用贪心算法。
具体实现方法：
/**
执行用时:7ms,在所有Java提交中击败了33.11%的用户
内存消耗:40.8MB,在所有Java提交中击败了5.00%的用户
*/
public String intToRoman3(int num) {
int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] strs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder sb = new StringBuilder();
int n = 0;
while(n < 13){
while(num >= nums[n]){
sb.append(strs[n]);
num -= nums[n];
}
n++;
}
return sb.toString();
}
代码的逻辑还是很好理解的，既然用到的贪心算法，趁热打铁去leetcode多搜几道
比如455.分发饼干
/*
执行用时 :8 ms, 在所有 Java 提交中击败了99.61%的用户
内存消耗 :41.8 MB, 在所有 Java 提交中击败了5.14%的用户
*/
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int l = s.length - 1;
int r = 0;
for(int i = g.length - 1; i >= 0; i--){
if(l < 0) return r;
if(g[i] <= s[l]){
r++;
l--;
}
}
return r;
}
这里使用贪心算法，思路就是在当前范围下先解决吃的最多的，然后递归，就可以了
leetcode还有一道中等难度的贪心算法，就是452.用最少数量的箭引爆气球
经过之前几道贪心算法的历练，我觉得首先要在题目中找到局部最优解，那有最优就有对比，所以首先找到比对的对象，像上面的分发饼干，比对的就是孩子的胃口，所以以胃口进行排序，先解决最大的，这道气球题，根据题目，是以x轴排序，那么对比的就是x轴上的位置，因为位置是从0开始的，所以从最小的开始是最优解
if(points==null||points.length==0)return 0;
int r=1;
Arrays.sort(points, Comparator.comparingInt(o->o[1]));
int end=points[0][1];
for(int i=0;i<points.length;i++){
if(points[i][0]<=end)continue;
r++;
end=points[i][1];
}
return r;
把气球按照x轴位置排序，从最左边的气球开始，把箭从最左边气球的最左边擦边过，这样射完所有能射的气球后，第二支箭就从剩下气球里最左边的开始射，以此往复。
从图上来看（这图从leetcode官方拷贝）
从左边的绿球开始扎，那么从6射，可以射到两个绿+红，剩下的气球里最左边的是黄色的，那么从黄色的最右边也就是12射，可以射到两只，射完后气球就没了，那么箭数就是2。
贪心算法和动态规划有点像，不过简单很多。。。
最新文章
- Angular2 CLI 快速开发
- BZOJ2320 : 最多重复子串
- 004_URL 路由 - 定制路由系统 & 使用区域
- jboss\server\default\.\tmp 拒绝访问 axis2
- nginx模块_使用gdb调试nginx源码
- junit组合模式应用
- Libsvm的MATLAB调用和交叉验证
- JS实时监听浏览器宽度的变化
- SQL数据类型介绍
- _sortBy用法
- php形式的内容被处理
- javascript 备忘 细节 相关
- nyist oj 756 重建二叉树
- FCL源码中数组类型的学习及排序函数Sort函数的分析
- WC2019冬眠记
- Android 异步框架 RxJava2
- Retrieve OpenGL Context from Qt 5.5 on OSX
- javaMail发邮件，激活用户账号
- DBWritable的使用
- pthread_mutex_timedlock