Tag: 每日一题

Posted 2022-06-25Updated 2022-06-24LeetCode / Medium2 minutes read (About 356 words)

Question

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Solution 1

记录两个最大值last1和last2，初始化为整数最小值。真值flag初始化为true用来记录是否已经有非单调递增的值出现。
遍历数组，如果当前数字num大于等于last2，则符合单调递增，更新last1和last2。

如果num小于last2，则不符合单调递增，此时将flag置为false。

如果num大于等于last1，则跳过现有的last2，将num保存在last2上。
如果num小于，则保留当前的last2

如果flag已经为false，则非单调递增的数字超过1个，返回false。
遍历完毕则返回true。

Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        boolean flag = true;
        int last1 = Integer.MIN_VALUE, last2 = Integer.MIN_VALUE;
        
        for(int num : nums){
            if(num >= last2){
                last1 = last2;
                last2 = num;
            }
            else if(flag){
                flag = false;
                if(num >= last1) last2 = num;
                else continue;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Solution 2

原理和Solution 1相同，只不过采用单调栈的形式保存单调递增数字。

Code

class Solution {
    public boolean checkPossibility(int[] nums) {
        Stack<Integer> s = new Stack<>();
        boolean flag = true;
        
        for(int num : nums){
            if(s.isEmpty() || num >= s.peek()) s.push(num);
            else if(flag){
                flag = false;
                int temp = s.pop();
                if(s.isEmpty() || num >= s.peek()) s.push(num);
                else s.push(temp);
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Posted 2022-06-24Updated 2022-06-24LeetCode / Hard / 复习2 minutes read (About 335 words)

630. Course Schedule III

Question

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Solution

贪心算法，优先级队列实现。
优先选择截止日期更短的课程。
优先级队列pq记录当前已选课程，按持续时间从长到短排列。
同时维护当前的日期curDay。

当当前选择的课程截止日期晚于curDay加上当前的持续时间duration时，查看大根堆里最长的课程longestDuration。如果最长的时间大于当前时间，则将其挤出，并将当前课程加入。

如果当前课程截止日期晚于curDay，则直接将其加入队列中，并更新curDay。

Code

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int curDay = 0;
        for(int[] course : courses){
            int duration = course[0];
            int lastDay = course[1];
            
            if(curDay + duration > lastDay){    //大于截止日期
                if(pq.isEmpty()) continue;
                int longestDuration = pq.peek()[0];
                if(longestDuration > duration){ //替换到当前队列中持续日期最长的课程
                    curDay -= pq.poll()[0];
                    curDay += duration;
                    pq.offer(course);
                }
            }
            else{   //小于截止日期则加入选课
                curDay += duration;
                pq.offer(course);
            }
        }
        return pq.size();
    }
}

Posted 2022-06-24Updated 2022-06-23LeetCode / Hard4 minutes read (About 547 words)

1354. Construct Target Array With Multiple Sums

Question

You are given an array target of n integers. From a starting array arr consisting of n 1’s, you may perform the following procedure :

let x be the sum of all elements currently in your array.

choose index i, such that 0 <= i < n and set the value of arr at index i to x.

You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

Solution 1

递归，每次寻找到数组中最大的数字的下标maxIndex，并对整个数组加和。
当数组中出现小于1的数时，不成立，返回false。
当数组加和等于数组长度时，返回true。

记录剩余的数字others，如果没有剩余数字，则返回false。
将target[maxIndex]减去others，因此每次翻倍，快速逼近。
当小于0时，则还原到上一个target[maxIndex]。

递归更改后的数组。

Code

class Solution {
    public boolean isPossible(int[] target) {
        int maxIndex = 0, sum = 0;
        for(int i = 0; i < target.length; i++){
            if(target[i] <= 0) return false;    //数组中出现小于1的数，则不成立，返回false
            if(target[maxIndex] < target[i]) maxIndex = i;
            sum += target[i];
        }
        if(sum == target.length) return true;   //加和等于长度，则数组内全部为1，返回true
        int others = sum - target[maxIndex];
        if(others == 0) return false;   //没有其他值时返回false
        target[maxIndex] -= others;
        int n = 1;
        while(target[maxIndex] > others){
            target[maxIndex] -= n * others;
            if(target[maxIndex] <= 0){
                target[maxIndex] += n * others;
                break;
            }
            n*=2;   //因子每次翻倍，快速逼近
        }
        return isPossible(target);
    }
}

Solution 2

优先级队列，大根堆。
每次挤出队列里最大的数字max。

如果max的值为1，则返回true。

计算加和和新的值，并更新sum。
如果最大的数字max小于0，或者剩余的sum小于0，则返回false。

当max仍然大于剩下的数字时，继续做减法。采用因数翻倍，快速接近目标值。
如果max小于0，则恢复到上一个值，并添加到优先级队列中。

Code

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        for(int num : target){
            pq.offer(num);
            sum+=num;
        }
        while(true){
            int max = pq.poll();
            if(max == 1) return true;

            sum -= max;
            max = max - sum;
            if(sum <= 0 || max <= 0) return false;
            
            int n = 1;
            while(max > sum){
                max -= n * sum;
                if(max <= 0){
                    max += n * sum;
                    break;
                }
                n*=2;
            }
            sum += max;
            pq.offer(max);
        }
    }
}

Posted 2022-06-21Updated 2022-06-21LeetCode / Easya few seconds read (About 72 words)

1108. Defanging an IP Address

Question

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Solution

迭代每个字符，用StringBuffer类来组成新的字符串。

Code

class Solution {
    public String defangIPaddr(String address) {
        StringBuffer sb = new StringBuffer();
        for(char c : address.toCharArray()){
            if(c == '.'){
                sb.append("[.]");
            }
            else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Posted 2022-06-21Updated 2022-06-20LeetCode / Medium / 复习2 minutes read (About 341 words)

1642. Furthest Building You Can Reach

Question

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.

If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Solution

贪心算法+优先级队列。

从第二栋楼开始遍历当前位置，下一栋楼与当前位置的高度差为h。
如果h小于0，则无成本前进。
否则如果剩余砖块，则优先使用砖块，并将使用砖块的个数加入大根堆中。
如果剩余砖块不足，且有梯子剩余时，用梯子替换掉小号最多砖块的位置，增加剩余砖块的数量。
如果剩余砖块和梯子都不足，则返回上一个位置。

如果遍历到最后，则返回最后一个建筑物的位置。

Code

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 1; i < heights.length; i++){
            int h = heights[i] - heights[i-1];
            if(h > 0){
                pq.add(h);
                bricks-=h;
                if(bricks < 0){
                    if(ladders > 0){
                        ladders--;
                        bricks += pq.poll();
                    }
                    else{
                        return i-1;
                    }
                }
            }
        }
        return heights.length - 1;
    }
}

Posted 2022-06-20Updated 2022-06-20LeetCode / Medium4 minutes read (About 596 words)

820. Short Encoding of Words

Question

A valid encoding of an array of words is any reference string s and array of indices indices such that:

words.length == indices.length

The reference string s ends with the '#' character.

For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Solution 1

LeetCode这几天的每日一题时不让我学会字典树势不罢休啊……

字典树，参数isLeaf记录每个TireNode节点是否为叶子节点。
将单词倒序组建字典树，并维护isLeaf的属性。

计算从根节点到达每个叶子节点的长度再加一的和即可。

Code

class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean isLeaf;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        countLeaves(root, 0);
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.isLeaf = false;
                curr.next[index] = new TrieNode();
                curr.next[index].isLeaf = true;
            }
            curr = curr.next[index];
        }
    }
    
    private void countLeaves(TrieNode root, int length){
        if(root.isLeaf){
            count += length + 1;
        } 
        else{
            for(int i = 0; i < 26; i++){
                if(root.next[i] != null) countLeaves(root.next[i], length+1);
            }
        }
    }
}

