u***8
发帖数: 1581 | 1 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
这一题，1小时，搞得定么？ |
f*******n
发帖数: 10 | 2 m * n的矩阵有m * n个未知数，m + n个方程组
当m * n > m + n的时候有无穷解
【在 u***8 的大作中提到】
: 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
: 这一题，1小时，搞得定么？
|
Y***o
发帖数: 29 | 3 好像分成小矩阵， 加上非负数prune， 再组合，我比较菜，大神来讲讲吧。 |
q*******0
发帖数: 6 | 4 感觉和leetcode解数独差不多。从第一行到最后一行，逐个试探，注意剪枝，经典的回
溯。 |
u***8
发帖数: 1581 | |
u***8
发帖数: 1581 | 6 我就是想大神跟我说说，fang面试onsite轮，遇到这一题，是我水，还是这题难，
死也死个明白。 |
t***s
发帖数: 4666 | 7 Linear programming
【在 u***8 的大作中提到】
: 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
: 这一题，1小时，搞得定么？
|
u***8
发帖数: 1581 | 8 请丢个code，上来，一下，结果出来。我可以给伪币。
【在 t***s 的大作中提到】
: Linear programming
|
u***8
发帖数: 1581 | 9 更新：我非常想知道，如何做这一题。今天HR来了电话，口气很冷淡的拒绝了。我问什
么都不说。就说12个月，block期。然后我说，这最后一题，实在不是1小时做得出来。
他也就说，有个survey，其余没办法。
求有大神丢个code上来，跑下来，答案出来。心服口服。给伪币。
给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
这一题，1小时，搞得定么？ |
Y***o
发帖数: 29 | 10 好像分成小矩阵， 加上非负数prune， 再组合，我比较菜，大神来讲讲吧。 |
|
|
q*******0
发帖数: 6 | 11 感觉和leetcode解数独差不多。从第一行到最后一行，逐个试探，注意剪枝，经典的回
溯。 |
u***8
发帖数: 1581 | 12 谁会？是什么graph cut么？求大牛来解。 |
u***8
发帖数: 1581 | 13 我就是想大神跟我说说，fang面试onsite轮，遇到这一题，是我水，还是这题难，
死也死个明白。 |
t***s
发帖数: 4666 | 14 Linear programming
【在 u***8 的大作中提到】
: 给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
: 这一题，1小时，搞得定么？
|
u***8
发帖数: 1581 | 15 请丢个code，上来，一下，结果出来。我可以给伪币。
【在 t***s 的大作中提到】
: Linear programming
|
c*******y
发帖数: 98 | 16 +1，对n^2范围的点逐一试探，递归下去，如果发现rowsum[i]或colsum[j]比当前累积
的数字小了就失败返回。或者行列剩下的数（假设有范围0-255）不够凑齐sum，也失败
返回。感觉这是二维图像重建，要是有特别快的方法意义感觉蛮大的，这个只能说是暴
力搜索。为了找所有的解感觉只能这样了吧，毕竟解空间那么大。别的算法一小时也不
现实。
如果没有范围的话，那每个点只能从1到min(rowsum[i], colsum[j]循环了。
如果不限制整数的话，那我就没辙了，没准是无穷多解，这个可能得先问清楚。
【在 q*******0 的大作中提到】
: 感觉和leetcode解数独差不多。从第一行到最后一行，逐个试探，注意剪枝，经典的回
: 溯。
|
p*****2
发帖数: 21240 | 17 大概写了半个小时，估计onsite直接就跪了。
public class Solution {
int m;
int n;
int[] rows;
int[] cols;
List> all = new ArrayList<>();
List serialize(int[][] matrix) {
List al = new ArrayList<>();
for(int[] arr : matrix) {
StringBuilder sb = new StringBuilder();
for(int i : arr) {
if(sb.length() > 0) {
sb.append(",");
}
sb.append(i);
}
al.add(sb.toString());
}
return al;
}
boolean valicate(int[][] matrix) {
int[] r = new int[m];
int[] c = new int[n];
for(int i=0; i
for(int j=0; j
r[i] += matrix[i][j];
c[j] += matrix[i][j];
if(i == m-1 && cols[j] != c[j]) {
return false;
}
}
if(rows[i] != r[i]) {
return false;
}
}
return true;
}
void dfs(int[][] matrix, int index) {
if(index == m*n) {
if(valicate(matrix)) {
all.add(serialize(matrix));
}
return;
}
int x = index/n;
int y = index%n;
int row = 0;
for(int j=0; j
row += matrix[x][j];
}
int col = 0;
for(int i=0; i
col += matrix[i][y];
}
for(int num = 1; num <= Math.min(rows[x]-row, cols[y]-col); num++) {
matrix[x][y] = num;
dfs(matrix, index+1);
}
matrix[x][y] = 0;
}
List> composeMatrix(int m, int n, int[] rows, int[] cols) {
this.m = m;
this.n = n;
this.rows = rows;
this.cols = cols;
all.clear();
int[][] matrix = new int[m][n];
dfs(matrix, 0);
return all;
}
} |
t******d
发帖数: 1383 | 18 2爷都说跪了，我也没什么遗憾了。还是被国人出的这一题。我也是没有办法。当场傻
眼。
【在 p*****2 的大作中提到】
: 大概写了半个小时，估计onsite直接就跪了。
: public class Solution {
: int m;
: int n;
: int[] rows;
: int[] cols;
: List> all = new ArrayList<>();
: List serialize(int[][] matrix) {
: List al = new ArrayList<>();
: for(int[] arr : matrix) {
|
f*****e
发帖数: 2992 | 19 用递归，很好写！f(m,n)｛一维递归里面call f(m-1, n)｝
明天我写个mutual recursive的。 |
p*****2
发帖数: 21240 | 20
我觉得面试过程很重要。如果是G家的话，interviewer很看重思路。按照我的理解，这
题主要考察的是DFS。现在DFS的趋势是不那么直接了，加了很多条件。LC上的有些
medium dfs也不是看起来简洁明了，比如756。
想想看，如果你工作起来怎么handle ambiguity。problem solving是面试官重点考察
的一个主要方面。
【在 t******d 的大作中提到】
: 2爷都说跪了，我也没什么遗憾了。还是被国人出的这一题。我也是没有办法。当场傻
: 眼。
|
|
|
e********2
发帖数: 495 | 21 class solution {
public:
void aux(vector& rows, vector& cols, int m, int n, vector<
vector>& temp, vector>>& res)
{
if (m == rows.size() - 1 && n == cols.size() - 1) {
if (rows[m] >= 0 && cols[n] >= 0 && rows[m] == cols[n]) {
temp[m][n] = rows[m];
res.push_back(temp);
}
}
else{
int start = n == cols.size() - 1 ? rows[m] : 0;
for (int i = start; i <= min(rows[m], cols[n]); i++) {
temp[m][n] = i;
rows[m] -= i;
cols[n] -= i;
if (n + 1 < cols.size())
aux(rows, cols, m, n + 1, temp, res);
else
aux(rows, cols, m + 1, 0, temp, res);
rows[m] += i;
cols[n] += i;
}
}
}
void f(vector& rows, vector& cols, vector>>
& res)
{
vector> temp(rows.size(), vector(cols.size()));
aux(rows, cols, 0, 0, temp, res);
}
}; |
e********2
发帖数: 495 | 22 //recurse entry by entry; if any constraint is violated, return
class solution {
public:
void aux(vector& rows, vector& cols, int m, int n, vector<
vector>& temp, vector>>& res)
{
if (m == rows.size() - 1) {
if (accumulate(cols.begin(), cols.end(), 0) == rows.back()) {
temp.back() = cols;
res.push_back(temp);
}
}
else{
int start = n == cols.size() - 1 ? rows[m] : 0;
for (int i = start; i <= min(rows[m], cols[n]); i++) {
temp[m][n] = i; rows[m] -= i; cols[n] -= i;
n + 1 < cols.size()?aux(rows, cols, m, n + 1, temp, res):aux
(rows, cols, m + 1, 0, temp, res); // recurse to next entry
rows[m] += i; cols[n] += i;
}
}
}
void f(vector& rows, vector& cols, vector>>
& res) {
if(accumulate(cols.begin(), cols.end(), 0) != accumulate(rows.begin(),
rows.end(), 0)) return;
vector> temp(rows.size(), vector(cols.size()));
aux(rows, cols, 0, 0, temp, res);
}
};
【在 e********2 的大作中提到】
: class solution {
: public:
: void aux(vector& rows, vector& cols, int m, int n, vector<
: vector>& temp, vector>>& res)
: {
: if (m == rows.size() - 1 && n == cols.size() - 1) {
: if (rows[m] >= 0 && cols[n] >= 0 && rows[m] == cols[n]) {
: temp[m][n] = rows[m];
: res.push_back(temp);
: }
|
b****h
发帖数: 2 | 23 这题写个最基本的回溯用不了20分钟吧。再加个记忆搜索，应该就够应付面试官了。 |
T*******e
发帖数: 4928 | 24 俺还是佩服2爷和你。敢直接贴码，肚里有货。我承认我只能马后炮
地说这是combination sum的变形，2D。但第一眼我也没认出来。：)
楼主加油。
【在 e********2 的大作中提到】
: //recurse entry by entry; if any constraint is violated, return
: class solution {
: public:
: void aux(vector& rows, vector& cols, int m, int n, vector<
: vector>& temp, vector>>& res)
: {
: if (m == rows.size() - 1) {
: if (accumulate(cols.begin(), cols.end(), 0) == rows.back()) {
: temp.back() = cols;
: res.push_back(temp);
|
u***8
发帖数: 1581 | 25 我到现在也没看出来是comb sum 2d。
【在 T*******e 的大作中提到】
: 俺还是佩服2爷和你。敢直接贴码，肚里有货。我承认我只能马后炮
: 地说这是combination sum的变形，2D。但第一眼我也没认出来。：)
: 楼主加油。
|
p*****2
发帖数: 21240 | 26
大牛慢慢来吧。
【在 u***8 的大作中提到】
: 我到现在也没看出来是comb sum 2d。
|
u***8
发帖数: 1581 | 27 某培训机构说，面试出这max flow，要么就是不招人，要么就是直接想拒人。
【在 p*****2 的大作中提到】
:
: 大牛慢慢来吧。
|
C*****y
发帖数: 42 | 28 我操，任何一个bi公司平时的活也碰不到这种问题吧。 |
