Tag Archives: 堆栈

LeetCode K Closest Points to Origin

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

给定二维平面上的若干个点,求距离原点最近的K个点。

看总结: https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/cyu-yan-san-chong-jie-fa-han-zong-jie-by-gan-cui-j/

事实上,诸如此类的,要在一个数组中寻找第K大的数(或者第K小的数),前K大的数,前K小的数,一般来说的方法有:

1.先排序(快排)时间复杂度为nlogn
2.建堆,堆的大小为K,建立大根堆或者小根堆,时间复杂度为nlogK(如果要求出前K个较大的,那么就建立小根堆,一旦比堆顶大,那么就入堆);
3.结合快速排序划分的方法,不断减小问题的规模

对于这一题,采用解法3,即快排划分的思路。采用标准快排思路,每次选区间最右边的元素作为pivot,然后划分,看看划分后的pivot位置和K的大小关系,递归在左右区间进行划分。完整代码如下:

class Solution {
private:
	vector<int> origin;

	int CalDist(vector<int> &p1, vector<int> &p2) {
		return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
	}

	void MySwap(vector<vector<int>>& points, int u, int v) {
		swap(points[u][0], points[v][0]);
		swap(points[u][1], points[v][1]);
	}

	void Work(vector<vector<int>>& points, int l, int r, int K) {
		if (l >= r) return;

		int pivot = r;
		int pdist = CalDist(points[pivot], origin);
		int i = l;
		for (int j = l; j < r; ++j) {
			int idist = CalDist(points[j], origin);
			if (idist < pdist) {
				MySwap(points, i++, j);
			}
		}
		MySwap(points, i, pivot);

		if (K == i)return;
		else if (K < i)Work(points, l, i - 1, K);
		else Work(points, i + 1, r, K);
	}
public:
	vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
		origin = { 0, 0 }; // 求与该点距离最近的top-k个点,本题中该点是原点

		for (int i = 0; i < points.size(); ++i) {
			printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
		}

		Work(points, 0, points.size() - 1, K - 1);

		vector<vector<int>> ans;
		for (int i = 0; i < K; ++i) ans.push_back(points[i]);
		return ans;
	}
};

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

LeetCode Make The String Great

5483. Make The String Great

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

  • 0 <= i <= s.length - 2
  • s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

Constraints:

  • 1 <= s.length <= 100
  • s contains only lower and upper case English letters.

给定一个字符串,如果相邻两个字符是同一字母的大小写形式,则需要删除这两个字母,问最终的字符串形式是什么。

简单题,使用栈,完整代码如下:

class Solution {
public:
    string makeGood(string s) {
        stack<char> stk;
        for(int i = 0; i < s.size(); ++i) {
            if(!stk.empty() && abs(stk.top() - s[i]) == 32) {
                stk.pop();
            } else {
                stk.push(s[i]);
            }
        }
        string ans="";
        while(!stk.empty()) {
            ans = string(1, stk.top()) + ans;
            stk.pop();
        }
        return ans;
    }
};

本代码提交AC。

LeetCode Avoid Flood in The City

1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

  • rains[i] > 0 means there will be rains over the rains[i] lake.
  • rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

  • ans.length == rains.length
  • ans[i] == -1 if rains[i] > 0.
  • ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9

Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.

Constraints:

  • 1 <= rains.length <= 10^5
  • 0 <= rains[i] <= 10^9

给定一个数组rains,rains[i]表示第i天在第rains[i]的湖上下雨,湖被灌满,比如第四个例子,rains[0]=69表示第0天在第69号湖上下雨,第69号湖被灌满。如果rains[i]=0表示第i天不下雨,可以抽干某个湖。问每个不下雨的天,抽干哪个湖,能让任意一个湖都不至于出现水灾(被灌满之后又被下雨)。

很有意思的一个题,暴力方法是,每个不下雨的天,对于之前被灌满的湖,抽干未来第一个要下雨的湖。比如对于rains=[1,2,3,0,2,0,0],当遇到第一个0时,我们选择抽干2号湖,因为下一天马上要在2号湖上下雨,如果不抽干2号湖,则会发生水灾,所以要抽干未来第一个要出现水灾的湖。但是这种时间复杂度是O(n^2)。

