LeetCode 11盛水最多的容器&12整数转罗马数字

举报
bigsai 发表于 2021/02/03 02:00:30 2021/02/03
【摘要】 目录 盛水最多的容器题目描述分析 整数转罗马数字题目描述:分析 结语 盛水最多的容器 公众号:bigsai,回复进群加入打卡,回复bigsai获取3GB的pdf资源。点赞再看,养成习惯! 题目描述 给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别...

盛水最多的容器

公众号:bigsai,回复进群加入打卡,回复bigsai获取3GB的pdf资源。点赞再看,养成习惯!

题目描述

给你 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;
	}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

不过效果很差……
在这里插入图片描述
这种方法就是没任何进步的方法。

思路二:
这题其实可以从两侧双指针动态试探,初始情况没什么疑问,但是下一次到底是左面指针向右移动还是右侧指针向左移动呢?你要清楚:

  • 无论左移还是右移动,数字之间的区间都是减小的(距离缩小)
  • 如果移动较大的那个,下一次移动结果一定不可能大于这一次结果!(就算你的下一个很高,但是要根据最矮的来)
  • 所以我们每次移动,把较小的那个指针向中间移动,寻找更大的可能

在这里插入图片描述

你可能会担心,这样看从一个位置元素来看确实满足,会不会你这样漏了更好的,当然不会,我说了当前情况是这个矮个子能够到达的最大情况,已经是一个极限,想要突破这个极限,就只能去找更高的组合。

实现代码为(具体可以看我另一篇优化的思路):

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;
	}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

效果良好:
在这里插入图片描述

整数转罗马数字

题目描述:

罗马数字包含以下七种字符: 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。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。
在这里插入图片描述

分析

对于这题,其实就是一个数字和字符串处理的问题。规则和进制准换很相似 ,思路也大体一致——不断整除和求余,只不过要考虑5和10的两种特殊情况:

  • 对于5种类来说除数的结果一定是4并且当前满足为偶数位(0,2,4等位)(比如处理4时候4/1=4,40/10=4)
  • 对于10种类来说除数的结果为1,且加上比它小一位的数和为比它大一位的数(比如9/5=1,9+1=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(); }

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

效果还不错!
image-20201115201234360

结语

原创不易,bigsai我请你帮两件事帮忙一下:

  1. star支持一下, 您的肯定是我在平台创作的源源动力。

  2. 微信搜索「bigsai」,关注我的公众号,不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见!

image-20201114211553660

文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。

原文链接:bigsai.blog.csdn.net/article/details/108148626

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200