Solution to 293 problems in the week of Li Kou

The first question is

Link to the original topic ：

2273. Result array after removing letter ectopic words

Single question solution ：

Power button 2273. Result array after removing letter ectopic words

subject ：

I'll give you a subscript from 0 Starting string words , among words[i] Composed of lowercase English characters .

In one step , Any subscript needs to be selected i , from words in Delete words[i] . Subscript i The following two conditions need to be met at the same time ：

1. 0 < i < words.length
2. words[i - 1] and words[i] yes Letter heterotopic word .

As long as you can choose a subscript that meets the conditions , Just keep doing this .

After performing all operations , return words . Can prove that , Selecting subscripts for each operation in any order will get the same result .

Letter heterotopic word Is a new word obtained by rearranging the letters of the source word , Letters in all source words are usually used just once . for example ,"dacb" yes "abdc" A letter heterotopic word of .

Example 1：

 Input ：words = ["abba","baba","bbaa","cd","cd"]    
 Output ：["abba","cd"]    
 explain ：    
 One way to get the result array is to perform the following steps ：  -  because  words[2] = "bbaa"  and  words[1] = "baba"  It's a letter variant word , Select subscript  2  And delete  words[2] .    
   Now?  words = ["abba","baba","cd","cd"] .  -  because  words[1] = "baba"  and  words[0] = "abba"  It's a letter variant word , Select subscript  1  And delete  words[1] .    
   Now?  words = ["abba","cd","cd"] .  -  because  words[2] = "cd"  and  words[1] = "cd"  It's a letter variant word , Select subscript  2  And delete  words[2] .    
   Now?  words = ["abba","cd"] .   No more operations can be performed , therefore  ["abba","cd"]  Is the final answer .

Example 2：

 Input ：words = ["a","b","c","d","e"]    
 Output ：["a","b","c","d","e"]    
 explain ：    
words  There are no two adjacent strings that are mutually alphabetic ectopic words , So there's no need to do anything .

Tips ：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• words[i] It's made up of lowercase letters

Related Topics

• Array
• Hashtable
• character string
• Sort

Ideas ：

Traversal string array , Replace each string with a character array , Character array sort , If the string converted after sorting is the same , It means that it is a letter ectopic word

Code ：

java：

class Solution {
    
    public List<String> removeAnagrams(String[] words) {
    
        char[] strs = words[0].toCharArray();
        Arrays.sort(strs);
        List<String> list = new ArrayList<>();
        int index = 0;
        for (int i = 1; i < words.length; i++) {
    
            char[] strs1 = words[i].toCharArray();
            Arrays.sort(strs1);
            if (!String.valueOf(strs).equals(String.valueOf(strs1))) {
    
                list.add(words[index]);
                strs = strs1;
                index = i;
            }
        }
        list.add(words[index]);
        return list;
    }
}

The second question is

Link to the original topic ：

2274. Maximum number of consecutive floors excluding special floors

Single question solution ：

Power button 2274. Maximum number of consecutive floors excluding special floors

subject ：

Alice Managing a company , And rent some floors of the building as office space .Alice Decided to use some floors as Special floor , For relaxation only .

Here are two integers bottom and top , Express Alice Rented from bottom To top（ contain bottom and top , ） All floors of the . Give you another integer array special , among special[i] Express Alice Specify a special floor for relaxation .

Returns the... Without special floors Maximum Number of consecutive floors .

Example 1：

  
 Input ：bottom = 2, top = 9, special = [4,6]  
 Output ：3  
 explain ： The following lists the continuous floor range without special floors ：  
- (2, 3) , The number of floors is  2 .  
- (5, 5) , The number of floors is  1 .  
- (7, 9) , The number of floors is  3 .  
 therefore , Returns the maximum number of consecutive floors  3 .  

Example 2：

  
 Input ：bottom = 6, top = 8, special = [7,6,8]  
 Output ：0  
 explain ： Each floor is planned as a special floor , So back  0 .  

Tips

• 1 <= special.length <= 105
• 1 <= bottom <= special[i] <= top <= 109
• special All the values in Different from each other

Related Topics

• Array
• Sort

Ideas ：

This is equivalent to bottom To top Within the scope of , By special The number of is divided , We need to find the longest segment after segmentation

step ：

1. In order to ensure the order of data , Yes special Sort
2. Traverse special Yes bottom~top Segmentation , When bottom<=special[i] when ,
   The number of consecutive floors is special[i]-bottom, Compared with the previous maximum number of continuous layers , Get the current maximum number of consecutive layers ,
   Simultaneous updating bottom = special[i] + 1
3. End of traversal , And the number of successive layers in the last paragraph top - special[special.length - 1]
4. thus , The maximum number of consecutive layers without special layers comes out

Code ：

java：

class Solution {
    
    public int maxConsecutive(int bottom, int top, int[] special) {
    
        Arrays.sort(special);
        int max = 0;
        for (int j : special) {
    
            if (bottom <= j) {
    
                max = Math.max(max, j - bottom);
                bottom = j + 1;
            }
        }
        max = Math.max(max, top - special[special.length - 1]);
        return max;
    }
}

Third question

Link to the original topic ：

2275. The longest combination of bitwise and result greater than zero

Single question solution ：

Power button 2275. The longest combination of bitwise and result greater than zero

subject ：

