Monthly Archives: April 2020

LeetCode Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

给定一个二叉树,要求树中某条路径的最大和。注意路径可以不经过叶子节点,也可以不经过根节点,即树中任意一条相连的路径即可。

使用递归的思路。对于一个节点,经过它的最大和路径有如下几种情况:

  • 仅包含节点本身(当左、右、父亲节点的路径和都是负数时)
  • 穿过该节点,且还会往该节点的父亲上面走,说明最优路径的跟在该节点上面,该节点的左子树或右子树路径构成了最优路径的一部分
  • 没有穿过该节点,即该节点为最优路径的跟,则路径的两端可能是该节点的左右孩子

完整代码如下,辅助函数maxSum的返回值即为上面的前两种情况的最大值,maxSum返回之后有可能构成父节点的最大和。ans则是全局的最大和,还包括上面列的第三种情况。

class Solution {
public:
	int maxSum(TreeNode *root, int &ans) {
		if (root == NULL)return 0;
		int left_sum = maxSum(root->left, ans), right_sum = maxSum(root->right, ans);

		// 经过root节点的子树,还得往root的父亲上面走
		int left_or_right_root = max(root->val, root->val + max(left_sum, right_sum));

		// 最后一项是以root为根,左右子树都走,即不往root的父亲上面走
		ans = max(ans, max(left_or_right_root, root->val + left_sum + right_sum));

		return left_or_right_root;
	}
	int maxPathSum(TreeNode* root) {
		int ans = INT_MIN;
		maxSum(root, ans);
		return ans;
	}
};

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

LeetCode First Unique Number

LeetCode First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

  • FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
  • int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
  • void add(int value) insert value to the queue.

Example 1:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 

[null,2,null,2,null,3,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3);            // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1

Example 2:

Input: 
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output: 

[null,-1,null,null,null,null,null,17]

Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17

Example 3:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output: 

[null,809,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^8
  • 1 <= value <= 10^8
  • At most 50000 calls will be made to showFirstUnique and add.

设计题。设计一个队列,能够快速返回当前队列中第一个unique的数。

和之前的LRU很类似,使用list+unordered_map实现。list保存当前unique的数,unordered_map保存每个unique的数在list中的迭代器。当插入一个数到队列中时,首先看看在不在unordered_map中,如果不在,说明这个数是unique的,插入list和unordered_map。如果在,则看看unordered_map中的迭代器,如果迭代器不为空,说明这个数之前是unique的,需要从list中删掉;否则说明这个数之前就已经不是unique的了,不做任何操作。

完整代码如下:

class FirstUnique {
private:
	list<int> uniques_;
	unordered_map<int, list<int>::iterator> hash;
public:
	FirstUnique(vector<int>& nums) {
		for (int i = 0; i < nums.size(); ++i) {
			add(nums[i]);
		}
	}

	int showFirstUnique() {
		if (uniques_.empty())return -1;
		else return uniques_.front();
	}

	void add(int value) {
		if (hash.find(value) == hash.end()) {
			uniques_.push_back(value);
			hash[value] = --uniques_.end();
		}
		else {
			if (hash[value] != uniques_.end()) {
				uniques_.erase(hash[value]);
				hash[value] = uniques_.end();
			}
		}
	}
};

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

LeetCode Diagonal Traverse II

1424. Diagonal Traverse II

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

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

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i].length <= 10^5
  • 1 <= nums[i][j] <= 10^9
  • There at most 10^5 elements in nums.

如上图所示,给定一个残缺矩阵,要求遍历每个对角线,输出所有元素的值。

朴素解法会TLE,特别是如果有某一行或某一列比其他行列长特别多的情况。

提示解法:观察规律发现,处于同一对角线的元素的行列下标之和相等。所以我们可以把所有元素的行列下标进行排序,如果下标和相等,则处于同一对角线,按行下标从大到小排序;如果下标和不相等,则按下标和从小到大排序。完整代码如下:

bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
	int sum1 = p1.first + p1.second, sum2 = p2.first + p2.second;
	if (sum1 == sum2) {
		return p1.first > p2.first;
	}
	else {
		return sum1 < sum2;
	}
}
class Solution {
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
		vector<pair<int, int>> idxs;
		for (int i = 0; i < nums.size(); ++i) {
			for (int j = 0; j < nums[i].size(); ++j) {
				idxs.push_back(make_pair(i, j));
			}
		}
		sort(idxs.begin(), idxs.end(), cmp);
		vector<int> ans;
		for (int i = 0; i < idxs.size(); ++i) {
			ans.push_back(nums[idxs[i].first][idxs[i].second]);
		}
		return ans;
	}
};

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

LeetCode Maximum Points You Can Obtain from Cards

1423. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

给定一个数组,要从中选k个数,每次只能从左边选或从右边选,问选出的数的和最大是多少。

