GG六月onsite

yanshuining 发表于 2017-6-22 13:57
第二轮，其实是一道概率题。我的想法是：比如给出的矩形array是: rectangle[] rec_array, 先生成一个长度 ...

谢谢lz回复～没有很明白，为啥array要存前i个矩形的sum，遇到重叠的矩形做法相同吗？

白丁117 发表于 2017-6-22 21:22
谢谢lz回复～没有很明白，为啥array要存前i个矩形的sum，遇到重叠的矩形做法相同吗？

如果有重叠的矩形，需要先将重叠的矩形处理成Non-overlap的，就是followup的问题

在上述矩形加入一个新的矩形 是说原来有n个 现在要加入一个矩形使得它不和任意前面n个矩形相交是吗？如果这样的话，就在所有矩形区域范围外随便加一个不就好了？

白丁117 发表于 2017-6-22 21:22
谢谢lz回复～没有很明白，为啥array要存前i个矩形的sum，遇到重叠的矩形做法相同吗？

大致的code如下， 用左下和右上的两个点，四个值表示一个矩阵， (x1, y1, x2, y2)

1. <div>
   
2. </div><div><div>def randomPoint(recs):</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>n = len(recs)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>area_array = [0 for i in xrange(n+1)]</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>for i in xrange(1, n+1):</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>area_array[i] = area_array[i-1] + (recs[i][2]-recs[i][0])*(recs[i][3]-recs[i][1])</div><div>
   
3. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>sum_area = array_array[n]</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>random_area = random.randint(0, sum_area)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>rec_index = binarySearch(random_area, area_array) - 1 </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>random_point = getRandomPoint(recs[rec_index])</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return random_point</div><div>
   
4. </div><div>def binarySearch(target, array):</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>start=0; end=len(array)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>while start+1<end:</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>mid = start+(end-start)/2</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>if array[mid]<target:</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>start=mid</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>else:</div><div><span class="Apple-tab-span" style="white-space:pre">                        </span>end=mid</div><div>
   
5. </div><div><span class="Apple-tab-span" style="white-space:pre">        </span>if array[end]<target:</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return end</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>if array[start]<target:</div><div><span class="Apple-tab-span" style="white-space:pre">                </span>return start</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return 1</div><div>
   
6. </div><div>def getRandomPoint(rec):</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>(x1, y1, x2, y2) = rec</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>x = random.randint(x1,x2)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>y = random.randint(y1, y2)</div><div><span class="Apple-tab-span" style="white-space:pre">        </span>return (x, y)</div></div>

复制代码

grasssu2 发表于 2017-6-23 01:52
在上述矩形加入一个新的矩形 是说原来有n个 现在要加入一个矩形使得它不和任意前面n个矩形相交是吗？如果这 ...

要加入的矩阵，坐标是给定的

额~ LZ不会黏贴代码。。。

多谢楼主分享

请问第三轮里面要求打印path是用bfs做的吗？每次bfs的时候build一个图然后倒着print？多谢楼主

请教一下第三题： >=1表示经过该点的cost

这个用BFS怎么做呢？需要用priority queue 而不是一般的queue 吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies