LeetCode Reshape the Matrix In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data. You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively. The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were. If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix. Example 1:

Input:
nums =
[[1,2],
 [3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

Input:
nums =
[[1,2],
 [3,4]]
r = 2, c = 4
Output:
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

1. The height and width of the given matrix is in range [1, 100].
2. The given r and c are all positive.

---

把一个n*m的矩阵按行重新组织为r*c的矩阵，相当于MATLAB的reshape函数。 简单题，新矩阵中第cnt个数，在原矩阵中的位置是(cnt/m,cnt%m)。 代码如下： [cpp] class Solution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { int n = nums.size(), m = nums[0].size(); if (n*m != r*c)return nums; vector<vector<int>> ans(r, vector<int>(c, 0)); for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { int cnt = i*c + j; ans[i][j] = nums[cnt / m][cnt % m]; } } return ans; } }; [/cpp] 本代码提交AC，用时62MS。]]>

LeetCode Array Partition I Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), …, (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible. Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

---

给定一个长度为2n的数组，要求把数组分成n组，即(a₁, b₁), (a₂, b₂), …, (a_n, b_n) ，使得每组的最小值之和最大。 使用贪心策略，比如样例中，4和3肯定不能和1配对，因为1肯定是最小的，不能拿很大的数和1陪葬，所以只拿2和1配对；然后3、4配对。所以规律就是对数组排序，从小到大每两个配对。那么每组最小值之和就是第0、2、4…个数之和。 代码如下： [cpp] class Solution { public: int arrayPairSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 0; for(int i = 0; i < nums.size(); i += 2) ans += nums[i]; return ans; } }; [/cpp] 本代码提交AC，用时92MS。]]>

hihoCoder 1496-寻找最大值

---