转换思路,无论从左边选多少个,从右边选多少个,剩余的数都是中间区域的某一段数。要使选出来的数和最大,则相当于要使剩下的连续区间的数和最小。所以可以设置一个大小为n-k的滑动窗口,求该滑动窗口的最小和,则用总和减去该最小和即为最终结果。

完整代码如下:

class Solution {
public:
	int maxScore(vector<int>& cardPoints, int k) {
		int sum = 0, n = cardPoints.size();
		for (int i = 0; i < n; ++i)sum += cardPoints[i];
		if (k == n)return sum;

		int min_window_sum = 0, i = 0, j = n - k - 1;
		for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
		int cur_window_sum = min_window_sum;
		while (j < n) {
			if (j == n - 1)break;
			cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
			min_window_sum = min(min_window_sum, cur_window_sum);
		}
		return sum - min_window_sum;
	}
};

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

我之前的想法一直是正向思维,即模拟每次拿左边或右边,甚至还用DP来求解,但都无果。

看讨论区后还是很有启发,无论你当前这一步是拿左边还是右边,经过k轮之后的最终效果是,左边拿了连续的a的,右边拿了连续的k-a个。所以只需要对最终左边拿了几个进行DP建模,而无需模拟每一步是拿了左边还是右边。DP方法可看讨论区: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/598111/Java-dp-solution(explanation-with-picture)

LeetCode Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • The input strings consist of lowercase English characters only.

最长公共子序列问题,直接DP,完整代码如下:

class Solution {
public:
	int longestCommonSubsequence(string text1, string text2) {
		int m = text1.size(), n = text2.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
				if (text1[i - 1] == text2[j - 1])++c;
				dp[i][j] = max(max(a, b), c);
			}
		}
		return dp[m][n];
	}
};

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

LeetCode Maximum Score After Splitting a String

1422. Maximum Score After Splitting a String

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

  • 2 <= s.length <= 500
  • The string s consists of characters ‘0’ and ‘1’ only.

给定一个仅包含0/1的字符串,要求把它分成两半,使得左边的0的数目加上右边的1的数目的和最大。

简单题,提前算好左边的0的数目的累加和,和右边的1的数目的累加和。完整代码如下:

class Solution {
public:
	int maxScore(string s) {
		int n = s.size();
		vector<int> zeros(n, 0), ones(n, 0);
		for (int i = 0; i < n - 1; ++i) {
			if (i == 0)zeros[i] = (s[i] == '0' ? 1 : 0);
			else zeros[i] = zeros[i - 1] + (s[i] == '0' ? 1 : 0);

			int j = n - i - 1;
			if (j == n - 1)ones[j] = (s[j] == '1' ? 1 : 0);
			else ones[j] = ones[j + 1] + (s[j] == '1' ? 1 : 0);
		}
		int ans = 0;
		for (int i = 0; i < n - 1; ++i) {
			ans = max(ans, zeros[i] + ones[i + 1]);
		}
		return ans;
	}
};

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

LeetCode Leftmost Column with at Least a One

LeetCode Leftmost Column with at Least a One

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

You can’t access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:

  • BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
  • BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

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

Example 2:

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

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

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

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • mat[i][j] is either 0 or 1.
  • mat[i] is sorted in a non-decreasing way.

给定一个0/1矩阵,且每行是升序排列的。问矩阵中至少包含一个1的列的最小列号。要求不能使用访问矩阵超过1k次,矩阵最大是100*100的。

常规解法。由于矩阵每行有序,所以在每一行中,使用二分搜索的方式找到1的最小下标,则所有行的最小下标的最小值即为答案。如果是m*n的矩阵,则时间复杂度为O(mlgn)。代码如下:

class Solution {
public:
	int LeftMost(BinaryMatrix &binaryMatrix, int row, int m, int n) {
		int l = 0, r = n - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			int midv = binaryMatrix.get(row, mid);
			if (midv == 0)l = mid + 1;
			else r = mid - 1;
		}
		return r + 1;
	}
	int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
		vector<int> dim = binaryMatrix.dimensions();
		int m = dim[0], n = dim[1];
		int ans = n;
		for (int i = 0; i < m; ++i) {
			ans = min(ans, LeftMost(binaryMatrix, i, m, n));
		}
		if (ans == n)return -1;
		else return ans;
	}
};

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

hint还提示了另一种解法,从矩阵的右上角开始,遇到0则往下走,遇到1则往左走。因为如果是1的话,至少当前所在列是包含1的,也许还可以再往左试探一下,而如果是0的话,只能往下走了。这种方法极端情况下可能从矩阵的右上角走到左下角,时间复杂度为O(m+n)。完整代码如下:

class Solution {
public:

	int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
		vector<int> dim = binaryMatrix.dimensions();
		int m = dim[0], n = dim[1];
		int x = 0, y = n - 1;
		int ans = n;
		while (x < m&&y >= 0) {
			int val = binaryMatrix.get(x, y);
			if (val == 0)++x;
			else if (val == 1) {
				ans = y;
				if (y - 1 >= 0 && binaryMatrix.get(x, y - 1) == 1) {
					--y;
					ans = y;
				}
				else ++x;
			}
		}
		if (ans == n)return -1;
		else return ans;
	}
};

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

