Tag Archives: 模拟

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的方式实现,代码如下:

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";
	}
};

本代码提交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扔到不同的桶中,前两个桶各有一个空闲等待,第三个桶因为结束了,所以不需等待。
因为每次都需要取出最高频的任务去分发,所以用一个优先队列来实时更新频率排名。
完整代码如下:

class Solution {
public:
	int leastInterval(vector<char>& tasks, int n) {
		map<char, int> count;
		for (const auto& c : tasks)++count;
		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;
	}
};

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

LeetCode Diagonal Traverse

LeetCode Diagonal Traverse
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

  1. The total number of elements of the given matrix will not exceed 10,000.

给定一个矩阵,要求以对角线的方式遍历该矩阵。
没什么特别的技巧,模拟对角线走法即可。设置一个up变量,设置up=true表示向右上角走,i--,j++;up=false表示向左下角走,i++,j--。
边界情况处理有点复杂。当向右上角走时,有两种情况,如果越过了右边界,比如样例中3往右上角走了一步,则要回到6的位置,方法是i+=2,j=n-1;如果没有越过右边界,只是越过了上边界,比如图中的1再往右上角走了一步,则只需要i=0。注意这两种判断的顺序不能乱,必须先判断是否越过了右边界,再判断是否越过了上边界。
当往左下角走时,越界处理的方法类似。如果越过了下边界,比如8再往左下角走了一步,则需要i=m-1,j+=2;如果只越过了左边界,比如4再往左下角走了一步,则只需要j=0。
完整代码如下:

class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
		int m = matrix.size(), n = 0;
		if (m != 0)n = matrix[0].size();
		if (m == 0 || n == 0)return vector<int>();
		vector<int> ans;
		int i = 0, j = 0;
		bool up = true;
		while (!(i == m - 1 && j == n - 1)) {
			ans.push_back(matrix[i][j]);
			if (up) {
				--i;
				++j;
				if (j >= n) {
					i += 2;
					j = n - 1;
					up = false;
				}
				if (i < 0) {
					i = 0;
					up = false;
				}
			}
			else {
				++i;
				--j;
				if (i >= m) {
					i = m - 1;
					j += 2;
					up = true;
				}
				if (j < 0) {
					j = 0;
					up = true;
				}
			}
		}
		ans.push_back(matrix[m - 1][n - 1]);
		return ans;
	}
};

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

LeetCode Elimination Game

LeetCode Elimination Game
There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.
We keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Find the last number that remains starting with a list of length n.
Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6

本题介绍了一个消除游戏,就是1~n排列了n个数,先从左往右每隔一个数消除一个(包含1),然后从右往左每隔一个数消除一个(包含最后一个数),如此循环,直到只剩一个数,要求输出这个数。
我一开始以为这是个模拟题,直接用STL的双向链表list模拟了,代码如下:

class Solution {
public:
	int lastRemaining(int n) {
		list<int> l;
		for (int i = 1; i <= n; i++)l.push_back(i);
		while (l.size() != 1) {
			list<int>::iterator it = l.begin();
			while (it != l.end()) {
				it = l.erase(it);
				if (it != l.end())++it;
			}
			if (l.size() == 1)break;
			list<int>::reverse_iterator rit = l.rbegin();
			while (rit != l.rend()) {
				rit = list<int>::reverse_iterator(l.erase(--(rit.base())));
				if (rit != l.rend())++rit;
			}
			if (l.size() == 1)break;
		}
		return *l.begin();
	}
};

很不幸,本代码提交TLE,超时了。
网上查题解,这个人讲得比较清楚。一开始1,2,3,4,5,6,7,8,...,n,第一次从左往右消除之后,剩余2,4,6,8...,n,其实就相当于2*(1,2,3,4,...n/2)。但是这个时候我们要对1,2,3,4,...n/2从右往左消除了,那么从右往左和从左往右消除得到的结果有什么规律呢,他们的结果应该是呈镜像对称的,也就是说如果长度为n/2的话,如果从左往右的结果为x,那么从右往左的结果就应该是n/2+1-x;同理如果从右往左的结果是y的话,那么从左往右的结果就应该是n/2+1-y。
代码实现为:

class Solution {
public:
	int lastRemaining(int n) {
		return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
	}
};

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

LeetCode Super Ugly Number

LeetCode Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.


