商汤科技2020.08.20后端开发笔试(1h AK)
第一题：找Good，每一个字符都只能使用一次，
思路：贪心策略，给已经拼过的Good的字符设置一个访问标记即可；
样例：
输入：
Goo23good Gooddd
123 GoodoodGGoooddjfhjdGGooo3dkdggggGoood0123
123 GoodoodGGoooddjfhjdGGooo3dkdggggGoood0123
输出：
2
5
代码：
#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
9 1 4
6 2 8
5 5 7
输出：
5
代码：
#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] ]
输出：
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;
}
}; 