参考讨论区,更好的做法是,先记录所有不下雨的天,然后对于每一个下雨天,如果要下雨的湖之前没被灌满,则不用管;如果之前被灌满了,则需要在之前被灌满那天之后找一个不下雨的天,把这个湖抽干。所以维护一个堆heap/set,记录之前不下雨的天,后续直接用lower_bound查找符合的天。

完整代码如下:

class Solution {
public:
	vector<int> avoidFlood(vector<int>& rains) {
		int n = rains.size();

		vector<int> ans;
		unordered_map<int, int> full_lakes;
		set<int> dry_days;

		for (int i = 0; i < n; ++i) {
			if (rains[i] == 0) {
				dry_days.insert(i);
				ans.push_back(1); // 先随便填一个数,后续会覆盖,填入真正要抽干的湖编号
			}
			else {
				if (full_lakes.find(rains[i]) != full_lakes.end()) { // 这个湖之前就满了,需要抽干
					int last_day = full_lakes[rains[i]];
					set<int>::iterator it = dry_days.lower_bound(last_day); //从之前满的那天往后选不下雨的一天抽干
					if (it == dry_days.end()) {
						return {}; // 失败
					}
					ans[*it] = rains[i];
					dry_days.erase(it);
				}
				full_lakes[rains[i]] = i; // 填入新的下雨日期
				ans.push_back(-1);
			}
		}

		return ans;
	}
};

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

LeetCode Exclusive Time of Functions

LeetCode Exclusive Time of Functions Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions. Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function. A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0. Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id. Example 1:

