e***s
发帖数: 799 | 1 //2. 不断从一个stream里读数据，找到最大的K个数。就是用一个大小为K的min-heap就
//好了。但是要求
//写code 实现min-heap的插入/删除操作。
public static void getKMaxNumber(int k)
{
int[] min_heap;
min_heap = new int[k + 1]; //min_heap[1] is root.
for (int i = 0; i <= k; i++)
min_heap[i] = int.MinValue;
while (true)
{
int n;
n = Convert.ToInt32(Console.ReadLine());
if(n > min_heap[1])
{
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2 void minWindows(int[] S, int[] T)
{
int m=S.length;
int n=T.length;
int[][] dp=new int[m+1][n+1];
int minindex=-1;
for(int i=0;i<=m;i++)
{
Arrays.fill(dp[i], -1);
dp[i][n]=0;
}
for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=Math.max(0, n-(m-i));j--)
if(S[i]==T[j] && dp[i+1][j+1]>=0)
dp[i][j]=dp[i+1][j+1]+1;
else if... 阅读全帖 |
|
x********3
发帖数: 160 | 3 第二题我想是可以用greedy的。我基本的思路是首尾两项肯定是在选的elements中的。
初始化是选择的序列是0,1,2..k-2,n-1（从0开始计）。循环从倒数第二项开始决定他
应该所在的index的位置，直到正数第二项为止。中间的调整的过程有点复杂，可能可
以简化。下面是我随便写的代码。写得蛮差的，欢迎大家测试指正。
$k = 4;
$a = Array(1, 2, 5, 6, 11, 16, 17);
$records = Array();
for ($i = 1; $i < $k - 1; $i++)
{
$record = new Record($a[$i] - $a[$i - 1], $i);
$records[$i - 1] = $record;
}
$records[$k - 2] = new Record($a[count($a) - 1] - $a[$k - 2], count($a) - 1);
for ($last = $k - 2; $last > 0; $last--)
{
for ($i = $records[$la... 阅读全帖 |
|
f********y
发帖数: 156 | 4 大概这样做:
use an array len[ ] to keep track of the longest subarray ending at A[i]
use {min, minIndex } and {max, maxIndex} to keep track of current min/max
and their indices.
if A[i] > max + 1, then update max and clear min; set len[i] = 1
if A[i] < min -1, then update min and clear max; set len[i] = 1
if A[i] is between min and max, then set len[i] = len[i-1] + 1
if A[i] == max + 1 && minIndex < maxIndex, then min = max; max = A[i],
len[i] = len[i-1] + (maxIndex - minIndex)
if A[i] == min -... 阅读全帖 |
|
o***g
发帖数: 2784 | 5 想要整个数组的1最多，那就要尽量多的flip 0.
因为是只能flip连续的一串数，所以当中有1的话，就相当于起了负作用，就是说本来
是1的，flip之后变成0. 最终结果里的1就少了一个。
如果flip一串数，开头的一个是1，是没有必要的。同样，结尾是1也没有必要，所以这
串数肯定是0开始0结束。
中间一串数，比如01，这两个数做flip对结果是没有影响的。
如果一串数00，flip了的结果是2，就是两个都需要flip。
如果这串数再加上1，变成001，根据前面的结论，我们只会flip前两个，最终结果是1+
2，1是原来有一个1,2是flip了之后出现了2个1.
如果再加一个0，变成0010，如果flip整个串，最终结果是1+3-1，最开始有个1，flip
出来3个1，但是中间的1变成0了，所以需要减掉。
再加一个0，变成00100，结果只能flip整个串，答案是1+4-1.
这时会发现，flip的串里有个0就是+1,有个1就是-1。
我们可以从左往右扫描，遇到0就+1，遇到1就-1，然后找最大值，这个点就是要flip的
右边界。
有个特例011111111000，这种情况，算到第一... 阅读全帖 |
|
c********r
发帖数: 286 | 6 随手写了一下第一题，请大牛们指教轻拍：
public static void findit(int[] a)
{
if(a==null || a.length<4)
{
return;
}
int min = a[0];
int minindex = 0;
int mid = a[0];
int midindex = 0;
int max = a[0];
int maxindex = 0;
for(int i=0;i
if(a[i]
{
min = a[i];
minindex = i;
}else if(max>a[i]&&a[i]>min){
max = a[i];
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 7 我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumulative
array called cum[], where cum[i] = cum[i-1] + A[i-1], and cum[0] = 0. Using
the cum[] array, we can easily find the contiguous sum from i to j, A[i...j
] = cum[j+1] - cum[i], i <= j. Here is an easy trap to fall into, you MUST
define cum[0] = 0 and the size of the cum[] array must be n+1, or else it
would miss including the first element in the c... 阅读全帖 |
|
g*****k
发帖数: 623 | 8 Your solution is actually the same as ibread's solution.
in ibread's solutio's last step, j starts from n to 0, so binary search
in the sorted cum array s.t. cum[i]<= cum[j]-k. Once you find i, you just
get the smallest index by min_index[i].
min_index[i]= min{k | cum[k]
j-min_index[i] is the length of the subarray starting at min_index[i]+1.
我今天写的代码，通过了我的一些随机数据测试（与 brute force 的方法进行比较）。
基于我上次贴的方法，有一些错误，造成一些混乱，不好意思。
1) First, we store the contiguous sum from the first element to a cumul... 阅读全帖 |
|
l******c
发帖数: 2555 | 9 1. one time scan O(n) three variables: max, maxindex, minindex
2. STL library, 递归 is wrong answer
.} |
|
B*********h
发帖数: 800 | 10 ☆─────────────────────────────────────☆
anyfun (anyfun?) 于 (Sat Jan 20 21:46:28 2007) 提到:
find an algorithm for finding the min and max of n numbers by using fewer
than 3n/2 comparisions. ^_^
☆─────────────────────────────────────☆
newnewlife (newlife) 于 (Sat Jan 20 22:04:47 2007) 提到:
Let's try this way:
int max,min;
min=max=a[0];
int minIndex=0,maxIndex=0;
for(int i=1; i < n;i+=2)
{
int bigger=a[i-1],smaller=a[i];
int biggerIndex=i-1, smallerIndex=i;
if(a[i-1] < a[i])
bi |
|
