Tag Archives: 模拟

LeetCode Detect Pattern of Length M Repeated K or More Times

5499. Detect Pattern of Length M Repeated K or More Times

Given an array of positive integers arr,  find a pattern of length m that is repeated k or more times.

pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

Constraints:

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100
  • 1 <= m <= 100
  • 2 <= k <= 100

给定一个数组,为是否存在长度为m的子数组,这个子数组重复了至少k词。

观察数据范围,数据量很小,直接暴力求解,代码如下:

class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        int n = arr.size();
        if(m * k > n) return false;
        for(int i = 0; i < n; ++i) {
            int rep = 0;
            for(int j = i; j < n; j += m) {
                bool good = true;
                for(int u = 0; u < m; ++u) {
                    if(u + j >= n || arr[u + j] != arr[i + u]) {
                        good = false;
                        break;
                    }
                }
                if(!good) break;
                else ++rep;
            }
            if(rep >= k) return true;
        }
        return false;
    }
};

本代码提交AC,用时4MS。

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:

输入:
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
提示:

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


用两个栈实现一个队列。栈是后进先出,队列是先进先出。设置两个栈stack_in_和stack_out_,分别负责数据的push和pop,如果stack_out_没数据,则需要从stack_in_中把数据捣腾到stack_out_中。完整代码如下:

class CQueue {
private:
    stack<int> stk_in_, stk_out_;
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        stk_in_.push(value);
    }
    
    int deleteHead() {
        if(!stk_out_.empty()) {
            int ans = stk_out_.top();
            stk_out_.pop();
            return ans;
        } else if(!stk_in_.empty()) {
            while(stk_in_.size() != 1) {
                int tmp = stk_in_.top();
                stk_in_.pop();
                stk_out_.push(tmp);
            }
            int tmp = stk_in_.top();
            stk_in_.pop();
            return tmp;
        } else {
            return -1;
        }
    }
};

本代码提交AC,用时696MS。

LeetCode Find Kth Bit in Nth Binary String

5484. Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string  Sn is formed as follows:

  • S1 = "0"
  • Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

  • S= "0"
  • S= "011"
  • S= "0111001"
  • S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".

Example 3:

Input: n = 1, k = 1
Output: "0"

Example 4:

Input: n = 2, k = 3
Output: "1"

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= 2n - 1

简单题,直接字符串模拟操作即可,完整代码如下:

class Solution {
private:
	string InvertStr(string &s) {
		string ans = "";
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '0')ans.push_back('1');
			else ans.push_back('0');
		}
		return ans;
	}
public:
	char findKthBit(int n, int k) {
		string s = "0";
		for (int i = 2; i <= n; ++i) {
			string inv_str = InvertStr(s);
			reverse(inv_str.begin(), inv_str.end());
			s = s + "1" + inv_str;
		}
		return s[k - 1];
	}
};

本代码提交AC。

LeetCode Water Bottles

5464. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

  • 1 <= numBottles <= 100
  • 2 <= numExchange <= 100

很贴近生活的一个题。初始有n瓶满饮料,喝完之后,可以每m个空瓶子换一瓶新饮料,问最终能喝多少瓶饮料。

直接模拟,代码如下:

class Solution {
public:
	int numWaterBottles(int numBottles, int numExchange) {
		int full = numBottles, empty = 0, div = numExchange;
		int ans = 0;
		while (full + empty >= div) {
			ans += full;
			empty += full;
			full = empty / div;
			empty = empty % div;
		}
		return ans + full;
	}
};

本代码提交AC。

LeetCode Last Moment Before All Ants Fall Out of a Plank

5453. Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Example 1:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).

Example 2:

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Example 3:

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.

Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6

Constraints:

  • 1 <= n <= 10^4
  • 0 <= left.length <= n + 1
  • 0 <= left[i] <= n
  • 0 <= right.length <= n + 1
  • 0 <= right[i] <= n
  • 1 <= left.length + right.length <= n + 1
  • All values of left and right are unique, and each value can appear only in one of the two arrays.

很有意思的一个题。一块长木板上,放了若干只蚂蚁,有的蚂蚁向左走,有的蚂蚁向右走。当两个蚂蚁碰头时,会各自掉头走。问所有蚂蚁走出木板的时间。

有点像智力题,分析了半天,发现挺简单的。想象一下,如果蚂蚁A向右走,蚂蚁B向左走,它们在坐标0点碰头了,则A掉头向左走,B掉头向右走。对于A和B来说,虽然它们的方向变了,但是对于整个木板来说,并没有差别,依然是有一只蚂蚁从0点向右走,有一只蚂蚁从0点向左走。相当于A和B交换了身份,各自帮对方走了剩下的流程。但是从宏观分析看,A和B不管掉不掉头,效果是一样的。