Input:
n = 2
logs =
["0:start:0",
 "1:start:2",
 "1:end:5",
 "0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.
Note:
  1. Input logs will be sorted by timestamp, NOT log id.
  2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
  3. Two functions won’t start or end at the same time.
  4. Functions could be called recursively, and will always end.
  5. 1 <= n <= 100

给定一个单核单线程的CPU,并且给出了该CPU跑不同函数的开始时间和结束时间,问每个函数单独运行的时间是多少。因为有些函数可能会调用其他函数,还可能递归调用自己,所以需要去掉调用其他函数的时间,只给出该函数自己运行的时间。 用Node记录每一个记录,Node包含四个属性:function_id,start_or_end,timestamp和exclude_time,前三个就是题目中描述的属性,最后一个exclude_time是指该函数调用其他函数花费的时间,需要减去的时间。 考虑到递归调用,递归返回之类的,马上想到函数调用的时候需要用堆栈保存现场,所以这里也用堆栈保存所有递归调用的函数。每次遇到新函数的start时,压栈,遇到end时,和栈顶求一下时间差,弹栈,并把时间差记录到结果数组中。同时,需要把这个函数用掉的时间累加到栈顶(也就是主调函数)Node的exclude_time中,这一点非常重要。 最后,因为一个函数可能出现多次,所以不论是对结果数组的赋值还是对exclude_time的赋值,都用+=,不能用赋值,否则会覆盖掉之前的数据。 完整代码如下: [cpp] class Solution { private: struct Node { int id_; bool start_; int timestamp_; int exclude_time_; }; void ParseLog(const string& log, Node& node) { size_t colon_pos = log.find(‘:’); node.id_ = stoi(log.substr(0, colon_pos)); if (log[colon_pos + 1] == ‘s’) node.start_ = true; else node.start_ = false; colon_pos = log.find(‘:’, colon_pos + 1); node.timestamp_ = stoi(log.substr(colon_pos + 1)); node.exclude_time_ = 0; } public: vector<int> exclusiveTime(int n, vector<string>& logs) { vector<int> ans(n); stack<Node> stk; for (const auto& log : logs) { Node node; ParseLog(log, node); if (node.start_) { stk.push(node); } else { Node start_node = stk.top(); stk.pop(); int cur_time = node.timestamp_ – start_node.timestamp_ + 1 – start_node.exclude_time_; // caution ans[node.id_] += cur_time; // caution if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution } } return ans; } }; [/cpp] 本代码提交AC,用时23MS。]]>

LeetCode Smallest Range

LeetCode Smallest Range You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists. We define the range [a,b] is smaller than range [c language=",d"][/c] if b-a < d-c or a < c if b-a == d-c. Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Note:
  1. The given list may contain duplicates, so ascending order means >= here.
  2. 1 <= k <= 3500
  3. -105 <= value of elements <= 105.
  4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you’ll see this point.

给定k个升序数组,求一个整数区间,该区间能至少包括所有数组的一个元素,且该区间最小。最小的定义是区间长度最小,如果区间长度相同,则区间起始点小则小。 参考Find smallest range containing elements from k lists这篇博客,突然发现GeeksforGeeks网站上的题比Leetcode上的多好多,而且都有详细题解和代码,好棒。 要求区间最小,则区间只包括每个数组的一个元素最好,所以我们要找k个数组中的k个数,使得这k个数的最大值和最小值的差最小,那么这个区间的两个端点就是这个最大值和最小值。 所以我们对k个数组维护k个指针,初始时都指向每个数组的首元素,然后找到这k个数的最大值和最小值,得到一个区间及其长度。然后我们不断循环:向前移动k个指针中的最小者,在新的k个数中求最大值和最小值及其区间长度。直到某个数组遍历结束,则返回得到的最小区间。 以样例为例。
  1. i,j,k分别指向三个数组的开头,即i=j=k=0,相当于在[4,0,5]中找最大值和最小值,构成区间[0,5],长度为5。
  2. 最小值为j所在数组,所以++j,在新的数组[4,9,5]中找最大值和最小值,构成区间[4,9],长度为5。
  3. 最小值为i所在数组,所以++i,在新的数组[10,9,5]中找最大值和最小值,构成区间[5,10],长度为5。
  4. ++k,新数组[10,9,18],区间[9,18],长度为9。
  5. ++j,新数组[10,12,18],区间[10,18],长度为8。
  6. ++i,新数组[15,12,18],区间[12,18],长度为6。
  7. ++j,新数组[15,20,18],区间[15,20],长度为5。
  8. ++i,新数组[24,20,18],区间[18,24],长度为6。
  9. ++k,新数组[24,20,22],区间[20,24],长度为4。
  10. ++j,第二个数组遍历完毕,结束,遍历过程中,得到的长度最短的区间是[20,24]。
完整代码如下: [cpp] class Solution { public: vector<int> smallestRange(vector<vector<int>>& nums) { int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size(); vector<int> ptr(k, 0); while (true) { bool done = false; int curmin = INT_MAX, curmax = INT_MIN, minid = 0; for (int i = 0; i < k; ++i) { if (ptr[i] >= nums[i].size()) { done = true; break; } if (nums[i][ptr[i]] < curmin) { curmin = nums[i][ptr[i]]; minid = i; } if (nums[i][ptr[i]] > curmax) { curmax = nums[i][ptr[i]]; } } if (done)break; if (curmax – curmin < ansrange) { ansrange = curmax – curmin; ansmin = curmin; ansmax = curmax; } ++ptr[minid]; } return{ ansmin,ansmax }; } }; [/cpp] 本代码提交AC,用时1016MS。 因为每一轮都需要从k个数组中找最大值和最小值,线性查找的复杂度为O(k)。最坏情况下,需要遍历k个数组的每个元素,假设k个数组所有元素个数为n,则总的时间复杂度为O(nk)。 求k个数组的最大值和最小值的过程,可以用大小为k的优先队列(最小堆)来优化,复杂度可以降为O(nlgk)。代码如下: [cpp] class Solution { private: struct Node { int value; int idx; int nxt; Node(int v, int i, int n) :value(v), idx(i), nxt(n) {}; bool operator<(const Node& nd) const { return value > nd.value; } bool operator>(const Node& nd) const { return value < nd.value; } }; public: vector<int> smallestRange(vector<vector<int>>& nums) { int ansmin = INT_MAX, ansmax = INT_MIN, ansrange = INT_MAX, k = nums.size(); priority_queue<Node> pq; for (int i = 0; i < k; ++i) { pq.push(Node(nums[i][0], i, 1)); if (nums[i][0] < ansmin) { ansmin = nums[i][0]; } ansmax = max(ansmax, nums[i][0]); } int curmax = ansmax; while (true) { int curmin = pq.top().value; int minidx = pq.top().idx; int minnxt = pq.top().nxt; pq.pop(); if (curmax – curmin < ansrange) { ansrange = curmax – curmin; ansmin = curmin; ansmax = curmax; } if (minnxt < nums[minidx].size()) { curmax = max(curmax, nums[minidx][minnxt]); pq.push(Node(nums[minidx][minnxt], minidx, minnxt + 1)); } else break; } return{ ansmin,ansmax }; } }; [/cpp] 本代码提交AC,用时56MS。  ]]>

LeetCode Remove K Digits

LeetCode Remove K Digits Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

给定一个数字字符串,要求从中删除k个数字,使得最终结果最小,返回最小的数字字符串。 使用栈和贪心的思路。为了使结果尽量小,我们从左往右扫描字符串,把字符存到一个栈中,如果当前字符比栈顶小,则可以把栈顶数字删掉,这样相当于用当前字符代替栈顶字符所在位置,使得结果更小了。否则把当前字符压栈,注意此时不能把当前字符删掉,因为可能后面还有更大的字符出现。 如果这样过了一遍之后,还是没删够k个字符,此时,字符串从左往右肯定是非降序的。所以我们依次弹栈,把栈顶的元素删掉,直到删够k个字符。 最后还要判断一下剩余字符串是否为空,并删除前导零。完整代码如下: [cpp] class Solution { public: string removeKdigits(string num, int k) { if (k >= num.size())return "0"; string ans = ""; for (const auto& c : num) { if (ans.empty() || k == 0)ans.push_back(c); else { while (!ans.empty() && ans.back() > c) { ans.pop_back(); if (–k == 0)break; } ans.push_back(c); } } while (k– > 0 && !ans.empty()) ans.pop_back(); while (!ans.empty() && ans[0] == ‘0’)ans.erase(ans.begin()); return ans.empty() ? "0" : ans; } }; [/cpp] 本代码提交AC,用时6MS。]]>

LeetCode Basic Calculator II

LeetCode Basic Calculator II Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. You may assume that the given expression is always valid. Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
本题是LeetCode Basic Calculator的简化版,去掉了括号,增加了乘除法。但是算法都是一模一样的,先把中缀转换为后缀,然后用栈求值。 代码如下: [cpp] // 优先级 unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} }; class Solution { private: void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) { if (isdigit(numOrop[0])) { numbers.push(numOrop); } else { if (numOrop == ")") { while (opers.top() != "(") { numbers.push(opers.top()); opers.pop(); } opers.pop(); } else if (numOrop == "(") { opers.push(numOrop); } else if (opers.empty() || opers.top() == "(") { opers.push(numOrop); } else if (priority[numOrop] > priority[opers.top()]) { opers.push(numOrop); } else { while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) { numbers.push(opers.top()); opers.pop(); } opers.push(numOrop); } } } // 中缀转后缀表达式 list<string> in2post(const string& s) { stack<string> numbers, opers; int start = 0, end = 1, n = s.size(); while (start < n) { while (start < n&&s[start] == ‘ ‘)++start; if (start >= n)break; if (isdigit(s[start])) { end = start + 1; while (end < n&&isdigit(s[end]))++end; string num = s.substr(start, end – start); push(numbers, opers, num); start = end; } else { string op = string(1, s[start]); push(numbers, opers, op); ++start; } } while (!opers.empty()) { numbers.push(opers.top()); opers.pop(); } list<string> ans; while(!numbers.empty()) { ans.push_front(numbers.top()); numbers.pop(); } return ans; } // 求值后缀表达式的值 int eval(list<string>& post) { int ans = 0; stack<int> numbers; for (const auto& s : post) { if (priority.find(s) != priority.end()) { int num2 = numbers.top(); numbers.pop(); int num1 = numbers.top(); numbers.pop(); if (s == "+")numbers.push(num1 + num2); else if (s == "-")numbers.push(num1 – num2); else if (s == "*")numbers.push(num1*num2); else numbers.push(num1 / num2); } else numbers.push(stoi(s)); } return numbers.top(); } public: int calculate(string s) { list<string> ans = in2post(s); return eval(ans); } }; [/cpp] 本代码提交AC,用时85MS。]]>

LeetCode Basic Calculator

224. Basic Calculator 224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

给定一个字符串表达式,要求求解该表达式的值。 使用栈解决。我们通常看到的表达式称为中缀表达式,需要把它转换为后缀表达式,比如1+((2+3)×4)-5转换为1 2 3 + 4 × + 5 -。我们可以很容易用栈求解后缀表达式,只需要遍历后缀表达式,把遇到的操作数压栈,只要遇到运算符,就从栈中弹出两个操作数,进行运算,再把运算结果压栈。最后栈中只能得到一个值,就是整个表达式的值。 所以问题的关键就是怎样把中缀表达式转换为后缀表达式。 使用两个栈,一个栈保存操作数numbers,另一个栈保存运算符opers。遍历原字符串,按如下规则进行压栈和弹栈:

  • 如果是操作数,直接压入numbers
  • 如果是操作符op:
    1. 如果op为左括号“(”,则直接把op压入opers
    2. 如果op为右括号“)”,则把opers的运算符不断弹栈并压入numbers,直到栈顶为左括号“(”,此时将这一对括号丢弃
    3. 如果opers为空,或者opers栈顶为左括号“(”,则直接把op压入opers
    4. 此时,栈顶肯定不可能是括号了,如果op的优先级高于opers栈顶的优先级,则直接把op压入opers
    5. 否则,把opers栈顶的运算符不断弹栈并压入numbers,直到栈顶为左括号,或者op的优先级高于opers栈顶的优先级。把op压入opers

如果是操作符op,下面的1~5的判断规则是有先后顺序的,需要先判断是否为括号,再判断是否是一般的运算符。 运算符的优先级是,+-优先级相同,*/优先级相同,且+-的优先级低于*/。 得到中缀表达式的后缀表达式之后,再用开头提到的栈求解。后缀表达式的求值就非常简单了。 完整代码如下:

// 优先级
unordered_map<string, int> priority = { { "+", 1 }, { "-", 1 }, { "*", 2 }, { "/", 2 } };
class Solution {
private:
    void push(stack<string>& numbers, stack<string>& opers, const string& numOrop)
    {
        if (isdigit(numOrop[0])) {
            numbers.push(numOrop);
        }
        else {
            if (numOrop == ")") {
                while (opers.top() != "(") {
                    numbers.push(opers.top());
                    opers.pop();
                }
                opers.pop();
            }
            else if (numOrop == "(") {
                opers.push(numOrop);
            }
            else if (opers.empty() || opers.top() == "(") {
                opers.push(numOrop);
            }
            else if (priority[numOrop] > priority[opers.top()]) {
                opers.push(numOrop);
            }
            else {
                while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
                    numbers.push(opers.top());
                    opers.pop();
                }
                opers.push(numOrop);
            }
        }
    }
    // 中缀转后缀表达式
    list<string> in2post(const string& s)
    {
        stack<string> numbers, opers;
        int start = 0, end = 1, n = s.size();
        while (start < n) {
            while (start < n && s[start] == ‘ ‘)
                ++start;
            if (start >= n)
                break;
            if (isdigit(s[start])) {
                end = start + 1;
                while (end < n && isdigit(s[end]))
                    ++end;
                string num = s.substr(start, end – start);
                push(numbers, opers, num);
                start = end;
            }
            else {
                string op = string(1, s[start]);
                push(numbers, opers, op);
                ++start;
            }
        }
        while (!opers.empty()) {
            numbers.push(opers.top());
            opers.pop();
        }
        list<string> ans;
        while (!numbers.empty()) {
            ans.push_front(numbers.top());
            numbers.pop();
        }
        return ans;
    }
    // 求值后缀表达式的值
    int eval(list<string>& post)
    {
        int ans = 0;
        stack<int> numbers;
        for (const auto& s : post) {
            if (priority.find(s) != priority.end()) {
                int num2 = numbers.top();
                numbers.pop();
                int num1 = numbers.top();
                numbers.pop();
                if (s == "+")
                    numbers.push(num1 + num2);
                else if (s == "-")
                    numbers.push(num1 – num2);
                else if (s == "*")
                    numbers.push(num1 * num2);
                else
                    numbers.push(num1 / num2);
            }
            else
                numbers.push(stoi(s));
        }
        return numbers.top();
    }
public:
    int calculate(string s)
    {
        list<string> ans = in2post(s);
        return eval(ans);
    }
};

本代码提交AC,用时92MS。
参考:http://blog.csdn.net/antineutrino/article/details/6763722

二刷。push函数实际上只有3个分支就可以了,上面的过于复杂,看下面:

unordered_map<string, int> priority = { {"+",1},{"-",1},{"*",2},{"/",2} };

class Solution {
private:
	bool IsDigit(char c) {
		return c >= '0'&&c <= '9';
	}

	vector<string> ParseString(const string &s) {
		vector<string> vec;
		int n = s.size();
		int i = 0, j = 0;
		while (i < n) {
			while (i < n&&s[i] == ' ')++i;
			if (i >= n)break;

			if (!IsDigit(s[i])) {
				vec.push_back(string(1, s[i]));
				++i;
			}
			else {
				j = i + 1;
				while (j < n&&IsDigit(s[j]))++j;
				vec.push_back(s.substr(i, j - i));
				i = j;
			}
		}
		return vec;
	}

	list<string> In2Post(const vector<string> &vec) {
		stack<string> numbers, opers;
		for (int i = 0; i < vec.size(); ++i) {
			if (IsDigit(vec[i][0])) {
				numbers.push(vec[i]);
			}
			else {
				if (vec[i] == ")") { // 右括号
					while (opers.top() != "(") {
						numbers.push(opers.top());
						opers.pop();
					}
					opers.pop();
				}
				else if (vec[i] == "(") { // 左括号
					opers.push(vec[i]);
				}
				else { // 操作符
					while (!opers.empty() && opers.top() != "("&&priority[vec[i]] <= priority[opers.top()]) {
						numbers.push(opers.top());
						opers.pop();
					}
					opers.push(vec[i]);
				}
			}
		}
		
		while (!opers.empty()) {
			numbers.push(opers.top());
			opers.pop();
		}
		list<string> lst;
		while (!numbers.empty()) {
			lst.push_front(numbers.top());
			numbers.pop();
		}
		return lst;
	}

	int Evaluate(const list<string> &lst) {
		stack<string> stk;
		for (list<string>::const_iterator it = lst.begin(); it != lst.end(); ++it) {
			if (IsDigit((*it)[0])) {
				stk.push(*it);
			}
			else {
				int b = atoi(stk.top().c_str());
				stk.pop();
				int a= atoi(stk.top().c_str());
				stk.pop();
				if (*it == "+") {
					stk.push(to_string(a + b));
				}
				else if (*it == "-") {
					stk.push(to_string(a - b));
				}
			}
		}
		return atoi(stk.top().c_str());
	}

public:
	int calculate(string s) {

		vector<string> vec = ParseString(s);
		list<string> lst = In2Post(vec);
		return Evaluate(lst);
	}
};

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

LeetCode Mini Parser

LeetCode Mini Parser Given a nested list of integers represented as a string, implement a parser to deserialize it. Each element is either an integer, or a list — whose elements may also be integers or other lists. Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].
Example 1:
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.
Example 2:
Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

给定一个嵌套的字符串,要求把它解析成一个NestedInteger。 解法1,使用栈。遇到左括号时,增加一个空的NestedInteger实例,压栈。遇到逗号时,把前面的数add到栈顶的NestedInteger中。遇到右括号时,把栈顶的NestedInteger弹栈,并add到新的栈顶(相当于前一个)NestedInteger中。最后栈顶只有一个元素,返回该元素即可。 代码如下: [cpp] class Solution { public: NestedInteger deserialize(string s) { auto isnumber = [](char c) {return c == ‘-‘ || isdigit(c); }; stack<NestedInteger> stk; stk.push(NestedInteger()); for (auto it = s.begin(); it != s.end();) { if (isnumber(*it)) { auto it2 = find_if_not(it, s.end(), isnumber); int v = stoi(string(it, it2)); stk.top().add(NestedInteger(v)); it = it2; } else { if (*it == ‘[‘) { stk.push(NestedInteger()); } else if (*it == ‘]’) { NestedInteger tmp = stk.top(); stk.pop(); stk.top().add(tmp); } ++it; } } return stk.top().getList().front(); } }; [/cpp] 本代码提交AC,用时19MS。 解法2,递归法。如果当前的字符串是一个裸的整数的话,类似于样例1,则直接返回以该数为参数的NestedInteger;否则剥掉左括号[,递归反序列化,把递归的结果add到当前的NestedInteger中。 代码如下: [cpp] class Solution { private: NestedInteger deserialize(istringstream &in) { int number; if (in >> number) return NestedInteger(number); in.clear(); in.get(); NestedInteger list; while (in.peek() != ‘]’) { list.add(deserialize(in)); if (in.peek() == ‘,’)in.get(); } in.get(); return list; } public: NestedInteger deserialize(string s) { istringstream in(s); return deserialize(in); } }; [/cpp] 本代码提交AC,用时19MS。 参考1,栈:https://discuss.leetcode.com/topic/54904/c-non-recursive-one-pass-solution-using-stack-a-possible-implementation-of-nestedinteger 参考2,递归:https://discuss.leetcode.com/topic/54258/python-c-solutions/10]]>

LeetCode Find K Pairs with Smallest Sums

LeetCode Find K Pairs with Smallest Sums You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u,v) which consists of one element from the first array and one element from the second array. Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums. Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:
Given nums1 = [1,2], nums2 = [3],  k = 3
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]

