LeetCode（Queue)2073. Time Needed to Buy Tickets

以你之姓@ 2023-09-25 18:11 9阅读 0赞

# 1.问题 #

There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets\[i\].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k (0-indexed) to finish buying tickets.

Example 1:

> Input: tickets = \[2,3,2\], k = 2  
> Output: 6  
> Explanation:
> 
>  *  In the first pass, everyone in the line buys a ticket and the line becomes \[1, 2, 1\].
>  *  In the second pass, everyone in the line buys a ticket and the line becomes \[0, 1, 0\].  
>     The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Example 2:

> Input: tickets = \[5,1,1,1\], k = 0  
> Output: 8  
> Explanation:
> 
>  *  In the first pass, everyone in the line buys a ticket and the line becomes \[4, 0, 0, 0\].
>  *  In the next 4 passes, only the person in position 0 is buying tickets.  
>     The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

Constraints:

*  n == tickets.length
 *  1 <= n <= 100
 *  1 <= tickets\[i\] <= 100
 *  0 <= k < n

# 2. 解题思路 #

## 方法1： ##

> 1.定义一个整数变量 res，用于保存购买门票所需的时间。  
> 2.通过一个 for 循环遍历 tickets 数组，对于每个窗口，计算当前窗口和购票者所在窗口之间的距离，根据距离分别计算购票所需的时间。具体而言，如果当前窗口与购票者所在窗口之间的距离小于等于 k，则购票所需的时间为当前窗口和购票者所在窗口的门票数量的最小值；否则购票所需的时间为当前窗口的门票数量和购票者所在窗口的门票数量减去 1 的最小值。  
> 3.函数返回购买门票所需的总时间。

## 方法2： ##

> 1.定义一个变量用于保存购买门票的总时间  
> 2.只要购票者所在窗口还有门票未售完，就继续购票  
> 3.遍历所有窗口，如果当前窗口还有门票未售完，增加购买门票所需的时间； 如果购票者所在窗口的门票已售完，则跳出循环  
> 4.返回购买门票的总时间

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int timeRequiredToBuy(int[] tickets, int k) {
        
            int res = 0; // 1.定义一个变量用于保存购买门票的总时间
            for (int i = 0; i < tickets.length; i++) {
         // 2.遍历所有窗口
                if (i <= k) {
         // 3.如果当前窗口在购票者所在窗口左侧或者就是购票者所在窗口
                    res += Math.min(tickets[k], tickets[i]); // 购买门票所需的时间为当前窗口和购票者所在窗口的门票数量的最小值
                } else {
         // 4.如果当前窗口在购票者所在窗口右侧
                    res += Math.min(tickets[k] - 1, tickets[i]); // 购买门票所需的时间为当前窗口的门票数量和购票者所在窗口的门票数量减去 1 的最小值
                }
            }
            return res; // 5.返回购买门票的总时间
        }
    }

## 代码2： ##

class Solution {
        
        public int timeRequiredToBuy(int[] tickets, int k) {
        
            int timeTaken = 0; // 1.定义一个变量用于保存购买门票的总时间
            while (tickets[k] > 0) {
         // 2.只要购票者所在窗口还有门票未售完，就继续购票
                for (int i = 0; i < tickets.length; i++) {
         // 3.遍历所有窗口，如果当前窗口还有门票未售完，增加购买门票所需的时间； 如果购票者所在窗口的门票已售完，则跳出循环
                    if (tickets[i] > 0) {
         // 如果当前窗口还有门票未售完
                        tickets[i]--; // 购买一张门票
                        timeTaken++; // 增加购买门票所需的时间
                    }
                    if (tickets[k] == 0)  break; // 如果购票者所在窗口的门票已售完，则跳出循环
                }
            }
            return timeTaken; // 4.返回购买门票的总时间
        }
    }

class Solution {
        
    	public int timeRequiredToBuy(int[] tickets, int k) {
        
        int timeTaken = 0; // 定义一个变量用于保存购买门票的总时间
        for (int i = 0; i < tickets.length; i++) {
         // 遍历所有窗口
            if (tickets[i] <= tickets[k]) {
         // 如果当前窗口所剩门票数量小于等于购票者所在窗口的门票数量
                timeTaken += tickets[i]; // 购买当前窗口所剩门票数量的门票，并增加购买门票所需的时间
            } else {
        
                timeTaken += tickets[k]; // 购买购票者所在窗口的所有门票，并增加购买门票所需的时间
            }
            if (i > k && tickets[i] >= tickets[k]) {
         // 如果当前窗口不是购票者所在窗口且其剩余门票数量大于等于购票者所在窗口的门票数量
                timeTaken--; // 减少购票时间，因为购票者不需要在该窗口等待
            }
        }
        return timeTaken; // 返回购买门票的总时间
    	}
    
    }

> 解题思路基本相同

public int timeRequiredToBuy(int[] tickets, int k) {
        
        int output = 0; // 定义一个变量用于保存购买门票的总时间
        int n = tickets.length; // 窗口数量
        for (int i = 0; i < n; i++) {
         // 遍历所有窗口
            if (tickets[i] < tickets[k]) {
         // 如果当前窗口所剩门票数量小于购票者所在窗口的门票数量
                output += tickets[i]; // 购买当前窗口所剩门票数量的门票，并增加购买门票所需的时间
            } else {
         // 如果当前窗口所剩门票数量大于等于购票者所在窗口的门票数量
                if (i <= k) {
         // 如果当前窗口在购票者所在窗口的左侧（包括购票者所在窗口）
                    output += tickets[k]; // 购买购票者所在窗口的所有门票，并增加购买门票所需的时间
                } else {
         // 如果当前窗口在购票者所在窗口的右侧
                    output += tickets[k] - 1; // 购买购票者所在窗口的所有门票除最后一个，并增加购买门票所需的时间
                }
            }
        }
        return output; // 返回购买门票的总时间
    }