商汤科技2020.08.20后端开发笔试(1h AK)

第一题：找Good，每一个字符都只能使用一次，

思路：贪心策略，给已经拼过的Good的字符设置一个访问标记即可；

样例：

输入：

Goo23good Gooddd
123 GoodoodGGoooddjfhjdGGooo3dkdggggGoood0123

输出：

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);

template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}

const int maxn = 100005;
bool visit[maxn];

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
#endif

    string s;
    while (getline(cin, s)) {
        memset(visit, 0, sizeof(visit));
        int n = s.size();
        int count = 0;
        for(int i = 0; i < n; ++i) {
            if(s[i] != 'G') continue;

            int onum = 0;
            for(int j = i+1; j < n; ++j) {
                if(visit[j]) continue;

                if(s[j] == 'o') {
                    ++onum;
                    if(onum <= 2) visit[j] = true;
                } else if(onum >= 2 && s[j] == 'd') {
                    visit[j] = true;
                    ++count;
                    break;
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}

第二题：矩阵中，找最长的严格递增路径

思路：记忆化搜索，f[i][j]表示从[i,j]开始的最长的长度，遍历二维数组，如果已经计算过改点的值，直接返回即可

样例：

输入：

3 3
9 1 4
6 2 8
5 5 7

输出：

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define ios ios::sync_with_stdio(false),cin.tie(0);

template <typename T>
inline void read(T &x) {char ch=getchar(); int f=1; x=0; while(!isdigit(ch)){if(ch=='-')f *= -1; ch=getchar();} while(isdigit(ch)) {x = (x<<1) + (x<<3) + (ch^48); ch=getchar();} x*=f;}
ll qpow(ll x, ll y) { ll a=1, b=x; while(y){if(y&0x1) a*=b; b*=b; y>>=1;} return a;}

int m;
int n;
vector<vector<int>> dirs = {{1,0},{0,1},{-1,0},{0,-1}};

int dfs(vector<vector<int>>& arr, vector<vector<int>>& f, int x, int y) {
    if(x < 1 || y < 1 || x > m || y > n) return 0;
    if(f[x][y] > 0) return f[x][y];

    int curMax = 0;
    for(auto d : dirs) {
        int i = x + d[0];
        int j = y + d[1];

        if(i < 1 || j < 1 || i > m || j > n || arr[i][j] <= arr[x][y]) continue;
        curMax = max(curMax, dfs(arr, f, i, j));
    }
    f[x][y] = curMax + 1;
    return f[x][y];
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("b.txt", "r", stdin);
#endif

    while(cin >> m >> n) {
        vector<vector<int>> arr(m+1, vector<int>(n+1, 0));
        vector<vector<int>> f(m+1, vector<int>(n+1, 0));
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) cin >> arr[i][j];
        }
        int ans = 0;
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(f[i][j] == 0) dfs(arr, f, i, j);
                ans = max(ans, f[i][j]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

第三题：n个区间，求最少删除多少个区间，可以让它们彼此不重叠

思路：本质就是一个最长递增子序列长度，但是首先要预处理数据，把区间段排序成升序，然后找最长递增的子序列即可。

答案就是 n - maxLen, 即：最少删除的区间

样例：

输入：

[ [1,2], [2,3], [3,4], [1,3] ]

输出：

代码：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int> >& intervals) {
        int n = intervals.size();
        if(n <= 1) return 0;
        sort(intervals.begin(), intervals.end(), [](const vector<int>& l, const vector<int>& r) {
            if(l[0] == r[0]) return l[1] < r[1];
            return l[0] < r[0];
        });

        vector<int> f(n, 1);
        int ans = 1;
        for(int i = 1; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                if(intervals[i][0] >= intervals[j][1]) {
                    f[i] = max(f[i], f[j] + 1);
                    ans = max(ans, f[i]);
                }
            }
        }
        return n - ans;
    }
};

#秋招##笔试题目##C/C++##商汤科技#