This afternoon one hour three questions OJ test came to an end. The first “cool cool” to myself. Working all day with CRUD and little recent code, combined with the fact that it’s been five years since OJ’s brushes led to several stupid basic mistakes and wasted valuable time. Question 2 was expected to get half of the score (if the background sample form is in my estimation).
Now the first two of the three questions in the test are sorted out. First of all, the title in this paper is not an exact copy. Here, only the key requirements are recalled and described. At the same time, in order to avoid unnecessary trouble, the title description is deformed to some extent, but the basic logic is consistent. In addition, my way of thinking is not necessarily correct and optimal, welcome to leave a message to discuss.
Language used: Java. The compiler can use standard classes as well as java.util.* classes.
Array and traversal
Description: A company has n stores, numbered from 1 to N, and supplies m goods from the ith to the JTH stores at a time. There are multiple supply records placed in a two-dimensional array. If there are five outlets, the supply records are as follows: [[1,2,10],[2,3,30],[2,5,60]]. The program needs to calculate the number of goods received by each supplier. In this example, the result is [10,100,90,60,60]. There is a maximum limit on the size of the two-dimensional array, the number of outlets (5000000 or 5000000), and 0 < I < j < n.
The first parameter list is the supply record, two-dimensional array; The second is the number of business outlets, int type. The problem is very simple, the simple idea is to build a one-dimensional array with the number of business points before traversing the two-dimensional array. After traversing the two-dimensional array, take the information of the second layer array as I,j and M in turn, build a loop from I to J, as the subscript of the one-dimensional array, and add M to the element of the one-dimensional array.
The only thing to notice in this case is that you build your own one-dimensional array subscript. Array subscripts start with 0 and end with n-1.
Problem two: string
Restore according to the entered string. For example WOSHINI[2BA], the program should return WOSHINIBABA. For example [3WO]SHINI[2BA], WOWOWOSHINIBABA should be returned. The sample has nested cases, such as WOSHI[3NI[2BA]], which should be WOSHINIBABANIBABANIBABA. The sample program shows no more than 10 layers of nesting.
I didn’t consider nesting when I did this problem. In fact, the string is divided into characters, and the final concatenation is made with the part without parentheses after traversing to determine the range of parentheses.
There are two or three unnested elements in this list. But according to the results submitted, it looks like just one… -‘0’ = ‘0’ = ‘0’ = ‘0’ = ‘0’ = ‘0’ There were only 10 minutes left when it was corrected… It’s really disturbing… Data structure, algorithm and ACM all returned to Teacher Yang, Teacher Sha and Huan ge…… Helpless…
Visually this can also be done with stacks and recursion. Welcome to share your ideas with Ben Tacca.
Question 3: tree
I don’t have time to look and do this problem because I don’t have time. Looks like a minimum spanning tree problem. You can comment in the comments section.
Since it was a test, the questions weren’t that difficult… So it looks like the pro division is getting cold, so it’s just the public division… It really exposes the problem to make such a bad shape. Taking this as an opportunity, I plan to do several problems every day and brush LeetCode more.