311, 543 Sparse Matrix Multiplication, Diameter of Binary Tree

311. Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

Input:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

-----------------------
Solution #1 Brute force, 正常的矩阵乘法，每一次行列相乘会得到[i][j]位置的最终结果
复杂度：rowA * colA * colB
或者：A矩阵的元素的个数 ＊ colB

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length;
        int colB = B[0].length;
        int[][] rt = new int[rowA][colB];
        
        for (int row = 0; row < rowA; row++) {
            for (int col = 0; col < colB; col++) {
                int s = 0;
                for (int i = 0; i < B.length; i++) {
                    s += A[row][i] * B[i][col];
                }
                rt[row][col] = s;
            }
        }
        
        return rt;
    }
}

Solution #2 对矩阵A进行遍历，A中的每一个元素A[i][j]都会被调用到B[0].length次，并计入到结果矩阵。如果A[i][j] == 0，则可省去B[0].length次运算
此算法不同处是每一次相乘相加得到的只是中间值，最终结果得等程序跑完之后才能算出

复杂度: A矩阵里非零元素的个数 * colB

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length;
        int colA = A[0].length;
        int colB = B[0].length;
        int[][] rt = new int[rowA][colB];
        
        for (int i = 0; i < rowA; i++) {
            for (int j = 0; j < colA; j++) {
                if (A[i][j] != 0) {
                    for (int k = 0; k < colB; k++) {
                        rt[i][k] += A[i][j] * B[j][k];
                    }
                }
            }
        }
        
        return rt;
    }
}

稀疏矩阵压缩后再进行乘积。压缩的方法是保证行数不变，只存下非零的列数跟数值。
http://www.cs.cmu.edu/~scandal/cacm/node9.html

此方法对这题而言不是什么好解法，因为题目已经给定了2个非压缩的2维矩阵

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length;
        int colA = A[0].length;
        int colB = B[0].length;
        int[][] rt = new int[rowA][colB];
        
        List<List<Integer>> sA = getCompressed(A);
        List<List<Integer>> sB = getCompressed(B);
    
        for (int i = 0; i < rowA; i++) {
            for (int j = 0; j < sA.get(i).size(); j += 2) {                
                int colAA = sA.get(i).get(j);
                int valAA = sA.get(i).get(j + 1);    
                
                for (int k = 0; k < sB.get(colAA).size(); k += 2) {
                    int colBB = sB.get(colAA).get(k);
                    int valBB = sB.get(colAA).get(k + 1);    
                    rt[i][colBB] += valAA * valBB;
                }
                
            }
        }
        
        return rt;
    }
    
    private List<List<Integer>> getCompressed(int[][] matrix) {
        List<List<Integer>> s = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            List<Integer> r = new ArrayList<>();
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != 0) {
                    r.add(j);
                    r.add(matrix[i][j]);
                }
            }
            s.add(r);
        }
        return s;
    }
}

543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

----------------------------

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        rec(root);
        return max;
    }
    
    private int rec(TreeNode root) {
        if (root == null) return 0;
        int left = rec(root.left);
        int right = rec(root.right);
        
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }
}