首页 > 商汤笔试算法大类A卷
头像
wwxgo
编辑于 2020-08-20 22:09
+ 关注

商汤笔试算法大类A卷

选择填空题...深度学习相关盲猜 ==
编程题1:计算图中环的长度
memset(vis,0,sizeof(vis)),随机从一个节点进入,到过i节点vis[i]=1,当发现下一节点的vis为1则找到了环的一个入口。找到入口很方便计算环的长度
class Solution {
public:
    int CalculateLength(vector<int>& input) {
        // write code here
        int n = input.size();
        vector<int> vis(n, 0);
        int point = 0;
        // 找到一个入口点 point
        while (vis[point] != 1) {
            vis[point] = 1;
            point = input[point];
        }
        int start = point, ans = 1;
        while (input[start] != point) {
            start = input[start];
            ans++;
        }
        return ans;
    }
};


编程题2:
给定一个区间集合,最少去掉多少个区间使得剩下区间两两不相交?--》转化为最多取多少个区间不相交,贪心算法
int eraseOverlapIntervals(vector<vector<int> >& intervals) {
    // write code here
    if (intervals.size() == 0) return 0;
    sort(intervals.begin(), intervals.end(), cmp);
    int n = intervals.size(), ans = 1, k = 0; // ans 最大可取多少不相交的区间
    for (int i = 1; i < n; i++) {
        if (intervals[k][1] <= intervals[i][0]) {
            ans++;
            k = i;
        }
    }
    return n - ans;
}
编程题3:
求数字矩阵的最长严格上升路径,每次可以上下左右移动,记忆化搜索dp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
	int val, y, x;
};
bool cmp(const Node & d1, const Node & d2) {
	return d1.val < d2.val;
}
class Solution {
public:
	void SetMap(vector<vector<int> > & ma) {
		n = ma.size(), m = ma[0].size();
		mapm.resize(n);
		dp.resize(n);
		for (int i = 0; i < n; i++) {
			mapm[i].resize(m);
			dp[i].resize(m);
			for (int j = 0; j < m; j++) {
				mapm[i][j] = ma[i][j];
				dp[i][j] = 0;
				node.push_back({ma[i][j], i, j});
			}
		}
	}
	void dfs(int y, int x, int len) { // 记忆化搜索dp
		if (dp[y][x] >= len) return;
		else dp[y][x] = len;
		for (int i = 0; i < 4; i++) 
			if (x + dir[i][0] >= 0 && x + dir[i][0] < m && y + dir[i][1] >= 0 && y + dir[i][1] < n) {
				if (mapm[y + dir[i][1]][x + dir[i][0]] > mapm[y][x])
					dfs(y + dir[i][1], x + dir[i][0], len + 1);
			}
	}
	int MaxSeqLen() {
		int ans = 1;
		sort(node.begin(), node.end(), cmp); // 从小到大排序以减少搜索量
		for (int i = 0; i < node.size(); i++) // 枚举起始点
			dfs(node[i].y, node[i].x, 1);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				ans = max(ans, dp[i][j]);
		return ans;
	}
private:
	int n, m;
	int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
	vector<vector<int> > mapm;
	vector<Node> node;
	vector<vector<int> > dp; // 记忆化搜索dp,dp[i][j]存储到达ij位置的路径最长值
};

int main()
{
	int n, m;
	while (cin >> n >> m) {
		vector<vector<int> > mapm(n, vector<int>(m));
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> mapm[i][j];
		Solution sol;
		sol.SetMap(mapm);
		cout << sol.MaxSeqLen();
	}
	return 0;
}



全部评论

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

相关热帖

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

近期精华帖

热门推荐