H***e
发帖数: 476 | 1 两个题目
1.
Given an array of integers, find out number of ways in which you can select
increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
2.
Given a sorted array of n integers, pick up k elements so that the minimal
difference between consecutive elements is maximized (that is choose the
elements to maximize the quantity min(a[i+1] - a[i])) | s******n
发帖数: 3946 | 2 第一题：(修订后）
n*k的matrix，m(i,k)表示第i个元素结尾，长度为k的结果个数
m(i,k) = sum{m(j,k-1), where a[j]
得O(k*n^2)，有更好的办法么？ | s******n
发帖数: 3946 | 3 第二题,搞个升序的dequeue, dequeue[0]表示当前k个连续元素最小difference。
每来一个元素diff[i]，把dequeue上所有比diff[i]大的扔掉，如果dequeue[0]=diff[i
-k]则把dequeue[0]也扔掉。 | A**u
发帖数: 2458 | 4 你的dp水平真不是盖的
【在 s******n 的大作中提到】
: 第二题,搞个升序的dequeue, dequeue[0]表示当前k个连续元素最小difference。
: 每来一个元素diff[i]，把dequeue上所有比diff[i]大的扔掉，如果dequeue[0]=diff[i
: -k]则把dequeue[0]也扔掉。
| i**d
发帖数: 357 | 5 第二题可以用binary search来做。lo = 0, high = (a[len-1]-a[0])/(k-1)+1
然后 对于任意一个Mid，考察是否存在k个数，使得minimum的值大于等于mid。 | s******n
发帖数: 3946 | 6 给个解法吧，我这抛砖引玉
【在 A**u 的大作中提到】
: 你的dp水平真不是盖的
| A**u
发帖数: 2458 | 7 这好像不对吧
m(i,k) 不是以 第i个元素结尾
m(i,k) 应该是 sum{m(j,k-1),where a[j]
【在 s******n 的大作中提到】
: 给个解法吧，我这抛砖引玉
| s******n
发帖数: 3946 | 8 恩。不过这样是O(k*n^2)，有更好的做法吗？
【在 A**u 的大作中提到】
: 这好像不对吧
: m(i,k) 不是以 第i个元素结尾
: m(i,k) 应该是 sum{m(j,k-1),where a[j]
| s****a
发帖数: 528 | | H***e
发帖数: 476 | 10 我做法跟swanswan一样，只不过M[i,k]定义要改成 前i个元素里符合条件的长度为k的
子数组数目。
为啥第一项没有了？ M[i-1,k] 不是分成以a[i]结尾和不以a[i]结尾两种情况吗？
【在 A**u 的大作中提到】
: 这好像不对吧
: m(i,k) 不是以 第i个元素结尾
: m(i,k) 应该是 sum{m(j,k-1),where a[j]
| | | H***e
发帖数: 476 | 11 第二题，
定义M[i,k]为以a[i]为结尾的，长度为k的符合条件的，则
M[i,k] = max_over_j( min ( M[j,k-1], a[i] -a[j]) ) , 0
帮看看有问题么？
select
then
【在 H***e 的大作中提到】
: 两个题目
: 1.
: Given an array of integers, find out number of ways in which you can select
: increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
: the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
: 2.
: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximized (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))
| H***e
发帖数: 476 | 12 怎么greedy呢》
【在 s****a 的大作中提到】
: 第二题好像是GREEDY，不用DP
| s******n
发帖数: 3946 | 13 你这个定义有问题，推不出M[i,k]=sum{M[j,k-1] a[j]
【在 H***e 的大作中提到】
: 我做法跟swanswan一样，只不过M[i,k]定义要改成 前i个元素里符合条件的长度为k的
: 子数组数目。
: 为啥第一项没有了？ M[i-1,k] 不是分成以a[i]结尾和不以a[i]结尾两种情况吗？
| i*o
发帖数: 149 | 14 第一题:
"where a[j]
can be improved to:
"where a[j]
And when k is close to n, the complexity is close to O(n^2) instead of
O(n^3
).
How should we describe this in O notion?
【在 s******n 的大作中提到】
: 恩。不过这样是O(k*n^2)，有更好的做法吗？
| x********3
发帖数: 160 | 15 第二题我想是可以用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[$last - 1]->index + 1; $i < $records[$last]->index; $
i++)
{
$newDiff = $a[$i] - $a[$records[$last - 1]->index];
$minDiff = PHP_INT_MAX;
$minIndex;
for ($j = 0; $j <= $last - 1; $j++)
{
if ($records[$j]->diff < $minDiff)
{
$minIndex = $j;
$minDiff = $records[$j]->diff;
}
}
$tmp = $a[$records[$last]->index] - $a[$i];
if ($tmp > $minDiff)
{
if ($newDiff > $minDiff)
{
array_splice($records, $last, 0, array(new Record($newDiff,
$i)));
$records[$minIndex + 1]->diff += $records[$minIndex]->diff;
array_splice($records, $minIndex, 1);
$records[$last]->diff = $tmp;
}
else
{
$records[$last - 1]->index = $i;
$records[$last - 1]->diff += $newDiff;
$records[$last]->diff = $tmp;
}
}
}
}
printf("0\n");
foreach ($records as $record) printf("%d\n", $record->index);
class Record
{
public $diff;
public $index;
public function __construct($diff, $index)
{
$this->diff = $diff;
$this->index = $index;
}
}
select
then
【在 H***e 的大作中提到】
: 两个题目
: 1.
: Given an array of integers, find out number of ways in which you can select
: increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
: the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
: 2.
: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximized (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))
| l***n
发帖数: 37 | 16 why not 2 4 5, 2 4 6....etc..??
if no, then why is 1 2 6 an answer?
1 2 6 is not in subseq order. I don't get the last output for the first
problem.
select
then
【在 H***e 的大作中提到】
: 两个题目
: 1.
: Given an array of integers, find out number of ways in which you can select
: increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
: the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
: 2.
: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximized (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))
| H***e
发帖数: 476 | 17 sorry typo
已改
【在 l***n 的大作中提到】
: why not 2 4 5, 2 4 6....etc..??
: if no, then why is 1 2 6 an answer?
: 1 2 6 is not in subseq order. I don't get the last output for the first
: problem.
:
: select
: then
| i*******h
发帖数: 216 | 18 首尾两项肯定是在选的elements中的 ==> 这是错误的。
比方说选3个from 2,3,4,6,8,9,
选择2，6，9和3，6，9一样，minimal difference between consecutive elements
都是3.
【在 x********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++)
: {
| c**********e
发帖数: 2007 | 19 Is there a final conclusion for 1?
select
then
【在 H***e 的大作中提到】
: 两个题目
: 1.
: Given an array of integers, find out number of ways in which you can select
: increasing subsequences of length k(k<=n).e.g.array is 1 4 6 2 5 & k=3 then
: the answer is : 1 4 5, 1 2 5,1 4 6, 1 2 6,所以总数是4
: 2.
: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximized (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))
| x********3
发帖数: 160 | 20 虽然这两个是一样的，但是你还是可以选择2，6，9，不是？题目只是说让你选择k个
elements就可以了。
【在 i*******h 的大作中提到】
: 首尾两项肯定是在选的elements中的 ==> 这是错误的。
: 比方说选3个from 2,3,4,6,8,9,
: 选择2，6，9和3，6，9一样，minimal difference between consecutive elements
: 都是3.
| H***e
发帖数: 476 | 21 我说的是你修改前的
用我的定义是有第二项的，也就是你删除的。
其实两个定义很象，复杂度也一样。
【在 s******n 的大作中提到】
: 你这个定义有问题，推不出M[i,k]=sum{M[j,k-1] a[j]
| H***e
发帖数: 476 | 22 编了下method 1(swanswan说的 ) and method 2(我说的）,
没太狂调。
/*
* Given an array of integers, find out number of ways in which you can
* select increasing subsequences of length K(K<=n).e.g.array is 1 4 6 2
5 &
* K=3 then the answer is : 1 4 5, 1 2 5,1 4 6, so total is 3
*/
// define M[i,k] is the # of k-length sequences that ends at i, i.e.
that sunseq ends at i.
public int numOfIncreasingSubSeq(int[] data, int K) {
// boundary
if (data == null || data.length == 0) {
return 0;
}
int[][] M = new int[data.length][K + 1];
// initialization
for (int t = 0; t < data.length; t++) {
for (int f = 0; f <= K; f++) {
M[t][f] = 0;
if (f == 1) {
M[t][f] = 1;
}
}
}
for (int i = 1; i < data.length; i++) {
for (int k = 2; k <= K; k++) {
int sum = 0;
for (int q = 0; q < i; q++) {
if (data[q] < data[i]) {
sum = sum + M[q][k - 1];
}
}
M[i][k] = sum;
}
}
int result = 0;
for (int p = 0; p < data.length; p++) {
result = result + M[p][K];
}
return result;
}
//method 2
// define M[i,k] is the # of length-k sub sequences within a sunstring
// ending at i(the increasing subseq not necessarily ends at i)
public int numOfIncreasingSubSeq2(int[] data, int K) {
// boundary
if (data == null || data.length == 0) {
return 0;
}
int[][] M = new int[data.length][K + 1];
// initialization
for (int t = 0; t < data.length; t++) {
for (int f = 0; f <= K; f++) {
M[t][f] = 0;
if (f == 1) {
M[t][f] = t + 1;
}
}
}
for (int i = 1; i < data.length; i++) {
for (int k = 2; k <= K; k++) {
if (k > i + 1) {
continue;
}
int sum = 0;
//the result comes from two parts: the subseq ends at i, or
not;
for (int b = 0; b < i; b++) {
sum = sum + M[b][k];
}
for (int q = 0; q < i; q++) {
if (data[q] < data[i]) {
sum = sum + M[q][k - 1];
}
}
M[i][k] = sum;
}
}
return M[data.length - 1][K];
}
【在 c**********e 的大作中提到】
: Is there a final conclusion for 1?
:
: select
: then
|
|