Solution 2

排序，将数组words根据单词倒序排序。
倒序构成字典树，如果展开新的字典树分支（创建新的TrieNode节点）则将count加入根节点到新节点的距离。

Code

class Solution {
    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }
    TrieNode root;
    int count;
    
    public int minimumLengthEncoding(String[] words) {
        Arrays.sort(words, new Comparator<String>(){
            public int compare(String a, String b){
                int i = a.length()-1, j = b.length()-1;
                while(i >= 0 && j >= 0){
                    int index = a.charAt(i) - b.charAt(j);
                    if(index == 0){
                        i--;
                        j--;
                    }
                    else{
                        return index;
                    }
                }
                return j - i;
            }
        });
        
        count = 0;
        root = new TrieNode();
        
        for(String word : words){
            add(word);
        }
        
        return count;
    }
    
    private void add(String word){
        TrieNode curr = root;
        int length = 1;
        boolean newTrieNode = false;
        for(int i = word.length()-1; i >= 0; i--){
            int index = word.charAt(i) - 'a';
            if(curr.next[index] == null){
                curr.next[index] = new TrieNode();
                newTrieNode = true;
            }
            curr = curr.next[index];
            length++;
        }
        curr.end = true;
        if(newTrieNode) count += length;
    }
}

Solution 3