An array nums perform Bitwise AND Equivalent to an array nums All integers in execute Bitwise AND .

• for example , Yes nums = [1, 5, 3] Come on , Bitwise and equal to 1 & 5 & 3 = 1 .
• Again , Yes nums = [7] for , Bitwise and equal to 7 .

Here's an array of positive integers candidates . Calculation candidates Under each combination of numbers in Bitwise AND Result . candidates Each number in can only be used in each combination once .

Returns a bitwise and result greater than 0 Of The longest The length of the combination .

Example 1：

  
 Input ：candidates = [16,17,71,62,12,24,14]  
 Output ：4  
 explain ： Combine  [16,17,62,24]  The bitwise and result is  16 & 17 & 62 & 24 = 16 > 0 .  
 The combination length is  4 .  
 It can be proved that there is no bitwise and the result is greater than  0  And the length is greater than  4  The combination of .  
 Be careful , There may be more than one combination with the largest length .  
 for example , Combine  [62,12,24,14]  The bitwise and result is  62 & 12 & 24 & 14 = 8 > 0 .  

Example 2：

  
 Input ：candidates = [8,8]  
 Output ：2  
 explain ： The longest combination is  [8,8] , Bitwise and result  8 & 8 = 8 > 0 .  
 The combination length is  2 , So back  2 .  

Tips ：

• 1 <= candidates.length <= 105
• 1 <= candidates[i] <= 107

Related Topics

• An operation
• Array
• Hashtable
• Count

Ideas ：

This question needs to find out that the position and result are greater than 0 The length of the longest combination of , Bitwise and result greater than 0,
It shows that every binary number in this array has the same bit, which is 1, According to the range of array values given by this question ,
It can be determined that there are at most 24 position , Then we can cycle 24 Frequency group , Each cycle counts the number of i The number of bits is 1 The number of ,
Then compare the number of each time , Get the length of the longest combination

Code ：

java：

class Solution {
    
    public int largestCombination(int[] candidates) {
    
        int max = 0;
        for (int i = 0; i < 25; i++) {
    
            int cnt = 0;
            for (int j = 0; j < candidates.length; j++) {
    
                if ((candidates[j] & (1 << i)) > 0) {
    
                    cnt++;
                }
            }
            max = Math.max(max, cnt);
        }
        return max;
    }
}

Fourth question

Link to the original topic ：

2276. The number of integers in the statistical interval

Single question solution ：

Power button 2276. The number of integers in the statistical interval

subject ：

Here you are empty Set , Please design and implement the data structure that meets the requirements ：

• newly added ： Add an interval to this interval set .
• Statistics ： The calculation appears in At least one The number of integers in the interval .

Realization CountIntervals class ：

• CountIntervals() Initialize the object with an empty set of intervals
• void add(int left, int right) Add interval [left, right] Into the interval set .
• int count() The return appears in At least one The number of integers in the interval .

Be careful ： Section [left, right] Express satisfaction left <= x <= right All integers of x .

Example 1：

  
 Input   
["CountIntervals", "add", "add", "count", "add", "count"]  
[[], [2, 3], [7, 10], [], [5, 8], []]  
 Output   
[null, null, null, 6, null, 8]  

 explain   
CountIntervals countIntervals = new CountIntervals(); //  Initialize the object with an empty interval set   
countIntervals.add(2, 3);  //  take  [2, 3]  Add to interval set   
countIntervals.add(7, 10); //  take  [7, 10]  Add to interval set   
countIntervals.count();    //  return  6  
                           //  Integers  2  and  3  Appear in interval  [2, 3]  in   
                           //  Integers  7、8、9、10  Appear in interval  [7, 10]  in   
countIntervals.add(5, 8);  //  take  [5, 8]  Add to interval set   
countIntervals.count();    //  return  8  
                           //  Integers  2  and  3  Appear in interval  [2, 3]  in   
                           //  Integers  5  and  6  Appear in interval  [5, 8]  in   
                           //  Integers  7  and  8  Appear in interval  [5, 8]  And interval  [7, 10]  in   
                           //  Integers  9  and  10  Appear in interval  [7, 10]  in 

Tips ：

• 1 <= left <= right <= 109
• Call at most add and count Method A total of 105 Time
• call count Method at least once

Ideas ：

This time, I added and sorted out my thoughts , utilize java Of TreeSet structure , Can quickly locate data .
Typical template questions

Code ：

java：

class CountIntervals {
    
    TreeSet<Interval> ranges;
    int cnt;
    public CountIntervals() {
    
        ranges = new TreeSet();
        cnt = 0;
    }
    public void add(int left, int right) {
    
        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();
        while (itr.hasNext()) {
    
            Interval iv = itr.next();
            if (right < iv.left) {
    
                break;
            }
            left = Math.min(left, iv.left);
            right = Math.max(right, iv.right);
            cnt -= iv.right - iv.left + 1;
            itr.remove();
        }
        ranges.add(new Interval(left, right));
        cnt += right - left + 1;
    }
    public int count() {
    
        return cnt;
    }
}
public class Interval implements Comparable<Interval> {
    
    int left;
    int right;
    public Interval(int left, int right) {
    
        this.left = left;
        this.right = right;
    }
    public int compareTo(Interval that) {
    
        if (this.right == that.right) return this.left - that.left;
        return this.right - that.right;
    }
}