LC 990. Satisfiability of Equality Equations
2024-09-01 09:41:31
Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.
Example 1:
Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations.
Example 2:
Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
Example 3:
Input: ["a==b","b==c","a==c"]
Output: true
Example 4:
Input: ["a==b","b!=c","c==a"]
Output: false
Example 5:
Input: ["c==c","b==d","x!=z"]
Output: true
Note:
1 <= equations.length <= 500equations[i].length == 4equations[i][0]andequations[i][3]are lowercase lettersequations[i][1]is either'='or'!'equations[i][2]is'='
Runtime: 12 ms, faster than 100.00% of C++ online submissions for Satisfiability of Equality Equations.
Memory Usage: 7.1 MB, less than 100.00% of C++ online submissions for Satisfiability of Equality Equations.
class Solution {
private:
int arr[];
public:
void unionab(int a, int b) {
arr[parent(a)] = arr[parent(b)];
}
int parent(int a) {
if(arr[a] != a) return parent(arr[a]);
return a;
}
bool uninit(int a) {
return arr[a] == a ? true : false;
}
bool hassameroot(int a, int b) {
return parent(a) == parent(b);
}
bool equationsPossible(vector<string>& equations) {
for(int i=; i<; i++) arr[i] = i;
for(int i=; i<equations.size(); i++) {
int a = ((int)equations[i][] - (int)'a');
int b = ((int)equations[i][] - (int)'a');
if ((int)equations[i][] == (int)'=') {
if(!hassameroot(a,b)) unionab(a,b);
}
}
for(int i=; i<equations.size(); i++) {
int a = ((int)equations[i][] - (int)'a');
int b = ((int)equations[i][] - (int)'a');
if((int)equations[i][] == (int)'!') {
if(hassameroot(a,b)) return false;
}
}
return true;
}
};
最新文章
- 我对BFC的理解
- mui 下拉刷新
- Computer assisted surgery
- 从零开始学jQuery插件开发
- [LeetCode] Word Break II (TLE)
- 可复用的js效果
- ContentProvider官方教程(8)自定义MIME
- Ubuntu环境变量——添加与删除
- PLS-00215:字符串长度限制在范围
- WebApp 中用 hashchange 做路由解析
- SharedPreference简介
- Centos 6.5中安装后不能打开emacs的问题
- ffmpeg参数具体解释
- C#中的ToString格式大全
- ABP+AdminLTE+Bootstrap Table权限管理系统一期
- [ZJOI2007]时态同步
- in成员资格符
- spring mvc 在上传图片时，浏览器报The request sent by the client was syntactically incorrect
- nginx访问统计
- [GAN] Generative networks