给定一个数组，要求从中选出两个数a和b（它们的下标不能相同），使得乘积a*b*(a&b)最大。 这题的AC之路还挺有意思的，首先我尝试了$$O(n^2)$$的暴力方法，不出所料的TLE了，不过也得了40分。所以$$O(n^2)$$的方法肯定是不行的，我就想各种O(n)的方法。 首先分析一下a*b*(a&b)，有两个部分，a*b和a&b。最优的方案当然是求a*b*(a&b)整体的最大值，但是这需要$$O(n^2)$$。次优的方案是求a*b或者a&b的最大值，然后看看整体a*b*(a&b)会不会也是最大呢。 我先考虑了a&b，因为要使a&b越大，则a和b的高位要有很多一致的’1’，这样，a和b本身也就比较大，进而a*b也就比较大。但还是需要$$O(n^2)$$的时间，只不过循环过程中省略了a*b*(a&b)的计算。提交之后WA了，而且是0分，推断这种解法不可行。 后来尝试了求a*b的最大值，想法也和求a&b的最大值类似。如果a*b越大，则a,b本身也比加大，导致a&b也会比较大吧？求a*b的最大值，就好办多了，当然不能暴力两层循环，要不然又TLE。我们只需一次遍历，找到最大和次大的两个数，则他们的乘积肯定是最大的。这次提交之后，虽然也是WA，但是居然得了80分。 所以我就想，可能真的是a,b越大，则a*b*(a&b)也越大。后来一想可能会遇到a很大，二进制是10000；但是b也很大，而且是只比a小1，二进制是01111，这样虽然a*b很大，但是a&b就是0了。导致整体a*b*(a&b)是0。于是我进一步扩大了范围，记录前3大的元素first,second和third，他们之间有3个组合(first,second)、(first,third)、(second,third)，只需在这3个对里面求最大就好了。我当时的想法是，虽然first和second会遇到10000和01111的情况，但是second和third可能会不会了。提交之后，居然真的AC了！ 代码如下： [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> #include<vector> #include<climits> #include<cfloat> using namespace std; typedef long long LL; vector<LL> nums(100005, 0); int main() { //freopen("input.txt", "r", stdin); int t, n; scanf("%d", &t); while (t–) { scanf("%d", &n); LL first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN; for (int i = 0; i < n; ++i) { scanf("%d", &nums[i]); if (nums[i] > first) { third = second; second = first; first = nums[i]; } else if (nums[i] > second) { third = second; second = nums[i]; } else if (nums[i] > third) { third = nums[i]; } } LL ans = max(first*second*(first&second), first*third*(first&third)); ans = max(ans, second*third*(second&third)); printf("%lld\n", ans); } return 0; } [/cpp] 本代码提交AC，用时85MS。 后来看前几名AC的代码，好多是先对数组排序，然后从大到小求a*b*(a&b)的最大值，这样最坏复杂度还是$$O(n^2)$$，但是好像也能AC。]]>

289. Game of Life 289. Game of Life

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

Input: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

Follow up:

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems? 289. Game of Life

---

本题有关康威生命游戏，第一次听说。。。 给一个二维矩阵，0表示死亡，1表示活着。每个细胞根据周围8个细胞的状态，有如下跳转规则：

1. 活着的细胞周围有少于2个活着的细胞，则该细胞死亡
2. 活着的细胞周围有2个或3个活着的细胞，则该细胞继续活着
3. 活着的细胞周围有多于3个活着的细胞，则该细胞死亡
4. 死亡的细胞周围有3个活着的细胞，则该细胞复活

最简单的方法是复制一个矩阵，遍历原矩阵然后更新新矩阵。但本题的难点是，要在in-place的情况下更新原矩阵。如果还是像之前那样更新的话，当前细胞的状态更新之后，会影响到后续细胞的判断，不可行。 参考网上题解，使用编码方法。 因为输入是以int来存储细胞状态的，int可以存储的状态数就很多了，不仅仅局限于0和1。 假设细胞状态重新编码如下：

• 0：0→0，原来死亡，现在还死亡
• 1：1→1，原来活着，现在还活着
• 2：1→0，原来活着，现在死亡
• 3：0→1，原来死亡，现在活着

则还是像之前一样，遍历细胞的周围8个点，根据以上编码可以知道周围细胞更新前的状态，比如某个邻居的状态是2，则知道该邻居更新前是1活着的。 所有细胞都更新完之后，需要复原成0，1编码，则状态为0和2表示新状态是死亡0，状态是1和3表示新状态是活着1。这可以用新状态对2取余数得到。 代码如下：

class Solution {
public:
    void gameOfLife(vector<vector<int> >& board)
    {
        int m = board.size(), n = 0;
        if (m != 0)
            n = board[0].size();
        if (m == 0 || n == 0)
            return;
        vector<vector<int> > dirs = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int lives = 0;
                for (int k = 0; k < dirs.size(); ++k) {
                    int x = i + dirs[k][0], y = j + dirs[k][1];
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2))
                        ++lives;
                }
                if (board[i][j] == 1 || board[i][j] == 2) {
                    if (lives < 2 || lives > 3)
                        board[i][j] = 2;
                    else
                        board[i][j] = 1;
                }
                else if (lives == 3)
                    board[i][j] = 3;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                board[i][j] %= 2;
            }
        }
    }
};

本代码提交AC，用时3MS。

二刷。 很简单，也不用定什么规则，直接按位编码，第0位是原来的状态，0为死1为生，第1位是更新后的状态，依然是0为死1为生，所有状态更新完之后，右移一位即可。代码如下：

class Solution {
public:
	void gameOfLife(vector<vector<int>>& board) {
		int m = board.size(), n = board[0].size();

		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {

				int lives = 0;
				int u = max(0, i - 1), v = max(0, j - 1);
				int x = min(m, i - 1 + 3), y = min(n, j - 1 + 3);
				for (int a = u; a < x; ++a) {
					for (int b = v; b < y; ++b) {
						if (a == i && b == j)continue;
						if ((board[a][b] & 1) == 1)++lives;
					}
				}

				int curlive = (board[i][j] & 1);
				if (curlive == 1 && lives < 2) {
					board[i][j] = (board[i][j] | (0 << 1));
				}
				else if (curlive == 1 && (lives == 2 || lives == 3)) {
					board[i][j] = (board[i][j] | (1 << 1));
				}
				else if (curlive == 1 && (lives > 3)) {
					board[i][j] = (board[i][j] | (0 << 1));
				}
				else if (curlive == 0 && lives == 3) {
					board[i][j] = (board[i][j] | (1 << 1));
				}

			}
		}

		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				board[i][j] >>= 1;
			}
		}

	}
};

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

