当前位置:网站首页>The container with the most water
The container with the most water
2020-11-08 10:30:00 【http://www.ubytovani-jihlava.cz】
Original published in :
Today is the weekend , Look at G An interview question from the company :
seek max{|i-j|*min{a[i], a[j]}} Value , among a It's an array of positive integers ,i and j The interval is [0, n-1].
This is actually leetcode Medium “ The container with the most water ”, as follows :
Lu xun said : Violence can solve all problems .
Hushi said : The problem that violence can solve , It's not a problem .
because i and j The possibility of a limited combination , So the brute force algorithm gets the result , But failed to pass the interview .
Do you use dynamic programming ? It seems that dynamic planning is not good either .
We can use double pointers , Point to the head and the tail respectively , Calculate the water content . And search in the middle , Try to find out more possibilities for holding water .
The barrel theory tells us : For two definite water baffles , The amount of water is determined by the short board .
therefore , When searching in the middle , Move the pointer from the short board to the middle , It is possible to produce a greater water holding value .
This is a central conclusion .
As for the code , It's simple , Take a look :
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
}
result :
The algorithm can pass the interview normally , I wish you all the best offer.
Have a nice weekend .
版权声明
本文为[osc_1ajf1srl]所创,转载请带上原文链接,感谢
边栏推荐
- 学习小结(关于深度学习、视觉和学习体会)
- Recommend an economic science video, very valuable!
- 413【毕设课设】基于51单片机无线zigbee无线智能家居光照温湿度传输监测系统
- 5g/4g工业无线路由器
- What is the difference between vivoy73s and vivoy70s
- Shiyou's numerical analysis assignment
- 狗狗也能操作无人机!你没看错,不过这其实是架自动驾驶无人机 - 知乎
- 推荐一部经济科普视频,很有价值!
- Tiktok live monitoring Api: random recommendation
- Python loop distinction (while loop and for loop)
猜你喜欢
2020-11-05
Six key points of data science interview
Close to the double 11, he made up for two months and successfully took the offer from a large factory and transferred to Alibaba
Spotify是如何推动数据驱动决策的?
211 postgraduate entrance examination failed, stay up for two months, get the byte offer! [face to face sharing]
Second assignment
C++在C的基础上改进了哪些细节
How TCP protocol ensures reliable transmission
YGC问题排查,又让我涨姿势了!
ArrayList源码分析
随机推荐
Iqkeyboardmanager source code to see
VC + + specified directory file output by time
How TCP protocol ensures reliable transmission
Japan PSE certification
C语言I博客作业03
双向LSTM在时间序列异常值检测的应用
Istio流量管理--Ingress Gateway
笔试面试题目:判断单链表是否有环
来自不同行业领域的50多个对象检测数据集
Cloud alibabab notes come out, the whole network detailed explanation only this one hand is slow
函数周期表丨筛选丨值丨SELECTEDVALUE - 知乎
PDMS cutting software
Face recognition: attack types and anti spoofing techniques
Japan PSE certification
SQL Server 2008R2 18456错误解决方案
运维人员常用到的 11 款服务器监控工具
Flink's sink: a preliminary study
AMD Zen3首发评测:频率超5GHz,IPC提升不止19%,这次真的Yes了 - 知乎
2020-11-05
【总结系列】互联网服务端技术体系:高性能之数据库索引