LeetCode Construct Binary Search Tree from Preorder Traversal

1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note: 

  1. 1 <= preorder.length <= 100
  2. The values of preorder are distinct.

根据二叉搜索树的先序遍历结果,构造该二叉搜索树。

简单题。先序遍历是根、左、右,又因为是二叉搜索树,所以左<根<右,所以数组中第一个元素是根节点,然后找到数组右边第一个大于根节点的树,把数组划分为左子树和右子树,然后递归构造。

完整代码如下:

class Solution {
public:
	TreeNode* Work(vector<int> &preorder, int l, int r) {
		if (l > r)return NULL;
		if (l == r)return new TreeNode(preorder[l]);
		TreeNode *root = new TreeNode(preorder[l]);
		int mid = -1;
		for (int i = l; i <= r; ++i) {
			if (preorder[i] > root->val) {
				mid = i;
				break;
			}
		}
		if (mid == -1)root->left = Work(preorder, l + 1, r);
		else {
			root->left = Work(preorder, l + 1, mid - 1);
			root->right = Work(preorder, mid, r);
		}
		return root;
	}
	TreeNode* bstFromPreorder(vector<int>& preorder) {
		return Work(preorder, 0, preorder.size() - 1);
	}
};

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

LeetCode Minimum Number of Frogs Croaking

1419. Minimum Number of Frogs Croaking

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1 
Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.

Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1

Constraints:

  • 1 <= croakOfFrogs.length <= 10^5
  • All characters in the string are: 'c''r''o''a' or 'k'.

这题有点意思,比赛结束前3分钟我才AC了。。。

给定一个字符串,表示青蛙咳嗽的字符串。青蛙每咳一声,会发出croak这一串字符。现在有多个青蛙同时咳嗽,则多个croak会被打乱输出,可以想象下多线程输出到同一个文件时,顺序是乱的。

问一个咳嗽字符串最少可以由几个青蛙产生的,注意青蛙咳完一声后可以接着咳。

我一开始的做法比较暴力,对于每个字符,检查它是否属于之前某个青蛙的咳嗽字符串中,如果属于则放入,不属于且是c的话,则新开一个咳嗽字符串。完整代码如下:

class Solution {
public:
	int minNumberOfFrogs(string croakOfFrogs) {
		map<char, char> pre = { {'r','c'},{'o','r'},{'a','o'},{'k','a'} };
		vector<vector<char>> ans;
		map<char, int> count;
		for (int i = 0; i < croakOfFrogs.size(); ++i) {
			int letter = croakOfFrogs[i];
			++count[letter];
			if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
			if (letter == 'c') {
				if (ans.empty()) {
					ans.push_back({ 'c' });
				}
				else {
					bool found = false;
					for (int j = 0; j < ans.size(); ++j) {
						if (ans[j].empty()) {
							ans[j].push_back('c');
							found = true;
							break;
						}
					}
					if (!found) {
						ans.push_back({ 'c' });
					}
				}
			}
			else {
				if (ans.empty())return -1;
				else {
					bool found = false;
					for (int j = 0; j < ans.size(); ++j) {
						if (!ans[j].empty() && ans[j].back() == pre[letter]) {
							ans[j].push_back(letter);
							found = true;
							if (letter == 'k')ans[j].clear();
							break;
						}
					}
					if (!found)return -1;
				}
			}
		}

		for (int j = 0; j < ans.size(); ++j) {
			if (!ans[j].empty())return -1;
		}

		return ans.size();
	}
};

这个解法TLE了,最后几个测试用例过不了。这个解法的问题是对每个字符都要遍历之前所有青蛙的咳嗽数组,太耗时了。

后来想到一种O(n)解法。因为咳嗽字符串是croak,在遍历的过程中,只要满足出现次数c>=r>=o>=a>=k就是合法的。然后设定一个free变量,记录当前有多少只青蛙是之前咳嗽结束了,已经空闲下来,可以进行下一轮咳嗽了。如果来一个c,且有free的话,则拿一个free的青蛙进行咳嗽,否则新开一个青蛙。如果新来一个k,则说明这个青蛙咳嗽结束,多一个空闲青蛙,free++。

完整代码如下:

class Solution {
public:
	int minNumberOfFrogs(string croakOfFrogs) {
		int n = croakOfFrogs.size();
		map<char, int> count;
		int free = 0, ans = 0;
		for (int i = 0; i < croakOfFrogs.size(); ++i) {
			char letter = croakOfFrogs[i];
			++count[letter];
			if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
			if (letter == 'c'&&free == 0) {
				++ans;
			}
			else if (letter == 'c'&&free > 0) {
				--free;
			}
			else if (letter == 'k') {
				++free;
			}
		}
		if (count['c'] != count['k'])return -1;
		return ans;
	}
};

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

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。