Category: Hard

Posted 2022-06-18Updated 2022-06-17Hard / 复习4 minutes read (About 570 words)

Question

Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.

Implement the WordFilter class:

WordFilter(string[] words) Initializes the object with the words in the dictionary.

f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Solution

改版的前缀树，用后缀+符号+前缀的形式记录字典树。

TrieNode

用参数id记录TrieNode经历过的最大下标。

27位TrieNode数组children[]记录子TrieNode。

初始化

将words[]中的每个字符串记录在TrieNode上，保存TrieNode的根节点root。
在遍历每个字符串时，需要将每个“后缀+符号+前缀”组成的新字符串记录在字典树中，并更新当前节点的id值。

将后缀部分添加完毕后，加入特殊符号。检查并创建当前节点的curr[26]位置。
然后继续将整个前缀字符串加入字典树，并更新当前节点的id值。

搜索

搜索时，先遍历后缀，查找字典树的路径是否存在，并更新当前节点的位置，如不存在则返回-1。
然后检查并跳过curr.children[26]的位置，如不存在则返回-1。
最后遍历前缀，更新节点位置，如果路径不存在则返回-1。

最后返回当前节点的id即可。

Code

class WordFilter {
    class TrieNode{
        int id;
        TrieNode[] children;
        public TrieNode(){
            children = new TrieNode[27];
            id = 0;
        }
    }
    
    TrieNode root;
    public WordFilter(String[] words) {
        root = new TrieNode();
    
        for(int k = 0; k < words.length; k++){
            String word = words[k];
            for(int i = 0; i < word.length(); i++){
                TrieNode curr = root;
                int j = i;
                while(j < word.length()){
                    int index = word.charAt(j) - 'a';
                    if(curr.children[index] == null) curr.children[index] = new TrieNode();
                    curr = curr.children[index];
                    curr.id = k;
                    j++;
                }
                if(curr.children[26] == null) curr.children[26] = new TrieNode();
                curr = curr.children[26];
                curr.id = k;
                for(char c : word.toCharArray()){
                    int index = c - 'a';
                    if(curr.children[index] == null) curr.children[index] = new TrieNode();
                    curr = curr.children[index];
                    curr.id = k;
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        TrieNode curr = root;
        for(char c : suffix.toCharArray()){
            int index = c - 'a';
            if(curr.children[index] == null) return -1;
            curr = curr.children[index];
        }
        
        if(curr.children[26] == null) return -1;
        curr = curr.children[26];
        
        for(char c : prefix.toCharArray()){
            int index = c - 'a';
            if(curr.children[index] == null) return -1;
            curr = curr.children[index];
        }
        return curr.id;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */

Posted 2022-06-18Updated 2022-06-17Hard / 复习10 minutes read (About 1452 words)

968. Binary Tree Cameras

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法，后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态：

未被监控，返回0。
摄像头，返回1。
已被监控，返回2。

递归，当当前节点为空，则返回2，表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控，则当前节点需要设置相机，返回1，计数res+1。
如果下面的子节点有一个为摄像头，则当前节点已被监控，返回2。
否则下面的节点均为已被监控，此时返回未被监控0。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

Solution 2

参考：从递归优化到树形DP

树形DP。
递归，每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态：

放置了相机。
没有相机，但是被父节点parent监控。
没有相机，但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched，来判断当前节点是否有相机，是否被监控。
当当前节点为空节点时，如果设置应当有相机（做不到）则返回无限大，消除这个返回值。如果不应该有相机，则返回0。

向下递归子节点。

当当前节点应该有相机时：
子节点一定被监控因此isWatched为true。
子节点可以放置或不放置相机，因此hasCamera可以为true或false。
注意当前位置放置相机，则子节点最多放置一个相机，因此一共有三种组合。
由于相机至少有一个，因此返回其中的最小值+1。
当当前节点没有放置相机，但被父节点监控时：
左右节点一共有四种组合，分别同时将子节点的监控状态向下递归。
返回其中的最小值。
当当前节点没有放置相机，也没有被父节点监控，而是被子节点监控时：
子节点至少有一个相机，向下递归状态，一共有三种组合。
返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle)，取两者中的小值，即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时，因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

withCam: 当前子树root有相机。
noCamWatchedByParent: 当前子树root没有相机，被父节点监控。
noCamWatchedBySon: 当前子树root没有相机，被子节点监控。

在每次递归时，获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数，将其返回。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}

Question

Solution

TrieNode

初始化

搜索

Code

Question

Solution 1

Code

Solution 2

递归方法 minCam()

树形dp优化剪枝

Code

Code

Recents

Archives

Links