• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

水池问题的lua语言算法(面试题分析:我的Twitter技术面试失败了) ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

twitter面试题内容

 

“看下面这个图片”

“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表,数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]”

“假如开始下雨了,那么墙之间的水坑能够装多少水呢?”

 


闲来无事给出一份解决此问题的lua代码(https://gist.github.com/jianchenglee/7262518):

-- author ljc

-- 1) find the max value, split the array to 2 array
-- 2) compute the increment ,get 2 increment array
-- 3) get the result by the increment value(if there are a minus value,then retain water,until one by one accumulation value become plus,then go on next)
waterpool={2,4,3,5,1,2,3,2,3,7,7,6,7,6,4,5}
testcase_1 = {2,5,1,2,3,4,7,7,6}
testcase_2 = {2,5,1,3,1,2,1,7,7,6}
testcase_3 = {6,1,4,6,7,5,1,6,4}




function watertotal(o)


-- v1:tempvalue total: result value
-- v_max,i_max: the biggest value and the index of the input array
-- waterpool_q1: first half increment value array waterpool_q2: secopd half increment value array
local v1,v_max,i_max,total=0,0,0,0,0;
local waterpool_q1={};
local waterpool_q2={};


local allnumber=table.maxn(o)


--1)
for i,v in ipairs(o) do
if v>v_max then
v_max=v
i_max=i
end
end






--2)
-- generate waterpool_q1
for i=1,i_max-1,1 do
--print(o[i]-v1)
table.insert(waterpool_q1,o[i]-v1)
v1=o[i]
end


-- generate waterpool_q2
v1=0
for i=allnumber,i_max,-1 do
--print(o[i]-v1)
table.insert(waterpool_q2,o[i]-v1)
v1=o[i]


end


--3)
-- the result of waterpool_q1
v1=0


for i,v in ipairs(waterpool_q1) do


if v<0 and v1>=0 then
v1=v
total=total+math.abs(v1)
elseif (v1+v<0) then
v1=v1+v
total=total+math.abs(v1)
elseif v+v1>=0 then
v1=0


end
--print(math.abs(v1))
end


-- the result of waterpool_q1
v1=0
for i,v in ipairs(waterpool_q2) do


if v<0 and v1>=0 then
v1=v
total=total+math.abs(v1)
elseif (v1+v<0) then
v1=v1+v
total=total+math.abs(v1)
elseif v+v1>=0 then
v1=0


end
--print(math.abs(v1))
end


print(total)


end


-- test the function
watertotal(waterpool)
watertotal(testcase_1)
watertotal(testcase_2)

watertotal(testcase_3)



测试结果:

>lua -e "io.stdout:setvbuf 'no'" "waterpool.lua" 
17
10
17
13

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
华丽的使用sublime写lua~sublimelua相关必装插件推荐~~发布时间:2022-07-22
下一篇:
Lua脚本之语法基础快速入门发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap