数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中等式方程的可满足性
假设我们有一组表示变量之间关系的方程，每个字符串equations[i]的长度为4，并采用两种不同形式之一：“a==b”或“a!=b”。这里，a和b是小写字母，代表单个字母的变量名。因此，我们必须找到只有当可以为变量名分配整数以满足所有给定方程时才为真的情况。
如果输入如下：["a==b","b==c","a==c"]，则答案为true。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为getParent()的方法，它将接收字符x和映射m，其工作原理如下：
如果m[x] = x，则返回x；
否则设置m[x] := getParent(m[x], m)并返回m[x]
在主方法中，执行以下操作：
定义两个数组equal和notEqual，创建一个名为parent的映射
n := e的大小
对于范围0到n – 1中的i
设置parent[e[i, 0]] := e[i, 0]，parent[e[i, 3]] := e[i, 3]
如果e[i, 1]是等号，则将i插入equal数组，否则将i插入notEqual数组
对于范围0到equal大小 – 1中的i
index := equal[i]，将u、v设置为e[index, 0]和e[index, 3]
parent[getParent(u, parent)] := parent[getParent(v, parent)]
对于范围0到notEqual大小 – 1中的i
index := notEqual[i]，将u、v设置为e[index, 0]和e[index, 3]
如果getParent(u, parent) = getParent(v, parent)，则返回false
返回true
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char getParent(char x, map <char, char> m){
if(m[x] == x) return x;
return m[x] = getParent(m[x], m);
}
bool equationsPossible(vector<string>& e) {
vector <int> equal;
vector <int> notEqual;
map <char, char> parent;
int n = e.size();
for(int i = 0; i < n; i++){
parent[e[i][0]]= e[i][0];
parent[e[i][3]]= e[i][3];
if(e[i][1] == '='){
equal.push_back(i);
}else{
notEqual.push_back(i);
}
}
for(int i = 0; i < equal.size(); i++){
int idx = equal[i];
char u = e[idx][0];
char v = e[idx][3];
parent[getParent(u, parent)] = parent[getParent(v, parent)];
}
for(int i = 0; i < notEqual.size(); i++){
int idx = notEqual[i];
char u = e[idx][0];
char v = e[idx][3];
if(getParent(u, parent) == getParent(v, parent)) return false;
}
return true;
}
};
main(){
vector<string> v1 = {"a==b","b==c","a==c"};
Solution ob;
cout << (ob.equationsPossible(v1));
}输入
["a==b","b==c","a==c"]
输出
true
更新于：2020年4月30日
浏览量 185
广告