LeetCode Third Maximum Number Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example 1:

Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

---

找出一个数组中的第三大的数，如果不存在第三大的数，则返回最大的数。数组中可能会有重复数字。要求用O(n)的时间。 定义最大的数、第二大、第三大的数分别为first、second、third，遍历数组然后不断更新这三个数，更新的方法是从最大数错位赋值，很容易理解。求数组中第二大的数也是类似的道理。 看代码就很好理解了，注意数组中可能会有INT_MIN，所以需要用long数据类型。另外，本题要求的第三大是相异数字的排名，比如第三个样例，第三大的应该是1，而不是2，虽然有第二个2排名第三，但和第二名重复了，不能算，这一点在两个else if中需要保证严格小于第一名或第二名。 [cpp] class Solution { public: int thirdMax(vector<int>& nums) { long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN; for (int i = 0; i < nums.size(); ++i) { if (nums[i] > first) { third = second; second = first; first = nums[i]; } else if (nums[i] < first && nums[i] > second) { third = second; second = nums[i]; } else if (nums[i] < second && nums[i] > third)third = nums[i]; } if (third == LONG_MIN)return first; else return third; } }; [/cpp] 本代码提交AC，用时6MS。]]>

228. Summary Ranges2

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

Input:  [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"] Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.28. Summary Ranges

---

给定一个数组，把数组汇总成若干个连续的区间，以字符串的形式给出。
方法是判断两个相邻的数之差是否为1，不是1则前面的构成一个区间，转换为字符串输出。判断前一个区间只有一个数还是有多个数的方法是区间的起止位置i,j是否相差1，如果是，则只有一个数，否则有多个数。
注意最后一个区间需要在while循环外部判断。代码如下：

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums)
    {
        vector<string> ans;
        int n = nums.size(), i = 0, j = 1;
        if (n == 0)
            return ans;
        while (j < n) {
            if (nums[j] – nums[j – 1] == 1)
                ++j;
            else {
                if (j – i == 1)
                    ans.push_back(to_string(nums[i]));
                else
                    ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
                i = j++;
            }
        }
        if (j – i == 1)
            ans.push_back(to_string(nums[i]));
        else
            ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
        return ans;
    }
};

本代码提交AC，用时0MS。
还有一种解法利用了二分查找的思路，很有意思，参考讨论区。
假如给定的数组是[1,2,3,4,5,…,10000,20000]，如果还是用上述方法，时间复杂度是O(n)，至少需要遍历一遍数组。但是数组的前10000个数是严格有序且连续递增的，如果能把这一部分识别出来，直接转换为”1->10000″，则速度会大大提高。
二分查找的思路是，对于给定区间[a,…,b]，假设其在数组中的下标起点分别为[i,…,j]，则如果b-a==j-i，说明[a,b]之间是类似上面的[1,2,…,10000]的情况的，因为数组中没有重复元素，所以区间有j-i个元素，且元素最大值和最小值的差b-a也是j-i，说明他们是一个连续的有序区间，我们直接把这个区间转换为”a->b”。
否则如果j-i!=b-a，则取中点mid=(i+j)/2，递归在[i,mid]和[mid+1,j]进行。
有一种情况需要注意的是，分割出来的区间可能需要合并，比如[1,2,3,4,5,6,8]，初始i[1,..,8]不满足b-a==j-i，所以递归在[1,2,3,4]和[5,6,8]进行。左边转换为了”1->4″，右边还需要递归，假设转换为了”5->6″和”8″，那么”1->4″和”5->6″是需要合并的。所以我们在插入”5->6″时，看看之前得到的区间”1->4″的end是否和当前区间”5->6″的start只差1，如果是，则需要合并，更新之前区间的end为现在要插入区间的end，变成了”1->6″。
完整代码如下：