这题是超级丑数,再也不想见到丑数了...
其实本质和LeetCode Ugly Number II没什么两样,只不过素数不局限于2,3,5了,只要用一个数组idx来存储不同素数对应的小丑数的下标。完整代码如下:

class Solution {
public:
	int nthSuperUglyNumber(int n, vector<int>& primes) {
		if (n == 1)return 1;
		vector<int> ugly_nums = { 1 };
		vector<int> idx(primes.size(), 0);
		int next_ugly_num = 0;
		while (ugly_nums.size() < n) {
			next_ugly_num = INT_MAX;
			for (int i = 0; i < primes.size(); i++) {
				next_ugly_num = min(next_ugly_num, primes[i] * ugly_nums[idx[i]]);
			}
			for (int i = 0; i < primes.size(); i++) {
				if (next_ugly_num == primes[i] * ugly_nums[idx[i]]) {
					idx[i]++;
				}
			}
			ugly_nums.push_back(next_ugly_num);
		}
		return next_ugly_num;
	}
};

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

LeetCode Ugly Number II

LeetCode Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.
Hint:

  1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
  2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
  3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
  4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

本题是LeetCode Ugly Number的升级版,题目还是不错的,要求出第n个丑数是什么。非常naive的方法就是从1开始不断调用LeetCode Ugly Number中判断丑数的函数,如果是丑数,cnt++,直到cnt==n时输出第n个丑数,但是hint里指出很多都不是丑数,所以这样很浪费时间。
hint里同时给出了怎样直接生成所有丑数序列的方法,不错。
主要思路是这样的,每个丑数都是更小的丑数乘以2,3或5得到的,所以我们可以维护一个丑数序列,要求更大的丑数时,用更小的丑数乘以2,3,5来得到,但是2,3,5对应的那个小丑数并不是一样的。举个例子,首先丑数序列中只有{1}这个元素,对于2,3,5,初始的时候i2=i3=i5=0,表明2,3,5对应丑数序列中的第0个元素1,此时用1分别乘以2,3,5得到的最小值是2,所以下一个丑数是1*2得到的,那么i2++去对应下一个小丑数,i3和i5对应的下标不变。不断这样产生丑数。
不太好描述,请看代码:

class Solution {
public:
	int nthUglyNumber(int n) {
		if (n == 1)return 1;
		vector<int> ugly_num = { 1 };
		int i2 = 0, i3 = 0, i5 = 0;
		int next_ugly_num = 0;
		while (ugly_num.size() < n) {
			next_ugly_num = min(min(ugly_num[i2] * 2, ugly_num[i3] * 3), ugly_num[i5] * 5);
			if (next_ugly_num == ugly_num[i2] * 2)i2++;
			if (next_ugly_num == ugly_num[i3] * 3)i3++;
			if (next_ugly_num == ugly_num[i5] * 5)i5++;
			ugly_num.push_back(next_ugly_num);
		}
		return next_ugly_num;
	}
};

代码很简洁,但是要想到这个思路还是有难度的。本代码提交AC,用时16MS。

LeetCode Spiral Matrix II

LeetCode Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

要求按螺旋方式把n阶方阵填满,和LeetCode Spiral Matrix几乎一样,而且还是方阵。直接一圈一圈填就好了。
完整代码如下:

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> vMatrix(n, vector<int>(n, 0));
		int sx = 0, sy = 0, tx = n, ty = n, k = 1;
		while (k <= n*n) {
			for (int j = sy; j < ty; j++)
				vMatrix[sx][j] = k++;
			for (int i = sx + 1; i < tx; i++)
				vMatrix[i][ty - 1] = k++;
			for (int j = ty - 2; sx + 1 < tx && j >= sy; j--) // 满足上一个条件sx+1<tx
				vMatrix[tx - 1][j] = k++;
			for (int i = tx - 2; ty - 2 >= sy && i > sx; i--) // 满足上一个条件ty-2>=sy
				vMatrix[i][sy] = k++;
			sx++;
			sy++;
			tx--;
			ty--;
			if (sx >= tx || sy >= ty)break;
		}
		return vMatrix;
	}
};

