leetcode990-等式方程的可满足性

原题

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。

只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。 

示例 1:

输入: ["ab","b!=a"] 输出: false
解释: 如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2:

输入: ["ba","ab"] 输出: true
说明: 我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3:

输入: ["ab","bc","ac"] 输出: true

示例 4:

输入: ["ab","b!=c","ca"] 输出: false

示例 5:

输入: ["cc","bd","x!=z"] 输出: true

提示:

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '=',要么是 '!'
  5. equations[i][2] 是 '='

解法

本题解同步发于leetcode题解:简洁的Java并查集

思想

见代码部分

代码

我写的这个代码没有任何优化但是很简洁,使用的HashMap实现的并查集(如果不了解并查集建议先去学习一下哦,还是蛮实用的一个数据结构的)

比较重要的思路是一定要先将字符串方程按相等到不等来排序,相等的方程用于建立并查集,不等的方程用于判断是否出错(即不等的两个代数是否出现在了同一个集合中)。

class Solution {
    public boolean equationsPossible(String[] equations) {
        // 并查集
        Map<Character,Character> father = new HashMap<>();
        // 先将字符串方程从相等到不等排序
        Arrays.sort(equations,(s1,s2)->{
            if(s1.charAt(1)==s2.charAt(1)) return 0;
            return s1.charAt(1)=='='?-1:1;
        });

        for(String s:equations){
            char[] chars = s.toCharArray();
            char first = chars[0];
            char second = chars[3];
            // 获取根代表
            while(father.containsKey(first) ) first = father.get(first);
            while(father.containsKey(second)) second = father.get(second);
            // 如果是不等,但根代表相同,说明出错
            if(chars[1] == '!'){
                if(first == second) return false;
            // 如果是相等,跳过根代表相同的情况,把一个根代表连接到另一个根代表上(合并集合)
            }else{
                if(first == second) continue;
                father.put(first, second);
            }
        }
        return true;
    }
}

刚看了下官方的题解并没有先排序,而是进行了两次遍历,第一次处理相等的,第二次处理不等的,确实比我写的时间复杂度要好,那么按这个思路修改之后就是:

class Solution {
    public boolean equationsPossible(String[] equations) {
        Map<Character,Character> father = new HashMap<>();
        //建立并查集
        for(String s:equations){
            char[] chars = s.toCharArray();
            if(chars[1] == '='){
                char first = chars[0];
                char second = chars[3];
                while(father.containsKey(first) ) first = father.get(first);
                while(father.containsKey(second)) second = father.get(second);
                if(first == second) continue;
                father.put(first, second);
            }
        }
        //检查是否有错
        for(String s:equations){
            char[] chars = s.toCharArray();
            if(chars[1] == '!'){
                char first = chars[0];
                char second = chars[3];
                while(father.containsKey(first) ) first = father.get(first);
                while(father.containsKey(second)) second = father.get(second);
                if(first == second) return false;
            }
        }
        return true;
    }
}

可以发现有一些重复代码,如果抽取成一个函数会更简洁,还有哈希集可以写成数组,时间成本会更低一些,感兴趣的小伙伴自己试试优化啦(^_^)。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode990-%e7%ad%89%e5%bc%8f%e6%96%b9%e7%a8%8b%e7%9a%84%e5%8f%af%e6%bb%a1%e8%b6%b3%e6%80%a7/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月7日
下一篇 2020年6月9日

相关推荐

  • leetcode105-从前序与中序遍历序列构造二叉树

    原题 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inord…

    算法 2020年1月13日
    090
  • leetcode151-翻转字符串里的单词

    原题 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he…

    算法 2019年11月22日
    090
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270
  • leetcode42-接雨水

    原题 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高…

    2020年1月23日
    0310
  • leetcode4-寻找两个有序数组的中位数

    这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m…

    算法 2020年1月9日
    0620
  • leetcode217-存在重复元素

    原题 给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。 示例1: 输入: [1,2,3…

    算法 2019年12月18日
    080
  • leetcode49-字母异位词分组

    原题 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat",…

    算法 2019年12月25日
    0110
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0110

发表回复

登录后才能评论