陌陌算法

一面

2021-10-20

简单几道题

递归计算数组的和（+数组实现）

数组每一个元素除以第一个元素

二叉树计算深度

矩阵乘法

// 你必须定义一个 `main()` 函数入口。
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int getsum(const vector<int>& nums, int index){

  if(index == nums.size()-1){
    return nums[index];
  }
  return nums[index]+getsum(nums, index+1);
}

/*
int getsum(int[] nums, int index, int len){
  if(index == len-1){
    return 
  }
}
*/

void div(int nums[], int len){
  int p = 0;
  int tmp = *nums;
  cout << "tmp: " << tmp << endl;
  while(p<len){
    nums[p]/=tmp;
    p++;
  }
  return;

}

/*
class TreeNode{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode():left(nullptr), right(nullptr), val(0){;}
};  // class TreeNode

int getDepth(TreeNode* root){
  if(!root){
    return 0;
  }
  auto l = getDepth(root->left);
  auto r = getDepth(root->right);
  return max({r, l})+1;
}
*/

int matMul(const vector<vector<int>>& m1, const vector<vector<int>>& m2, vector<vector<int>>& out){
  int r1 = m1.size();
  int c1 = m1[0].size();
  int r2 = m2.size();
  int c2 = m2[0].size();

  if(c1!=r2){
    return -1;
  }

  out.clear();
  for(int i = 0; i<r1; i++){
    out.emplace_back(vector<int>(c2, 0));
  }

  for(int i = 0; i<r1; i++){
    for(int j = 0; j<c2; j++){
      for(int k = 0; k<c1; k++){
        out[i][j]+=m1[i][k]*m2[k][j];
      }
    }
  }
  return 1;
}

int main()
{
  /*
  cout << "Hello, World!" << endl;
  vector<int> nums = {1,2,3,4};
  auto res = getsum(nums, 0);
  cout << res << endl;
  int arr[4] = {2,2,4,4};
  div(arr, 4);
  for(int i = 0; i<4; i++){
    cout << arr[i] << " ";
  }
  cout << endl;

  */


  vector<vector<int>> m1 = {{1,1,1},
                            {1,1,1}};
  vector<vector<int>> m2 = {{2,2},
                            {2,2},
                            {2,2}};

  vector<vector<int>> out;
  int f = matMul(m1, m2, out);
  for(const auto& line:out){
    for_each(line.begin(), line.end(), [](int a){cout << a << " ";});
    cout << endl;
  }
  return 0;
}