倒序重组字符串并记录到reversedWords[]数组，然后根据字典顺序排序。
如果数组的上一个字符串不是下一个字符串的前缀，则加入上一个字符串的长度加一。

Code

class Solution {    
    public int minimumLengthEncoding(String[] words) {
        String[] reversedWords = new String[words.length];
        int count = 0, index = 0;
        for(String word : words){
            reversedWords[index] = new StringBuffer(word).reverse().toString();
            index++;
        }
        
        Arrays.sort(reversedWords);
        for(int i = 0; i < words.length-1; i++){
            if(!reversedWords[i+1].startsWith(reversedWords[i])) count += reversedWords[i].length()+1;
        }
        count += reversedWords[words.length-1].length()+1;
        return count;
    }
}

Posted 2022-06-19Updated 2022-06-18LeetCode / Medium / 复习2 minutes read (About 366 words)

1268. Search Suggestions System

Question

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Solution

字典树+优先级队列。
在TrieNode节点中保存PriorityQueue，以记录该节点下的三个单词。
注意PriorityQueue中的String需要按倒序排列，以保证维护时可以直接poll掉字符顺序较后的单词。

add()方法

创建并添加TrieNode节点，同时在移动当前节点位置时，需要维护PriorityQueue，当长度大于3时，则挤出字典顺序排列较后的单词。

search()方法

在查找前缀时，将每个TrieNode节点上的PriorityQueue倒序加入List。

Code

class Solution {
    class TrieNode{
        boolean end;
        TrieNode[] children = new TrieNode[26];
        PriorityQueue<String> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
    }
    
    TrieNode root;
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ret = new ArrayList<>();
        root = new TrieNode();
        for(String word : products){
            add(word);
        }
        return search(searchWord);
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            curr.q.add(word);
            if(curr.q.size() > 3) curr.q.poll();
        }
        curr.end = true;
    }
    
    private List<List<String>> search(String prefix){
        List<List<String>> ret = new ArrayList<>();
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            List<String> temp = new ArrayList<>();
            while(!curr.q.isEmpty()){
                temp.add(curr.q.poll());
            }
            Collections.reverse(temp);
            ret.add(temp);
        }
        return ret;
    }
}

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

745. Prefix and Suffix Search

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};
    }
}

Posted 2022-06-15Updated 2022-06-14LeetCode / Medium3 minutes read (About 477 words)

1048. Longest String Chain

Question

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain* *is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return *the length of the longest possible word chain with words chosen from the given list of *words.

Solution

排序+动态规划。
采用一个一维动态规划数组记录到某个word的最大字符串链长度。

排序

每个predecessor必定比next少1，因此首先将数组根据word的长度排序。

动态规划

数组dp[i]记录到i位置时的最大长度。
双重遍历i和j，其中j>i。如果words[i-1]是words[j-1]的predecessor，则更新dp[j]为dp[j]与dp[i]+1的较大值。

辅助方法 isValid()

判断predecessor是否有效。
初始化一个flag为false记录不同字符是否已出现。
如果两者长度差不为1直接返回false。
双指针分别指向两个字符串，如果两个当前字符相等，则两个指针共同前进。
如果不相等且flag为true则i指针前进，并且将flag改为false。否则返回false。
如果循环结束返回true。

Code

