avatar
s*n
1
Given an N x M matrix having only positive values, we have to nullify the
matrix i.e make all entries 0.
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time
Find the minimum number of operations required to nullify the matrix.
Note: no range of input was given
http://www.careercup.com/question?id=14691685
avatar
S*t
2
其实就是写成二进制就好办了。不过感觉偏数学了点

【在 s*****n 的大作中提到】
: Given an N x M matrix having only positive values, we have to nullify the
: matrix i.e make all entries 0.
: We are given two operations
: 1) multiply each element of any one column at a time by 2.
: 2) Subtract 1 from all elements of any one row at a time
: Find the minimum number of operations required to nullify the matrix.
: Note: no range of input was given
: http://www.careercup.com/question?id=14691685

avatar
s*u
3
求具体解法

【在 S********t 的大作中提到】
: 其实就是写成二进制就好办了。不过感觉偏数学了点
avatar
b*m
4
能不能用溢出的方式把某些数字清零啊?

【在 s*****n 的大作中提到】
: Given an N x M matrix having only positive values, we have to nullify the
: matrix i.e make all entries 0.
: We are given two operations
: 1) multiply each element of any one column at a time by 2.
: 2) Subtract 1 from all elements of any one row at a time
: Find the minimum number of operations required to nullify the matrix.
: Note: no range of input was given
: http://www.careercup.com/question?id=14691685

avatar
s*n
5
我不知道行不行,呵呵。感觉上好像不行。

【在 b***m 的大作中提到】
: 能不能用溢出的方式把某些数字清零啊?
avatar
p*2
6

感觉大牛现在做的都是非人类的题目。

【在 s*****n 的大作中提到】
: 我不知道行不行,呵呵。感觉上好像不行。
avatar
b*m
7
为什么不行呢?乘二不就是左移一位吗,最左边的位是不是就木有了?

【在 s*****n 的大作中提到】
: 我不知道行不行,呵呵。感觉上好像不行。
avatar
D*d
8
这是为什么特别说明 数 没有 range 的原因吧

【在 b***m 的大作中提到】
: 为什么不行呢?乘二不就是左移一位吗,最左边的位是不是就木有了?
avatar
b*m
9
也许本题可以理解为默认没有溢出,否则这题就没意思了,一直往左移就完了。
avatar
p*2
10

一直往左移就是最优吗?

【在 b***m 的大作中提到】
: 也许本题可以理解为默认没有溢出,否则这题就没意思了,一直往左移就完了。
avatar
b*m
11

呵呵,当然不一定是最优了,但是这可以是选择之一了。

【在 p*****2 的大作中提到】
:
: 一直往左移就是最优吗?

avatar
p*2
12

这题是要求最优。

【在 b***m 的大作中提到】
:
: 呵呵,当然不一定是最优了,但是这可以是选择之一了。

avatar
b*m
13

我知道。我只是说,如果考虑溢出的话,情况就复杂了。应该不是本题要考虑的因素。

【在 p*****2 的大作中提到】
:
: 这题是要求最优。

avatar
p*2
14

大牛有什么好的思路?

【在 b***m 的大作中提到】
:
: 我知道。我只是说,如果考虑溢出的话,情况就复杂了。应该不是本题要考虑的因素。

avatar
b*m
15

刚刚花了一点儿时间写了代码,后来发现跟150上的思路差不多。没什么特别的,凑数
吧,还在考虑怎么优化。
void DoubleColumn(int **ppn, int nNumRows, int idCol)
{
if( !ppn ) return;
for( int i = 0; i < nNumRows; i++ )
{
ppn[i][idCol] *= 2;
}
}
void DecreaseRow(int **ppn, int nNumCols, int idRow)
{
if( !ppn ) return;

for( int i = 0; i < nNumCols; i++ )
{
ppn[idRow][i]--;
}
}
vector GetColsWithMinValue(int **ppn, int nNumCols, int idRow)
{
int i, nMin = MAX_INT;
vector vecMinCols;

if( !ppn || nNumCols <= 0 || idRow < 0 )
return vecMinCols;
for( i = 0; i < nNumCols; i++ )
{
if( ppn[idRow][i] < nMin )
nMin = ppn[idRow][i];
}
for( i = 0; i < nNumCols; i++ )
{
if( ppn[idRow][i] == nMin )
vecMinCols.push_back(i);
}
return vecMinCols;
}
void NullifyMatrix(int **ppn, int M, int N) // Matrix, NumCols, NumRows
{
if( !ppn || M <= 0 || N <= 0 ) return;

for( int i = 0; i < N; i++ )
{
vector vecMinCols = GetColsWithMinValue(ppn, M, i);
if( vecMinCols.size() == 0 ) break; // Something wrong
int nMin = ppn[i][vecMinCols[0]];

for( int j = 0; j < nMin - 1; j++ )
DecreaseRow(ppn, M, i);

bool bFoundGreaterThan1 = false;
for( j = 0; j < M; j++ )
{
if( ppn[i][j] > 1 )
{
bFoundGreaterThan1 = true;
break;
}
}
if( bFoundGreaterThan1 )
{
for( int k = 0; k < vecMinCols.size(); k++ )
DoubleColumn(ppn, i, k);
i--;
}
else
DecreaseRow(ppn, M, i);
}
}

