月度归档:2018年03月

Leetcode 232. Implement Queue using Stacks(两个栈实现队列)

没什么卵用的东西,就是弄两个栈,再加入元素的时候辅助栈帮助实现逆序的过程,然后在加回去。。。

Leetcode 798. Smallest Rotation with Highest Score

Given an array A, we may rotate it by a non-negative integer K so that the array becomes A[K], A[K+1], A{K+2], … A[A.length – 1], A[0], A[1], …, A[K-1]. Afterward, any entries that are less than or equal to their index are worth 1 point.

For example, if we have [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4]. This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point]. Over all possible rotations, return the rotation index K that corresponds to the highest score we could receive. If there are multiple answers, return the smallest such index K. Example 1: Input: [2, 3, 1, 4, 0] Output: 3 Explanation: Scores for each K are listed below: K = 0, A = [2,3,1,4,0], score 2 K = 1, A = [3,1,4,0,2], score 3 K = 2, A = [1,4,0,2,3], score 3 K = 3, A = [4,0,2,3,1], score 4 K = 4, A = [0,2,3,1,4], score 3 So we should choose K = 3, which has the highest score. Example 2: Input: [1, 3, 0, 2, 4] Output: 0 Explanation: A will always have 3 points no matter how it shifts. So we will choose the smallest K, which is 0. Note: A will have length at most 20000. A[i] will be in the range [0, A.length]. 比赛的时候没想清楚以为要线段树觉得不可能那么麻烦就失去了梦想不想写了。。。 然后郑爹告诉我只需要树状数组就可以了。。 当a[i]<=i的时候,那么贡献的区间分为了两段,首先是从[1,i-a[i]+1],另外一段因为移动i+1次后a[i]变成了下标为n,所以就是[i+1,n]。 当a[i]>i的时候只有一段:[i,i+n-a[i]+1]。但是因为树状数组从1开始下标,而题目是0,所以整体加1在处理就好了。。。

蓄水池抽样

了解了一下蓄水池抽样。
它可以在O(n)的时间内对n个数据进行等概率的随机抽取k个样本,并且适用于n不断增长(就是n未知的情况下),或者n很大(不能放入内存的情况)。
算法的步骤就是:
假设要等概率的抽取样本数为k。那么首先把n个数列中的前k个元素放入到一个长度为k的数组中,称为蓄水池。然后对于之后的第k+1个元素到第n个元素中,第i个元素的时候,生成一个在[1,i]之间的随机数j,如果j小于k,就把蓄水池中的第j个元素换成第i个。
通过数学归纳法证明这样做可以让每个元素都有k/n的概率进入蓄水池。
首先,对于任意的 i,第 i 个元素进入蓄水池的概率为 k / i;而在蓄水池内每个元素被替换的概率为 1 / k; 因此在第 i 轮第j个元素被替换的概率为 (k / i ) * (1 / k) = 1 / i。
那么假设在第(i-1)轮,任意一个元素进入蓄水池的概率均为k/(i-1)。那么在第i轮其被替换概率为1/i,那么继续留在蓄水池的概率为k/(i-1)*(1-1/i)=k/i。得证。
写了个做实验的代码,的确可以说是非常随机了.