Category: Medium

Posted 2022-07-05Updated 2022-07-04LeetCode / Medium / 复习2 minutes read (About 306 words)

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}

Posted 2022-07-02Updated 2022-07-01LeetCode / Medium2 minutes read (About 264 words)

1465. Max Area After Horizontal and Vertical Cuts

Question

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and

verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.

Solution

先排序，记录两次切割之间的距离的最大值。
最后同样需要比较蛋糕的总尺寸和最后一次切割的距离。

返回宽度和长度的最大值的乘积即可。

注意：两个int整数相乘会溢出，max需要记录为long类型。

Code

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int MOD = (int) Math.pow(10,9)+7;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = 0, maxV = 0;
        int lastH = 0, lastV = 0;
        
        for(int i = 0; i < horizontalCuts.length; i++){
            maxH = Math.max(maxH, horizontalCuts[i] - lastH);
            lastH = horizontalCuts[i];
        }
        
        maxH = Math.max(maxH, h - lastH);
        
        for(int i = 0; i < verticalCuts.length; i++){
            maxV = Math.max(maxV, verticalCuts[i] - lastV);
            lastV = verticalCuts[i];
        }
        
        maxV = Math.max(maxV, w - lastV);
        return (int) (maxV * maxH % MOD) ;
    }
}

Posted 2022-06-28Updated 2022-07-01LeetCode / Medium2 minutes read (About 227 words)

1647. Make Character Frequencies Unique

Question

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return* the minimum number of characters you need to delete to make s good.*

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Solution

数组统计+哈希表
用数组统计记录每个字符出现的数量。
count记录需要减少的字符数量。

遍历统计数组，如果哈希表中已经记录，则将数组统计减少，直到归零。
每减少一次则为count加一。
如果哈希表中未记录，则将当前数字添加到哈希表中。

Code