综上所述,完全不用考虑碰头掉头的问题,直接对向左走和向右走的蚂蚁单独分析。对于向左走的蚂蚁,最右边的蚂蚁要走最长的时间。对于向右走的蚂蚁,最左边的蚂蚁要走最长的时间。总时间就是这两种情况的最大值。代码如下:

class Solution {
public:
	int getLastMoment(int n, vector<int>& left, vector<int>& right) {
		sort(left.begin(), left.end());
		sort(right.begin(), right.end());
		int ans = 0;
		if (!left.empty())ans = max(ans, left.back());
		if (!right.empty())ans = max(ans, n - right.front());
		return ans;
	}
};

本代码提交AC。

LeetCode Display Table of Food Orders in a Restaurant

1418. Display Table of Food Orders in a Restaurant

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders.

Return the restaurant’s “display table. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] 
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito". 

Example 2:

Input: orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
Output: [["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]] 
Explanation: 
For the table 1: Adam and Brianna order "Canadian Waffles".
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".

Example 3:

Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

Constraints:

  • 1 <= orders.length <= 5 * 10^4
  • orders[i].length == 3
  • 1 <= customerNamei.length, foodItemi.length <= 20
  • customerNamei and foodItemi consist of lowercase and uppercase English letters and the space character.
  • tableNumberi is a valid integer between 1 and 500.

很啰嗦的一个题目。给定一系列顾客的点餐清单,输出整个餐厅的点餐信息表。直接按照题意做就行,题目要求行按桌号升序排列,列按菜名字母序排列,所以行可以用vector下标存储,菜名放到set里会自动有序排列。

完整代码如下:

class Solution {
public:
	vector<vector<string>> displayTable(vector<vector<string>>& orders) {
		vector<map<string, int>> tables(501, map<string, int>());
		set<string> allfoods;
		for (int i = 0; i < orders.size(); ++i) {
			string name = orders[i][0], tb = orders[i][1], food = orders[i][2];
			int ntb = stoi(tb.c_str());
			++tables[ntb][food];
			allfoods.insert(food);
		}
		vector<vector<string>> ans;
		vector<string> header;
		header.push_back("Table");
		for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it)header.push_back(*it);
		ans.push_back(header);
		for (int i = 1; i <= 500; ++i) {
			vector<string> cur;
			if (tables[i].size() > 0) {
				cur.push_back(to_string(i));
				for (set<string>::iterator it = allfoods.begin(); it != allfoods.end(); ++it) {
					cur.push_back(to_string(tables[i][*it]));
				}
				ans.push_back(cur);
			}
		}
		return ans;
	}
};

本代码提交AC,用时1152MS。

LeetCode Queries on a Permutation With Key

1409. Queries on a Permutation With Key

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

  • In the beginning, you have the permutation P=[1,2,3,...,m].
  • For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].  

Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints:

  • 1 <= m <= 10^3
  • 1 <= queries.length <= m
  • 1 <= queries[i] <= m

初始时给定一个P=[1,2,…,m]的数组,然后有一个queries数组,对于每一个query,问其在P中的下标,并且将该元素移到P的开头,最后问queries数组中所有query的下标的数组。

模拟题,由于有元素的移动操作,即删除和插入操作,所以这里借用链表来处理。完整代码如下:

class Solution {
public:
	vector<int> processQueries(vector<int>& queries, int m) {
		list<int> lst;
		for (int i = 1; i <= m; ++i)lst.push_back(i);
		vector<int> ans;
		for (int i = 0; i < queries.size(); ++i) {
			int val = queries[i];
			int j = 0;
			list<int>::iterator it = lst.begin();
			while (it != lst.end()) {
				if (*it == val) {
					ans.push_back(j);
					lst.erase(it);
					lst.push_front(val);
					break;
				}
				else {
					++it;
					++j;
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时28MS。

LeetCode Create Target Array in the Given Order

1389. Create Target Array in the Given Order

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

  • Initially target array is empty.
  • From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
  • Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]
Output: [1]

Constraints:

  • 1 <= nums.length, index.length <= 100
  • nums.length == index.length
  • 0 <= nums[i] <= 100
  • 0 <= index[i] <= i

很无聊的一个题。给定一个值数组nums,和一个下标数组index,表示数nums[i]插入到index[i]所在位置。有可能多个数插入到同一个位置了,此时先插入的数要往后挪。

很无聊的一个题,模拟题意照做即可,完整代码如下:

class Solution {
public:
	vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
		int n = nums.size();
		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			ans.insert(ans.begin() + index[i], nums[i]);
		}
		return ans;
	}
};

本代码提交AC,用时0MS。

LeetCode Dota2 Senate

LeetCode Dota2 Senate In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

  1. Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
  2. Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.
Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n. The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure. Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire. Example 1:
Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.
Example 2:
Input: "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.
Note:
  1. The length of the given string will in the range [1, 10,000].

Dota2中有两个党派,分别是Radiant和Dire,分别用R和D表示。给定一个长度为n的字符串s,表示n个人,如果s[i]=’R’,表示第i个人是Radiant党的人;如果s[i]=’D’,表示第i个人是Dire党的人。 投票过程是从1~n不断重复的,每个人可以禁止任何一个其他人投票。如果某个人投票之后,剩下的人都是同一个党派的,则该党派胜利。问最终是哪个党派的人胜利。 使用贪心的原则,因为是round-based的投票方式,为了获胜,第i个人肯定是禁止其后的第一个非本党人员投票。比如序列DRDRR: 第一个D如果杀其后的第一个R:
  1. DXDRR
  2. DXDXR
  3. XXDXR
  4. XXDXX
Dire胜利;第一个D如果杀其后的第二个R:
  1. DRDXR
  2. DRXXR
  3. XRXXR
Radiant胜利。 这其实很好理解,因为是round-based的投票方式,对于D来说,他必须首先把其后的第一个R杀掉,要不然很快就会轮到这个R杀己方人员了。 round-based的方式是用%n的方式实现,代码如下: [cpp] class Solution { public: string predictPartyVictory(string senate) { int r_cnt = 0, d_cnt = 0, n = senate.size(); for (int i = 0; i < n; ++i) { if (senate[i] == ‘R’) ++r_cnt; else ++d_cnt; } int pos = 0; while (r_cnt > 0 && d_cnt > 0) { if (senate[pos] == ‘X’) { pos = (pos + 1) % n; continue; } int pos_next = (pos + 1) % n; while (senate[pos_next] == senate[pos] || senate[pos_next] == ‘X’) pos_next = (pos_next + 1) % n; if (senate[pos_next] == ‘R’) –r_cnt; else –d_cnt; senate[pos_next] = ‘X’; pos = (pos + 1) % n; } return r_cnt == 0 ? "Dire" : "Radiant"; } }; [/cpp] 本代码提交AC,用时752MS。]]>

LeetCode Task Scheduler

LeetCode Task Scheduler Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the least number of intervals the CPU will take to finish all the given tasks. Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
  1. The number of tasks is in the range [1, 10000].

CPU需要处理一系列任务,限制条件是两个相同的任务被处理的时间至少需要间隔n时刻,问CPU最少需要多长时间能处理完所有任务。 比赛没做出来,参考讨论区。 根据题意,两个任务被处理至少需要间隔n时刻,所以我们可以认为CPU处理一批任务的循环周期是n+1,比如0时刻处理了任务’A’,则至少要到n+1时刻才能再次处理任务’A’,中间间隔了n时刻。 假设数量最多的任务的数量是k,则我们至少需要k个周期才能把这个任务处理完。为了让CPU处理的空闲时间更少,我们在一个周期内尽量让CPU处理的任务更丰富。所以想象一下,我们有k个桶,相当于k个周期,每个周期,我们把频率最高的任务拿出来,分发到这最多k个桶中。如果所有不同任务都分发完了还没有填满一个桶,则说明该桶内(周期内)CPU需要空闲等待。 比如样例中,最高频的任务是A和B,都是3,所以我们至少需要3个桶。每个桶的容量是n+1=3,相当于相同任务的距离是3。每次我们把A和B扔到不同的桶中,前两个桶各有一个空闲等待,第三个桶因为结束了,所以不需等待。 因为每次都需要取出最高频的任务去分发,所以用一个优先队列来实时更新频率排名。 完整代码如下: [cpp] class Solution { public: int leastInterval(vector<char>& tasks, int n) { map<char, int> count; for (const auto& c : tasks)++count[c]; priority_queue<pair<int, char>> pq; for (const auto& p : count)pq.push({ p.second,p.first }); int cycle = n + 1, time = 0; while (!pq.empty()) { vector<pair<int, char>> tmp; int tsk = 0; for (int i = 0; i < cycle; ++i) { if (!pq.empty()) { tmp.push_back(pq.top()); pq.pop(); ++tsk; } } for (auto& t : tmp) { if (–t.first) { pq.push(t); } } time += pq.empty() ? tsk : cycle; } return time; } }; [/cpp] 本代码提交AC,用时95MS。]]>