最短距离
1.本题为某公司的笔试题，所以没有这个测试链接。在这里只给出代码和思路。
2.题目描述
3.解题思路
4.对应代码
int minDistance1(vector<vector<int>>& road, int n, int x, int y)
{
//注意城市的下标是从1位置开始的0位置丢弃不用
vector<vector<int>>Map(n + 1, vector<int>(n + 1, INT_MAX));
//一开始设计为整型最大代表不可达
for (int i = 0; i < n; i++)
{
//这是因为输入犯贱
//1 2 10
//1 2 9 有可能有这样的输入
Map[road[i][0]][road[i][1]] = min(Map[road[i][0]][road[i][1]], road[i][2]);
Map[road[i][1]][road[i][0]] = min(Map[road[i][1]][road[i][0]], road[i][2]);
}
//生成邻接表，Map[i][j]的含义代表 i到j的距离为d
vector<bool>visit(n+ 1);
return process(Map, x, y, visit, n);
}
//从cur这个节点到target这个节点的最小距离是多少
int process(vector<vector<int>>& Map, int cur, int target, vector<bool>& visit,int n)
{
//已经访问过了
if (visit[cur]) {
return INT_MAX;
}
if (cur == target) {//找到x这个节点了
return 0;
}
visit[cur] = true;
int ans = INT_MAX;
for (int next = 1; next <= n; next++)
{
//如果不是自己并且这个点可达并且没有访问过
if (next != cur && Map[cur][next] != INT_MAX && !visit[next]) {
int ret = process(Map, next, target, visit, n);//遍历其可达的节点
if (ret != INT_MAX) {//说明可以到达ret
ans = min(ans, ret+Map[cur][next]);
}
}
}
visit[cur] = false;
return ans;
}
但是这样的方式是最暴力的所有节点都搞一遍时间复杂都有点高。下面我们来看看迪结特斯拉算法怎么来解这个题
1.第一步和暴力解一样需要生成邻接表，并且需要求这个最小值这一步还是不变的
2.准备一个优先级对象小根堆和一个visit数组标记某个节点是否从堆中弹出过，如果已经在堆当中弹出过再次弹出的时候直接忽略调因为第一次弹出的距离是最小的。
3.一开始先将x这个节点加入到优先级队列当中加入的形式为Node类型，Node当中有这个路径和城市的编号。x到x的距离为0所有pathSum为0加入到优先级队列当中，进入队列当中后每次在弹出一个看是否来到y了，是直接返回路径和，不是开始遍历当前节点可达的城市并且没有访问过将其加入到队列当中。
下面我们来看看代码如何来实现
int minDistance2(vector<vector<int>>& road, int n, int x, int y)
{
vector<vector<int>>Map(n + 1, vector<int>(n + 1, INT_MAX));
//一开始设计为整型最大代表不可达
for (int i = 0; i < n; i++)
{
//这是因为输入犯贱
//1 2 10
//1 2 9 有可能有这样的输入
Map[road[i][0]][road[i][1]] = min(Map[road[i][0]][road[i][1]], road[i][2]);
Map[road[i][1]][road[i][0]] = min(Map[road[i][1]][road[i][0]], road[i][2]);
}
vector<bool>visit(n + 1);
auto cmp = [&](Node& a, Node& b) {return a.pathSum > b.pathSum; };
priority_queue <Node, vector<Node>, decltype(cmp)>minHeap(cmp);
//小根堆
minHeap.push(Node(x,0));//x到x的距离为0
while (!minHeap.empty())
{
auto node = minHeap.top();
minHeap.pop();
//已经弹出过的节点不在弹出
if (visit[node.city] == true) {
continue;
}
if (node.city == y) {
return node.pathSum;
}
visit[node.city] = true;//当前这个节点已经被访问过了
for (int next = 1; next <= n; next++)
{
if (next != node.city && !visit[next] && Map[node.city][next] != INT_MAX) {
minHeap.push(Node(next,node.pathSum + Map[node.city][next]));
}
}
}
return INT_MAX;//x到y不可达
}
对应总代码包含测试代码
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
/*
int n, int[][] roads, int x, int y
n表示城市数量，城市编号0~n-1
roads[i][j] == distance，表示城市i到城市j距离为distance(无向图)
求城市x到城市y的最短距离
*/
//d算法的适用条件：1.这个图一定是有向图。2：所有的边没有负数
/*
* 牛客网有测试链接名字叫做单源最段路径
*/
class Soulution
{
public:
// 当前来到的Node，注意这不是城市的意思，这是就是一个普通的封装类
// Node封装了，当前来到的城市是什么，以及，从源出发点到这个城市的路径和是多少？
struct Node
{
Node(int c,int p)
:pathSum(p)
,city(c)
{}
int pathSum;
int city;
};
int minDistance1(vector<vector<int>>& road, int n, int x, int y)
{
//注意城市的下标是从1位置开始的0位置丢弃不用
vector<vector<int>>Map(n + 1, vector<int>(n + 1, INT_MAX));
//一开始设计为整型最大代表不可达
for (int i = 0; i < n; i++)
{
//这是因为输入犯贱
//1 2 10
//1 2 9 有可能有这样的输入
Map[road[i][0]][road[i][1]] = min(Map[road[i][0]][road[i][1]], road[i][2]);
Map[road[i][1]][road[i][0]] = min(Map[road[i][1]][road[i][0]], road[i][2]);
}
//生成邻接表，Map[i][j]的含义代表 i到j的距离为d
vector<bool>visit(n+ 1);
return process(Map, x, y, visit, n);
}
//从cur这个节点到target这个节点的最小距离是多少
int process(vector<vector<int>>& Map, int cur, int target, vector<bool>& visit,int n)
{
//已经访问过了
if (visit[cur]) {
return INT_MAX;
}
if (cur == target) {//找到x这个节点了
return 0;
}
visit[cur] = true;
int ans = INT_MAX;
for (int next = 1; next <= n; next++)
{
//如果不是自己并且这个点可达并且没有访问过
if (next != cur && Map[cur][next] != INT_MAX && !visit[next]) {
int ret = process(Map, next, target, visit, n);//遍历其可达的节点
if (ret != INT_MAX) {//说明可以到达ret
ans = min(ans, ret+Map[cur][next]);
}
}
}
visit[cur] = false;
return ans;
}
int minDistance2(vector<vector<int>>& road, int n, int x, int y)
{
vector<vector<int>>Map(n + 1, vector<int>(n + 1, INT_MAX));
//一开始设计为整型最大代表不可达
for (int i = 0; i < n; i++)
{
//这是因为输入犯贱
//1 2 10
//1 2 9 有可能有这样的输入
Map[road[i][0]][road[i][1]] = min(Map[road[i][0]][road[i][1]], road[i][2]);
Map[road[i][1]][road[i][0]] = min(Map[road[i][1]][road[i][0]], road[i][2]);
}
vector<bool>visit(n + 1);
auto cmp = [&](Node& a, Node& b) {return a.pathSum > b.pathSum; };
priority_queue <Node, vector<Node>, decltype(cmp)>minHeap(cmp);
//小根堆
minHeap.push(Node(x,0));//x到x的距离为0
while (!minHeap.empty())
{
auto node = minHeap.top();
minHeap.pop();
//已经弹出过的节点不在弹出
if (visit[node.city] == true) {
continue;
}
if (node.city == y) {
return node.pathSum;
}
visit[node.city] = true;//当前这个节点已经被访问过了
for (int next = 1; next <= n; next++)
{
if (next != node.city && !visit[next] && Map[node.city][next] != INT_MAX) {
minHeap.push(Node(next,node.pathSum + Map[node.city][next]));
}
}
}
return INT_MAX;//x到y不可达
}
};
vector<vector<int>>getRandom(int n, int v, int d)
{
vector<vector<int>>Map;
for (int i = 0; i < n; i++)
{
int x = rand() % v + 1;
int y = rand() % v + 1;
int distance = rand() % d;
Map.push_back({ x,y,distance });
}
return Map;
}
int main()
{
srand(time(0));
int times = 1000;
int cityMax = 16;
int pathMax = 30;
for (int i = 0; i < times; i++)
{
int n = rand() % cityMax + 1;
int m = rand() % 100+n;
int x = rand() % n + 1;
int y = rand() % n+ 1;
vector<vector<int>>Map = getRandom(m, n, pathMax);
int ans1 = Soulution().minDistance1(Map,n,x,y);
int ans2 = Soulution().minDistance2(Map,n, x,y);
if (ans1 != ans2) {
cout << ans1 << ":" << ans2 << endl;
cout << "错了" << endl;
return 0;
}
}
cout << "对了" << endl;
return 0;
}
下面我们还可以看看牛客网上的一道题来验证这道题的正确性
1.对应牛客网链接
2.题目描述
3.解题思路
这个题其实就是上面那个题的弱化版本，这里变成了有效图只要拿上面那个代码给一下下就可以了，非常的简单在这里就只给出代码不做过多解释了。
4.对应代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
struct Node
{
Node(int c,int p)
:pathSum(p),city(c)
{}
int pathSum;
int city;
};
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
// write code here
vector<vector<int>>Map(n+1,vector<int>(n+1,INT_MAX));
for(auto&road:graph)
{
Map[road[0]][road[1]]=min(Map[road[0]][road[1]],road[2]);
}
vector<bool>visit(n+1);
auto cmp=[&](Node&a,Node&b){return a.pathSum>b.pathSum;};
priority_queue<Node,vector<Node>,decltype(cmp)>minHeap(cmp);
minHeap.push(Node(1,0));
while(!minHeap.empty())
{
auto node=minHeap.top();
minHeap.pop();
if(visit[node.city]){
continue;
}
visit[node.city]=true;
if(node.city==n){
return node.pathSum;
}
for(int i=1;i<=n;i++){
if(i!=node.city&&Map[node.city][i]!=INT_MAX&&!visit[i]){
minHeap.push(Node(i,node.pathSum+Map[node.city][i]));
}
}
}
return -1;
}
};
4键键盘
1.对应letecode链接：
4.对应代码
class Solution {
public:
int maxA(int n) {
vector<int>dp(n);
for(int i=0;i<6&&i<n;i++){
dp[i]=i+1;//下标变换而已
}
// 可以证明：
// 来到i的时候，包括i在内最多有连续4次粘贴行为
// 不可能更多，如果有连续5次粘贴，一定就不再是最优解
// 假设开始时，A的数量为S，看如下的变化过程，我们称这是行为一：
// 开始 全选 复制(粘贴板S个A) 粘贴 粘贴 粘贴 粘贴 粘贴
// S S S 2*S 3*S 4*S 5*S 6*S
// 但是，注意看如下的行为二：
// 开始 全选 复制(粘贴板S个A) 粘贴 全选 复制(粘贴板2S个A) 粘贴 粘贴
// S S S 2*S 2*S 2*S 4*S 6*S
// 行为一，经历8步，最后是6*S个A
// 行为二，经历8步，最后是6*S个A
// 但是行为二在粘贴板上有2S个A，而行为一在粘贴板上有S个A
// 所以行为一没有行为二优
// 以此说明：来到i的时候，包括i在内最多有连续4次粘贴行为
// 那么就尝试：连续1次、连续2次、连续3次、连续4次粘贴行为即可
for(int i=6;i<n;i++)
{
dp[i]=max(max(dp[i-3]*2,dp[i-4]*3),max(dp[i-5]*4,dp[i-6]*5));
}
return dp[n-1];
}
};
冗余的边II
1.对应letecode链接：
冗余的边
2.题目描述
4.对应代码
class Solution {
public:
class UniFind {
public:
UniFind(int n) {
parent.resize(n + 1);
size.resize(n + 1);
help.resize(n + 1);
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = i;
}
}
int findFather(int i) {
int hi = 0;
while (parent[i] != i) {
i = parent[i];
help[hi++] = i;
}
hi--;
while (hi >= 0) {
parent[help[hi--]] = i;
}
return i;
}
bool IsSame(int i, int j) {
return findFather(i) == findFather(j);
}
void Union(int i, int j) {
int fatheri = findFather(i);
int fatherj = findFather(j);
if (fatheri != fatherj) {
if (size[fatheri] >= size[fatherj]) {
size[fatheri] += size[fatherj];
parent[fatherj] = fatheri;
} else {
size[fatherj] += size[fatheri];
parent[fatheri] = fatherj;
}
}
}
private:
vector<int>parent;
vector<int>size;
vector<int>help;
};
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int N = edges.size();
vector<int>prev(N + 1);
UniFind uf(N);
/*
prev[i]=0代表的是i这个节点第一次来到
prev[i]不为0代表是第二次来到了其值代表是那个节点来到我的
*/
vector<int>first;
vector<int>second;
vector<int>circle;//含义有点复杂
// 如果，没有入度为2的点，
// first second 都维持是null
// 如果，有入度为2的点，那么也只可能有一个
// 比如入度为2的点，是5
// first = [3,5]
// second = [12,5]
for (int i = 0; i < N; i++) {
int from = edges[i][0];
int to = edges[i][1];
if (prev[to] != 0) { //不是第一次到这个点了
//分别记录是第一次到这个点和第二次到这个点
first = {prev[to], to};
second = edges[i];
} else {
//to这个点是第一次来的
prev[to] = from;
if (uf.IsSame(from, to)) {//看是否形成环了
circle = edges[i];
} else {
uf.Union(from, to);//进行合并
}
}
}
//如果first为空那么second也一定为空
return first.empty() ? circle : (circle.empty() ? second : first);
}
};
下面我们在看来看看一到弱化版本的题目
冗余的边
1.对应letecode链接
2.题目描述
3.解题思路
4.对应代码
class Solution {
public:
struct UnFind
{
UnFind(int n)
{
parent.resize(n+1);
size.resize(n+1);
help.resize(n+1);
for(int i=1;i<=n;i++){
parent[i]=i;
size[i]=1;
}
}
int findFather(int i)
{
int hi=0;
while(i!=parent[i])
{
i=parent[i];
help[hi++]=i;
}
hi--;
while(hi>=0)
{
parent[help[hi--]]=i;
}
return i;
}
bool IsSame(int i,int j)
{
return findFather(i)==findFather(j);
}
void Union(int i,int j)
{
int findi=findFather(i);
int findj=findFather(j);
if(findi!=findj)
{
if(size[findi]>=size[findj])
{
size[findi]+=size[findj];
parent[findj]=findi;
}
else
{
size[findj]+=size[findi];
parent[findi]=findj;
}
}
}
vector<int>parent;
vector<int>size;
vector<int>help;
};
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n=edges.size();
UnFind uf(n);
//无相图只要找到环肯定就是那条冗余的边
for(auto &edge:edges)
{
int from=edge[0];
int to=edge[1];
if(uf.IsSame(from,to)){
return edge;
}
else
{
uf.Union(from,to);
}
}
return {};
}
};