Find the lucky number in the array

















In an array of integers, we call an integer a “lucky number” if its frequency of occurrence is equal to its numerical value.

You are given an array of integers, arr, and ask you to find and return a lucky number.

If there are more than one lucky number in the array, just return the largest one.
If the array contains no lucky number, -1 is returned.

Example:
Input: arr = [2, 2, 3, 4]
Output: 2
Explanation: The only lucky number in the array is 2, because 2 occurs twice as often.








The Map data structure is used in JavaScript.

Step 1: Map can be used to count the number of occurrences of each number.

Step 2: Find the largest number of occurrences in the Map.

Time complexity O(n), space complexity O(n).










Count the combat units

















The famous soldiers stood in a row. Each soldier has a unique rating.
Every 3 soldiers can form an operational unit, and the grouping rules are as follows:

Rating [j], rating[k], rating[j], rating[k], rating[j], rating[k]
Rating [I] < rating[j] < rating[k] rating[j] < rating[k
Return the number of units that can be formed according to the above conditions. Each soldier can be part of multiple combat units.

Example:
Enter: rating = [2, 5, 3, 4, 1]
Output: 3
Explanation: Three units (2, 3, 4) (5, 3, 1) (5, 4, 1)








Because the range of array lengths given in this problem is very small, an attempt to expose enumeration unexpectedly passed.

Time order n^3.

There are three soldiers required, so you can use the soldier in the middle as a reference point and look for soldiers on both sides that meet the requirements.

This is actually using the double pointer technique to reduce the dimension, the time complexity optimization is O(n^2).










5370. Design the subway system

















You can implement a class UndergroundSystem that supports the following three methods:

1. checkIn(int id, string stationName, int t)

The passenger numbered id enters the stationName at time t.
A passenger can enter or leave only one station at a time.

2. checkOut(int id, string stationName, int t)

The passenger numbered id leaves stationName at time t.

3. getAverageTime(string startStation, string endStation)
Returns the average time taken from startStation to endStation.
The average time calculated includes all current trips directly from startStation to endStation.
When getAverageTime is called, the asked route contains at least one trip.

You can assume that all calls to checkIn and checkOut are logical. In other words, if a customer arrives at a subway station at time T1, then his departure time t2 must satisfy t2 > T1. All events are presented in chronological order.








After reading the description of this problem, most of the coder will think of using HashMap statistics, but what information should be collected to facilitate the calculation of getAverageTime?

First of all, for any passenger, he must come in and go out in a cycle, so when we get the information of his departure, we only need to keep the time interval between arrival and departure, and delete the previous information of arrival and departure, otherwise it will be troublesome to count the subsequent arrival and departure of the passenger.

Finally, the getAverageTime method is executed, using the inbound and outbound information to query the HashMap calculations and values.

The time complexity of checkIn and checkOut is O(1), and the time complexity of getAverageTime is O(n).










Find all the good strings

















You are given two strings of length N, S1 and S2, and a string evil. Please return the number of good strings.

A good string is defined as having a length of n, a lexicographical order greater than or equal to S1, a lexicographical order less than or equal to S2, and no substring evil.
Since the answer may be large, return the answer mod 10^9 + 7.

Example:
Input: n = 2, s1 = ‘aa’, s2 = ‘da’, EVIL = ‘b’
Output: 51
Explanation: There are 25 good strings that start with ‘a’ : ‘AA’, ‘ac’, ‘AD’… , ‘ ‘ ‘. There are also 25 nice strings that start with ‘c’ : ‘ca’, ‘cc’, ‘CD’… , ‘cz. Finally, there’s a nice string that starts with ‘d’ : ‘da’.








2. What is the meaning of this passage?

  • Digital DP

  • KMP

First, we can ignore the evil condition. How do we solve for all strings between [s1, s2]?

The easy way to think about it is to judge the upper and lower limits and enumerate all the cases by violence.

There are two problems with this approach:

  • In the enumeration process, it is more complicated to deal with both upper and lower limits

  • Violence enumeration will appear a lot of repeated enumeration, low efficiency

For the first problem, we can convert the problem to a simpler form, where the lexicographical order is less than or equal to s1, and then the lexicographical order is less than or equal to S2, and the result is S2 – s1 + 1.

For the second problem: enumerating from the highest level combined with mnemonic optimization repeated enumeration operations, this is digit DP.

The difficulty is that it does not contain the EVIL string.

This requires the NEXT array in the KMP algorithm to help us record whether the current string matches the EVIL string.

So in the process of digital DP, we need to add a state that currently matches the length of evil characters, and use the NEXT array of KMP to solve the currently matched characters in the enumeration process.










Highlights from the past






  • Front End Engineer’s LeetCode Journey — Week 181

  • Front End Engineer’s Journey to LeetCode – Week 180

  • Front End Engineer’s LeetCode Journey – Week 179

  • LeetCode Tour for Front End Engineers – Week 178

  • JavaScript AC solutions to problems on LeetCode