Monthly Archives: September 2016

LeetCode Add Binary

67. Add Binary

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

  • Each string consists only of '0' or '1' characters.
  • 1 <= a.length, b.length <= 10^4
  • Each string is either "0" or doesn’t contain any leading zero.

把两个二进制字符串相加,注意进位即可。 把while (i >= 0 && j >= 0)改成while (i >= 0 || j >= 0),这样就只需要一个while循环了,只不过循环体里面求sum需要判断一下i,j。完整代码如下:

class Solution {
public:
    string addBinary(string a, string b)
    {
        int i = a.size() – 1, j = b.size() – 1;
        string ans = "";
        bool carry = false;
        while (i >= 0 || j >= 0) {
            int sum = (i >= 0 ? (a[i] – ‘0’) : 0) + (j >= 0 ? (b[j] – ‘0’) : 0);
            sum += carry ? 1 : 0;
            if (sum >= 2) {
                ans.push_back(sum – 2 + ‘0’);
                carry = true;
            }
            else {
                ans.push_back(‘0’ + sum);
                carry = false;
            }
            i–;
            j–;
        }
        if (carry)
            ans.push_back(‘1’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

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

二刷。更简洁的代码:

class Solution {
public:
	string addBinary(string a, string b) {
		int m = a.size(), n = b.size();
		string ans = "";
		int i = m - 1, j = n - 1;
		int carry = 0;
		while (i >= 0 || j >= 0) {
			int u = i >= 0 ? a[i] - '0' : 0;
			int v = j >= 0 ? b[j] - '0' : 0;
			int sum = u + v + carry;
			carry = sum / 2;
			ans.push_back('0' + (sum % 2));
			--i;
			--j;
		}
		if (carry != 0)ans.push_back('1');
		reverse(ans.begin(), ans.end());
		return ans;
	}
};

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

LeetCode Permutation Sequence

60. Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

求1~n的所有排列中,第k大的数。肯定不可能先用LeetCode Permutations把所有排列找出来,然后sort取第k个,肯定TLE,所以换思路。

假设给的例子中,原数组为s=”123″,要求第5大的数,即”312″。我们首先找出这个数的首位数字是什么。我们知道以某个数字固定开头的排列个数=(n-1)!=2!=2,即以1和2开头的排列数共有2*2=4个,而我们要求的是第5大的数,所以这个数开头必须是3=5/2+1=ceil( k / (n-1)! )=m。
确定了第一位之后,把3从原数组s中删掉,然后递归查找剩余数组s=”12″中第5-2*2=1=k-(m-1)*(n-1)!位的排列。显然就是最小的“12”了,然后拼起来为”312″。

完整代码如下:

class Solution {
public:
    vector<int> fact(int n)
    {
        vector<int> vFact;
        vFact.push_back(1); // 0!=1
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            ans *= i;
            vFact.push_back(ans);
        }
        return vFact;
    }
    char work(string& candidates, vector<int>& vFact, int& k)
    {
        int tmp = vFact[candidates.size() – 1];
        int idx = ceil(k / float(tmp));
        idx–;
        char ans = candidates[idx];
        candidates.erase(idx, 1);
        k -= idx * tmp;
        return ans;
    }
    string getPermutation(int n, int k)
    {
        vector<int> vFact = fact(n);
        string candidates = string("123456789").substr(0, n);
        string ans(n, ‘ ‘);
        for (int i = 0; i < n; i++)
            ans[i] = work(candidates, vFact, k);
        return ans;
    }
};

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

二刷。直接DFS的过程就是从小到大排序的过程,DFS到第k个排列的时候返回即可:

class Solution {
public:
	void dfs(string &s, int n, vector<int>& visited, int k, int &m, string &ans) {
		if (m == k)return;

		if (s.size() == n) {
			++m;
			if (m == k)
				ans = s;
			return;
		}
		for (int i = 1; i <= n; ++i) {
			if (visited[i] == 0) {
				s.push_back('0' + i);
				visited[i] = 1;
				dfs(s, n, visited, k, m, ans);
				s.pop_back();
				visited[i] = 0;
			}
		}
	}
	string getPermutation(int n, int k) {
		string s = "", ans = "";
		vector<int> visited(n + 1, 0);
		int m = 0;
		dfs(s, n, visited, k, m, ans);
		return ans;
	}
};

本代码提交AC,用时1356MS,太慢了,还是用之前的方法吧。

LeetCode Minimum Path Sum

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

一个网格,每个格子中都有一个数字,问从左上角走到右下角,求走过的格子数字之和最小值是多少。 和LeetCode Unique Paths II是一样的,一个格子只可能从其左边或者上边的格子而来,所以求两者最小值即可。不过要注意边界问题,完整代码如下:

class Solution {
public:
    int minPathSum(vector<vector<int> >& grid)
    {
        vector<int> dp(grid[0].size(), 0);
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                int top = i == 0 ? INT_MAX : dp[j];
                int left = j == 0 ? INT_MAX : dp[j – 1];
                if (i == 0 && j == 0)
                    dp[j] = grid[i][j];
                else
                    dp[j] = (top < left ? top : left) + grid[i][j];
            }
        }
        return dp[grid[0].size() – 1];
    }
};

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

