Generates a string in which each character is odd

















Given an integer n, return a string of n characters in which each character occurs exactly an odd number of times in the string.
The returned string must contain only lowercase English letters. If there are multiple strings that meet the requirements of the problem, return any one of them.

Example:
Enter: n = 4
Output: ‘PPPZ’
Explanation: ‘PPPZ’ is a satisfactory string because ‘p’ occurs three times and ‘z’ occurs once. Of course, there are many other strings that satisfy the question, such as ‘ohhh’ and ‘love’.








Judge the odd and even form of an integer.










Light Bulb Switch III

















There are n light bulbs, numbered from 1 to N, arranged in a row from left to right. At first, all the lights were off.

At time K (k ranges from 0 to n-1), we turn on the light[k].

In order for the light to turn blue, two conditions must be met:

The light is on.
All the lights before it (left) are also on.
Return the number of times when all lights turned blue.

Example:
Input: light = [2, 1, 3, 5, 4]
Output: 3
Explanation: the moments when all lights turn blue are 1,2 and 4.








First understand the conditions under which a light bulb turns blue:

  • The light is on

  • All the lights in front of it are switched on

If you want all lights turned blue at any given moment, then the lights that are turned on should be in a range of 1 to N.

The first solution: If all the lights on at the moment are in an order of 1 to N, then the maximum subscript of the lights on at the moment should be the same as the number.

Second solution: If all lights on at the moment are a 1 to N array, then the subscript sum of all lights on satisfies the sum of the first n arithmetic sequences.










Notify all employees of the time required

















There are n employees in the company, and each employee has a unique ID, numbered from 0 to N-1. The general manager of the company is identified by headID.

In the Manager array, each employee has a direct manager, where Manager [I] is the direct manager of the ith employee. For the overall manager, manager[headID] = -1. The title ensures that the dependencies can be displayed in a tree structure.

The head of the company would like to send an urgent message to all employees. He will first notify his immediate reports, who will then notify their subordinates, until all employees are informed of the urgent message.

Employee I needs informTime[I] minutes to notify all his immediate reports (that is, after informTime[I] minutes, all his immediate reports can start spreading the message).

Returns the number of minutes required to notify all employees of this urgent message.

Example:

Input: n = 6, headID = 2, Manager = [2,2,-1,2,2], informTime = [0,0,1,0,0]
Output: 1.
Explanation: The employee with ID = 2 is the general manager of the company and the direct manager of all other employees. He needs 1 minute to notify all employees.

The following figure shows the tree structure of the company’s employees.








Search algorithm.

Step 1: Use Map data structures in JavaScript to store tree relationships of nodes.

Step 2: Since the notification time of each leader is strongly dependent on the notification time of his immediate subordinates, the notification time of the current node needs to be passed up during DFS (depth-first search algorithm).










T the position of the frog in seconds

















You are given an undirected tree with n vertices numbered from 1 to n. The frog jumps from top 1. Here are the rules:

In one second, the frog jumps from its current vertex to another unvisited vertex (if they are directly connected).
The frog cannot jump back to a vertex already visited.
If a frog can jump to multiple different vertices, it has an equal chance of jumping to any one of them.
If the frog can’t jump to any unvisited vertices, it stays in the same place every time it jumps.
Edges of an undirected tree are described by the array edges, where edges[I] = [fromi, toi] means that there is an edge that directly connects fromi and toi.

Returns the probability that the frog will be at the target vertex after t seconds.

Example:
Input: n = 7, edges = [[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]], t = 2, target = 4
Output: 0.16666666666666666
Explanation: The image above shows the frog’s jumping path. The frog jumps from vertex 1 with a 1/3 chance of jumping to vertex 2 in the first second and then to vertex 4 in the second with a 1/2 chance, so the probability of the frog being at vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.1666666666666.








This problem is similar to the previous one.

Note that this problem is an undirected tree, so when using Map to record edges in the array of edges, we need to deal with bidirectional relations. Since this is a tree relationship, we can judge the size of parent and child nodes to avoid judging the access status of the current node in the subsequent search process.

Next, DFS is used to simulate the track of frog jumping. In the DFS process, the following processing is needed:

  • Pass down the probability that the current node is selected

  • Judge whether the current node is the target node and return the final probability

There are two scenarios in which the current node is the target node:

  • The target node is searched and time runs out

  • Search to the target node, although time is not running out, but there is no way to go










Highlights from the past






  • LeetCode Journey for front End Engineers — 173 weeks

  • LeetCode Journey for Front End Engineers — 174 weeks

  • Front End Engineer’s Journey to LeetCode – 177 weeks

  • Front End Engineer’s Journey to LeetCode – 178 weeks

  • The LeetCode Journey for front-end Engineers — Binary Tree

  • JavaScript AC solutions to problems on LeetCode