g*****i
发帖数: 2162 | 1 1.Given an array, find the longest subarray which the sum of the subarray
less or equal then the given MaxSum
int[] FindMaxSumArray(int[] array, int maxsum)
2. Given an array of 'n' random integers. Given an integer k<=n. Find the k
numbers such that the minimum difference of all the possible pairs of k
numbers is maximum (maximum among other minimum differences for various
possible selections of k numbers ).
3.Given an array of integers(both positive and negative) divide the array
into two parts(sub-arrays) such that the difference between the sum of
elements in each array is minimum?
原题似乎很简单,修改下这题,如果是a set of integer, divide into two parts,怎么分?
4.Given a string of 10 characters and a number, insert multiplies and
additions to make the characters equal the number
ie: 1232537859, 995 -> 123*2+35*7+8*58 | r*******g
发帖数: 1335 | 2 第一题感觉和那道求"连续subarray和最大"的题很类似，貌似用dp，对每个element维
护两个subarray，一个是它之前最大的符合题意的subarray，一个是包含这个element
自己的符合题意的最大的subarray就可以了。不知道我遗漏什么没有。
第四题很困难，光从个位入手也不行，万一string大了怎么办？有个很笨的dp方法，就
是从第一个乘法位置入手，然后后面继续dp，但是感觉无法简化。同求解
第三题很经典，我只想到了从1一直到中点不停做dp，看看有无sum到这个数，这个题目
中那个both positive and negative应该很重要，可能会巧妙的利用0。同求解
第二题，首先是排序，然后dp，排序后，minimum difference就是相邻的距离的最小值
，相当于把一个区间分为k-1段，使最小那段尽量最大，区间的划分方法只有固定多的
选择。假设总长度为M。
首先，可以证明一定会选第一个数和最后一个数，虽然直观看起来如此，但是也需要证
明。
然后，假设第一段长度为m，那剩下就是如何把M-m分为k-2段。对不同的m对应着不同的
后续划分的最小区间长度，求最大值。只需要对开始若干m做比较即可。后面的划分还
需要维护表格，否则会大量重复计算。思路如此，写起来还是比较麻烦。
k
【在 g*****i 的大作中提到】
: 1.Given an array, find the longest subarray which the sum of the subarray
: less or equal then the given MaxSum
: int[] FindMaxSumArray(int[] array, int maxsum)
: 2. Given an array of 'n' random integers. Given an integer k<=n. Find the k
: numbers such that the minimum difference of all the possible pairs of k
: numbers is maximum (maximum among other minimum differences for various
: possible selections of k numbers ).
: 3.Given an array of integers(both positive and negative) divide the array
: into two parts(sub-arrays) such that the difference between the sum of
: elements in each array is minimum?
| f*******t
发帖数: 7549 | | y*******g
发帖数: 6599 | 4 第四题，因为只能加法和乘法，所以结果是递增的。搜索的时候大部分情况可以直接排除 | r*******g
发帖数: 1335 | 5 什么意思，没看明白，第三题感觉也很烦，难道真的是从0开始一直dp上去到sum/2？貌
似还不清楚思路。
排除
【在 y*******g 的大作中提到】
: 第四题，因为只能加法和乘法，所以结果是递增的。搜索的时候大部分情况可以直接排除
| r*******g
发帖数: 1335 | 6 大概知道你的意思了，你似乎在说，到了一定地步就不用搜索后面，因为值已经大于要
求了。
能详细说下第三题么，我总感觉我dp的想法有问题。
谢谢了。
排除
【在 y*******g 的大作中提到】
: 第四题，因为只能加法和乘法，所以结果是递增的。搜索的时候大部分情况可以直接排除
| g*****i
发帖数: 2162 | 7 第一题和经典题看上去像,但这里是求最长的子数组,还是有明显区别.而且bruteforce
只要O(N^2),dp复杂度肯定不会低于这个.我在想有没有nlogn的解法,但觉得挺难.O(N)
应该很难,举个例子吧.数组是: 1 2 3 4 5 100 -200. MaxSum=109. 用sliding window
的话到了-200还得往左扩张.
第二题你给我启发了,确实这个思路,dp其实复杂度还太高,可以用binary search更快的
找出如何分割,类似以前讨论过的paint问题,我怎么没想到呢,唉.
第四题看来只能brute force一个个尝试了?
element
【在 r*******g 的大作中提到】
: 第一题感觉和那道求"连续subarray和最大"的题很类似，貌似用dp，对每个element维
: 护两个subarray，一个是它之前最大的符合题意的subarray，一个是包含这个element
: 自己的符合题意的最大的subarray就可以了。不知道我遗漏什么没有。
: 第四题很困难，光从个位入手也不行，万一string大了怎么办？有个很笨的dp方法，就
: 是从第一个乘法位置入手，然后后面继续dp，但是感觉无法简化。同求解
: 第三题很经典，我只想到了从1一直到中点不停做dp，看看有无sum到这个数，这个题目
: 中那个both positive and negative应该很重要，可能会巧妙的利用0。同求解
: 第二题，首先是排序，然后dp，排序后，minimum difference就是相邻的距离的最小值
: ，相当于把一个区间分为k-1段，使最小那段尽量最大，区间的划分方法只有固定多的
: 选择。假设总长度为M。
| r*******g
发帖数: 1335 | 8 binary search paint是仿造1373上面的那个题吧，在这里具体怎么做呢？
如果面试我估计想不到。
bruteforce
window
【在 g*****i 的大作中提到】
: 第一题和经典题看上去像,但这里是求最长的子数组,还是有明显区别.而且bruteforce
: 只要O(N^2),dp复杂度肯定不会低于这个.我在想有没有nlogn的解法,但觉得挺难.O(N)
: 应该很难,举个例子吧.数组是: 1 2 3 4 5 100 -200. MaxSum=109. 用sliding window
: 的话到了-200还得往左扩张.
: 第二题你给我启发了,确实这个思路,dp其实复杂度还太高,可以用binary search更快的
: 找出如何分割,类似以前讨论过的paint问题,我怎么没想到呢,唉.
: 第四题看来只能brute force一个个尝试了?
:
: element
| d*******d
发帖数: 2050 | 9 1,如果全部是positive integer的话,可以O(n),但是如果有负数的话,我还没想出来.
2,b-search,
3,这题哪用得上dp?直接用个array存从头到当前位置的sum,再从头到尾走一遍,每个位
置拆一下一比取最优那个不就得了?难道是我题目意思理解错了?
4.估计是recursive做.因该是个NPC问题. | g*****i
发帖数: 2162 | 10 对,方法也和1337的一样啊,没区别吧.
【在 r*******g 的大作中提到】
: binary search paint是仿造1373上面的那个题吧，在这里具体怎么做呢？
: 如果面试我估计想不到。
:
: bruteforce
: window
| | | g*****i
发帖数: 2162 | 11 第三题我也没仔细,如果只是array divide那就O(N)就出来了.
如果是set divide那这题怎么做呢?
【在 d*******d 的大作中提到】
: 1,如果全部是positive integer的话,可以O(n),但是如果有负数的话,我还没想出来.
: 2,b-search,
: 3,这题哪用得上dp?直接用个array存从头到当前位置的sum,再从头到尾走一遍,每个位
: 置拆一下一比取最优那个不就得了?难道是我题目意思理解错了?
: 4.估计是recursive做.因该是个NPC问题.
| m****t
发帖数: 555 | 12 如果是a set of integer, divide into two parts,实际上就是背包问题,可以用DP解
决。
假设集合中所有数的和为S, 则问题就变成了在其中选择一些数，使得这些数的和不大
于但最接近于S/2. 这就是标准的背包问题。
【在 g*****i 的大作中提到】
: 第三题我也没仔细,如果只是array divide那就O(N)就出来了.
: 如果是set divide那这题怎么做呢?
| h**6
发帖数: 4160 | 13 第一题反过来，在数组两端求最短和达到 allsum-maxsum 的两段子数组，中间就是所
求的数组。 | g*****i
发帖数: 2162 | 14 看了下背包问题的wiki,似乎主要是处理nonnegative的输入,有负数也能处理吗?
【在 m****t 的大作中提到】
: 如果是a set of integer, divide into two parts,实际上就是背包问题,可以用DP解
: 决。
: 假设集合中所有数的和为S, 则问题就变成了在其中选择一些数，使得这些数的和不大
: 于但最接近于S/2. 这就是标准的背包问题。
| m****t
发帖数: 555 | 15 如果有负数的话, 就变成了Partition problem.
Find a partition into two subsets S1,S2 such that max(sum(s1),sum(s2)) is
minimized.
http://en.wikipedia.org/wiki/Partition_problem
【在 g*****i 的大作中提到】
: 看了下背包问题的wiki,似乎主要是处理nonnegative的输入,有负数也能处理吗?
| g*****i
发帖数: 2162 | 16 等价转换的思路很好啊,小尾羊以前也提过.
两种基本的情况,也就是只找左边开始的最短子数组大于allsum-maxsum和只找右边的都
可以很容易找到.
问题是如果左右都要包括,也就是类似循环数组的情况,如何找出最短的呢?这个问题和
原问题几乎一模一样,感觉没有减低难度啊.
【在 h**6 的大作中提到】
: 第一题反过来，在数组两端求最短和达到 allsum-maxsum 的两段子数组，中间就是所
: 求的数组。
| h**6
发帖数: 4160 | 17 只对非负有效。
先找左边，然后左边逐个减少，直到没有，右边酌情增加，始终保持和大于等于某个数
。然后找出两边数量最少的情况。 | g*****i
发帖数: 2162 | 18 恩,我刚看了这个,似乎里面没有讨论是否能处理负数,给出了两个approximation算法.
【在 m****t 的大作中提到】
: 如果有负数的话, 就变成了Partition problem.
: Find a partition into two subsets S1,S2 such that max(sum(s1),sum(s2)) is
: minimized.
: http://en.wikipedia.org/wiki/Partition_problem
| g*****i
发帖数: 2162 | 19 如果非负的话,一个sliding window就解决原问题了吧.
看来这题有负数只能brute force了
【在 h**6 的大作中提到】
: 只对非负有效。
: 先找左边，然后左边逐个减少，直到没有，右边酌情增加，始终保持和大于等于某个数
: 。然后找出两边数量最少的情况。
| m**q
发帖数: 189 | 20 第一题可以用部分和的方法，先算出a[0]~a[i] (0<=i
放在数组b[]中，同时把对应的i值记录下来，就是说b数组每个元素是一个
结构，包含a[0]~a[i]的部分和以及对应的i值；然后根据部分和的值sort b数组，
用两个指针指向b数组开头，递增前指针直到前后指针指向的元素的部分和字段的
差值大于或等于MaxSum，然后递增后指针直到两指针指向元素的部分和字段的差
小于或等于MaxSum，在此过程中只要前后指针指向元素的部分和字段差值小于
等于MaxSum时就计算前后指针指向元素的i值字段的差值，并更新最大差值。
算部分和O(n), sort b数组 O(nlgn), 前后指针遍历数组b O(n)，总时间O(nlgn)。
【在 g*****i 的大作中提到】
: 1.Given an array, find the longest subarray which the sum of the subarray
: less or equal then the given MaxSum
: int[] FindMaxSumArray(int[] array, int maxsum)
: 2. Given an array of 'n' random integers. Given an integer k<=n. Find the k
: numbers such that the minimum difference of all the possible pairs of k
: numbers is maximum (maximum among other minimum differences for various
: possible selections of k numbers ).
: 3.Given an array of integers(both positive and negative) divide the array
: into two parts(sub-arrays) such that the difference between the sum of
: elements in each array is minimum?
| | | g*****i
发帖数: 2162 | 21 是个好思路,但是觉得有问题.前指针到了临界位时(再移动的话和后指针差距就超过
maxsum),前指针和它左边一直到后指针的每个位置都满足两者差<=MaxSum,但是你的方
法没有全部比较他们,因为后指针前进了一会可能前指针又前进了.
举例: 数组 3 -1 -1 3 1 1, MaxSum=3
b[]={(3,0),(2,1),(1,2),(4,3),(5,4),(6,5)} 前面是和,后面是i
排序后 b={(1,2),(2,1),(3,0),(4,3),(5,4),(6,5)}
第一次前指针到(5,4)就超过MaxSum了,用你的方法(3,0)和(5,4)不会比较,因为后指针
到(2,1)的时候前指针就继续前进了.
【在 m**q 的大作中提到】
: 第一题可以用部分和的方法，先算出a[0]~a[i] (0<=i: 放在数组b[]中，同时把对应的i值记录下来，就是说b数组每个元素是一个
: 结构，包含a[0]~a[i]的部分和以及对应的i值；然后根据部分和的值sort b数组，
: 用两个指针指向b数组开头，递增前指针直到前后指针指向的元素的部分和字段的
: 差值大于或等于MaxSum，然后递增后指针直到两指针指向元素的部分和字段的差
: 小于或等于MaxSum，在此过程中只要前后指针指向元素的部分和字段差值小于
: 等于MaxSum时就计算前后指针指向元素的i值字段的差值，并更新最大差值。
: 算部分和O(n), sort b数组 O(nlgn), 前后指针遍历数组b O(n)，总时间O(nlgn)。
| d*******d
发帖数: 2050 | 22 nodnod,归根结底还是负数找麻烦.
【在 g*****i 的大作中提到】
: 是个好思路,但是觉得有问题.前指针到了临界位时(再移动的话和后指针差距就超过
: maxsum),前指针和它左边一直到后指针的每个位置都满足两者差<=MaxSum,但是你的方
: 法没有全部比较他们,因为后指针前进了一会可能前指针又前进了.
: 举例: 数组 3 -1 -1 3 1 1, MaxSum=3
: b[]={(3,0),(2,1),(1,2),(4,3),(5,4),(6,5)} 前面是和,后面是i
: 排序后 b={(1,2),(2,1),(3,0),(4,3),(5,4),(6,5)}
: 第一次前指针到(5,4)就超过MaxSum了,用你的方法(3,0)和(5,4)不会比较,因为后指针
: 到(2,1)的时候前指针就继续前进了.
| d*******d
发帖数: 2050 | 23 这不是背包问题,这是subset-sum问题,是npc问题.
【在 m****t 的大作中提到】
: 如果是a set of integer, divide into two parts,实际上就是背包问题,可以用DP解
: 决。
: 假设集合中所有数的和为S, 则问题就变成了在其中选择一些数，使得这些数的和不大
: 于但最接近于S/2. 这就是标准的背包问题。
| s*******f
发帖数: 1114 | 24 //1.Given an array, find the longest subarray which the sum of the subarray
//less or equal then the given MaxSum
//int[] FindMaxSumArray(int[] array, int maxsum)
//can only deal with all positive, or all negative
void FindMaxSumArray(int *in, int len, int *out, int maxsum){
if (!in || len < 1 || !out)
return 0;
int i = 0;
int j = 0;
int sum = 0;
int maxi = 0;
int maxj = 0;
while(j < len){
sum += in[j];
if (sum > maxsum){
if (j - i > maxj - maxi){
maxi = i;
maxj = j;
}
sum -= in[i];
++i;
}
++j;
}
if (sum <= maxsum && len - i > maxj - maxj){
maxi = i;
maxj = len;
}
for (int i = maxi; i < maxj; ++i)
out[i] = i[i];
return;
} | s*******f
发帖数: 1114 | 25 //2. Given an array of 'n' random integers. Given an integer k<=n. Find the
k
//numbers such that the minimum difference of all the possible pairs of k
//numbers is maximum (maximum among other minimum differences for various
//possible selections of k numbers ).
//
void FindMaxMinGapSubArray(int *in, int len, std::vector *out, int k){
if (!in || len < 1 || !out || len < k || k < 2)
return;
std::sort(in, in + len);
// 1 2 3 4 5
int max_gap = (*(in + len - 1) - *in) / (k - 1);
int min_gap = 0;
while (min_gap <= max_gap){
int mid = (max_gap + min_gap) / 2;
int prei = 0;
int curk = 1;
std::vector v;
v.clear();
v.push_back(in[0]);
for (int i = 1; i < len; ++i){
if (in[i] - in[prei] < mid)
continue;
++curk;
v.push_back(in[i]);
prei = i;
}
if (curk < k){
max_gap = mid - 1;
}else{
out->assign(v.begin(), v.begin() + (std::min(k, static_cast
(v.size()))));
min_gap = mid + 1;
}
}
}
k
【在 g*****i 的大作中提到】
: 1.Given an array, find the longest subarray which the sum of the subarray
: less or equal then the given MaxSum
: int[] FindMaxSumArray(int[] array, int maxsum)
: 2. Given an array of 'n' random integers. Given an integer k<=n. Find the k
: numbers such that the minimum difference of all the possible pairs of k
: numbers is maximum (maximum among other minimum differences for various
: possible selections of k numbers ).
: 3.Given an array of integers(both positive and negative) divide the array
: into two parts(sub-arrays) such that the difference between the sum of
: elements in each array is minimum?
|
|
