Huawei mindspire open source internship machine test questions

Record Huawei MindSpore Open source internship machine test topic , Three questions .

On the whole, it's not too difficult . The difficulty is that the input and output are awkward , I don't know whether it was intentional or for other reasons .

The first question ： Please refer to this question The finger of the sword Offer 39. A number that appears more than half the times in an array

There are more than half of the numbers in the array （ Hash ）

Answer key ：

//
// Created by zhanghao on 2022/6/2.
//

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace  std;

int countNum(vector<int> & nums){
    int ans = 0;
    int n = nums.size();
    unordered_map<int,int> mymap(n);
    for(int i = 0 ; i < n; i++){
        mymap[nums[i]]++;
    }
    for(int i = 0 ; i < n;i++){
        if(mymap[nums[i]] > n/2){
            ans = nums[i];
            break;
        }
    }
    return ans;
}
int main(){
    vector<int> nums;
    int num;
    string s;
    cin >> s;
    for(auto i : s){
        if(i >= '0' && i <= '9'){
            nums.push_back((i-'0'));
        }
    }

    int ans = countNum(nums);
    cout<<ans<<endl;
    return 0;
}

The second question ： Please refer to this question 14. The longest common prefix

 

Answer key ：

 

//
// Created by zhanghao on 2022/6/2.
//


#include <iostream>
#include <vector>
#include <string>
using namespace std;
string longest(const string& str1, const string& str2) {
    int length = min(str1.size(), str2.size());
    int index = 0;
    while (index < length && str1[index] == str2[index]) {
        ++index;
    }
    return str1.substr(0, index);
}
string longestCommonPrefix(vector<string>& strs) {
    if (!strs.size()) {
        return "";
    }
    string prefix = strs[0];
    int count = strs.size();
    for (int i = 1; i < count; ++i) {
        prefix = longest(prefix, strs[i]);
        if (!prefix.size()) {
            break;
        }
    }
    return prefix;
}






int main()
{
    // please define the C++ input here. For example: int a,b; cin>>a>>b;;
    // please finish the function body here.
    // please define the C++ output here. For example:cout<<____<<endl;
    string s;
    vector<string> arr;
    cin >> s;
    int n = s.size();
    for(int i = 0 ; i < n;i++){
        if(s[i] == '"'){
            int left = ++i;

            int n = 0;
            while(s[i]!='"'){
                n++;
                i++;
            }
            string temp = s.substr(left,n);
            arr.push_back(temp);
        }
    }
    string ans = longestCommonPrefix(arr);
    cout<<ans<<endl;
    return 0;
}

  Third question ： Please refer to this question 96. Different binary search trees

  Answer key ：

#include <iostream>
#include <vector>
using namespace std;

int numTree(int n){
    vector<int> dp(n+1);
    dp[0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 0; j <= i-1;j++){
            dp[i] += dp[j]*dp[(i-1)-j];
        }
    }
    return dp[n];
}
int main(){
    int n;
    cin >> n;
    int ans = numTree(n);
    cout<<ans<<endl;
    return 0;
}