大厂面试真题详解:稀疏矩阵乘法

简介: 大厂面试真题详解:稀疏矩阵乘法

给定两个 稀疏矩阵 A 和 B,返回AB的结果。
您可以假设A的列数等于B的行数。

在线评测地址:领扣题库官网

样例1

Input: 
[[1,0,0],[-1,0,3]]
[[7,0,0],[0,0,0],[0,0,1]]
Output:
[[7,0,0],[-7,0,3]]
Explanation:
A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

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


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |
AI 代码解读

样例2

Input:
[[1,0],[0,1]]
[[0,1],[1,0]]
Output:
[[0,1],[1,0]]
AI 代码解读

算法:模拟

思路
矩阵乘法的实现:一个m行n列的矩阵A,与一个n行p列的矩阵B可以相乘,得到的结果AB是一个m行p列的矩阵,其中的第i行第j列位置上的数AB(i,j)为,矩阵A第i行上的n个数与矩阵B第j列上的n个数一一对应相乘后,所得到的n个乘积之和。直接模拟即可。

复杂度分析

空间复杂度O(n^2)
时间复杂度O(n^3)

public class Solution {
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length, columnA = A[0].length;
        int rowB = B.length, columnB = B[0].length;
        // AB为 rowA * columnB 大小的矩阵
        int[][] AB = new int [rowA][columnB];
        for (int i = 0; i < rowA; i++){
            for (int j = 0; j < columnB; j++){
                // 求出每一项
                int sum = 0;
                for (int k = 0; k < columnA; k++){
                    sum += A[i][k] * B[k][j];
                }
                AB[i][j] = sum;
            }
        }
        return AB;
    }
}
AI 代码解读

更多题解参考:九章官网solution

目录
打赏
0
0
0
0
6
分享
相关文章
软件测试面试题及答案,这个题库有3千多道最新面试真题可以刷
相信对于很多软件测试新手来说,技术项目的面试是十分让人头疼的,生怕没回答得好,就会跟这个offer失之交臂
288 0
腾讯Java高级岗180道面试真题,面试大厂拿45Koffer没问题!
一、数据结构与算法基础 · 说一下几种常见的排序算法和分别的复杂度。 · 用Java写一个冒泡排序算法 · 描述一下链式存储结构。 · 如何遍历一棵二叉树? · 倒排一个LinkedList。 · 用Java写一个递归遍历目录下面的所有文件
字节跳动三面Java经历,砍下年薪50W的Offer,面试真题整理分享
应广大读者要求,今天开更一些大厂的面经和相关的面试干货,下面这份**最新字节跳动春招面经+笔记**带给大家。
228 0
字节跳动三面Java经历,砍下年薪50W的Offer,面试真题整理分享
Java工程师丨面试真题(一)
Java工程师丨面试真题(一)
面试官:java中的编码转化方式都有哪些?(中兴面试真题)
昨天晚上在微信上有人跟我说,他去中兴面试,面试官问了一个很变态的问题,问Java中的编码格式转换都有哪几种方式?由于之前就知道String中的转换方式,还有一些工具类,因此今天就好好的整理一下java中jdk提供的几种转换方式,希望在今年的面试中对你有帮助。
200 0
面试官:java中的编码转化方式都有哪些?(中兴面试真题)
阿里面试真题:NIO为什么不适合文件上传场景、如何优雅解决
阿里面试真题:NIO为什么不适合文件上传场景、如何优雅解决
阿里面试真题:NIO为什么不适合文件上传场景、如何优雅解决
【每日SQL打卡】​​​​​​​​​​​​​​​DAY 7丨字节面试真题【难度困难】
【每日SQL打卡】​​​​​​​​​​​​​​​DAY 7丨字节面试真题【难度困难】
【每日SQL打卡】​​​​​​​​​​​​​​​DAY 7丨字节面试真题【难度困难】

热门文章

最新文章

  • 1
    云计算运维工程师面试技巧
    912
  • 2
    【机器学习】面试问答:PCA算法介绍?PCA算法过程?PCA为什么要中心化处理?PCA为什么要做正交变化?PCA与线性判别分析LDA降维的区别?
    323
  • 3
    【机器学习】面试问答:决策树如何进行剪枝?剪枝的方法有哪些?
    240
  • 4
    【机器学习】SVM面试题:简单介绍一下SVM?支持向量机SVM、逻辑回归LR、决策树DT的直观对比和理论对比,该如何选择?SVM为什么采用间隔最大化?为什么要将求解SVM的原始问题转换为其对偶问题?
    216
  • 5
    【深度学习】Pytorch面试题:什么是 PyTorch?PyTorch 的基本要素是什么?Conv1d、Conv2d 和 Conv3d 有什么区别?
    738
  • 6
    【深度学习】TensorFlow面试题:什么是TensorFlow?你对张量了解多少?TensorFlow有什么优势?TensorFlow比PyTorch有什么不同?该如何选择?
    575
  • 7
    【机器学习】面试题:LSTM长短期记忆网络的理解?LSTM是怎么解决梯度消失的问题的?还有哪些其它的解决梯度消失或梯度爆炸的方法?
    508
  • 8
    【数据挖掘】XGBoost面试题:与GBDT的区别?为什么使用泰勒二阶展开?为什么可以并行训练?为什么快?防止过拟合的方法?如何处理缺失值?
    566
  • 9
    【数据挖掘】 GBDT面试题:其中基分类器CART回归树,节点的分裂标准是什么?与RF的区别?与XGB的区别?
    191
  • 10
    【机器学习】过拟合和欠拟合怎么判断,如何解决?(面试回答)
    1021
  • AI助理

    你好,我是AI助理

    可以解答问题、推荐解决方案等

    登录插画

    登录以查看您的控制台资源

    管理云资源
    状态一览
    快捷访问