w****o 发帖数: 2260 | 1 是8.10
给一个数组(数组的数没有任何的限制) 和一个target,要求一个subarray with the
sum closest to the target.
提示是说要用到cululative array,就是可以先算出来a[0...i]的和。 | p****n 发帖数: 148 | 2 8.10是什么啊?
第8章第10节?
第8章第10题?
是哪个版本,第几页啊?
贴上来看看?
这个问题有时间复杂度为O(n log(n))的算法。
能做得更好吗?我不知道
【在 w****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是8.10 : 给一个数组(数组的数没有任何的限制) 和一个target,要求一个subarray with the : sum closest to the target. : 提示是说要用到cululative array,就是可以先算出来a[0...i]的和。
| x*******5 发帖数: 152 | 3 终于有人做pearl,给一个我的解答
此题是第9题的扩展,第9题求的是subvector whose sum is close to zero,解答如下
(python)
def Subvector_Zero(v):
"find the subvector whose sum is close to zero"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(1,len(v)):
minv=min(minv,s[i]-s[i-1])
return minv
C++:
/*Description: find the subvector whose sum is close to zero
Input: vector t
Output: int
K.O.: auxiliary sum array
*/
int Pearl::Vector_zero(vector t){
int n=t.size();
vector sum(n,0);
sum[0]=t[0];
for(int i=1;i
sum[i]=t[i]+sum[i-1];
sort(sum.begin(),sum.end());
int minv=numeric_limits::max();
for(int i=1;i
minv=min(minv,sum[i]-sum[i-1]);
return minv;
}
于是要求sum 为k, 就是在sum array中排序后进行binary search找离他距离为k的j,
然后比较找出最小值,即可,有点麻烦,不过还好
def BS_range(v,x):
"find x within v if found return index otherwise return the index\
of its closest value"
l,r=0,len(v)-1
if x<=v[l]: return l
if x>=v[r]: return r
while l<=r:
mid=l+(r-l)//2
if v[mid]<=x and x<=v[mid+1]: return mid+1
elif v[mid+1]
else:r=mid
def Subvector_k(v,k):
"find the subvector whose sum is k"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
return minv+k
C++:
/*Description: given an sorted array, if a value is in it, return its index;
otherwise return
the index of closest value
Input: vector t, int x
Output: int
K.O.: Binary Search Variant
*/
int Pearl::BS_range(vector t, int x){
int l=0,r=t.size()-1;
if(x<=t[l]) return l;
if(x>=t[r]) return r;
while(l<=r){
int mid=l+(r-l)/2;
if(t[mid]<=x&&x<=t[mid+1]) return mid+1;
else if(t[mid+1]
else r=mid;
}
return -1;
}
/*Description: find the subvector whose sum is close to K
Input: vector t, int x
Output:int
K.O.: similar to vector_zero but with BS_range*/
int Pearl::Subvector_k(vector t, int x){
int n=t.size();
vector sum(n,0);
sum[0]=t[0];
for(int i=1;i
sum[i]=t[i]+sum[i-1];
sort(sum.begin(),sum.end());
int minv=numeric_limits::max();
for(int i=0;i
int j=BS_range(sum,sum[i]+x);
int jj=(j
minv=min(minv,abs(sum[j]-sum[i]-x));
minv=min(minv,abs(sum[jj]-sum[i]-x));
}
return abs(minv-x);
} | p****n 发帖数: 148 | 4 返回值是什么意思?
一会儿 return minv+k
一会儿 return abs(minv-x);
下
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 终于有人做pearl,给一个我的解答 : 此题是第9题的扩展,第9题求的是subvector whose sum is close to zero,解答如下 : (python) : def Subvector_Zero(v): : "find the subvector whose sum is close to zero" : s=[0 for a in range(len(v))] : s[0]=v[0] : for i in range(1,len(v)): : s[i]=v[i]+s[i-1] :
| x*******5 发帖数: 152 | 5 恩,对的,c++应该该为minv+x,谢谢啦
【在 p****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 返回值是什么意思? : 一会儿 return minv+k : 一会儿 return abs(minv-x); : : 下
| w***y 发帖数: 6251 | | p*****2 发帖数: 21240 | | z*********8 发帖数: 2070 | 8 subarray 是指连续的数吧? 你sort之后顺序不就乱了?
下
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 终于有人做pearl,给一个我的解答 : 此题是第9题的扩展,第9题求的是subvector whose sum is close to zero,解答如下 : (python) : def Subvector_Zero(v): : "find the subvector whose sum is close to zero" : s=[0 for a in range(len(v))] : s[0]=v[0] : for i in range(1,len(v)): : s[i]=v[i]+s[i-1] :
| l*********8 发帖数: 4642 | 9 he/she sorted the array of the sum,not the original array.
【在 z*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : subarray 是指连续的数吧? 你sort之后顺序不就乱了? : : 下
| p****n 发帖数: 148 | 10 但你的返回值到底是什么意思呢?
最佳子数组的元素的和?
怎么猜似乎都和你的程序不符
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩,对的,c++应该该为minv+x,谢谢啦
| | | x*******5 发帖数: 152 | 11 返回的值是离k最近的值,如果要数组的开始和结束的话,就中间记录起点和终点就可
以了
其实不用猜,每一个程序都是runnable code,可以去运行 | p****n 发帖数: 148 | 12 运行后更猜不着了
比如
输入是
t = {11, -30, -20} x = 20
输出是
30 if return abs(minv+x);
10 if return abs(minv-x)
啥意思啊?
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 返回的值是离k最近的值,如果要数组的开始和结束的话,就中间记录起点和终点就可 : 以了 : 其实不用猜,每一个程序都是runnable code,可以去运行
| x*******5 发帖数: 152 | 13 谢谢指正,修正两个bug,原始程序中只考虑了vector s[j]-s[i],也就是位于i和j之
间的subarray,person同学给出的test case 是[0,i]之间的subarray,程序修正如下
def Subvector_Zero(v):
"find the subvector whose sum is close to zero"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(1,len(v)):
minv=min(minv,abs(s[i]-s[i-1]))
for c in s:
minv=min(minv,abs(c))
return minv
返回值是离0的最近距离
test case
v=[11,-30,-20],
output:
11
def Subvector_k(v,k):
"find the subvector whose sum is k"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
for c in s:
minv=min(minv,abs(c-k))
return minv
test case
v=[11, -30, -20]
k=20
Output:
9 (离20的最近距离)
如果要求具体的subarray的start和end,可以在程序中记录
谢谢person同学坚持的质疑
【在 p****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 运行后更猜不着了 : 比如 : 输入是 : t = {11, -30, -20} x = 20 : 输出是 : 30 if return abs(minv+x); : 10 if return abs(minv-x) : 啥意思啊?
| x*******5 发帖数: 152 | 14 我是把pearl上的题做了3遍,用C++和python都写了一遍,收益很大,虽然每道题都测
试了,但还是会有bug,非常感谢person同学认真的阅读和质疑,给我很大帮助。希望
大家一起认真思考,认真coding, 认真找bug | p*****2 发帖数: 21240 | 15
一共有多少道习题呢?
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我是把pearl上的题做了3遍,用C++和python都写了一遍,收益很大,虽然每道题都测 : 试了,但还是会有bug,非常感谢person同学认真的阅读和质疑,给我很大帮助。希望 : 大家一起认真思考,认真coding, 认真找bug
| a***g 发帖数: 234 | 16 几十道不到100道吧
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 一共有多少道习题呢?
| x*******5 发帖数: 152 | 17 这个是我的题库,还有一些题没有coding,比如back of envelop计算,idea思考,等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_
Permute; String::string_permute_noduplicate)
69. Output legal braces of { and } (String::brace)
70. Tokenize a string in C++ (stringstream) (String::Split)
71. Write the BS_first and BS_last (binary search for the first occurrence
of an element and last occurrence of an element ) in iterative and recursive
fashioin (BS_first; BS_last)
72. Write a function to compute the n-th power of x
73. Maximum sum subvector (auxiliary array, Divide and Conquer, Dynamic
Programming, Improved D&C) (Maxium_Vector; Maxium_Vector_dp; Maxium_Vector_
rec)
74 Maximum sum submatrix (extended to 2-dimension array) (Maxium_Rectangle)
75. Write a function to find the subvctor whose sum is close to zero (Vector
_zero)
76 Write a function to binary search the range of value in an sorted array (
BS_range)
77 Write a function to find the subvector whose sum is close to K (Subvector
_k)
78. Write an efficient memory allocation in C-style (mallocation)
79. InsertSort (insertSort)
80. QuickSort (time complexity improvement, space complexity improvement) (
quicksort)
81. Select k-th element (selectK)
82. RadixSort (radixSort; lsd_radix_sort; msd_radix_sort)
83. BubbleSort, SelectSort, ShellSort (bubbleSort; selectSort; shellSort)
84. Compare insertSort, mergeSort, quickSort and heapSort
85. Write a quickSort function with fat pivot (i.e. many elements are the
same with the pivot)
86. countSort for integers (quicksort_fatpivot)
87. Write a function to generate m distinct integer with equal probability
but chooses some subset with greater probability than others
88. Write a function to generate all m-size subarry of an array of size n (
SubArrayS_size_m)
89. Reservoir Sampling: sample 1 and k elements without knowing the total
sample size (ReservoirSampling)
90. Using bit operation to implement add, subtract, multiply and divide (add
subtract multiply divide)
91. Implement two functions of heap operation: siftup and siftdown (siftup,
siftdown)
92. Implement a Huffman tree using priority queue (HuffmanTree)
93. Compute the sum of a large set of float (Sum_float)
94. Find the largest k number from a large sequence of numbers (Find_Top_K)
95. Find the second minimum element in an array using least compare times (
SecondMin)
96. Given a bunch of words, build a hashtable of these words (Hash)
97. Given a string, find the longest duplication subarray (String::Duplicate
_Subarray). | p*****2 发帖数: 21240 | 18
都是很经典的题吗?
我也准备买本练练了。
【在 a***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 几十道不到100道吧
| x*******5 发帖数: 152 | 19 题目是37道,但是程序(函数数目)是70个,不少题都是要求编两三个程序的,比如
array rotation, string permutation, quick sort(这个就要编5个,各种quicksort,
解决时间,空间,tail-recursion问题, fat-pivot), quicksort还有变体: dutch
flag, select-k,等等
我自己在面试的时候,所有问题都来自这个,有一题还要我分析tournament tree(这
个是pearl的一个小题目,我当时偷懒没想清楚,所以不能偷懒啊),不过我当时的程
序做错了,和面试官一讨论发现错了。另一次面试全是quicksort,如果做了pearl的题
,应该不会有问题。
欢迎大家一起讨论,这些代码一定有不少hidden bugs | a***g 发帖数: 234 | 20 这书不错,值得收藏
作者很有趣
2爷加油!
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 都是很经典的题吗? : 我也准备买本练练了。
| | | p*****2 发帖数: 21240 | 21
多谢推荐。这几天一直在犹豫买哪本呢。决定买它了。
【在 a***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这书不错,值得收藏 : 作者很有趣 : 2爷加油!
| p****n 发帖数: 148 | 22 要不要再做一遍?
test case
v=[-10,-100,-1000,-10000]
k=123
Output:
23
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我是把pearl上的题做了3遍,用C++和python都写了一遍,收益很大,虽然每道题都测 : 试了,但还是会有bug,非常感谢person同学认真的阅读和质疑,给我很大帮助。希望 : 大家一起认真思考,认真coding, 认真找bug
| h*********e 发帖数: 247 | 23 then at least O(n^2) 吧.
【在 w****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是8.10 : 给一个数组(数组的数没有任何的限制) 和一个target,要求一个subarray with the : sum closest to the target. : 提示是说要用到cululative array,就是可以先算出来a[0...i]的和。
| x*******5 发帖数: 152 | 24 很好的test case,不过我再次阅读pearl发现,在原始题目中,即找subarray such
that its sum is maximal中有一个限制条件就是数组不能全为负,经过思考,我的程
序同样要满足这个限制条件,否则会出错。因为在这种情况,只要求出数组最大值就可
以了,o(n)解法。所以代码修改如下
def Subvector_k(v,k):
"find the subvector whose sum is k"
All_Negative=True
if [c for c in v if c>0]:
All_Negative=False
if All_Negative:
return max(v)
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
print v
print s
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
for c in s:
minv=min(minv,abs(c-k))
return minv
test case
v=[-10,-100,-1000,-10000]
k=123
Output:
-10
【在 p****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要不要再做一遍? : test case : v=[-10,-100,-1000,-10000] : k=123 : Output: : 23
| x*******5 发帖数: 152 | 25 全部都是O(nlogn),主要用于对cumulative array 排序
【在 h*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : then at least O(n^2) 吧.
| p****n 发帖数: 148 | 26 test case
v=[ 10,-100,-1000,-10000]
k=123
Output:
23
要不要你再做一遍?
另,可否寄我一份你看的pearl啊?想看看原题的描述,包括上下文
【在 x*******5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很好的test case,不过我再次阅读pearl发现,在原始题目中,即找subarray such : that its sum is maximal中有一个限制条件就是数组不能全为负,经过思考,我的程 : 序同样要满足这个限制条件,否则会出错。因为在这种情况,只要求出数组最大值就可 : 以了,o(n)解法。所以代码修改如下 : def Subvector_k(v,k): : "find the subvector whose sum is k" : : All_Negative=True : if [c for c in v if c>0]: : All_Negative=False
| x*******5 发帖数: 152 | 27 这次还是要感谢,代码的Logic是错的,重新再看pearl, 如附件所示
重新修改代码如下
def Subvector_k(v,k):
"find the subvector whose sum is k"
All_Negative=True
if [c for c in v if c>0]:
All_Negative=False
if All_Negative:
return max(v)
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
if j==i: break
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]+s[i]-k))
minv=min(minv,abs(s[jj]+s[i]-k))
for c in s:
minv=min(minv,abs(c-k))
return minv
重要修改 原来的s[j]-s[i]-k编程s[j]+s[i]-k,如pearl上所示。理解不对,抱歉抱歉啊 |
|