class Solution {
private:
    struct Range {
        int start, end;
        Range(int s, int e)
            : start(s)
            , end(e){};
    };
    void add2Ans(int a, int b, vector<Range>& ranges)
    {
        if (ranges.empty() || ranges[ranges.size() – 1].end != a – 1) {
            ranges.push_back(Range(a, b));
        }
        else {
            ranges[ranges.size() – 1].end = b;
        }
    }
    void helper(vector<int>& nums, int start, int end, vector<Range>& ranges)
    {
        if (start == end || end – start == nums[end] – nums[start]) {
            add2Ans(nums[start], nums[end], ranges);
            return;
        }
        int mid = start + (end – start) / 2;
        helper(nums, start, mid, ranges); // 先左区间
        helper(nums, mid + 1, end, ranges); // 后右区间
    }

public:
    vector<string> summaryRanges(vector<int>& nums)
    {
        vector<string> ans;
        if (nums.empty())
            return ans;
        vector<Range> ranges;
        helper(nums, 0, nums.size() – 1, ranges);
        for (const auto& r : ranges) {
            if (r.start == r.end)
                ans.push_back(to_string(r.start));
            else
                ans.push_back(to_string(r.start) + "->" + to_string(r.end));
        }
        return ans;
    }
};

本代码提交AC，用时0MS。
这个代码在数据有很多连续区间时，接近O(lgn)的复杂度。但是当数据全是不连续的时，比如[1,3,5,7,9]，则只有到递归到最深层start==end（即针对单个数字）时，才得到一个区间，所以退化为O(n)的算法。
如果再follow up可能有重复元素时，上述二分查找的方法就不管用了，因为属于一个区间的不一定满足b-a==j-i，比如[1,2,2,2,3]，b-a=2，而j-i=4。此时只能用第一种O(n)的方法：

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums)
    {
        vector<string> ans;
        if (nums.empty())
            return ans;
        int i = 0, j = 1, n = nums.size();
        while (j < n) {
            while (j < n && (nums[j] == nums[j – 1] || nums[j] – nums[j – 1] == 1))
                ++j; // 考虑重复元素
            if (j >= n)
                break;
            if (j – 1 == i)
                ans.push_back(to_string(nums[i]));
            else
                ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
            i = j++;
        }
        if (j – 1 == i)
            ans.push_back(to_string(nums[i]));
        else
            ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j – 1]));
        return ans;
    }
};

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

二刷。更加鲁邦容易理解的代码：

class Solution {
public:
	vector<string> summaryRanges(vector<int>& nums) {
		vector<vector<int>> ranges;
		int i = 0, n = nums.size();
		while (i < n) {
			int j = i + 1;
			while (j < n&&nums[j] == nums[j - 1] + 1)++j;
			ranges.push_back({ nums[i],nums[j - 1] });
			i = j;
		}
		vector<string> ans;
		for (int i = 0; i < ranges.size(); ++i) {
			if (ranges[i][0] == ranges[i][1]) {
				ans.push_back(to_string(ranges[i][0]));
			}
			else {
				ans.push_back(to_string(ranges[i][0]) + "->" + to_string(ranges[i][1]));
			}
		}
		return ans;
	}
};

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

73. Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

---

给定一个矩阵，如果元素(i,j)是0，则把第i行和第j列都赋值为0。要求用常数空间。 因为前面的元素如果赋值为0，会影响后面的行列，所以是否赋值为0需要预先存起来，最后再一次性处理矩阵。 可以用一个行向量row[]和一个列向量col[]分别存储第i行和第j列是否应该赋值为0，具体方法就是扫描矩阵，如果matrix[i][j]==0，则赋值row[i]=0和col[j]=0表明第i行和第j列应该被赋值为0。但是这种方法需要O(m+n)的空间。

为了不使用额外的空间，我们可以借用原矩阵的第一行和第一列当作上面的row[]和col[]，但是需要提前判断第一行和第一列是否应该被置为0。具体代码如下：

class Solution {
public:
    void setZeroes(vector<vector<int> >& matrix)
    {
        int m = matrix.size();
        if (m == 0)
            return;
        int n = matrix[0].size();
        if (n == 0)
            return;
        bool clearFirstRow = false, clearFirstColumn = false;
        for (int i = 0; i < m; ++i) { // first column
            if (matrix[i][0] == 0) {
                clearFirstColumn = true;
                break;
            }
        }
        for (int j = 0; j < n; ++j) { // first row
            if (matrix[0][j] == 0) {
                clearFirstRow = true;
                break;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0)
                    matrix[i][j] = 0;
            }
        }
        if (clearFirstRow) {
            for (int j = 0; j < n; ++j)
                matrix[0][j] = 0;
        }
        if (clearFirstColumn) {
            for (int i = 0; i < m; ++i)
                matrix[i][0] = 0;
        }
    }
};

