登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

几道小题  

2008-12-04 13:33:31|  分类: 思维训练 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1.
将数组{32,74,25,53,28,43,86,47}按从小到大排列,每次可以交换任意两个元素,最少
需要交换_______次

答案是5次,置换的分解。

2.
给你一个已经排好序的数组a,里面可能有重复元素,比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。现在需要重新调整
a里面的元素为a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1},要求里面的每个子序列都是有序的,并且其中的元素唯一。
另外,要求这样的子序列数最小,并且只能使用O(1)的辅助空间。

3.
很多数正正负负组成一个首尾相接的环,求连续的数之和的最大值。
O(n),类似最长递增数列的dp,将环变为链,设断开处的点为o,则注意该最大子序列,要麽经过o点,要么不经过o点
,如果不经过o点,显然可以按照链式的方法O(n),类似最长递增序列的dp结构。如果经过o,换个角度,从反面去考虑,
,因为环的和是一定的,如果求最大,相当于剩下部分最小,所以只要求出链上的最小子序列和,用总和减去即是结果。

4.
很多数正正负负组成一个首尾相接的环,求连续的数之和的最大值。
排序,然后数的和实际上构成一个杨氏矩阵,可以O(n^2)

5.
寻找攻击IP。
IP总数不大于1,000,000,000,格式,已经按照时间顺序排好,比如:
202.117.14.154 21:08:02
202.117.14.154 21:08:02
202.117.14.179 21:08:03
攻击IP判定:在X秒内,有超过Y条,即认为是攻击IP。
输出攻击IP,每个IP只能输出一次

hash,设置一个x秒的滑动窗口,每隔1秒进行更新检查


6.
序列从零个元素开始向里添加整数,每添加一个数,就输出序列的中位数,中位数定义:
奇数2N+1, 中位数 N+1;
偶数2N,中位数N;

用两个堆试试,一个最小堆,一个最大堆

7.
有n个水桶,组成一个环,相邻两个有水管连接,
水管中间有阀门,都关上。
初始条件是:水桶有水,深度不一,保存在数组a[n]里面。
问:设计算法,针对具体的a[n],使得打开阀门最少情况下,水桶深度相同。

打开最少的阀门等价于把环尽可能多的分成若干段,每一段的平均值都是∑a[i]/n.

枚举一个切割点,把环展开成直的一段,然后从左往右扫描一遍算出最多能分成多少段使得
每段的平均值都是∑a[i]/n.枚举切割点需要n次, 展开后算最多能分成多少段需要O(n)的时间,总的时间复杂度是O(n
*n).记忆已经枚举过的位置,避免重复枚举,可以帮助优化。


  评论这张
 
阅读(740)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018