华为MindSpore开源实习机试题

浅浅记录下华为MindSpore开源实习机试题目，三道题。

整体来看不算太难。难点是输入输出别扭，不知道是有意为之还是其他原因。

第一道题：请参考此题剑指 Offer 39. 数组中出现次数超过一半的数字

数组中出现超过次数超过一半的数字（哈希）

题解：

//
// 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;
}

第二道题：请参考此题14. 最长公共前缀

 

题解：

 

//
// 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;
}

 第三题：请参考此题96. 不同的二叉搜索树

 题解：

#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;
}