当前位置：网站首页>Yyds dry goods inventory leetcode question set 911 - 920

Yyds dry goods inventory leetcode question set 911 - 920

2022-06-12 17:16:00 【Brother daze who loves learning】

LeetCode Exercise set
Some questions may be skipped directly , Brush before tidying up leetcode

911. Online elections

Here are two arrays of integers persons and times . In the election , The first i The ticket is for times[i] Vote for the candidate persons[i] Of .

For what happened at the moment t For each query , Need to find out where t The number of the candidate who is always ahead in the election .

stay t The votes cast at any time will also be included in our query . In the case of a draw , The candidate who has recently won the vote will win .

Realization TopVotedCandidate class ：

TopVotedCandidate(int[] persons, int[] times) Use persons and times Array initialization object .
int q(int t) According to the rules described above , Return at time t The number of the leading candidate in the election .

Example ：

 Input ：
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
 Output ：
[null, 0, 1, 1, 0, 0, 1]

 explain ：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); //  return  0 , At the moment  3 , The distribution of votes is  [0] , The number is  0  Your candidate is ahead .
topVotedCandidate.q(12); //  return  1 , At the moment  12 , The distribution of votes is  [0,1,1] , The number is  1  Your candidate is ahead .
topVotedCandidate.q(25); //  return  1 , At the moment  25 , The distribution of votes is  [0,1,1,0,0,1] , The number is  1  Your candidate is ahead .（ In the case of a draw ,1  Is the candidate who recently won the vote ）.
topVotedCandidate.q(15); //  return  0
topVotedCandidate.q(24); //  return  0
topVotedCandidate.q(8); //  return  1

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.
      12.
      13.
      14.

Tips ：

1 <= persons.length <= 5000
times.length == persons.length
0 <= persons[i] < persons.length
0 <= times[i] <= 109
times Is a strictly increasing ordered array
times[0] <= t <= 109
Each test case calls at most 104 Time q

PS:
     Custom structure Vote, People and time 
    A Is to add the current person and time to the subscript of the number of votes 
     And then when you check ,
     Bisection traverses each point , The time of the first person to see the current points is t
     Then find the current points , Time is t People who 

     
      1.
      2.
      3.
      4.
      5.
      6.

class TopVotedCandidate {
    List<List<Vote>> A;
    public TopVotedCandidate(int[] persons, int[] times) {
        A = new ArrayList();
        Map<Integer, Integer> count = new HashMap();
        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i], t = times[i];
            int c = count.getOrDefault(p, 0) + 1;

            count.put(p, c);
            while (A.size() <= c)
                A.add(new ArrayList<Vote>());
            A.get(c).add(new Vote(p, t));
        }
    }

    public int q(int t) {
        // Compare the corresponding points first 
        int lo = 1, hi = A.size();
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A.get(mi).get(0).time <= t)
                lo = mi + 1;
            else
                hi = mi;
        }
        int i = lo - 1;

        
        lo = 0; hi = A.get(i).size();
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A.get(i).get(mi).time <= t)
                lo = mi + 1;
            else
                hi = mi;
        }
        int j = Math.max(lo-1, 0);
        return A.get(i).get(j).person;
    }
}

