存档

2013年1月 的存档

定长线段最多覆盖点的个数

2013年1月5日 2 条评论

---

来自之前百度一面的题目:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

题目不难,但也不是太容易想出来,两个指针前后跑的思路:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。

阅读全文...