class Solution {
    public int minDeletions(String s) {
        int count = 0;
        HashSet<Integer> set = new HashSet<>();
        int[] bin = new int[26];
        for(char c : s.toCharArray()){
            bin[c - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            while(bin[i] !=0 && set.contains(bin[i])){
                bin[i]--;
                count++;
            }
            set.add(bin[i]);
        }
        return count;
    }
}

Posted 2022-06-27Updated 2022-06-27LeetCode / Mediuma few seconds read (About 100 words)

1689. Partitioning Into Deci-Binary Numbers

Question

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Solution

遍历所有字符，返回字符串中的最大整数。

Code

class Solution {
    public int minPartitions(String n) {
        char max = '0';
        for(char s : n.toCharArray()){
            if(s > max) max = s;
        }
        return max - '0';
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Medium2 minutes read (About 305 words)

2320. Count Number of Ways to Place Houses

Question

There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 109 + 7.

Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.

Solution

计算单侧河道可以放置的种类。
一开始用的是DFS搜素来计算可以放置的种类。
计算后发现是以（2，3）开始的斐波那契数列。

因此直接计算n位置的斐波那契数列值即可。
然后两边可以匹配的种类就是其平方。

记忆化搜索

在计算斐波那契数列时，由于要多次重复计算前面的位置，因此可以采用记忆化搜索记录对应的斐波那契额值。

Code

class Solution {
    long[] memo;
    public int countHousePlacements(int n) {
        memo = new long[n+1];
        long res = fibo(n);
        res *= res;
        res %= 1000000007;
        return (int) res;
    }
    
    private long fibo(int n){
        if(n == 1) return 2;
        else if(n == 2) return 3;
        if(memo[n] != 0) return memo[n];
        memo[n] = fibo(n-1) % 1000000007 + fibo(n-2) % 1000000007;

        return memo[n];
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Medium3 minutes read (About 390 words)

1423. Maximum Points You Can Obtain from Cards

Question

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Solution 1

这种取两端的问题可以转化为取中间连续k个元素之和最小。

计算所有数字的和sum。
然后用维护一个宽度为k的窗口内的加和temp，并记录其最小值min。

返回sum - min，结果即是取两侧时可以取的最大值。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, sum = 0;
        for(int point : cardPoints) sum += point; //求所有数值的和
        if(k == n) return sum;
        int left = 0, right = n-k, temp = 0, min = 0;
        
        for(int i = 0; i < n-k; i++){
            temp += cardPoints[i];
            min = temp;
        }
        while(right < n){   //维护窗口内的temp，并更新min
            temp += cardPoints[right] - cardPoints[left];; 
            min = Math.min(min, temp);
            right++;
            left++;
        }
        return sum - min;
    }
}

Solution 2

分别计算从两侧开始的加和并记录在两个数组left[]和right[]上。

然后分别取两个指针，左侧指针l从0开始遍历到k，右侧指针对应的位置为l+n-k。计算并更新最大值max。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, max = 0;
        int[] left = new int[n+1], right = new int[n+1];
        
        for(int i = 0; i < n; i++){
            left[i+1] = left[i] + cardPoints[i];
            right[n-i-1] = right[n-i] + cardPoints[n-i-1];
        }
        
        for(int l = 0; l <= k; l++){
            max = Math.max(max, left[l] + right[n-k+l]);
        }
        
        return max;
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Medium / 复习3 minutes read (About 400 words)

2317. Maximum XOR After Operations

Question

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

Solution

异或运算相当于不进位的加和。
和运算相当于掩码操作。
或运算相当于保留该位上的1。

由于我们要对所有数字进行异或运算，因此只要能改变某一位对应的数字，我们就可以确保这一位在进行异或运算时结果可以为1。（当不改变时改为的异或运算结果为0，则我们只需要改变改为即可得到1）

将所有我们可以操作的位置变为1，就可以得到最大值。

因此，我们只需要确定哪些位是我们可以操作的即可：

nums[i]与任意正整数进行异或运算可以得到任意整数。在这个条件下我们可以得到任意的32位整数。
然而和运算相当于掩码操作，如果nums[i]对应二进制的某一位上位0，则我们无法通过和运算将这一位改变为1。

只要该位出现过1，则我们可以控制这个位。因此我们可以通过或运算所有数字，保留所有可控制的位。

Code

class Solution {
    public int maximumXOR(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum |= num;
        }
        return sum;
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Medium / 复习3 minutes read (About 419 words)

2316. Count Unreachable Pairs of Nodes

Question

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

Solution

并查集，将所有元素union，然后计算每个元素所在集之外的元素和相加即可。
注意由于是无向图，因此计算加和时每两个点之间都计算了两次，因此需要将结果除以2。

路径压缩

在进行find()查找时，将经过的每一个节点设置为根节点。
这样做可以有效的降低树高，减少操作次数。
采用递归的形式实现。

按秩合并

用size[]数组记录当前位置的节点数量。
在合并两个数字时，将秩较小的数字指向秩较大的数字。
并更新根节点的size[]值。

Code

class Solution {
    public long countPairs(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        long res = 0;
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        
        for(int i = 0; i < n; i++){
            res +=  ( n - uf.getSize(i) );
        }
        return res/2;   //无向图，因此每两个节点计算了两次
    }
    
    class UnionFind {
        int[] parent;
        int[] size;

        public UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        } 
           
        private int find(int id){
            return parent[id] == id ? id : find(parent[id]);   //路径压缩，将路径上的所有节点归结到根节点上
        }
           
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(size[p1] > size[p2]){    //按秩进行压缩
                parent[p2] = p1;
                size[p1] += size[p2];
            }
            else{
                parent[p1] = p2;
                size[p2] += size[p1];
            }
            return true;
        }

        public int getSize(int num){
            return size[find(num)];
        }
    }
}****

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

665. Non-decreasing Array

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-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-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-12Updated 2022-06-11LeetCode / Medium / 复习4 minutes read (About 574 words)

2300. Successful Pairs of Spells and Potions

Question

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Solution 1

排序+二分搜索。同时记录success与spells[i]的比值来减小计算量。

排序

首先对potions[]进行排序，这样可以使用二分搜索查找分界值。
数组scales[]记录success与spells[i]的比值，以此为界大于等于scales[i]的位置都可以计入ret[]数组。

二分搜索

这里有一些tricky。

由于Arrays.binarySearch()方法无法返回重复的数字，因此在搜索时我们将查找值scale减去一个小值，保证在搜索时一定返回负值。（查找值的插入位置的负数-1）
将ret[i]记录为potions[]的总数减去正确的插入位置即可。

Code

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        
        Arrays.sort(potions);
        double[] scales = new double[potions.length];
        
        for(int i = 0; i < potions.length; i++){
            scales[i] = (double) potions[i];
        }
        
        for(int i = 0; i < spells.length; i++){
            double scale = (double) success / spells[i] - 0.000001;   //确保浮点数不在scale中出现，binarySearch方法返回的结果必定为上一个插入位置
            int index = Arrays.binarySearch(scales, scale);
            ret[i] = potions.length + (index + 1);
        }
        return ret;
    }
}

Solution 2

由于Arrays.binarySearch()无法正确的搜索有重复元素的数组，因此采用辅助方法binarySearch()来搜索最左侧的下标。

直接在binarySearch()方法中查找target，比较的对象为spell和potions[i]的乘积。

为了搜寻重复的第一个元素，当遇到target时不直接返回，而是继续修改right的位置，直到left等于right。

如果未搜索到，则返回数组的总长度。

Code

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ret = new int[spells.length];
        Arrays.sort(potions);
        for(int i = 0; i < spells.length; i++){
            int index = binarySearch(potions, spells[i], success);
            ret[i] = potions.length - index;
        }
        return ret;
    }
    
    private int binarySearch(int[] potions, long spell, long target){
        int left = 0, right = potions.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(potions[mid] * spell < target) left = mid + 1;
            else right = mid;
        }
        return potions[left] * spell < target ? potions.length : left;
    }
}

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

记忆化搜索

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

路径压缩

按秩合并

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Question

Solution

add()方法

search()方法

Code

Question

Solution

排序

动态规划

辅助方法 isValid()

Code

Question

Solution

Code

Question

Solution 1

排序

二分搜索

Code

Solution 2

Code

Recents

Archives

Links