给定两个从小到大排列的数组,要求选出k个数对(u_i,v_i),其中u_i来自第一个数组nums1,v_i来自第二个数组v_i,使得这k个数对的和最小。 要使得k各数对的和最小,那么这k个数对本身肯定是前k个最小的。遇到要选前k个最小或者最大的问题,一般都用优先队列(堆)来做,比如维护一个大小为k的大顶堆,当堆中元素大于k时,弹出堆顶的最大的元素,也就是堆中维护的一直是当前最小的前k个元素。当所有元素都遍历完时,返回堆中所有元素即可。 优先队列采用STL中的priority_queue,需要自定义比较运算符。 完整代码如下: [cpp] class Solution { private: struct P { int x, y; P(int x_, int y_) :x(x_), y(y_) {}; bool operator<(const P& p) const{ return (this->x + this->y) < (p.x + p.y); } bool operator>(const P& p) const { return (this->x + this->y) > (p.x + p.y); } }; public: vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { priority_queue<P> pq; // 大顶堆 for (int i = 0; i < nums1.size(); ++i) { for (int j = 0; j < nums2.size(); ++j) { P p(nums1[i], nums2[j]); pq.push(p); if (pq.size() > k)pq.pop(); // 弹出最大元素 } } vector<pair<int, int>> ans; while (!pq.empty()) { // 保留的都是最小元素 ans.push_back(pair<int, int>(pq.top().x, pq.top().y)); pq.pop(); } return ans; } }; [/cpp] 本代码提交AC,用时99MS。]]>