我现在知道这题为什么 AC 率这么高了。。因为直接写个 triple nested loop 也能过。。
然后就是以 1021ms 的傲人速度打败了 3% 的用户 =。= 绝大多数 submission 在 60~70ms 之间。
所以看来这题的主要思路还是“空间换时间”。
public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int rowsA = A.length;
int colsA = A[0].length;
int rowsB = B.length;
int colsB = B[0].length;
int[][] rst = new int[rowsA][colsB];
for(int i = 0; i < rowsA; i++){
for(int j = 0; j < colsB; j++){
for(int k = 0; k < colsA; k++){
if(A[i][k] == 0 || B[k][j] == 0) continue;
rst[i][j] += A[i][k] * B[k][j];
}
}
}
return rst;
}
}
经过一番简单优化之后,时间已然降到了 324ms,用 List of Lists 存 A/B 矩阵中不为 0 的 row/col
这题用 HashMap,Key = Integer, Value = List,600ms;
改用 List of Lists,324ms;
最后用 List[] 里面放 List,248ms.
public class Solution {
private class Tuple{
int index;
int val;
public Tuple(int index, int val){
this.index = index;
this.val = val;
}
}
public int[][] multiply(int[][] A, int[][] B) {
int rowsA = A.length;
int colsA = A[0].length;
int rowsB = B.length;
int colsB = B[0].length;
int[][] rst = new int[rowsA][colsB];
List[] rowList = new List[rowsA];
List[] colList = new List[colsB];
for(int i = 0; i < rowsA; i++){
List<Tuple> newList = new ArrayList<Tuple>();
for(int j = 0; j < colsA; j++){
if(A[i][j] != 0) newList.add(new Tuple(j, A[i][j]));
}
rowList[i] = newList;
}
for(int i = 0; i < colsB; i++){
List<Tuple> newList = new ArrayList<Tuple>();
for(int j = 0; j < rowsB; j++){
if(B[j][i] != 0) newList.add(new Tuple(j, B[j][i]));
}
colList[i] = newList;
}
for(int i = 0; i < rowsA; i++){
for(int j = 0; j < colsB; j++){
rst[i][j] = multiply(rowList[i], colList[j]);
}
}
return rst;
}
private int multiply(List<Tuple> A, List<Tuple> B){
if(A == null || B == null) return 0;
if(A.size() == 0 || B.size() == 0) return 0;
int sum = 0;
int ptrA = 0;
int ptrB = 0;
while(ptrA < A.size() && ptrB < B.size()){
if(A.get(ptrA).index == B.get(ptrB).index){
sum += A.get(ptrA++).val * B.get(ptrB++).val;
} else if(A.get(ptrA).index < B.get(ptrB).index){
ptrA ++;
} else {
ptrB ++;
}
}
return sum;
}
}
优化方法参考论坛这个帖子,里面提到了一个 CMU Lecture ,明天有空看看。
70ms 的解其实很简单;考虑到外面都是 i,j,k 的三重循环,所有操作都在最里面执行,可以直接把index 的顺序交换,这样可以利用其中某个位置为 0 的特点,直接跳过最内圈的循环。
public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int rowsA = A.length;
int colsA = A[0].length;
int rowsB = B.length;
int colsB = B[0].length;
int[][] rst = new int[rowsA][colsB];
for(int i = 0; i < rowsA; i++){
for(int k = 0; k < colsA; k++){
if(A[i][k] == 0) continue;
for(int j = 0; j < colsB; j++){
if(B[k][j] == 0) continue;
rst[i][j] += A[i][k] * B[k][j];
}
}
}
return rst;
}
}
public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int rowsA = A.length;
int colsA = A[0].length;
int rowsB = B.length;
int colsB = B[0].length;
int[][] rst = new int[rowsA][colsB];
for(int k = 0; k < colsA; k++){
for(int j = 0; j < colsB; j++){
if(B[k][j] == 0) continue;
for(int i = 0; i < rowsA; i++){
if(A[i][k] == 0) continue;
rst[i][j] += A[i][k] * B[k][j];
}
}
}
return rst;
}
}
这题考察的是,如何实现一个 “双向 one-to-one onto mapping (bijection)”,原 domain 是 String S 的字符集,目标 domain 是 String T 的字符集。不能出现 one-to-many 或者 many-to-one.
写一会儿很快就可以发现,一个 hashmap 是不够的,至少不够快。因为一个 hashmap 只能做一个方向的 mapping,不能高效反方向查找有没有出现 one-to-many / many-to-one 的情况。
public class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length() != t.length()) return false;
HashMap<Character, Character> mapS = new HashMap<Character, Character>();
HashMap<Character, Character> mapT = new HashMap<Character, Character>();
for(int i = 0; i < s.length(); i++){
char charS = s.charAt(i);
char charT = t.charAt(i);
if(mapT.containsKey(charT) && mapT.get(charT) != charS) return false;
if(mapS.containsKey(charS) && mapS.get(charS) != charT) return false;
mapS.put(charS, charT);
mapT.put(charT, charS);
}
return true;
}
}
既然输入都是字符串,方便起见,可以用 int[256] 代替 hashmap 加速。
public class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length() != t.length()) return false;
int[] mapS = new int[256];
int[] mapT = new int[256];
for(int i = 0; i < s.length(); i++){
char charS = s.charAt(i);
char charT = t.charAt(i);
if(mapT[charT] != 0 && mapT[charT] != (int) charS) return false;
if(mapS[charS] != 0 && mapS[charS] != (int) charT) return false;
mapS[charS] = (int)charT;
mapT[charT] = (int)charS;
}
return true;
}
}