LeetCode Unique Paths II

63. Unique Paths II

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

承接LeetCode Unique Paths,只是把网格中设置了障碍,第一思路是DFS,如果下一步能走,则递归深入搜索,否则返回。完整代码如下:

class Solution {
public:
    void dfs(vector<vector<int> >& obstacleGrid, int x, int y, int& numPath)
    {
        if (obstacleGrid[x][y] == 1)
            return;
        if (x == obstacleGrid.size() – 1 && y == obstacleGrid[0].size() – 1)
            numPath++;
        else {
            if (y + 1 < obstacleGrid[0].size())
                dfs(obstacleGrid, x, y + 1, numPath);
            if (x + 1 < obstacleGrid.size())
                dfs(obstacleGrid, x + 1, y, numPath);
        }
    }
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)
    {
        int numPath = 0;
        dfs(obstacleGrid, 0, 0, numPath);
        return numPath;
    }
};

但是TLE失败:-(

查题解,恍然大悟,DP解决。设dp[j]为从左上角到obstacleGrid[i][j]共有多少种方案,如果obstacleGrid[i][j]==1,则不可能到达这一点,dp[j]=0;否则,可以从[i][j-1]和[i-1][j]两个点到达[i][j],即dp[j]=dp[j]+dp[j-1]。因为只用了一个数组保存中间结果,所以右边的dp[j]相当于dp[i-1][j],dp[j-1]相当于dp[i][j-1],左边的dp[j]才是dp[i][j]。
$$dp[i][j]=\begin{cases}0\quad\text{if obstacleGrid[i][j]==1}\\dp[i-1][j]+dp[i][j-1]\quad\text{otherwise}\end{cases}$$

完整代码如下:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid)
    {
        vector<int> dp(obstacleGrid[0].size(), 0);
        if (obstacleGrid[0][0] == 0)
            dp[0] = 1; // caution!
        for (int i = 0; i < obstacleGrid.size(); i++) {
            for (int j = 0; j < obstacleGrid[i].size(); j++) {
                if (obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else
                    dp[j] += j == 0 ? 0 : dp[j – 1];
            }
        }
        return dp[obstacleGrid[0].size() - 1];
    }
};

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

LeetCode Unique Paths

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?


Above is a 7 x 3 grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Constraints:

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

问从左上角走到右下角一共有多少种方案,每次只能往右或者下走。很简单的题,高中学过排列组合的都知道。 假设右下和左上的坐标之差为(x,y),则从左上走到右下一共需要走x+y步,可以分为x步往右走,y步往下走。每一步都可以选择往右或者往下走,所以总的方案数为$C_{x+y}^x==C_{x+y}^y$,用x,y中的较小者来算就可以了,计算方法就是高中数学老师教的啦:-) 完整代码如下