本代码提交AC，用时59MS。

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 2 * 10^4
• It’s guaranteed that nums[i] fits in a 32 bit-signed integer.
• k >= 0

---

本题要把一个数组向右旋转k步，尽量想出3种方法。
首先，无论什么解法，都先判断一下n是否小于2，如果是的话，不管k是多少，都不必旋转了。其次，执行k%=n，因为移动n的倍数位相当于没移动。
暴力解法是每次保留最后一位数字，然后把前n-1个数往后移动一位，重复操作k次。代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        while (k–) {
            int last = nums[n – 1];
            int j = n – 2;
            while (j >= 0) {
                nums[j + 1] = nums[j];
                –j;
            }
            nums[0] = last;
        }
    }
};

本代码提交TLE，过不了最后一个大数据集，因为最坏是O(n^2)复杂度。
稍微高明一点的方法是，先把末尾k位数保存到一个临时数组中，然后一次性把前n-k个数移动到末尾，最后再把临时数组中的数据回帖到原数组开头。完整代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        vector<int> right(nums.begin() + n – k, nums.end());
        int i = n – k – 1, j = n – 1;
        while (i >= 0)
            nums[j–] = nums[i–];
        i = 0;
        while (i < k) {
            nums[i] = right[i];
            ++i;
        }
    }
};

本代码提交AC，用时29MS。
还可以对上述解法稍加变换，即把末尾k位数保存到临时数组right中，然后把原数组的前n-k个数拼接到right的后面，vector的拼接可以用insert。思路和上述算法是一样的。代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        vector<int> right(nums.begin() + n – k, nums.end());
        right.reserve(n);
        right.insert(right.end(), nums.begin(), nums.begin() + n – k);
        nums = right;
    }
};

本代码提交AC，用时19MS。
最后还有一种很巧妙的方法，比如题目中的例子，要对1,2,3,4,5,6,7向右旋转3位，我们可以首先对整个数组逆序一下（reverse），编程7,6,5,4,3,2,1，然后再对前k=3，后n-k=4个数分别逆序，得到5,6,7,1,2,3,4，这不就是最终答案吗，很有意思。数组逆序可以直接用STL中的reverse，其实也可以自己实现，就是收尾元素不断交换swap。这种解法是常数空间复杂度、O(n)时间复杂度的，代码如下：

class Solution {
private:
    void my_reverse(vector<int>::iterator bg, vector<int>::iterator ed)
    {
        –ed;
        while (bg < ed) {
            swap(*bg, *ed);
            ++bg;
            –ed;
        }
    }
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        my_reverse(nums.begin(), nums.end());
        my_reverse(nums.begin(), nums.begin() + k);
        my_reverse(nums.begin() + k, nums.end());
    }
};

本代码提交AC，用时19MS。

57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

---

一个已经排好序的区间数组，现在要插入一个新的区间，并且如果能合并则需要合并。最简单的方法就是把新加入的区间和原有区间一起排个序，然后统一合并，问题就转换为LeetCode Merge Intervals了。

但是原有区间数组是已经按start排序了，所以有更简单的办法。我们可以分三个过程插入新的区间，首先把明显小于新区间的区间放到结果数组中，然后处理所有可能和新区间有overlap的区间，不断合并并更新新区间，直到无法再合并时，把新区间加入结果数组中，最后把明显大于新区间的区间放到结果数组中。

完整代码如下：

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval)
    {
        vector<Interval> ans;
        int i = 0, n = intervals.size();
        while (i < n && intervals[i].end < newInterval.start)
            ans.push_back(intervals[i++]);
        while (i < n && newInterval.end >= intervals[i].start) {
            newInterval.start = min(newInterval.start, intervals[i].start);
            newInterval.end = max(newInterval.end, intervals[i].end);
            ++i;
        }
        ans.push_back(newInterval);
        while (i < n)
            ans.push_back(intervals[i++]);
        return ans;
    }
};

本代码提交AC，用时13MS。