資料結構
網路
關係資料庫管理系統 (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
廣告