class Solution {
public:
    int uniquePaths(int m, int n)
    {
        int x = m – 1, y = n – 1;
        int z = x + y, u = x < y ? x : y;
        double ans = 1.0;
        for (int i = 1; i <= u; i++) {
            ans *= z;
            ans /= i;
            z–;
        }
        return ans;
    }
};

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

LeetCode Spiral Matrix II

59. Spiral Matrix II

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
 [ 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。

三刷。朴素方法,依次填空:

class Solution {
public:
	vector<vector<int>> generateMatrix(int n) {
		vector<vector<int>> matrix(n, vector<int>(n, 0));
		int m = 0, i = 0, j = 0;
		int left = 0, right = n - 1, up = 1, down = n - 1;
		int dir = 1;// 0:left,1:right,2:up,3:down
		while (m != n * n) {
			matrix[i][j] = ++m;
			if (dir == 1) {
				if (j == right) {
					dir = 3;
					++i;
					--right;
				}
				else {
					++j;
				}
			}
			else if (dir == 3) {
				if (i == down) {
					dir = 0;
					--j;
					--down;
				}
				else {
					++i;
				}
			}
			else if (dir == 0) {
				if (j == left) {
					dir = 2;
					--i;
					++left;
				}
				else {
					--j;
				}
			}
			else if (dir == 2) {
				if (i == up) {
					dir = 1;
					++j;
					++up;
				}
				else {
					--i;
				}
			}
		}
		return matrix;
	}
};

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

LeetCode Spiral Matrix

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

把矩阵按螺旋形打印出来,很有意思的一道题,我隐隐约约记得本科找工作的时候有这么一道笔试题。中等难度,需要多次调试修改才能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。

三刷。直接模拟,设置left、right、up、down分别表示向左、右、上、下的结束位置,到达该位置需要换方向,同时更新对应的结束位置。完整代码如下:

class Solution {
public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> ans;
		if (matrix.size() == 0)return {};
		int m = matrix.size(), n = matrix[0].size();
		if (m <= 1 || n <= 1) {
			for (int i = 0; i < m; ++i) {
				for (int j = 0; j < n; ++j) {
					ans.push_back(matrix[i][j]);
				}
			}
			return ans;
		}
		int left = 0, right = n - 1, up = 1, down = m - 1;
		int dir = 0, i = 0, j = 0; // dir: 0: right; 1: down; 2: left; 3:up
		int total_num = m * n, cur_num = 0;
		while (cur_num < total_num) {
			ans.push_back(matrix[i][j]);
			++cur_num;
			switch (dir) {
			case 0:
				if (j == right) {
					++i;
					dir = 1;
					--right;
				}
				else {
					++j;
				}
				break;
			case 1:
				if (i == down) {
					--j;
					dir = 2;
					--down;
				}
				else {
					++i;
				}
				break;
			case 2:
				if (j == left) {
					--i;
					dir = 3;
					++left;
				}
				else {
					--j;
				}
				break;
			case 3:
				if (i == up) {
					++j;
					dir = 0;
					++up;
				}
				else {
					--i;
				}
				break;
			}
		}
		return ans;
	}
};

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

LeetCode Search Insert Position

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

已经排好序的数组,找出target或者target应该插入的位置。
显然二分查找,简单题,完整代码如下:

class Solution {
public:
    int findPos(vector<int>& nums, int s, int t, int target)
    {
        if (s == t) {
            if (nums[s] >= target)
                return s;
            else
                return s + 1;
        }
        else if (s > t) { // caution!
            return t + 1;
        }
        else {
            int m = (s + t) / 2;
            if (nums[m] == target)
                return m;
            else if (nums[m] > target)
                return findPos(nums, s, m – 1, target);
            else
                return findPos(nums, m + 1, t, target);
        }
    }
    int searchInsert(vector<int>& nums, int target) { return findPos(nums, 0, nums.size() – 1, target); }
};

需要注意当s>t的分支,我也是遇到一个错误样例之后发现的。本代码提交AC,用时6MS。

