leetcode47,leetcode491,leetcode40,leetcode90,系列问题包你懂!!!Trie树对于排列问题、组合等结果集去重的应用

2024-01-08 00:08:09

leetcode47. 全排列 IIleetcode491. 非递减子序列leetcode40. 组合总和 IIleetcode90. 子集 II

题目

不过多赘述

思路

实际上这几题是相同的,都是求一个结果集合,然后集合中的元素不能重复。并且每一个元素都满足一定要求。
那么实际上,我们想一想,trie树就是一种很好的具有去重功能的数据结构,那么这些问题就都可以归结为建立一个trie树,然后从头读到叶子节点,然后对于具体问题就是看他的要求了,比如排列问题相当于没要求,非递减子序列则是要求trie树dfs过程元素一致单调不减,求和就是累计递归过程中节点的值与target值对比,子集则是递归过程中每读一个新节点我就存一次结果。
这么一看是不是通透了,那么我们举一个例子,这个例子是leetcode491. 非递减子序列,也是我思考出这一思路的题,下面将是我逐步优化代码的过程。注意第三版trie树的set还可以用map,这样甚至能记录一些其他属性比如每个节点上出现该数字的次数。

题解

// 第一版,这时候我是建立一个trie树,然后再遍历的
class Solution {
    // 这题用trie树解决,其实init时候可以边建立树边记录数据,不用再dfs,可以优化一下
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();
    int len = 0;

    public List<List<Integer>> findSubsequences(int[] nums) {
        Node dummy = new Node();
        // 别忘了初始化默认是0
        dummy.val = -101;
        dummy.subNode = new ArrayList<>();
        trieInit(dummy, nums, 0);
        dfs(dummy);
        return list;
    }

    public void dfs(Node root) {
        if (root == null) {
            return;
        }
        for(int i=0;i<root.subNode.size();i++) {
            subList.add(root.subNode.get(i).val);
            len++;
            if (len > 1) {list.add(new ArrayList<>(subList));}
            dfs(root.subNode.get(i));
            len--;
            subList.remove(subList.size() - 1);
        }
    }

    public void trieInit(Node root, int[] nums, int idx) {
        if (idx == nums.length) {return;}
        for(int i=idx;i<nums.length;i++) {
            if (!root.subNode.isEmpty() && root.subNode.get(root.subNode.size() - 1).val == nums[i]) {continue;}
            if (root.val > nums[i]) {continue;}
            boolean flag = false;
            for (int j=0;j<root.subNode.size();j++) {
                if (root.subNode.get(j).val == nums[i]) {
                    trieInit(root.subNode.get(j), nums, i + 1);
                    flag = true;
                    break;
                }
            }
            if (flag) {continue;}
            Node node = new Node();
            node.val = nums[i];
            node.subNode = new ArrayList<>();
            root.subNode.add(node);
            /*subList.add(nums[i]);
            len++;
            if (len > 1) {list.add(new ArrayList<>(subList));}*/
            trieInit(node, nums, i + 1);
            /*len--;
            subList.remove(subList.size() - 1);*/
        }
    }
}

class Node {
    List<Node> subNode;
    int val;
}
// 第二版,我将建立树和遍历树合为一起,一边建立一边读
class Solution {
    // 这题用trie树解决,其实init时候可以边建立树边记录数据,不用再dfs,可以优化一下
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();
    int len = 0;

    public List<List<Integer>> findSubsequences(int[] nums) {
        Node dummy = new Node();
        // 别忘了初始化默认是0
        dummy.val = -101;
        dummy.subNode = new ArrayList<>();
        trieInit(dummy, nums, 0);
        return list;
    }
    
    public void trieInit(Node root, int[] nums, int idx) {
        //if (idx == nums.length) {return;}
        for(int i=idx;i<nums.length;i++) {
            if (!root.subNode.isEmpty() && root.subNode.get(root.subNode.size() - 1).val == nums[i]) {continue;}
            if (root.val > nums[i]) {continue;}
            boolean flag = false;
            for (int j=0;j<root.subNode.size();j++) {
                if (root.subNode.get(j).val == nums[i]) {
                    trieInit(root.subNode.get(j), nums, i + 1);
                    flag = true;
                    break;
                }
            }
            if (flag) {continue;}
            Node node = new Node();
            node.val = nums[i];
            node.subNode = new ArrayList<>();
            root.subNode.add(node);
            subList.add(nums[i]);
            len++;
            if (len > 1) {list.add(new ArrayList<>(subList));}
            trieInit(node, nums, i + 1);
            len--;
            subList.remove(subList.size() - 1);
        }
    }
}

class Node {
    List<Node> subNode;
    int val;
}
// 第三版,我意识到不需要Node类来具体对应树的数据结构,可以在每个节点进到trieInit函数时候建立一个set,这样set就是记录trie树当前节点下的所有可能子节点了,并且是自带去重的,还不用for遍历子节点了
class Solution {
    // 这题用trie树解决,其实init时候可以边建立树边记录数据,不用再dfs,可以优化一下
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        trieInit(nums, 0);
        return list;
    }

    public void trieInit(int[] nums, int idx) {
        // 子节点中的数字都有哪些
        Set<Integer> set = new HashSet<>();
        for(int i=idx;i<nums.length;i++) {
            if (!subList.isEmpty() && subList.get(subList.size() - 1) > nums[i]) {continue;}
            if (set.contains(nums[i])) {continue;}
            subList.add(nums[i]);
            set.add(nums[i]);
            if (subList.size() > 1) {list.add(new ArrayList<>(subList));}
            trieInit(nums, i + 1);
            subList.remove(subList.size() - 1);
        }
    }
}

文章来源:https://blog.csdn.net/pige666/article/details/135446144
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。