谷歌onsite，15-19这一周

第二题我有个想法：先考虑N*N的方阵，我们把对角线先填满，所填的值为该元素所在行的和与所在列的和比较小的那个。因为行和之和等于列和之和，所以一定有些元素绗和大于列和，另外一些元素行和小于列和。然后我们在其他位置贪心地补值即可。对于非方阵，我们把它补成方阵，多的元素全置0，然后再按刚才的方法做就行了。

每天都很郁闷。想着准备了快一年，甚至是几年的谷歌onsite，最后弄成这个样子。心理很痛苦，懊悔。

第二题可以这样麽：

1.     private static int[][] fillMatrix(int[] rows, int[] cols) {
   
2.         int[][] matrix = new int[rows.length][cols.length];
   
3.         int r = 0;
   
4.         int c = 0;
   
5.         while (r < rows.length && c < cols.length) {
   
6.             if (rows[r] <= cols[c]) {
   
7.                 matrix[r][c] += rows[r];
   
8.                 cols[c] -= rows[r];
   
9.                 rows[r] = 0;
   
10.                 r++;
    
11.             } else {
    
12.                 matrix[r][c] += cols[c];
    
13.                 rows[r] -= cols[c];
    
14.                 cols[c] = 0;
    
15.                 c++;
    
16.             }
    
17.         }
    
18.         return matrix;
    
19.     }

复制代码

[quote]YZeng 发表于 2018-10-23 08:44
第二题可以这样麽：

1.     private static int[][] fillMatrix(int[] rows, int[] ...[/quote]
3. 补充一下testing的代码：
   
4. 
   
5. [code]public class fillMatrix {
   
6.     public static void main(String[] args) {
   
7.         int[] rows = new int[]{6,15,29};
   
8.         int[] cols = new int[]{10,11,14,15};
   
9.         int[][] matrix = fillMatrix(rows, cols);
   
10.         for (int[] row : matrix) {
    
11.             System.out.println(Arrays.toString(row));
    
12.         }
    
13.     }
    
14. 
    
15.     private static int[][] fillMatrix(int[] rows, int[] cols) {
    
16.         int[][] matrix = new int[rows.length][cols.length];
    
17.         int r = 0;
    
18.         int c = 0;
    
19.         while (r < rows.length && c < cols.length) {
    
20.             if (rows[r] <= cols[c]) {
    
21.                 matrix[r][c] += rows[r];
    
22.                 cols[c] -= rows[r];
    
23.                 rows[r] = 0;
    
24.                 r++;
    
25.             } else {
    
26.                 matrix[r][c] += cols[c];
    
27.                 rows[r] -= cols[c];
    
28.                 cols[c] = 0;
    
29.                 c++;
    
30.             }
    
31.         }
    
32.         return matrix;
    
33.     }
    
34. }

复制代码

哈哈 第二题就是最大流的教材例题

sfsttz 发表于 2018-10-23 08:58
哈哈 第二题就是最大流的教材例题

是我太水了。献丑了。

jtzgz 发表于 2018-10-23 10:23
是我太水了。献丑了。

没有这个意思，我是觉得考这种题很搞笑，就算你写出正解面试官有可能不懂把你挂了，这种例子还是挺多的

sfsttz 发表于 2018-10-23 10:24
没有这个意思，我是觉得考这种题很搞笑，就算你写出正解面试官有可能不懂把你挂了，这种例子还是挺多的

他出题的，怎么会不懂呢。这一题是CLRS的题么？

clrs没找到 有个几十年前的论文：https://core.ac.uk/download/pdf/82798986.pdf

第二题CS的不懂，纯线性代数的角度来说。。。
有无数可能性，只要构造一种最简单满足条件的矩阵。
就是列和的行向量和行和的列向量的张量积。然后注意行和之和和列和之和是相等的，称为总和，张量积的每个元素除以这个总和，得到满足性质的矩阵。

怎么感觉不用写code，倒是可以写证明。。。