class Vote {
    int person, time;
    Vote(int p, int t) {
        person = p;
        time = t;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.

912. Sort array

Give you an array of integers nums, Please arrange the array in ascending order .

Example 1：

Example 2：

Tips ：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

PS:
     If the direct violence sorting will time out ,n^2 yes  2.5*10^9
     Here we use the counting sort 
     Use numeric values as subscripts 
     In order to be more efficient , Directly use the difference between the maximum and minimum as the subscript , Subtract... When saving min, Add... When you get it min

     
      1.
      2.
      3.
      4.
      5.

class Solution {
     public int[] sortArray(int[] nums) {
        int max = -50001, min = 50001;
        for (int num: nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }


        int[] counter = new int[max - min + 1];
        for (int num: nums) {
            counter[num - min]++;
        }

        int idx = 0;
        for (int num = min; num <= max; num++) {
            int cnt = counter[num - min];
            while (cnt-- > 0) {
                nums[idx++] = num;
            }
        }
        return nums;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

913. Tom and Jerry

The two players play cat and mouse respectively , In one Undirected Play on the map , They take turns .

The form of the graph is ：graph[a] It's a list , Satisfied by ab Is all the nodes of an edge in the graph b form .

Mouse from node 1 Start , Be the first to set out ; Cat slave node 2 Start , The second one set out . At the node 0 There is a hole in the .

In every player's action , they must Move along an edge in the graph connected to the current position . for example , If the mouse is at the node 1 , Then it must move to graph[1] Any node in .

Besides , The cat can't move into the hole （ node 0）.

then , The game ends in one of the following three situations ：

If the cat and mouse appear at the same node , Cat wins .
If the mouse reaches the hole , The mouse wins .
If a position repeats （ namely , The player's position and movement order are the same as the last action ）, Game draw .

Here's a picture graph , And assume that both players participate in the game at their best ：

If the mouse wins , Then return to 1;
If the cat wins , Then return to 2;
If there is a draw , Then return to 0 .

Example 1：

#yyds Dry inventory # LeetCode Brush question set 911 - 920_ Array

Example 2：

#yyds Dry inventory # LeetCode Brush question set 911 - 920_ Array initialization _02

Tips ：

3 <= graph.length <= 50
1 <= graph[i].length < graph.length
0 <= graph[i][j] < graph.length
graph[i][j] != i
graph[i] Different from each other
The cat and mouse always move in the game

class Solution {
    static final int MOUSE_WIN = 1;
    static final int CAT_WIN = 2;
    static final int DRAW = 0;
    int n;
    int[][] graph;
    int[][][] dp;
        // initialization , Assign values to each position -1
    public int catMouseGame(int[][] graph) {
        this.n = graph.length;
        this.graph = graph;
        this.dp = new int[n][n][n * 2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return getResult(1, 2, 0);
    }
    // The end condition , If mouse Just go mouse win , If a cat meets a mouse , Direct cat wins 
    // Keep running the rest of the time , One by one, one by one 
    public int getResult(int mouse, int cat, int turns) {
        if (turns == n * 2) {
            return DRAW;
        }
        if (dp[mouse][cat][turns] < 0) {
            if (mouse == 0) {
                dp[mouse][cat][turns] = MOUSE_WIN;
            } else if (cat == mouse) {
                dp[mouse][cat][turns] = CAT_WIN;
            } else {
                getNextResult(mouse, cat, turns);
            }
        }
        return dp[mouse][cat][turns];
    }
    // Deep search , If you get to a certain place , Must jump to graph[i] One of them , Continue recursion to the new coordinates 
    // If there is any change in the results, record the new results , Use an array to record the results of each step in real time 
    public void getNextResult(int mouse, int cat, int turns) {
        int curMove = turns % 2 == 0 ? mouse : cat;
        int defaultResult = curMove == mouse ? CAT_WIN : MOUSE_WIN;
        int result = defaultResult;
        int[] nextNodes = graph[curMove];
        for (int next : nextNodes) {
            if (curMove == cat && next == 0) {
                continue;
            }
            int nextMouse = curMove == mouse ? next : mouse;
            int nextCat = curMove == cat ? next : cat;
            int nextResult = getResult(nextMouse, nextCat, turns + 1);
            if (nextResult != defaultResult) {
                result = nextResult;
                if (result != DRAW) {
                    break;
                }
            }
        }
        dp[mouse][cat][turns] = result;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.

914. Card groups

Give a deck of cards , There is a whole number written on each card .

here , You need to choose a number X, So that we can divide the whole deck into 1 Groups or more ：

In each group X card .
All the cards in the group are written with the same integer .

Only if you choose X >= 2 When to return to true.

Example 1：

Example 2：

Tips ：

1 <= deck.length <= 104
0 <= deck[i] < 104

PS:
     What we need to ensure here is that each group has the same number , And this number should be greater than 1
     We count the number of each number 
     Let's look directly at their greatest common divisor , If their greatest common divisor is greater than or equal to 2 Just meet 
     If the number of numbers is X Twice as many , Can be divided into two groups , Each group is this number , It conforms to the meaning of the topic ,
     Or more divided into three groups ,
     As for these numbers, they can be divided into groups , It depends on their greatest common divisor 

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[deck.length + 1];
        // int max = -1;
        for (int i : deck) {
            count[i]++;
            // max = Math.max(count[i], max);
        }
        int res = count[deck[0]];
        for (int i : count) {
            if (i > 0) {
                res = gcd(res, i);
            }
        }
        return res >= 2;




        // Find the greatest common divisor 
        //
        // int min = 2;
        // while (min <= max) {
        // int i;
        // for (i = 0; i < count.length; i++) {
        // if (count[i] % min != 0) {
        // min++;
        // break;
        // }
        // }
        // if (i == count.length) {
        // return true;
        // }
        // }
        // return false;
    }
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}


     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.

915. Split array

Medium difficulty 95 Switch to English to receive dynamic feedback

Given an array nums , Divide it into two consecutive subarrays left and right, bring ：

left Each element in is less than or equal to right Every element in .
left and right It's all non empty .
left The length of the should be as small as possible .

After completing this grouping, return to left Of length .

Use cases can guarantee the existence of such a partitioning method .

Example 1：

Example 2：

Tips ：

2 <= nums.length <= 105
0 <= nums[i] <= 106
It can be guaranteed that there is at least one way to deal with nums division .

PS;
     Here is a direct change of approach ,
         Record the highest point of the sequence , Record the lowest point in reverse order 
         Because it is necessary to ensure that the point of the order is less than the point of the reverse order 
         As long as the highest order is less than the lowest reverse order , Then it conforms to the law 

     
      1.
      2.
      3.
      4.
      5.

class Solution {
    public int partitionDisjoint(int[] A) {
        int N = A.length;
        int[] maxleft = new int[N];
        int[] minright = new int[N];

        int m = A[0];
        for (int i = 0; i < N; ++i) {
            m = Math.max(m, A[i]);
            maxleft[i] = m;
        }

        m = A[N-1];
        for (int i = N-1; i >= 0; --i) {
            m = Math.min(m, A[i]);
            minright[i] = m;
        }

        for (int i = 1; i < N; ++i)
            if (maxleft[i-1] <= minright[i])
                return i;

        throw null;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

916. Word subsets

Here are two string arrays words1 and words2.

Now? , If b Every letter in the text appears in a in , Including repeated letters , So it's called string b Is string a Of A subset of .

for example ,"wrr" yes "warrior" Subset , But it's not "world" Subset .

If the words2 Every word in b,b All are a Subset , Then we call words1 The words in a yes ** Common words **.

Return... As an array words1 All common words in . You can press In any order Return to the answer .

Example 1：

Example 2：

Example 3：

Example 4：

Example 5：

Tips ：

1 <= words1.length, words2.length <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i] and words2[i] It's only made up of lowercase letters
words1 All the strings in Different from each other

PS:
     Any order , We can calculate by counting the number of characters 
     First find  b  The maximum number of characters per character , As long as the maximum number of characters per character is met , It meets all b
     Then the cycle  a , As long as there is one non-compliance, directly skip the current a,
      No skipping after the loop , Add to results 

     
      1.
      2.
      3.
      4.
      5.

class Solution {
    public List<String> wordSubsets(String[] A, String[] B) {
        int[] bmax = count("");
        for (String b: B) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; ++i)
                bmax[i] = Math.max(bmax[i], bCount[i]);
        }

        List<String> ans = new ArrayList();
        search: for (String a: A) {
            int[] aCount = count(a);
            for (int i = 0; i < 26; ++i)
                if (aCount[i] < bmax[i])
                    continue search;
            ans.add(a);
        }

        return ans;
    }

    public int[] count(String S) {
        int[] ans = new int[26];
        for (char c: S.toCharArray())
            ans[c - 'a']++;
        return ans;
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.

917. Just reverse the letters

The difficulty is simple 100 Switch to English to receive dynamic feedback

Given a string S, return “ After reversal ” character string , All characters that are not letters remain in place , And the positions of all letters are reversed .

Example 1：

Example 2：

Example 3：

Tips ：

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S Contains no `` or "


PS:
     Because you want to reverse the string , We directly store strings in positive order by stack 
     Then loop the original string , If it is a letter, a character pops up , If it is  -  Just add a  -
     Finally, the string is returned 
    

     
      1.
      2.
      3.
      4.
      5.
      6.

class Solution {
    public String reverseOnlyLetters(String S) {
        Stack<Character> letters = new Stack();
        for (char c: S.toCharArray())
            if (Character.isLetter(c))
                letters.push(c);

        StringBuilder ans = new StringBuilder();
        for (char c: S.toCharArray()) {
            if (Character.isLetter(c))
                ans.append(letters.pop());
            else
                ans.append(c);
        }

        return ans.toString();
    }
}

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

918. The maximum sum of the ring subarray

Given a length of n Of Circular integer array nums , return nums Non empty of Subarray Maximum possible and .

Ring array ** It means that the end of the array will be connected with the beginning in a ring . Formally , nums[i] The next element of this is nums[(i + 1) % n] , nums[i] The previous element of is nums[(i - 1 + n) % n] .

Subarray Can only contain fixed buffers at most nums Once for each element in the . Formally , For subarrays nums[i], nums[i + 1], ..., nums[j] , non-existent i <= k1, k2 <= j among k1 % n == k2 % n .

Example 1：

Example 2：

Example 3：

Tips ：

n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104

PS:
     Because it's cyclic , So we have to divide into left and right 
     The prefix and , Add the maximum suffix and （ First find the suffix sum , Add the maximum suffix and for each position ）

     
      1.
      2.
      3.

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int N = A.length;

        int ans = A[0], cur = A[0];
        for (int i = 1; i < N; ++i) {
            cur = A[i] + Math.max(cur, 0);
            ans = Math.max(ans, cur);
        }

        //  Calculate the suffix and  

        // rightsums[i] = A[i] + A[i+1] + ... + A[N-1]
        int[] rightsums = new int[N];
        rightsums[N-1] = A[N-1];
        for (int i = N-2; i >= 0; --i)
            rightsums[i] = rightsums[i+1] + A[i];

        //  Then calculate each suffix and the maximum value in the current position 
        int[] maxright = new int[N];
        maxright[N-1] = A[N-1];
        for (int i = N-2; i >= 0; --i)
            maxright[i] = Math.max(maxright[i+1], rightsums[i]);

        //  For each of these i  Guarantee  j >= i+2
        // Then use the prefix and plus the suffix and of the current position 
        int leftsum = 0;
        for (int i = 0; i < N-2; ++i) {
            leftsum += A[i];
            ans = Math.max(ans, leftsum + maxright[i+2]);
        }

        return ans;
    }
}
 

     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.

919. Complete binary tree inserter

Medium difficulty 60 Switch to English to receive dynamic feedback

Perfect binary tree Every floor （ Except for the last floor ） All completely filled （ namely , The number of nodes reaches the maximum ） Of , And all nodes are concentrated on the left as much as possible .

Design an algorithm , Insert a new node into a complete binary tree , And keep it intact after insertion .

Realization CBTInserter class :

CBTInserter(TreeNode root) Use the header node as root Initialize the data structure for the given tree ;
CBTInserter.insert(int v) Insert a value of... Into the tree Node.val == val The new node TreeNode. Keep the tree in the state of a complete binary tree , And return to the insert node TreeNode The value of the parent node of ;
CBTInserter.get_root() The head node of the tree will be returned .

Example 1：

#yyds Dry inventory # LeetCode Brush question set 911 - 920_ Array initialization _03

 Input 
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
 Output 
[null, 1, 2, [1, 2, 3, 4]]

 explain 
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3);  //  return  1
cBTInserter.insert(4);  //  return  2
cBTInserter.get_root(); //  return  [1, 2, 3, 4]

     
      1.
      2.
      3.
      4.
      5.
      6.
      7.
      8.
      9.
      10.
      11.

Tips ：

The number of nodes in the tree ranges from [1, 1000]
0 <= Node.val <= 5000
root It's a perfect binary tree
0 <= val <= 5000
Each test case calls at most insert and get_root operation 104 Time

class CBTInserter {
    TreeNode root;
    Deque<TreeNode> deque;
    public CBTInserter(TreeNode root) {
        this.root = root;
        deque = new LinkedList();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);

        // BFS Build a complete binary tree , During the construction process, the nodes that lack child nodes should be recorded 
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left == null || node.right == null)
                deque.offerLast(node);
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
    }
    // Take out the child node , If the child node is missing the left node , Just give the new node to the left node 
    // If the right node is missing, give the new node to the right node 
    public int insert(int v) {
        TreeNode node = deque.peekFirst();
        deque.offerLast(new TreeNode(v));
        if (node.left == null)
            node.left = deque.peekLast();
        else {
            node.right = deque.peekLast();
            deque.pollFirst();
        }

        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}


     1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.