思维训练

几道小题

2008年12月4日 阅读(267)

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).记忆已经枚举过的位置,避免重复枚举,可以帮助优化。

You Might Also Like