11. 盛最多水的容器
题目
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
注意：你不能倾斜容器，n 至少是2。
思路
按照题目的要求即找出任意两个垂直线与X轴组成的容器能装最多的水。即寻找height数组中下标之差与两者之间最小者的乘积所的到的面积。
可以从左右两个端点开始每次丢弃最小边，然后向中心移动。
代码
class Solution {public int maxArea(int[] height) {if(height.length<2)return 0;int left = 0;int right = height.length-1;int max = 0;while(left<right){max = Math.max(max,(right-left)*Math.min(height[left],height[right]));if(height[left]<height[right])left++;else right--;} return max;}
}12. 整数转罗马数字
题目
罗马数字包含以下七种字符： 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 的范围内。
思路
题目的要求很明确，唯一注意的情况也列出。
代码
最简单粗暴的方式
class Solution {public String intToRoman(int num) {StringBuilder sd = new StringBuilder();while(num>=1000){sd.append("M");num-=1000;}if(num>=900){sd.append("CM");num-=900;}if(num>=500){sd.append("D");num-=500;}if(num>=400){sd.append("CD");num-=400;}while(num>=100){sd.append("C");num-=100;}if(num>=90){sd.append("XC");num-=90;}if(num>=50){sd.append("L");num-=50;}if(num>=40){sd.append("XL");num-=40;}while(num>=10){sd.append("X");num-=10;}if(num>=9){sd.append("IX");num-=9;}if(num>=5){sd.append("V");num-=5;}if(num>=4){sd.append("IV");num-=4;}while(num>0){sd.append("I");num-=1;}return sd.toString();}
}可以发现其实很多相似点可以将代码改进
class Solution {public String intToRoman(int num) {StringBuilder sb = new StringBuilder(); String[][]r = { {
"","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(r[3][num/1000%10]); sb.append(r[2][num/100%10]); sb.append(r[1][num/10%10]); sb.append(r[0][num%10]);return sb.toString();}
}13. 罗马数字转整数
题目
罗马数字包含以下七种字符：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 的范围内。
思路
这个题目其实就是上一个题目的反转，直接可以通过判断每个字符的对应的数值。然后加上，对于一些特殊的字符做处理即可，如100、10、1.
代码
class Solution {public int romanToInt(String s) {if(s==null||s.length()==0)return 0;int i = 0;int res = 0;while(i<s.length()){switch(s.charAt(i)){case 'M':res+=1000;break;case 'D':res+=500;break;case 'C':if(i+1<s.length()&&(s.charAt(i+1)=='M'||s.charAt(i+1)=='D')){res += s.charAt(i+1)=='M'?900:400;i++;}else{res+=100;}break;case 'L':res+=50;break;case 'X':if(i+1<s.length()&&(s.charAt(i+1)=='L'||s.charAt(i+1)=='C')){res += s.charAt(i+1)=='C'?90:40;i++;}else{res+=10;}break;case 'V':res+=5;break;case 'I':if(i+1<s.length()&&(s.charAt(i+1)=='V'||s.charAt(i+1)=='X')){res += s.charAt(i+1)=='X'?9:4;i++;}else{res+=1;}break;}i++;}return res;}
}