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; } }
No comments:
Post a Comment