【在 p*****2 的大作中提到】
:
: 大牛有什么好的思路?

avatar
s*n
16
新版的150收了这题?
这个程序是一个基本解,可以考虑一些优化。

【在 b***m 的大作中提到】
:
: 刚刚花了一点儿时间写了代码,后来发现跟150上的思路差不多。没什么特别的,凑数
: 吧,还在考虑怎么优化。
: void DoubleColumn(int **ppn, int nNumRows, int idCol)
: {
: if( !ppn ) return;
: for( int i = 0; i < nNumRows; i++ )
: {
: ppn[i][idCol] *= 2;
: }

avatar
b*m
17
我的意思是careercup,不是书。
优化还在考虑,目前思路不太清晰。

【在 s*****n 的大作中提到】
: 新版的150收了这题?
: 这个程序是一个基本解,可以考虑一些优化。

avatar
p*2
18

能不能先谈谈你思路呀?

【在 b***m 的大作中提到】
: 我的意思是careercup,不是书。
: 优化还在考虑,目前思路不太清晰。

avatar
b*m
19
思路不太清晰的意思就是迷茫得木有思路。;-)

【在 p*****2 的大作中提到】
:
: 能不能先谈谈你思路呀?

avatar
p*2
20

没思路都把code写完了,实在是太牛了。

【在 b***m 的大作中提到】
: 思路不太清晰的意思就是迷茫得木有思路。;-)
avatar
b*m
21

