w*x
2 楼
瞬间想到了8皇后
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
b*d
3 楼
my first thought is probing and pruning, maybe too slow.
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
t*t
4 楼
care to elaborate?
n! complexity?
【在 b*******d 的大作中提到】
:
: my first thought is probing and pruning, maybe too slow.
n! complexity?
【在 b*******d 的大作中提到】
:
: my first thought is probing and pruning, maybe too slow.
p*2
5 楼
不就是0-n-1的排列吗？
i*h
6 楼
什么叫0-n-1的排列?
【在 p*****2 的大作中提到】
: 不就是0-n-1的排列吗？
【在 p*****2 的大作中提到】
: 不就是0-n-1的排列吗？
p*2
7 楼
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
就这么几种情况吧？
【在 i***h 的大作中提到】
: 什么叫0-n-1的排列?
t*t
8 楼
u mean n! complexity?
too slow bah
【在 p*****2 的大作中提到】
:
: 0 1 2
: 0 2 1
: 1 0 2
: 1 2 0
: 2 0 1
: 2 1 0
: 就这么几种情况吧？
too slow bah
【在 p*****2 的大作中提到】
:
: 0 1 2
: 0 2 1
: 1 0 2
: 1 2 0
: 2 0 1
: 2 1 0
: 就这么几种情况吧？
b*d
9 楼
解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
很少的prune，可能有些large test不过。
【在 t**********t 的大作中提到】
: care to elaborate?
: n! complexity?
w*x
10 楼
一维数组record, 递归得了
i*h
11 楼
如果有负数呢?
【在 b*******d 的大作中提到】
:
: 解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
: 经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
: 不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
: 很少的prune，可能有些large test不过。
【在 b*******d 的大作中提到】
:
: 解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
: 经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
: 不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
: 很少的prune，可能有些large test不过。
p*2
12 楼
面试题需要什么过larget test呢？
【在 b*******d 的大作中提到】
:
: 解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
: 经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
: 不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
: 很少的prune，可能有些large test不过。
i*h
13 楼
考试只能用递归了
【在 w****x 的大作中提到】
: 一维数组record, 递归得了
【在 w****x 的大作中提到】
: 一维数组record, 递归得了
p*2
14 楼
有啥slow的？面试题这样的多了。
【在 t**********t 的大作中提到】
: u mean n! complexity?
: too slow bah
p*2
15 楼
可以先sort
【在 i***h 的大作中提到】
: 如果有负数呢?
i*7
16 楼
本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
i*h
17 楼
???
sort啥? 矩阵是不能动的
【在 p*****2 的大作中提到】
:
: 可以先sort
sort啥? 矩阵是不能动的
【在 p*****2 的大作中提到】
:
: 可以先sort
p*2
18 楼
不好意思。说错了。
【在 i***h 的大作中提到】
: ???
: sort啥? 矩阵是不能动的
i*h
19 楼
估计就是考写递归的
【在 i*********7 的大作中提到】
: 本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
【在 i*********7 的大作中提到】
: 本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
e*l
20 楼
第一行的N个元素，分别对应N个(N-1)x(N-1)的余子阵（即去掉这个元素所在的行和列
之后剩下的矩阵）。假设N个余子阵上该问题的最优解已经得到（递归），就可以通过
比较第一行元素的N种选择，来得到NxN上的最优解。
之后剩下的矩阵）。假设N个余子阵上该问题的最优解已经得到（递归），就可以通过
比较第一行元素的N种选择，来得到NxN上的最优解。
w*x
21 楼
我觉得你瞒强的
【在 i*********7 的大作中提到】
: 本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
b*d
22 楼
这仍是N！，和那个8后一维数组permute是一样的。
【在 e***l 的大作中提到】
: 第一行的N个元素，分别对应N个(N-1)x(N-1)的余子阵（即去掉这个元素所在的行和列
: 之后剩下的矩阵）。假设N个余子阵上该问题的最优解已经得到（递归），就可以通过
: 比较第一行元素的N种选择，来得到NxN上的最优解。
f*e
23 楼
先用LP表示：
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了，每行对应一个源s_i,每列对应一个汇t_j，
每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
N个源s_i与总源s相连，N个汇t_j与总汇t相连，
边的cost是w_ij/2，capacity是1，其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了，每行对应一个源s_i,每列对应一个汇t_j，
每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
N个源s_i与总源s相连，N个汇t_j与总汇t相连，
边的cost是w_ij/2，capacity是1，其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
e*l
24 楼
对。
【在 b*******d 的大作中提到】
:
: 这仍是N！，和那个8后一维数组permute是一样的。
【在 b*******d 的大作中提到】
:
: 这仍是N！，和那个8后一维数组permute是一样的。
b*d
25 楼
强。
【在 f*****e 的大作中提到】
: 先用LP表示：
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了，每行对应一个源s_i,每列对应一个汇t_j，
: 每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
: N个源s_i与总源s相连，N个汇t_j与总汇t相连，
: 边的cost是w_ij/2，capacity是1，其他边cost=0。
e*l
26 楼
Interesting。
把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
【在 f*****e 的大作中提到】
: 先用LP表示：
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了，每行对应一个源s_i,每列对应一个汇t_j，
: 每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
: N个源s_i与总源s相连，N个汇t_j与总汇t相连，
: 边的cost是w_ij/2，capacity是1，其他边cost=0。
把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
【在 f*****e 的大作中提到】
: 先用LP表示：
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了，每行对应一个源s_i,每列对应一个汇t_j，
: 每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
: N个源s_i与总源s相连，N个汇t_j与总汇t相连，
: 边的cost是w_ij/2，capacity是1，其他边cost=0。
f*e
27 楼
LP是凸优化，所以解是最优的。
LP描述了空间一个凸多面体，一般LP的解就是多面体的顶点，顶点坐标一般不是整数。但
我以前学combinatorial optimization的时候，说如果LP的系数矩阵A如果满足某个条件
的时候，多面体的顶点坐标就是整数了，我猜这道题就是。
【在 e***l 的大作中提到】
: Interesting。
: 把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
LP描述了空间一个凸多面体，一般LP的解就是多面体的顶点，顶点坐标一般不是整数。但
我以前学combinatorial optimization的时候，说如果LP的系数矩阵A如果满足某个条件
的时候，多面体的顶点坐标就是整数了，我猜这道题就是。
【在 e***l 的大作中提到】
: Interesting。
: 把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
x*o
28 楼
求大牛鉴定，这个也N！吗？
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList avail = new ArrayList();
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList availCols)
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList rest = (ArrayList) availCols.
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
x*o
29 楼
嘿嘿，貌似是哦~！能再快吗？求大牛指导
【在 x*****o 的大作中提到】
: 求大牛鉴定，这个也N！吗？
: public int findMin(int[][] a)
: {
: if (a == null || a.length == 0)
: {
: return 0;
: }
: if (a.length == 1)
: {
: return a[0][0];
【在 x*****o 的大作中提到】
: 求大牛鉴定，这个也N！吗？
: public int findMin(int[][] a)
: {
: if (a == null || a.length == 0)
: {
: return 0;
: }
: if (a.length == 1)
: {
: return a[0][0];
w*g
30 楼
一种取法， 还是所有种类？
v*c
31 楼
矩阵看成是一个bipartite graph的adjacency matrix.
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
t*t
32 楼
N x N integer矩阵。
每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
求取法。
感觉应该可以用DP做?
每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
求取法。
感觉应该可以用DP做?
w*x
33 楼
瞬间想到了8皇后
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
b*d
34 楼
my first thought is probing and pruning, maybe too slow.
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
t*t
35 楼
care to elaborate?
n! complexity?
【在 b*******d 的大作中提到】
:
: my first thought is probing and pruning, maybe too slow.
n! complexity?
【在 b*******d 的大作中提到】
:
: my first thought is probing and pruning, maybe too slow.
p*2
36 楼
不就是0-n-1的排列吗？
i*h
37 楼
什么叫0-n-1的排列?
【在 p*****2 的大作中提到】
: 不就是0-n-1的排列吗？
【在 p*****2 的大作中提到】
: 不就是0-n-1的排列吗？
p*2
38 楼
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
就这么几种情况吧？
【在 i***h 的大作中提到】
: 什么叫0-n-1的排列?
t*t
39 楼
u mean n! complexity?
too slow bah
【在 p*****2 的大作中提到】
:
: 0 1 2
: 0 2 1
: 1 0 2
: 1 2 0
: 2 0 1
: 2 1 0
: 就这么几种情况吧？
too slow bah
【在 p*****2 的大作中提到】
:
: 0 1 2
: 0 2 1
: 1 0 2
: 1 2 0
: 2 0 1
: 2 1 0
: 就这么几种情况吧？
b*d
40 楼
解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
很少的prune，可能有些large test不过。
【在 t**********t 的大作中提到】
: care to elaborate?
: n! complexity?
w*x
41 楼
一维数组record, 递归得了
i*h
42 楼
如果有负数呢?
【在 b*******d 的大作中提到】
:
: 解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
: 经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
: 不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
: 很少的prune，可能有些large test不过。
【在 b*******d 的大作中提到】
:
: 解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
: 经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
: 不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
: 很少的prune，可能有些large test不过。
p*2
43 楼
面试题需要什么过larget test呢？
【在 b*******d 的大作中提到】
:
: 解空间是N！，但很多可以prune掉，因为当前valid 的m个列或行填充后，其sum可能已
: 经大于当前最小值了，就不必继续probe了，就可以递归进行下一选择了。
: 不好的是这个方法在worst case（min sum是N!个解的“最后”一个），进行了没有或
: 很少的prune，可能有些large test不过。
i*h
44 楼
考试只能用递归了
【在 w****x 的大作中提到】
: 一维数组record, 递归得了
【在 w****x 的大作中提到】
: 一维数组record, 递归得了
p*2
45 楼
有啥slow的？面试题这样的多了。
【在 t**********t 的大作中提到】
: u mean n! complexity?
: too slow bah
p*2
46 楼
可以先sort
【在 i***h 的大作中提到】
: 如果有负数呢?
i*7
47 楼
本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
i*h
48 楼
???
sort啥? 矩阵是不能动的
【在 p*****2 的大作中提到】
:
: 可以先sort
sort啥? 矩阵是不能动的
【在 p*****2 的大作中提到】
:
: 可以先sort
p*2
49 楼
不好意思。说错了。
【在 i***h 的大作中提到】
: ???
: sort啥? 矩阵是不能动的
i*h
50 楼
估计就是考写递归的
【在 i*********7 的大作中提到】
: 本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
【在 i*********7 的大作中提到】
: 本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
e*l
51 楼
第一行的N个元素，分别对应N个(N-1)x(N-1)的余子阵（即去掉这个元素所在的行和列
之后剩下的矩阵）。假设N个余子阵上该问题的最优解已经得到（递归），就可以通过
比较第一行元素的N种选择，来得到NxN上的最优解。
之后剩下的矩阵）。假设N个余子阵上该问题的最优解已经得到（递归），就可以通过
比较第一行元素的N种选择，来得到NxN上的最优解。
w*x
52 楼
我觉得你瞒强的
【在 i*********7 的大作中提到】
: 本来在想greedy的，不过后来觉得好像还是只能类似八皇后的permutation
b*d
53 楼
这仍是N！，和那个8后一维数组permute是一样的。
【在 e***l 的大作中提到】
: 第一行的N个元素，分别对应N个(N-1)x(N-1)的余子阵（即去掉这个元素所在的行和列
: 之后剩下的矩阵）。假设N个余子阵上该问题的最优解已经得到（递归），就可以通过
: 比较第一行元素的N种选择，来得到NxN上的最优解。
f*e
54 楼
先用LP表示：
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了，每行对应一个源s_i,每列对应一个汇t_j，
每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
N个源s_i与总源s相连，N个汇t_j与总汇t相连，
边的cost是w_ij/2，capacity是1，其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
min sum_(ij)(w_ij*x_ij)
s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
然后看能否转成combinatorial的问题。
minimum cost flow(algorithm design上有详细介绍)。
想到了，每行对应一个源s_i,每列对应一个汇t_j，
每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
N个源s_i与总源s相连，N个汇t_j与总汇t相连，
边的cost是w_ij/2，capacity是1，其他边cost=0。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
e*l
55 楼
对。
【在 b*******d 的大作中提到】
:
: 这仍是N！，和那个8后一维数组permute是一样的。
【在 b*******d 的大作中提到】
:
: 这仍是N！，和那个8后一维数组permute是一样的。
b*d
56 楼
强。
【在 f*****e 的大作中提到】
: 先用LP表示：
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了，每行对应一个源s_i,每列对应一个汇t_j，
: 每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
: N个源s_i与总源s相连，N个汇t_j与总汇t相连，
: 边的cost是w_ij/2，capacity是1，其他边cost=0。
e*l
57 楼
Interesting。
把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
【在 f*****e 的大作中提到】
: 先用LP表示：
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了，每行对应一个源s_i,每列对应一个汇t_j，
: 每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
: N个源s_i与总源s相连，N个汇t_j与总汇t相连，
: 边的cost是w_ij/2，capacity是1，其他边cost=0。
把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
【在 f*****e 的大作中提到】
: 先用LP表示：
: min sum_(ij)(w_ij*x_ij)
: s.t. sum_i(x_ij)=1, sum_j(x_ij)=1, 0<=x_ij<=1
: 然后看能否转成combinatorial的问题。
: minimum cost flow(algorithm design上有详细介绍)。
: 想到了，每行对应一个源s_i,每列对应一个汇t_j，
: 每个数组元素w_ij看成是一个node，与源s_i，汇t_j相连，
: N个源s_i与总源s相连，N个汇t_j与总汇t相连，
: 边的cost是w_ij/2，capacity是1，其他边cost=0。
f*e
58 楼
LP是凸优化，所以解是最优的。
LP描述了空间一个凸多面体，一般LP的解就是多面体的顶点，顶点坐标一般不是整数。但
我以前学combinatorial optimization的时候，说如果LP的系数矩阵A如果满足某个条件
的时候，多面体的顶点坐标就是整数了，我猜这道题就是。
【在 e***l 的大作中提到】
: Interesting。
: 把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
LP描述了空间一个凸多面体，一般LP的解就是多面体的顶点，顶点坐标一般不是整数。但
我以前学combinatorial optimization的时候，说如果LP的系数矩阵A如果满足某个条件
的时候，多面体的顶点坐标就是整数了，我猜这道题就是。
【在 e***l 的大作中提到】
: Interesting。
: 把x_ij松弛了之后，能得到一个数值解，在离散化吗？能保证全局最优吗？
x*o
59 楼
求大牛鉴定，这个也N！吗？
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList avail = new ArrayList();
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList availCols)
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList rest = (ArrayList) availCols.
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
public int findMin(int[][] a)
{
if (a == null || a.length == 0)
{
return 0;
}
if (a.length == 1)
{
return a[0][0];
}
int n = a[0].length;
ArrayList
for (int i = 0; i < n; i++)
{
avail.add(i);
}
return find(a, 0, avail);
}
private int find(int[][] a, int curRow, ArrayList
{
if (availCols.size() == 1)
{
return a[curRow][availCols.get(0)];
}
else
{
int min = Integer.MAX_VALUE;
for (int i : availCols)
{
int cur = a[curRow][i];
ArrayList
clone();
rest.remove(rest.indexOf(i));
int min_s = cur + find(a, curRow + 1, rest);
if (min_s < min)
{
min = min_s;
}
}
return min;
}
}
x*o
60 楼
嘿嘿，貌似是哦~！能再快吗？求大牛指导
【在 x*****o 的大作中提到】
: 求大牛鉴定，这个也N！吗？
: public int findMin(int[][] a)
: {
: if (a == null || a.length == 0)
: {
: return 0;
: }
: if (a.length == 1)
: {
: return a[0][0];
【在 x*****o 的大作中提到】
: 求大牛鉴定，这个也N！吗？
: public int findMin(int[][] a)
: {
: if (a == null || a.length == 0)
: {
: return 0;
: }
: if (a.length == 1)
: {
: return a[0][0];
w*g
61 楼
一种取法， 还是所有种类？
v*c
62 楼
矩阵看成是一个bipartite graph的adjacency matrix.
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
Y*f
63 楼
这道题是不是可以这样做:
1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
+ A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
， 重复这一步知道不存在前续条件的一对元素。
这样得到的应该是最优的，收敛已经改也比较快。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
+ A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
， 重复这一步知道不存在前续条件的一对元素。
这样得到的应该是最优的，收敛已经改也比较快。
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
Y*Y
64 楼
这个想法不错，但不能保证收敛到最优解：
比如这个：初始是{1, 1, 1}，对任何两个都是最优，所以无法达到{0, 0, 0}
1 1000 0
0 1 1000
1000 0 1
m]
【在 Y********f 的大作中提到】
: 这道题是不是可以这样做:
: 1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
: 2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
: + A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
: ， 重复这一步知道不存在前续条件的一对元素。
: 这样得到的应该是最优的，收敛已经改也比较快。
比如这个：初始是{1, 1, 1}，对任何两个都是最优，所以无法达到{0, 0, 0}
1 1000 0
0 1 1000
1000 0 1
m]
【在 Y********f 的大作中提到】
: 这道题是不是可以这样做:
: 1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
: 2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
: + A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
: ， 重复这一步知道不存在前续条件的一对元素。
: 这样得到的应该是最优的，收敛已经改也比较快。
x*0
65 楼
mark
m*g
66 楼
This is a NP problem.
w*p
67 楼
me too
考到这题我就默默转身，
顺手拿两块糕点。
【在 w****x 的大作中提到】
:
: 我觉得你瞒强的
考到这题我就默默转身，
顺手拿两块糕点。
【在 w****x 的大作中提到】
:
: 我觉得你瞒强的
c*t
68 楼
俺说个naive的办法，大牛看行不，开新的二维数组，对每一行排序并保留原column
index （ ValueIndex[N][N])
时间(N*N*logN),空间（N*N)
取第一列值，index没冲突的sum, 有冲突的比较一下与第二列的差值，差值最大的留下
，继续第二列。假设每次都有一半冲突 时间（n/2+n/4+。。。）=N, 空间 N
最终时间 O(N*N*logN),空间O（N*N)
可以吗？
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
index （ ValueIndex[N][N])
时间(N*N*logN),空间（N*N)
取第一列值，index没冲突的sum, 有冲突的比较一下与第二列的差值，差值最大的留下
，继续第二列。假设每次都有一半冲突 时间（n/2+n/4+。。。）=N, 空间 N
最终时间 O(N*N*logN),空间O（N*N)
可以吗？
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
m*s
69 楼
为什么G开始出网络流/匹配的题目了。。。水题全被废了么？
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
【在 t**********t 的大作中提到】
: N x N integer矩阵。
: 每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
: 求取法。
: 感觉应该可以用DP做?
s*1
70 楼
似乎不行
1 2. 5
1. 3. 100
1. 200. 4
最小为7， 这个算法为9
【在 c********t 的大作中提到】
: 俺说个naive的办法，大牛看行不，开新的二维数组，对每一行排序并保留原column
: index （ ValueIndex[N][N])
: 时间(N*N*logN),空间（N*N)
: 取第一列值，index没冲突的sum, 有冲突的比较一下与第二列的差值，差值最大的留下
: ，继续第二列。假设每次都有一半冲突 时间（n/2+n/4+。。。）=N, 空间 N
: 最终时间 O(N*N*logN),空间O（N*N)
: 可以吗？
1 2. 5
1. 3. 100
1. 200. 4
最小为7， 这个算法为9
【在 c********t 的大作中提到】
: 俺说个naive的办法，大牛看行不，开新的二维数组，对每一行排序并保留原column
: index （ ValueIndex[N][N])
: 时间(N*N*logN),空间（N*N)
: 取第一列值，index没冲突的sum, 有冲突的比较一下与第二列的差值，差值最大的留下
: ，继续第二列。假设每次都有一半冲突 时间（n/2+n/4+。。。）=N, 空间 N
: 最终时间 O(N*N*logN),空间O（N*N)
: 可以吗？
l*8
71 楼
正解！
【在 v****c 的大作中提到】
: 矩阵看成是一个bipartite graph的adjacency matrix.
: 行是一边的顶点，列是另外一边的顶点
: 这个问题相当于min weight matching in bipartite graph
: Hungarian method O(n^3)时间可解
【在 v****c 的大作中提到】
: 矩阵看成是一个bipartite graph的adjacency matrix.
: 行是一边的顶点，列是另外一边的顶点
: 这个问题相当于min weight matching in bipartite graph
: Hungarian method O(n^3)时间可解
Y*y
72 楼
这个就是经典的one to one assignment problem吧。
l*b
73 楼
对啊, 好像就是前阵hackercup闹得那个hungarian method
G家题目真难呀,不会做...
G家题目真难呀,不会做...
p*2
74 楼
不知道面试官是不是真的要考匈牙利算法。那样的话估计只有han6这样的大牛才能通过
了。而且不是n^3的算法说是不太好写吗？n^4的可能容易些。
【在 l*******b 的大作中提到】
: 对啊, 好像就是前阵hackercup闹得那个hungarian method
: G家题目真难呀,不会做...
d*x
75 楼
二分图最大匹配？
用naive的网络流算法也不会到n^4吧。。
【在 p*****2 的大作中提到】
:
: 不知道面试官是不是真的要考匈牙利算法。那样的话估计只有han6这样的大牛才能通过
: 了。而且不是n^3的算法说是不太好写吗？n^4的可能容易些。
用naive的网络流算法也不会到n^4吧。。
【在 p*****2 的大作中提到】
:
: 不知道面试官是不是真的要考匈牙利算法。那样的话估计只有han6这样的大牛才能通过
: 了。而且不是n^3的算法说是不太好写吗？n^4的可能容易些。
j*2
76 楼
我本来想：不就是八皇后改改吗？看完大家的回帖后，我只有说：Wow!
p*2
77 楼
没看naive的，就看的匈牙利的。
【在 d**********x 的大作中提到】
: 二分图最大匹配？
: 用naive的网络流算法也不会到n^4吧。。
c*t
78 楼
目前看，这个比较可行。
啥匈牙利的一点不懂。
m]
【在 Y********f 的大作中提到】
: 这道题是不是可以这样做:
: 1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
: 2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
: + A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
: ， 重复这一步知道不存在前续条件的一对元素。
: 这样得到的应该是最优的，收敛已经改也比较快。
啥匈牙利的一点不懂。
m]
【在 Y********f 的大作中提到】
: 这道题是不是可以这样做:
: 1. 初始化选定N个元素A[0][0], A[1][1], A[2][2] .....
: 2. 对任意两个已经选定的元素A[i][j], A[k][m], 如果A[i][j] + A[k][m] > A[i][m]
: + A[k][j], 则从选定的N个元素里面删除A[i][j], A[k][m], 添加A[i][m], A[k][j]
: ， 重复这一步知道不存在前续条件的一对元素。
: 这样得到的应该是最优的，收敛已经改也比较快。
s*t
79 楼
感觉如果N的值够小的话（e.g.<=32)是可以用dp做的。
大的话不会了: D
用一个二进制数表示取列的状态，比如S = 8 = 1000表示列0被取了，其它3列没被取
dp[i][s]表示取到第i行的时候取列状态为s时的最大值
for(int i=0; ifor(int row=1; row
[s]);
}
}
这里s/one_digit代表用某一位来试一下，如果这一位已经被取，那么不取，否则就取。
data[row][this_digit]代表这个矩阵里面我们正在考虑的row行this_digit列，也就是
用来试的那一列
输出dp[N-1][(1<
大的话不会了: D
用一个二进制数表示取列的状态，比如S = 8 = 1000表示列0被取了，其它3列没被取
dp[i][s]表示取到第i行的时候取列状态为s时的最大值
for(int i=0; ifor(int row=1; row
[s]);
}
}
这里s/one_digit代表用某一位来试一下，如果这一位已经被取，那么不取，否则就取。
data[row][this_digit]代表这个矩阵里面我们正在考虑的row行this_digit列，也就是
用来试的那一列
输出dp[N-1][(1<
s*t
80 楼
应该把max换成min...INF换成-INF...
我了个去的。。。这马虎程度真是一面就挂
row]
【在 s******t 的大作中提到】
: 感觉如果N的值够小的话（e.g.<=32)是可以用dp做的。
: 大的话不会了: D
: 用一个二进制数表示取列的状态，比如S = 8 = 1000表示列0被取了，其它3列没被取
: dp[i][s]表示取到第i行的时候取列状态为s时的最大值
: for(int i=0; i: for(int row=1; row
: [s]);
: }
我了个去的。。。这马虎程度真是一面就挂
row]
【在 s******t 的大作中提到】
: 感觉如果N的值够小的话（e.g.<=32)是可以用dp做的。
: 大的话不会了: D
: 用一个二进制数表示取列的状态，比如S = 8 = 1000表示列0被取了，其它3列没被取
: dp[i][s]表示取到第i行的时候取列状态为s时的最大值
: for(int i=0; i: for(int row=1; row
: [s]);
: }
e*r
81 楼
带权值的二分图最佳匹配用KM算法比匈牙利更快吧 匈牙利一般都只用来不带权值的二
分图吧
【在 p*****2 的大作中提到】
:
: 没看naive的，就看的匈牙利的。
分图吧
【在 p*****2 的大作中提到】
:
: 没看naive的，就看的匈牙利的。
相关阅读
zillow onsite实习面试挂了，对fulltime面试有影响吗？Dropbox的online coding exerciseSr PHP developer startup内推(north NJ)猎头帮忙递简历到底靠谱不靠谱呢？急求推荐加州的 ICC/CCCG开始玩lowball了？白板code 一个小技巧 能用 auto就多用各位码工的公司，都多久开始给办绿卡收到高通research的电面通知，该怎么准备啊？提供F家内推有没有半导体公司的面经？两次推迟onsite会不会不好？有知道NTT data 或者everis的么？据了offer有没有人谈谈Uber的offer？WalmartLab at San Bruno 的software engineer， new grad 要价多少合适？请问有没有Leetcode 解题网站？大家来谈谈出差这个层面（看某帖有感）版上最高学位非cs的马农多吗