本代码提交AC,用时3MS。
二刷。和LeetCode Spiral Matrix类似,更安全的方法,如下:

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int cnt = 1;
        int start_row = 0, start_col = 0, end_row = n - 1, end_col = n - 1;
        while(start_row <= end_row && start_col <= end_col) {
            for(int j = start_col; j <= end_col; ++j) {
                ans[start_row][j] = cnt++;
            }
            ++start_row;
            for(int i = start_row; i <= end_row; ++i) {
                ans[i][end_col] = cnt++;
            }
            --end_col;
            if(start_row <= end_row) {
                for(int j = end_col; j >= start_col; --j) {
                    ans[end_row][j] = cnt++;
                }
            }
            --end_row;
            if(start_col <= end_col) {
                for(int i = end_row; i >= start_row; --i) {
                    ans[i][start_col] = cnt++;
                }
            }
            ++start_col;
        }
        return ans;
    }
};

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

LeetCode Spiral Matrix

LeetCode Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].


把矩阵按螺旋形打印出来,很有意思的一道题,我隐隐约约记得本科找工作的时候有这么一道笔试题。中等难度,需要多次调试修改才能AC。
思路是标记矩阵的左上角和右下角两个坐标,分别为sx,sy和tx,ty。然后每次从左上角开始,绕一圈,则起点sx,sy都加1,终点tx,ty都减1。如此循环,直到终点跑到起点上面去了。
需要注意后两个for循环的条件,要依次同时满足上一个条件,因为有可能遇到行向量(第三个for)或者列向量(第四个for)。完整代码如下:

class Solution {
public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> vSpiralOrder;
		if (matrix.size() == 0)return vSpiralOrder;
		int sx = 0, sy = 0, tx = matrix.size(), ty = matrix[0].size();
		while (true) {
			for (int j = sy; j < ty; j++)
				vSpiralOrder.push_back(matrix[sx][j]);
			for (int i = sx + 1; i < tx; i++)
				vSpiralOrder.push_back(matrix[i][ty - 1]);
			for (int j = ty - 2; sx + 1 < tx && j >= sy; j--) // 满足上一个条件sx+1<tx
				vSpiralOrder.push_back(matrix[tx - 1][j]);
			for (int i = tx - 2; ty - 2 >= sy && i > sx; i--) // 满足上一个条件ty-2>=sy
				vSpiralOrder.push_back(matrix[i][sy]);
			sx++;
			sy++;
			tx--;
			ty--;
			if (sx >= tx || sy >= ty)break;
		}
		return vSpiralOrder;
	}
};

本代码提交AC,用时0MS。
二刷。更安全的做法(https://discuss.leetcode.com/topic/3713/super-simple-and-easy-to-understand-solution):

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty() || matrix[0].empty()) return ans;
        int start_row = 0, start_col = 0, end_row = matrix.size() - 1, end_col = matrix[0].size() - 1;
        while(start_row <= end_row && start_col <= end_col) {
            for(int j = start_col; j <= end_col; ++j) {
                ans.push_back(matrix[start_row][j]);
            }
            ++start_row;
            for(int i = start_row; i <= end_row; ++i) {
                ans.push_back(matrix[i][end_col]);
            }
            --end_col;
            if(start_row <= end_row) { // 防止行向量
                for(int j = end_col; j >= start_col; --j) {
                    ans.push_back(matrix[end_row][j]);
                }
            }
            --end_row;
            if(start_col <= end_col) { // 防止列向量
                for(int i = end_row; i >= start_row; --i) {
                    ans.push_back(matrix[i][start_col]);
                }
            }
            ++start_col;
        }
        return ans;
    }
};

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

LeetCode ZigZag Conversion

LeetCode ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".


估计大多数人看到这题都不知道Zigzag具体是怎样一个pattern,题目也只给了一个例子,不好找规律,这是维基百科上介绍Zigzag时给的一张图片:

也就是先下后上来回走两条路径,下去和上来的路径是各自平行的。这一题中,下去是竖直下去的,上来是45°斜着走上来的。使用数组模拟走路过程即可。
代码如下:

class Solution {
public:
	string convert(string s, int numRows) {
		int n = s.size();
		if (numRows >= n || numRows == 1)
			return s;
		vector<vector<char>> board(numRows);
		int k = 0, i = 0;
		bool up = false;
		while (k < n)
		{
			board[i].push_back(s[k]);
			if (i >= numRows - 1)
				up = true;
			else if (i <= 0)
				up = false;
			if(up)
				i--;
			else
				i++;
			k++;
		}
		string ret = "";
		for (int i = 0; i < numRows; i++)
			for (int j = 0; j < board[i].size(); j++)
					ret += board[i][j];
		return ret;
	}
};

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