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].

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 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.

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
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

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
Write a program to find the n^th 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 ≤ 10⁶, 0 < primes[i] < 1000.

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
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 n^th 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: L₁, L₂, and L₃.
4. Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

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
Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.
For example,
Given n = 3,
You should return the following matrix:

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

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
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].

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。