C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-06-28
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix string字符串vector
* @param versionA int整型
* @param versionB int整型
* @return int整型
*/
int Git(vector<string>& matrix, int versionA, int versionB) {
// write code here
if(versionA == 0|| versionB == 0)return 0;
set<int> s;
s.insert(versionA);
dfs(matrix,versionA,versionB,s);
queue<int> qe;
vector<int> isVisit(matrix.size(),0);
qe.push(0);
isVisit[0] = 1;
while(!qe.empty())
{
int node = qe.front();
qe.pop();
if(s.count(node))return node;
for(int i = 0;i<matrix[0].size();i++)
{
if(matrix[node][i] == '0'||isVisit[i])continue;
isVisit[i] = 1;
qe.push(i);
}
}
return -1;
}
bool dfs(vector<string>& matrix,int versionA,int versionB,set<int>& s)
{
if(versionA == versionB)
{
return true;
}
for(int i = 0;i<matrix[0].size();i++)
{
if(matrix[versionA][i] == '0'||s.count(i))continue;
s.insert(i);
if(dfs(matrix,i,versionB,s)) return true;
s.erase(i);
}
return false;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 428KB, 提交时间: 2022-05-08
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix string字符串vector
* @param versionA int整型
* @param versionB int整型
* @return int整型
*/
int Git(vector<string>& matrix, int va, int vb) {
// write code here
int n = matrix.size();
vector<vector<int>> e(n);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(matrix[i][j]=='1')
e[i].emplace_back(j);
}
}
vector<int> deep(n);
vector<array<int, 9>> bfa(n);
auto dfs = [&](auto &&self, int u,int fa,int depth) -> void{
deep[u] = depth;
bfa[u][0] = fa;
for(auto v:e[u]){
if(v==fa) continue;
self(self, v, u, depth+1);
}
};
dfs(dfs, 0, -1, 0);
for(int i=1;i<=8;++i){
for(int j=0;j<n;++j){
bfa[j][i] = bfa[bfa[j][i-1]][i-1];
}
}
auto lca = [&](int x,int y) -> int{
if(deep[x]<deep[y]) swap(x,y);
while(deep[x]>deep[y]){
x = bfa[x][(int)log2(deep[x]-deep[y])];
}
if(x==y) return x;
for(int i=log2(deep[x]);i>=0;--i){
if(bfa[x][i]!=bfa[y][i]){
x = bfa[x][i];
y = bfa[y][i];
}
}
return bfa[x][0];
};
return lca(va,vb);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-01-25
#include <iostream>
#include <cstring>
#include <list>
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
map<int, int>layer;
Solution(){
layer[0] = 0;
}
void layered(vector<string>& matrix, int node, int l){
string temp = matrix[node];
for(int i = 0; i < temp.length(); i++){
if(temp[i] == '1') {
if(layer.find(i) == layer.end()){
layer[i] = l + 1;
layered(matrix, i, l + 1);
}
}
}
}
// 寻找node的父节点
int find_father(vector<string>& matrix, int node){
string temp = matrix[node];
int node_layer = layer[node];
for(int i = 0; i < temp.length(); i++){
if(temp[i] == '1' && layer[i] < node_layer) return i;
}
return 0;
}
list<int> find_ancestor(vector<string>& matrix, int node){
list<int> ret;
while(node != 0){
cout << "node is " << node << endl;
ret.push_front(node);
node = find_father(matrix, node);
}
ret.push_front(0);
return ret;
}
int Git(vector<string>& matrix, int versionA, int versionB) {
int ret = 0;
layered(matrix, 0, 0);
list<int> a = find_ancestor(matrix, versionA);
cout << "#" << endl;
list<int> b = find_ancestor(matrix, versionB);
cout << "b" << endl;
for(auto it = b.begin(); it != b.end(); it++){
cout << *it << " ";
}
cout << "b" << endl;
cout << endl;
for(auto it_a = a.begin(), it_b = b.begin(); it_a != a.end() && it_b != b.end(); it_a++, it_b++){
if(*it_a == *it_b) {
ret = *it_a;
}
else break;
}
return ret;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-01-26
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix string字符串vector
* @param versionA int整型
* @param versionB int整型
* @return int整型
*/
int Git(vector<string>& matrix, int versionA, int versionB) {
// write code here
vector<int> A;
vector<int> B;
queue<vector<int>> q;
q.push(vector<int>(1,0));
if(versionA == 0){
A = vector<int>(1,0);
}
if(versionB == 0){
B = vector<int>(1,0);
}
while(A.size() == 0 || B.size() == 0){
int sz = q.size();
for(int i = 0; i < sz; i++){
vector<int> tmp = q.front();
q.pop();
for(int j = 0; j < matrix[tmp.back()].length(); j++){
if(matrix[tmp.back()][j] == '1'){
if(tmp.size() <= 1 || (tmp.size() >= 2 && j != tmp[tmp.size()-2])){
vector<int> tmp1 = tmp;
tmp1.push_back(j);
q.push(tmp1);
if(j == versionA){
A = tmp1;
}
if(j == versionB){
B = tmp1;
}
}
}
}
}
}
int p = 0;
while(p<A.size() && p<B.size() && A[p] == B[p]){
p++;
}
return A[p-1];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 448KB, 提交时间: 2022-03-04
class Solution
{
public:
int shared_a, shared_b;//保存目标值
bool flag = 0;//判断两个节点是否在树同侧
int Git(vector<string>& matrix, int versionA, int versionB) {
shared_a = versionA, shared_b = versionB;
if (shared_a == shared_b) {
return shared_a;
}
else {
return Search(matrix, 0);
}
}
int Search(vector<string>& a, int j) {
int res = -1;
int count = 0;// 判断是否同侧
if (j == shared_a || j == shared_b) {
count++;
res = j;
}
// if (flag) {
// return -1; //剪枝
// }
for (int i = 0; i < a[j].size(); ++i) {
if (a[j][i] == '1') {
a[i][j] = '0';//去环
int t = Search(a, i);
if (t != -1) {
res = t;
count++;
}
}
}
if (count == 2) {
flag = true;
return j;
}
return res;
}
};