class Solution {
    public int longestStrChain(String[] words) {
        int max = 0;
        Arrays.sort(words, (a,b) -> a.length() - b.length());
        int[] dp = new int[words.length+1];
        for(int i = 1; i <= words.length; i++){
            for(int j = i + 1; j <= words.length; j++){
                if(isValid(words[i-1], words[j-1])){
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    max = Math.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private boolean isValid(String predecessor, String next){
        if(predecessor.length() + 1 != next.length()) return false;
        boolean flag = true;
        int i = 0, j = 0;
        while(i < next.length() && j < predecessor.length()){
            if(next.charAt(i) == predecessor.charAt(j)){
                i++;
                j++;
            }
            else if(flag){
                i++;
                flag = false;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Posted 2022-06-12Updated 2022-06-12LeetCode / Mediuma minute read (About 217 words)

1695. Maximum Erasure Value

Question

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Solution

滑动窗口+数组统计。

用sum记录窗口内的和，max记录和的最大值。
当新滑入的右侧指针不为0时，从左侧滑出元素并将滑出的元素改为0。
然后将右侧指针指针对应的数组统计改为1并更新当前的和max。

Code

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int[] bin = new int[10001];
        int left = 0, max = 0, sum = 0;
        
        for(int right = 0; right < nums.length; right++){
            sum += nums[right];
            while(bin[nums[right]] != 0){
                bin[nums[left]] = 0;
                sum -= nums[left];
                left++;
            }
            bin[nums[right]] = 1;
            max = Math.max(max, sum);
        }
        return max;
    }
}

Posted 2022-06-11Updated 2022-06-10LeetCode / Medium / 复习2 minutes read (About 367 words)

1658. Minimum Operations to Reduce X to Zero

Question

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return *the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return *-1.

Solution

将原有问题的从两边减去一定的值，寻找加和为x的问题转换为寻找滑动窗口中的总和为total - x的新问题。

滑动窗口

初始化当前窗口内的sum，左侧指针left与右侧指针right。
每次将一个新的元素nums[right]加入窗口范围。

当当前的sum大于寻找的target，则将nums[left]滑出窗口，更新left与sum的值。

如果当前窗口内的sum等于寻找的target，则更新记录最小操作次数的min。

Code

class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0, min = Integer.MAX_VALUE;
        for(int num : nums){
            total += num;
        }
        int target = total - x; //将减去两侧元素并寻找和为x的结果的问题转换为用滑动窗口寻找total - x的结果。
        int sum = 0, left = 0, right = 0;
        while(right < nums.length){
            sum += nums[right]; //调整右侧范围，加入新元素到窗口
            right++;
            
            while(left < right && sum > target){ //如果窗口内的和大于目标，则调整左侧范围
                sum -= nums[left];
                left++;
            }
            if(sum == target){   //如果窗口内的和等于目标，则更新最小操作次数
                min = Math.min(min, nums.length - (right - left));
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

Posted 2022-06-09Updated 2022-06-10LeetCode / Easy2 minutes read (About 246 words)

1332. Remove Palindromic Subsequences

Question

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Solution

当字符为空时，返回0。
注意本题中的子序列不需要连续。
由于只有’a’与’b’两个字符，因此最多两步即可将字符串清空。

辅助方法判断字符串是否为回文字符串。
如果为真则返回1，只需要删除一次。

如果为假则返回2，需要先删除所有的’a’，再删除所有的’b’。

Code

class Solution {
    public int removePalindromeSub(String s) {
        if(s.length() == 0) return 0;
        return isPalindrome(s) ? 1 : 2;
    }
    
    private boolean isPalindrome(String s){
        int i = 0, j = s.length() - 1;
        while(j > i){
            if(s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

Posted 2022-06-05Updated 2022-06-05LeetCode / Harda minute read (About 188 words)

52. N-Queens II

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Solution

和昨天的题目51. N-Queens一样。
只是不需要转换并记录字符串了，递归结束时直接将res+1即可。

Code

class Solution {
    int target;
    int res;
    int[][] operations;
    public int totalNQueens(int n) {
        target = n;
        res = 0;
        operations = new int[][]{{-1,0},{-1,1},{-1,-1}};
        backtracking(new int[n][n], 0, 0);
        return res;
    }
    
    private void backtracking(int[][] board, int i, int n){
        if(n == target){
            res++;
            return;
        }
        for(int j = 0; j < target; j++){
            if(isValid(board, i, j)){
                board[i][j] = 1;
                backtracking(board, i+1, n+1);
                board[i][j] = 0;
            }
        }
    }
    
    private boolean isValid(int[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0], q = j + operation[1];
            while(p >= 0 && p < target && q >= 0 && q < target){
                if(board[p][q] == 1) return false;
                p += operation[0];
                q += operation[1];                
            }
        }
        return true;
    }
}

Posted 2022-06-04Updated 2022-06-05LeetCode / Hard / 复习5 minutes read (About 749 words)

51. N-Queens

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Solution

话说今天出这道题真的不是搞事情嘛？

八皇后问题，回溯+剪枝。按顺序搜索可以减少情况的重复计算。
由于棋盘的大小为n * n，要放n个皇后，因此每一行（列）上都有且只有一位皇后。
我们可以依顺序逐行回溯，对逐行的每一列进行回溯。
由于每一行的可选位置都减少1，因此时间复杂度为O(N!)。

回溯

通过一个char数组board[][]记录棋子状态。将board[][]初始化为’.’。
遍历这一行的所有列，如果该位置有效，则board[i][j]改为’Q’，将这个点设置为有棋子，并递归下一行。
回溯，将board[i][j]重新设置为’.’。

当递归次数达到n时，将char[]数组转换为字符串加入答案。

辅助方法 isValid

检测该位置是否有效。即该位置的路径上是否已经有棋子，或该位置已经有棋子。
由于我们的回溯方法是逐行确定棋子位置，因此不需要查看全部八个方向，而是查看之前已经遍历过的行即可。

Code

class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{-1,-1},{-1,1},{-1,0}};
        char[][] board = new char[n][n];
        for(char[] s : board){
            Arrays.fill(s,'.');
        }
        backtracking(board,0,0);
        return ret;
    }
    
    private void backtracking(char[][] board, int n, int i){
        if(n == size){
            List<String> ans = new ArrayList<>();
            for(char[] s : board) ans.add(new String(s));
            ret.add(ans);
            return;
        }

        for(int j = 0; j < size; j++){
            if(isValid(board, i, j)){
                board[i][j] = 'Q';
                backtracking(board, n+1, i+1);
                board[i][j] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0];
            int q = j + operation[1];
            while(p >= 0 && p < size && q >= 0 && q < size){
                if(board[p][q] == 'Q') return false;
                p += operation[0];
                q += operation[1];
            }
        }
        return true;
    }
}

Solution 2

简单回溯。
在回溯时搜索二维位置，因此增加了时间复杂度，正常是过不了的。
通过按顺序进行搜索（只搜索当前行之后的位置）进行剪枝。

Code

class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    HashSet<String> set;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{1,1},{1,-1},{1,0},{0,1},{0,-1}};
        backtracking(new int[n][n],0,0);
        return ret;
    }
    
    private void backtracking(int[][] border, int n, int start){
        if(n == size){
            //print(border);
            List<String> ans = new ArrayList<>();
            for(int i = 0; i < size; i++){
                StringBuffer sb = new StringBuffer();
                for(int j = 0; j < size; j++){
                    if(border[i][j] == 1){
                        sb.append("Q");
                    }
                    else{
                        sb.append(".");
                    }
                }
                ans.add(sb.toString());
            }
            ret.add(ans);
            return;
        }
        
        for(int i = start; i < size; i++){
            for(int j = 0; j < size; j++){
                if(border[i][j] == 0){
                    border[i][j] = 1;
                    List<int[]> temp = new ArrayList<>();
                    for(int[] operation : operations){
                        int p = i, q = j;
                        while(p >= 0 && p < size && q >= 0 && q < size){
                            if(border[p][q] == 0){
                                border[p][q] = 2;
                                temp.add(new int[]{p,q});
                            }
                            p += operation[0];
                            q += operation[1];
                        }
                    }
                    backtracking(border, n+1, i+1);
                    for(int[] t : temp){
                        border[t[0]][t[1]] = 0;
                    }
                    border[i][j] = 0;
                }
            }
        }
    }
}

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Question

Solution

add()方法

search()方法

Code

Question

Solution

TrieNode

初始化

搜索

Code

Question

Solution 1

Code

Solution 2

递归方法 minCam()

树形dp优化剪枝

Code

Code

Question

Solution

排序

动态规划

辅助方法 isValid()

Code

Question

Solution

Code

Question

Solution

滑动窗口

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

回溯

辅助方法 isValid

Code

Solution 2

Code

Recents

Archives

Links