首页 > 20200820-2021届商汤笔试-开发大类A卷-编程题解
头像
t9UhoI
编辑于 2020-08-21 10:17
+ 关注

20200820-2021届商汤笔试-开发大类A卷-编程题解

一个小时全 Accept 了,题目还算友好~

第一题,找 Good
#include<bits/stdc++.h>
using namespace std;
int main() {
    string str = "", s;
    cin >> str;
    while (cin >> s) { str += " " + s; }
    int ans = 0;
    int i = 0, j = 1, k = 3, onum = 0;
    bool flag = false;
    for (int i = 0; i < str.length() - 3; i++) {
        if (str[i] != 'G') continue;
        j = max(i + 1, j);
        for (; j < str.length() - 1; j++) {
            if (str[j] != 'o') continue;
            if (onum == 0) onum++;
            else if (onum == 1) { onum++; break; }
        }
        if (j == str.length() - 1) {  flag = true; }
        if (onum == 2) {
            onum = 0; j++; k = max(j + 1, k);
            for (; k < str.length(); k++) {
                if (str[k] != 'd') continue;
                k++; ans++; break;
            }
            if (k == str.length()) { flag = true; }
        }
        if (flag) break;
    }
    cout << ans << endl;
    return 0;
}
第二题,找最长递增路径
#include<bits/stdc++.h>
using namespace std;
int main() {
    int rows, cols, i, j;
    cin >> rows >> cols;
    vector<vector<int>> matrix(rows, vector<int>(cols));
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) { cin >> matrix[i][j]; }
    }
    vector<vector<int>> outdegree(rows, vector<int>(cols, 0));
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            if (j != cols-1 && matrix[i][j] < matrix[i][j+1]) outdegree[i][j]++;
            if (i != rows-1 && matrix[i][j] < matrix[i+1][j]) outdegree[i][j]++;
            if (j != 0 && matrix[i][j] < matrix[i][j-1]) outdegree[i][j]++;
            if (i != 0 && matrix[i][j] < matrix[i-1][j]) outdegree[i][j]++;
        }
    }
    vector<pair<int,int>> leaves;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < cols; j++) {
            if (outdegree[i][j] == 0) leaves.emplace_back(i, j);
        }
    }
    int ans = 0;
    while (!leaves.empty()) {
        ans++;
        vector<pair<int,int>> newLeaves;
        for (int index = 0; index < leaves.size(); index++) {
            i = leaves[index].first, j = leaves[index].second;
            if (j != cols-1 && matrix[i][j] > matrix[i][j+1] && --outdegree[i][j+1] == 0) 
                newLeaves.emplace_back(i, j+1);
            if (i != rows-1 && matrix[i][j] > matrix[i+1][j] && --outdegree[i+1][j] == 0) 
                newLeaves.emplace_back(i+1, j);
            if (j != 0 && matrix[i][j] > matrix[i][j-1] && --outdegree[i][j-1] == 0) 
                newLeaves.emplace_back(i, j-1);
            if (i != 0 && matrix[i][j] > matrix[i-1][j] && --outdegree[i-1][j] == 0) 
                newLeaves.emplace_back(i-1, j);
        }
        leaves = newLeaves;
    }
    cout << ans << endl;
    return 0;
}
第三题,删区间
class Solution {
public:
    /**
     * 
     * @param intervals int整型vector<vector<>> 
     * @return int整型
     */
    int eraseOverlapIntervals(vector<vector<int> >& intervals) {
        // write code here
        if (intervals.size() < 2) return 0;
        sort(intervals.begin(), intervals.end());
        int start = intervals[0][0], end = intervals[0][1];
        int ans = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= end) {
                start = intervals[i][0]; end = intervals[i][1];
            } else if (intervals[i][1] <= end) {
                start = intervals[i][0]; end = intervals[i][1];
                ans++;
            }
        }
        return ans;
    }
};

求个面试机会~


全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