给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
示例:
输入:[1,8,6,2,5,4,8,3,7] 输出:49
对于这题来说,要求是求能够组成容器最大面积(忽略宽度)。直白的讲就是从若干个数字中找到一对数字,它们的距离和较小的数字成绩最大。
越好的情况就是数字很大(高度很高),并且距离也足够长!但是也很可能出现最大的在中间的情况:
思路一: 这题可以使用暴力的方法求解,枚举所有可能的情况,我们知道每个容器需要两根柱子组成,我们每次遍历柱子让当前柱子成为最矮的,去找最长的那个计算结果。当然这个结果可能是左侧,也可能是右侧。所以要找到远的那个比当前数字大的结果与max进行比较即可。
在具体的实现方面,注意一下相邻距离为1就可以啦:
public int maxArea(int[] height) {
int max = 0;
for (int i = 0; i < height.length; i++) {
int left = 0, right = 0;
for (int j = i; j >= 0; j--) {
if (height[i] <= height[j]) {
left = j;
}
}
for (int j = i; j < height.length; j++) {
if (height[i] <= height[j]) {
right = j;
}
}
max = Math.max(max, Math.max((i - left) * height[i], (right - i) * height[i]));
}
return max;
}
不过效果很差……
这种方法就是没任何进步的方法。
思路二: 这题其实可以从两侧双指针动态试探,初始情况没什么疑问,但是下一次到底是左面指针向右移动还是右侧指针向左移动呢?你要清楚:
你可能会担心,这样看从一个位置元素来看确实满足,会不会你这样漏了更好的,当然不会,我说了当前情况是这个矮个子能够到达的最大情况,已经是一个极限,想要突破这个极限,就只能去找更高的组合。
实现代码为(具体可以看我另一篇优化的思路):
public int maxArea(int[] height) {
int max = 0;
int left = 0;
int right = height.length - 1;
int team = 0;
int len = height.length;
int leftvalue=0;int rightvalue=0;
while (len-- > 0) {
leftvalue=height[left];rightvalue=height[right];
if (leftvalue < rightvalue) {
team = leftvalue * len;
if(max<team) {max=team;}
left++;
} else {
team = rightvalue * len;
if(max<team) {max=team;}
right--;
}
}
return max;
}
效果良好:
罗马数字包含以下七种字符:I, V, X, L,C,D 和 M。
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。
对于这题,其实就是一个数字和字符串处理的问题。规则和进制准换很相似 ,思路也大体一致——不断整除和求余,只不过要考虑5和10的两种特殊情况:
有了上述方法找到对应位置的数就可以进行操作了,记住叠加罗马数字一定别用String而要用StringBuilder。
实现代码为:
public static String intToRoman(int num) {
int numvalue []={1,5,10,50,100,500,1000};
char charvalue []= {'I', 'V', 'X', 'L','C','D','M'};
StringBuilder sBuilder=new StringBuilder();
int team=0;
for(int i=numvalue.length-1;i>=0;i--)
{
team=num/numvalue[i];
if(team==4&&i%2==0) {//向上进一为
sBuilder.append(charvalue[i]);
sBuilder.append(charvalue[i+1]);
num=num%numvalue[i];
}
else if (team==1&&i%2==1&&(num+numvalue[i-1])/numvalue[i+1]==1) {
sBuilder.append(charvalue[i-1]);
sBuilder.append(charvalue[i+1]);
num%=numvalue[i-1];
}
else {
for(int j=0;j<team;j++)
{
sBuilder.append(charvalue[i]);
}
num=num%numvalue[i];
}
}
return sBuilder.toString();
}
效果还不错!
本次试题介绍就到这里了,当然如果有其他想法也欢迎讨论!如果哪里有问题也欢迎指出!