1. Minimum Swaps
A shopkeeper in HackLand assigns each item in a shop a unique popularity rating. To order the items in decreasing popularity from left to right, the shopkeeper can swap any 2 items in one operation. Determine the minimum number of operations needed to reorder the items correctly.
Example
Input:
n = 4
popularity = [3, 4, 1, 2]
Steps:
First, switch 3 and 4 to get popularity' = [4, 3, 1, 2].
Then, switch 1 and 2 to get [4, 3, 2, 1].
The array is reordered in 2 operations.
Function Description
Complete the function minimumSwaps in the editor below.
minimumSwaps has the following parameter(s):
- int popularity[n]: an array of integers that represents the popularity of each item
- Returns:
- int: the minimum number of swaps to order the items properly
Constraints
- 1 ≤ n ≤ 2 × 10⁵
- 1 ≤ popularity[i] ≤ n
Input Format for Custom Testing
Input from stdin will be processed as follows and passed to the function:
- The first line contains an integer n, the size of the array popularity.
- Each of the next n lines contains an integer popularity[i] where 0 ≤ i < n.
Sample Case 0
Sample Input 0:
3
3
1
2
Sample Output 0:
1
Explanation 0:
n = 3
popularity = [3, 1, 2]
Switch 1 and 2, and the items in the array [3, 2, 1] are reordered in 1 operation.
The return value is 1.
2. Delivery Management System
A manufacturing company is located in a certain city. Their goods need to be shipped to other cities that are connected with bidirectional roads, though some cities may not be accessible because roads don’t connect to them. The order of deliveries is determined first by distance, then by priority. Given the number of cities, their connections via roads, and what city the manufacturing company is located in, determine the order of cities where the goods will be delivered.
For example, let's say that the number of cities is cityNodes = 4, where cityFrom = [1, 2], cityTo = [2, 3, 4], and company = 1.
In other words, the manufacturing company is located in city 1, and the roads run between cities 1 and 2, 2 and 3, and 2 and 4, like so:
Delivery Order Logic
- The closest city (or cities) is visited first. This is city 2, which is 1 unit from the manufacturing company.
- The next-closest city (or cities) is visited next. This is city 3 and city 4, which are both 2 units from the manufacturing company.
- Priority is calculated, visiting the smaller-numbered city first (city 3) and continuing in ascending order (city 4).
Therefore, the final order is [2, 3, 4].
Function Description
Complete the function order in the editor below.
order has the following parameters:
- int cityNodes: the number of cities
- int cityFrom[n]: the first city node where there is a bidirectional edge
- int cityTo[n]: the second city node where there is a bidirectional edge
- int company: the node where the route starts
Returns:
- int[]: the cities where the goods will be delivered in the order visited
Constraints
- 2 ≤ cityNodes ≤ 10⁵
- 1 ≤ n ≤ min((cityNodes × (cityNodes - 1)) / [2], 10⁵)
- 1 ≤ cityFrom[i], cityTo[i], company ≤ n
- cityFrom[i] ≠ cityTo[i]
Input Format for Custom Testing
The first line contains two space-separated integers: cityNodes, denoting the number of cities, and n, denoting the number of roads.
Each i of the n subsequent lines (where 0 ≤ i < n) contains two space-separated integers, cityFrom[i] and cityTo[i].
The next line contains one integer, company.
Sample Case 0
Sample Input 0:
5 5
1 2
1 3
2 4
3 5
1 5
1
Sample Output 0:
2
3
5
4
Explanation 0:
- Cities 2, 3, and 5 are all 1 unit of distance away from the manufacturing company.
- They are visited in ascending order: [2, 3, 5].
- City 4 is 2 units of distance away from the manufacturing company, so it is visited next.
- Final order: [2, 3, 5, 4].
Sample Case 1
Sample Input 1:
3 1
1 2
2
Sample Output 1:
1
Explanation 1:
- City 1 is 1 unit of distance away from the manufacturing company.
- City 3 is not accessible because there are no roads connecting it to the manufacturing company's city.
- Final order: [1].
3. Movie Ratings
Alex loves movies and maintains a list of negative and/or positive integer ratings for the movies in a collection. Alex is getting ready for a film festival and wants to choose some subsequence of movies from the collection to bring such that the following conditions are satisfied:
- The collective sum of their ratings is maximal.
- Alex must go through the list in order and cannot skip more than one movie in a row.
- In other words, Alex cannot skip over two or more consecutive movies.
- For example, if ratings = [-1, -3, -2], Alex must include either the second number or the first and third numbers to get a maximal rating sum of -3.
Example
Input:
ratings = [-3, 2, 4, -1, -2, -5]
Optimal Choice:
Alex selects [2, 4, -2], which gives a sum of 4.
Function Description
Complete the function maximizeRatings in the editor below.
maximizeRatings has the following parameter(s):
- int ratings[n]: movie ratings
Returns:
- int: the maximum possible rating sum for a subsequence of movies
Constraints
- 1 ≤ n ≤ 10⁵
- -1000 ≤ ratings[i] ≤ 1000, where 0 ≤ i < n
Input Format for Custom Testing
Input from stdin will be processed as follows and passed to the function:
- The first line contains an integer n, the size of the array ratings.
- Each of the next n lines contains an integer ratings[i].
Sample Case 0
Sample Input 0:
5
9
-1
-3
4
5
Sample Output 0:
17
Explanation 0:
Alex picks the bolded items in ratings = [9, -1, -3, 4, 5] to get maximum rating = 9 + (-1) + 4 + 5 = 17.
Sample Case 1
Sample Input 1:
5
-1
-2
-3
-4
-5
Sample Output 1:
-6
Explanation 1:
Alex picks the bolded items in ratings = [-1, -2, -3, -4, -5] to get maximum rating = -2 + (-4) = -6.
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