本题也可以把递归改成非递归形式,而且好像不会有这种边界问题,代码如下:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() – 1;
        while (l <= r) {
            int m = l + (r – l) / 2;
            if (nums[m] == target)
                return m;
            if (nums[m] < target)
                l = m + 1;
            else
                r = m – 1;
        }
        return l;
    }
};

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

LeetCode Pow(x, n)

50. Pow(x, n)

Implement pow(xn), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

实现幂指数运算。 如果对x连乘n次,时间复杂度为$O(n)$,但使用分治法能降到$O(\log n)$。因为可以把$x^n$分解为: $\begin{equation*} x^n= \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}, & \text{if } n \text{ even}\\ x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x, & \text{if } n \text{ odd} \end{cases} \end{equation*}$

完整代码如下:

class Solution {
public:
    double doPow(double x, int n)
    {
        if (n == 0)
            return 1.0;
        double v = doPow(x, n / 2);
        if (n % 2 == 0)
            return v * v;
        else
            return v * v * x;
    }
    double myPow(double x, int n)
    {
        int m = n > 0 ? n : -n;
        double ans = doPow(x, m);
        return n > 0 ? ans : 1.0 / ans;
    }
};

本代码提交AC,用时3MS。
注意在子程序中不要调用两次doPow(x, n/2),算出一个v,然后直接v*v即可。

二刷。使用非递归的方法实现快速幂,代码如下:

class Solution {
public:
    double myPow(double x, int n)
    {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        long long m = n; // 先转换为ll,否则n=INT_MIN是有问题
        m = m > 0 ? m : -m;
        double ans = 1;
        while (m) {
            if (m & 1)
                ans *= x;
            m >>= 1;
            x = x * x;
        }
        return n > 0 ? ans : 1 / ans;
    }
};

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

三刷。注意n=INT_MIN时,第一种解法会有问题,需要用long long存储,代码如下:

class Solution {
public:
	double myPow2(double x, long long m) {
		if (x == 0.0)return 0.0;
		if (x == 1.0 || m == 0)return 1.0;
		if (m == 1)return x;
		if (m < 0) return 1.0 / myPow2(x, -m);

		if (m % 2 == 1)return x * myPow2(x*x, m >> 1);
		else return myPow2(x*x, m >> 1);
	}
	double myPow(double x, int n) {
		return myPow2(x, n);
	}
};

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

LeetCode Group Anagrams

49. Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Anagrams是指颠倒字母而成的字,比如ate和eat,颠倒字母包括随意乱序颠倒,比如nat和tan。
本题要求把所有anagrams分组找出来,思路是对每个单词内部排序,然后对排序完的所有单词再外部排序,这样相同的anagrams就会排在一起,只要把anagrams相同的放在一个group就可以。比如ate、eat、tea都内部排序成aet,然后3个aet外部排序时会排在一起,这样就能把ate、eat、tea组合成一个group。

完整代码如下:

struct Word {
    string key, value;
    bool operator<(const Word& w) { return this->key < w.key; }
};
class Solution {
public:
    vector<vector<string> > groupAnagrams(vector<string>& strs)
    {
        vector<Word> words;
        for (int i = 0; i < strs.size(); i++) {
            Word tmp;
            tmp.value = strs[i];
            sort(strs[i].begin(), strs[i].end());
            tmp.key = strs[i];
            words.push_back(tmp);
        }
        sort(words.begin(), words.end());
        vector<string> group;
        vector<vector<string> > ans;
        group.push_back(words[0].value);
        for (int i = 1; i < words.size(); i++) {
            if (words[i].key == words[i – 1].key) {
                group.push_back(words[i].value);
            }
            else {
                ans.push_back(group);
                group.clear();
                group.push_back(words[i].value);
            }
        }
        ans.push_back(group);
        return ans;
    }
};

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

二刷。不自定义数据结构,使用map<string, vector<string=””>>,完整代码如下:

class Solution {
public:
    vector<vector<string> > groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string> > hash;
        for (const auto& s : strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string> > ans;
        for (const auto& it : hash) {
            ans.push_back(it.second);
        }
        return ans;
    }
};

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