当前位置:网站首页>笔试面试题目:盛水最多的容器
笔试面试题目:盛水最多的容器
2020-11-08 10:30:30 【osc_1ajf1srl】
原文发表于:
今天周末,来看G公司的一道面试题:
求max{|i-j|*min{a[i], a[j]}}的值,其中a是正整数数组,i和j的区间为[0, n-1].
这其实就是leetcode中的“盛水最多的容器”,如下:
鲁迅说:暴力可以解决一切问题。
胡适说:暴力能解决的问题,都不是问题。
因为i和j的可能性是有限组合,所以暴力算法能得到结果,但无法通过面试。
用动态规划吗?貌似也不好动态规划。
我们可以采用双指针,分别指向头尾,计算出盛水值。然后向中间搜索,尝试找出更大的盛水可能性。
木桶理论告诉我们:对于两块确定的盛水挡板而言,盛水的多少是由短板决定的。
所以,在向中间搜索时,从短板侧向中间移动指针,才有可能产生更大的盛水值。
这是一个核心结论。
至于代码,很简单,来看下:
func maxArea(a []int) int {
n := len(a)
if n < 2 {
return 0
}
if n == 2 {
return min(a[1], a[0])
}
max := min(a[n - 1], a[0]) * (n - 1)
i := 0
j := n - 1
for i < j {
if a[i] < a[j] {
i++
}else {
j--
}
area := min(a[i], a[j]) * (j - i)
if area > max {
max = area
}
}
return max
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
结果:
该算法能正常通过面试,祝大家获得自己心仪的offer.
周末愉快。
版权声明
本文为[osc_1ajf1srl]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4272693/blog/4707996
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World