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
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;
}
}