不是吧,写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候,用A*算法
对所有关卡的地图数据做预处理,最大的512x512的地图,用当时配置的机器运行需要2
个小时(没办法,当时机器太慢了)。后来CTO嫌太慢,人家熬了一个通宵对算法做了
优化,结果同样的地图在同样的机器上运行,只要10分钟。简直羞愤得我要死啊……差
距太大了。人家现在在硅谷某中型软件公司做CTO。:-(

【在 p*****2 的大作中提到】
:
: 没思路都把code写完了,实在是太牛了。

avatar
p*2
22

要2
我的意思是说你现在写的code 是什么思路呀?不是说最优思路。

【在 b***m 的大作中提到】
:
: 不是吧,写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候,用A*算法
: 对所有关卡的地图数据做预处理,最大的512x512的地图,用当时配置的机器运行需要2
: 个小时(没办法,当时机器太慢了)。后来CTO嫌太慢,人家熬了一个通宵对算法做了
: 优化,结果同样的地图在同样的机器上运行,只要10分钟。简直羞愤得我要死啊……差
: 距太大了。人家现在在硅谷某中型软件公司做CTO。:-(

avatar
b*m
23
现在的思路就是一个劲把当前行的大数字往下降呗,一直降到所有数字都是1,不知道
有哪些地方可以优化呢?
avatar
b*m
24

哦,刚刚回复一帖大概解释了一下。

【在 p*****2 的大作中提到】
:
: 要2
: 我的意思是说你现在写的code 是什么思路呀?不是说最优思路。

avatar
b*m
25
貌似可以考虑不要把当前行的最小数字减到1,这样要double好多次才能尽量跟最大数
凑齐。也许可以考虑什么公倍数之类的?
avatar
p*2
26

这个能保证是最优的吗?
我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。

【在 b***m 的大作中提到】
: 现在的思路就是一个劲把当前行的大数字往下降呗,一直降到所有数字都是1,不知道
: 有哪些地方可以优化呢?

avatar
b*m
27

肯定不是最优的,理由我在上面说过了。还在思考中……

【在 p*****2 的大作中提到】
:
: 这个能保证是最优的吗?
: 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。

avatar
C*U
28
对!现在不是程序优不优的问题,而是对不对的问题。题目要求最少操作次数。

【在 p*****2 的大作中提到】
:
: 这个能保证是最优的吗?
: 我的意思是只要能保证解是最优就可以了。具体实现的算法不用是最优。

avatar
b*m
29

嗯,有了思路后,程序的实现很简单。现在的问题就是思路还不是最优。

【在 C***U 的大作中提到】
: 对!现在不是程序优不优的问题,而是对不对的问题。题目要求最少操作次数。
avatar
b*m
30
我又稍微想了一下,觉得现在的程序有个致命问题,导致几乎肯定不是最优解(最少操
作次数):我们是解决了一行(全为0)后,再解决下一行,由于使得数字变小的唯一
操作就是该行全部减1,因此某行最少操作次数不可能少于该行最大的数字。由于我们
不断地把某些列乘2,其后果很可能是某些行最大的数字会被增大,导致操作次数增加
。这是由于我们只着眼于局部,而忽略了全局。改变一下思路,我们不苛求先解决一行
,而是扫描所有的行,把所有行的最小数字减到1,然后把所有含1的列都加倍,再扫描
所有的行,然后再加倍……这样应该可以避免增加无谓的减1的操作,几乎肯定比我前
面那个策略更优(但是我还无法确定是否最优)。请大家指正。
avatar
b*m
31
现在的策略如下:
1、设当前行为第1行;
2、如果该行数字全部相同,假设是N,那么进行N次减1操作,并且跳到第5步;
3、扫描出最小的数字,假设是A;
4、把该行进行A-1次减1操作;
5、如果不是最后一行,移动到下一行,并且回到第2步;
6、设当前列为第1列;
7、扫描该列是否有1,有的话该列进行乘2操作;
8、如果不是最后一列,移动到下一列,并且回到第6步;
9、回到第1步。
大家请提提意见。
avatar
l*b
32
这个有问题吧
1 50
50 1
是不是越来越大了

【在 b***m 的大作中提到】
: 现在的策略如下:
: 1、设当前行为第1行;
: 2、如果该行数字全部相同,假设是N,那么进行N次减1操作,并且跳到第5步;
: 3、扫描出最小的数字,假设是A;
: 4、把该行进行A-1次减1操作;
: 5、如果不是最后一行,移动到下一行,并且回到第2步;
: 6、设当前列为第1列;
: 7、扫描该列是否有1,有的话该列进行乘2操作;
: 8、如果不是最后一列,移动到下一列,并且回到第6步;
: 9、回到第1步。

avatar
b*m
33

是哦,这个可怎搞。

【在 l*******b 的大作中提到】
: 这个有问题吧
: 1 50
: 50 1
: 是不是越来越大了

avatar
l*8
34
32 50
1600 1
18 36
1600 1
36 36
3200 1
0 0
3200 1
0 0
3200 2048
0 0
2304 1152
0 0
2304 2304
0 0
0 0
avatar
b*m
35
嗯,看来还不仅仅是翻番,还得考虑倍数关系。有什么通则呢?
avatar
l*8
36
不知道啊,这题很复杂,水很深……
avatar
b*m
37
嗯,解出来不难,最优解看来不易。与其说是道编程算法题,不如说是道数学题。
avatar
l*b
38
厉害,这样每一行都会解了。
exactly需要这一行的MAX次减法和对每一项a_k m次乘以2,2^{m-1}a_k < MAX <= 2^m
a_k.
多行的情形,还是很复杂。。。每一行的MAX和没一项的m值都是刻画这个问题混乱程度
的指标。

【在 l***8 的大作中提到】
: 32 50
: 1600 1
: 18 36
: 1600 1
: 36 36
: 3200 1
: 0 0
: 3200 1
: 0 0
: 3200 2048

avatar
q*m
39
能套用 DP吗 ?
不过感觉情况太多了.
第一步就有 M + N种情况.

【在 s*****n 的大作中提到】
: Given an N x M matrix having only positive values, we have to nullify the
: matrix i.e make all entries 0.
: We are given two operations
: 1) multiply each element of any one column at a time by 2.
: 2) Subtract 1 from all elements of any one row at a time
: Find the minimum number of operations required to nullify the matrix.
: Note: no range of input was given
: http://www.careercup.com/question?id=14691685

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。