选择填空题...深度学习相关盲猜 ==
编程题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) 回帖