Uber OA 面试真题解析：Resource Cycle Simulation 资源循环模拟

Each cycle, one of the three events happens:

• Option 1: If there are at least conversionRate P resources, then the last conversionRate P resources are removed and one A is added at the beginning of the array.
• Option 2: If there is at least one A, the last A changes to P.
• Option 3: If neither Option 1 nor Option 2 can be completed, then the process halts.

Follow the process and compute how many cycles will pass until the process halts.

Refer to the examples below for better understanding.

Note: You are expected to provide a solution with time complexity not worse than O(resources.length * conversionRate^2).

Example 1:

For resources = ["A", "A", "A", "P", "P", "P"] and conversionRate = 2, the output should be solution(resources, conversionRate) = 13.

这道 Uber OA 题本质上是一个按规则迭代的状态模拟：每一轮优先检查是否有至少 conversionRate 个 P，可以把最后 conversionRate 个 P 变成一个开头的 A；否则如果还有 A，就把最后一个 A 变成 P；两种操作都无法进行时结束。关键在于不要真的每次都去修改整个数组，而是只维护 A 和 P 的数量，并严格按题意更新计数，这样就能把每一步的耗时降到常数级，整体满足题目要求的复杂度。