Monthly Archives: March 2020

LeetCode Design Underground System

1396. Design Underground System

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

  • A customer with id card equal to id, gets in the station stationName at time t.
  • A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

  • A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation) 

  • Returns the average time to travel between the startStation and the endStation.
  • The average time is computed from all the previous traveling from startStation to endStation that happened directly.
  • Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

  • There will be at most 20000 operations.
  • 1 <= id, t <= 10^6
  • All strings consist of uppercase, lowercase English letters and digits.
  • 1 <= stationName.length <= 10
  • Answers within 10^-5 of the actual value will be accepted as correct.

设计一个地铁记录系统。完整代码如下,使用system记录每条线路的用时和乘坐次数,使用starts记录每个人旅行起点。不用记录终点,因为checkout的时候,把起点取出计算用时即可。

class UndergroundSystem {
private:
	map<string, map<string, pair<int, int>>> system_; // start->end, total time, #travels
	map<int, pair<string, int>> starts_; // travel start station
public:
	UndergroundSystem() {

	}

	void checkIn(int id, string stationName, int t) {
		starts_[id] = make_pair(stationName, t);
	}

	void checkOut(int id, string stationName, int t) {
		string start_station = starts_[id].first;
		int start_time = starts_[id].second;
		starts_.erase(id);
		if (system_.find(start_station) == system_.end()
			|| system_[start_station].find(stationName) == system_[start_station].end()) {
			system_[start_station][stationName] = make_pair(0, 0);
		}
		system_[start_station][stationName].first += (t - start_time);
		system_[start_station][stationName].second += 1;
	}

	double getAverageTime(string startStation, string endStation) {
		return system_[startStation][endStation].first / double(system_[startStation][endStation].second);
	}
};

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

LeetCode Count Number of Teams

1395. Count Number of Teams

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

  • Choose 3 soldiers with index (ijk) with rating (rating[i]rating[j]rating[k]).
  • A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

  • n == rating.length
  • 1 <= n <= 200
  • 1 <= rating[i] <= 10^5

给定一个数组,要求找出这样的升序或者降序的三元组数目。

竞赛阶段,由于n的范围较小,首先尝试暴力O(n^3)解法,代码如下:

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				for (int k = j + 1; k < n; ++k) {
					if (rating[i] < rating[j] && rating[j] < rating[k])++ans;
					else if (rating[i] > rating[j] && rating[j] > rating[k])++ans;
				}
			}
		}
		return ans;
	}
};

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

还有更优的O(n^2)的解法。对于每个士兵,统计其左边小于它的数目,和右边大于它的数目,则这两个数相乘即为该士兵能组成的升序数目,类似的可以算到该士兵能组成的降序数目。代码如下:

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 1; i < n - 1; ++i) {
			vector<int> less_num(2, 0), greater_num(2, 0);
			for (int j = 0; j < n; ++j) {
				if (rating[j] < rating[i])++less_num[j < i];
				else if (rating[j] > rating[i])++greater_num[j > i];
			}
			ans += less_num[1] * greater_num[1] + less_num[0] * greater_num[0];
		}
		return ans;
	}
};

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

LeetCode Find Lucky Integer in an Array

5368. Find Lucky Integer in an Array

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

Example 1:

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

Example 3:

Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.

Example 4:

Input: arr = [5]
Output: -1

Example 5:

Input: arr = [7,7,7,7,7,7,7]
Output: 7

Constraints:

  • 1 <= arr.length <= 500
  • 1 <= arr[i] <= 500

给定一个数组,定义幸运数字是它的值与它在数组中出现的次数相等的数,问数组中最大的幸运数字是哪个。

简单题,用一个map计数即可,代码如下:

class Solution {
public:
	int findLucky(vector<int>& arr) {
		map<int, int> lucky;
		for (int i = 0; i < arr.size(); ++i) {
			++lucky[arr[i]];
		}
		int max_lucky = -1;
		for (map<int, int>::iterator it = lucky.begin(); it != lucky.end(); ++it) {
			if (it->first == it->second) {
				max_lucky = max(max_lucky, it->first);
			}
		}
		return max_lucky;
	}
};

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

LeetCode Check if There is a Valid Path in a Grid

1391. Check if There is a Valid Path in a Grid

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

  • 1 which means a street connecting the left cell and the right cell.
  • 2 which means a street connecting the upper cell and the lower cell.
  • 3 which means a street connecting the left cell and the lower cell.
  • 4 which means a street connecting the right cell and the lower cell.
  • 5 which means a street connecting the left cell and the upper cell.
  • 6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1)The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • 1 <= grid[i][j] <= 6

给定一个网格,每个格子中标明了路的走向,问能否从网格的左上角走到右下角。

简单题,bfs或dfs都可以,我用的是bfs。就是在搜索的时候,各种条件比较多,写起来很费劲。

完整代码如下:

class Solution {
public:
	bool hasValidPath(vector<vector<int>>& grid) {
		int m = grid.size(), n = grid[0].size();
		vector<vector<int>> flag(m, vector<int>(n, 0));
		vector<vector<int>> dirs = { {0,-1},{0,1},{-1,0},{1,0} };//左右上下
		queue<pair<int, int>> q;
		q.push(make_pair(0, 0));
		while (!q.empty()) {
			pair<int, int> p = q.front();
			int u = p.first, v = p.second;
			int src = grid[u][v];
			if (u == m - 1 && v == n - 1)return true;
			q.pop();
			flag[u][v] = 1;
			for (int i = 0; i < dirs.size(); ++i) {
				int x = u + dirs[i][0], y = v + dirs[i][1];
				if (x >= 0 && x < m&&y >= 0 && y < n && flag[x][y] == 0) {
					int dest = grid[x][y];
					if (grid[u][v] == 1) {
						if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
							(i == 1 && (dest == 1 || dest == 3 || dest == 5))) {
							q.push(make_pair(x, y));
						}
					}
					else if (grid[u][v] == 2) {
						if ((i == 2 && (dest == 2 || dest == 3 || dest == 4)) ||
							(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
							q.push(make_pair(x, y));
						}
					}
					else if (grid[u][v] == 3) {
						if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
							(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
							q.push(make_pair(x, y));
						}
					}
					else if (grid[u][v] == 4) {
						if ((i == 1 && (dest == 1 || dest == 3 || dest == 5)) ||
							(i == 3 && (dest == 2 || dest == 5 || dest == 6))) {
							q.push(make_pair(x, y));
						}
					}
					else if (grid[u][v] == 5) {
						if ((i == 0 && (dest == 1 || dest == 4 || dest == 6)) ||
							(i == 2 && (dest == 2 || dest == 3 || dest == 4))) {
							q.push(make_pair(x, y));
						}
					}
					else if (grid[u][v] == 6) {
						if ((i == 1 && (dest == 1 || dest == 3 || dest == 5)) ||
							(i == 2 && (dest == 2 || dest == 3 || dest == 4))) {
							q.push(make_pair(x, y));
						}
					}
				}
			}
		}
		return false;
	}
};

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

LeetCode Four Divisors

1390. Four Divisors

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

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

给定一个数组,问其中哪些数只有4个因子,把只有4个因子的数对应的所有因子加起来。

也是很无聊的一个题,按题意照做即可,注意求解因子的时候只需要循环到sqrt(v)即可,因为如果一个因子大于sqrt(v)的话,其对应的另一个因子肯定小于sqrt(v),也就是之前已经遍历过了。

完整代码如下:

class Solution {
public:
	void FindDivisors(int v, vector<int>& ans) {
		int mid = sqrt(v);
		for (int i = 1; i <= mid; ++i) {
			if (v%i == 0) {
				ans.push_back(i);
				if (v / i != i)ans.push_back(v / i);
			}
		}
	}
	int sumFourDivisors(vector<int>& nums) {
		int ans = 0;
		for (int i = 0; i < nums.size(); ++i) {
			vector<int> divs;
			FindDivisors(nums[i], divs);
			if (divs.size() == 4) {
				for (int j = 0; j < divs.size(); ++j)ans += divs[j];
			}
		}
		return ans;
	}
};

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

LeetCode Create Target Array in the Given Order

1389. Create Target Array in the Given Order

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

  • Initially target array is empty.
  • From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
  • Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]
Output: [1]

Constraints:

  • 1 <= nums.length, index.length <= 100
  • nums.length == index.length
  • 0 <= nums[i] <= 100
  • 0 <= index[i] <= i

很无聊的一个题。给定一个值数组nums,和一个下标数组index,表示数nums[i]插入到index[i]所在位置。有可能多个数插入到同一个位置了,此时先插入的数要往后挪。

很无聊的一个题,模拟题意照做即可,完整代码如下:

class Solution {
public:
	vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
		int n = nums.size();
		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			ans.insert(ans.begin() + index[i], nums[i]);
		}
		return ans;
	}
};

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

LeetCode Longest Happy Prefix

1392. Longest Happy Prefix

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

Constraints:

  • 1 <= s.length <= 10^5
  • s contains only lowercase English letters.

给定一个字符串,要求找出这个字符串中前缀和后缀相等的最长子串。本质是KMP算法中求解模式串的next数组的过程。KMP算法解读请看这篇博客: http://code.bitjoy.net/2016/05/05/leetcode-implement-strstr/

因为在KMP算法中,next[i]表示i之前的字符串中前缀和后缀相等的最大长度,不包括i,而本题是需要考虑以最后一个字符结尾的情况,所以我们在原字符串后面随便增加一个char,则可直接套用KMP中求解next数组的方法,然后取next[n-1]即可。

完整代码如下:

class Solution {
public:
	string longestPrefix(string s) {
		s = s + ".";
		int n = s.size();
		vector<int> next(n, 0);
		next[0] = -1;
		int i = 0, j = -1;
		while (i < n - 1) {
			if (j == -1 || s[i] == s[j]) {
				++i;
				++j;
				next[i] = j;
			}
			else {
				j = next[j];
			}
		}
		return s.substr(0, next[n - 1]);
	}
};

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

LeetCode Find First and Last Position of Element in Sorted Array

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

给定一个有序数组,里面可能有重复元素,要求找出某个元素所有出现位置的起始位置和终止位置。

由于是有序数组,所以直接二分搜索,需要注意的是如果是找起始位置,则找到目标元素后还应该继续往左找,可以想象mid一直遇到target,则要不断执行r=mid-1,直到退出while循环,此时老的mid是等于target的最小下标,所以要返回r+1。类似的,如果找终止位置,则遇到相等后还要继续往右找,即l=mid+1,失败的时候返回上一个mid,即l-1。

完整代码如下:

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

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

LeetCode Maximum Performance of a Team

1383. Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers. 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n

给定n个工程师,每个工程师有自己的速度值speed和效率值efficiency,一个包含k个工程师的团队的总体performance等于所有工程师的速度之和乘以最小效率:sum(speed)*min(efficiency)。问最多选k个工程师,最大的performance是多少。

我一开始被“最多k个”迷惑了,一直以为是一个DP题,后来看题解发现不是。

由于performance=sum(speed)*min(efficiency),所以首先对n个工程师按efficiency从大到小排序,然后对于前m个工程师,他们的最小efficiency就是当前遍历到的第m个工程师的efficiency。如果m已经超过k,则需要从m个工程师中剔除掉速度最小的工程师,因为此时的min(efficiency)固定是第m个工程师的efficiency,所以只需要剔除速度低的工程师。

那么,如果最优解是少于k个人,这种方法能否找到最优解呢?其实是可以的,因为对于每加入一个工程师,我们都会和当前最优解对比,刚开始的时候,队列中的人数肯定少于k。

完整代码如下:

class Solution {
public:
	int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
		vector<pair<int, int>> workers;
		for (int i = 0; i < n; ++i) {
			workers.push_back(make_pair(efficiency[i], speed[i]));
		}
		sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
		priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆,这是构建最小堆
		long long ans = 0;
		long long sum_speed = 0;
		for (int i = n - 1; i >= 0; --i) {
			sum_speed += workers[i].second;
			pq.push(workers[i].second);
			if (pq.size() > k) {
				sum_speed -= pq.top();
				pq.pop();
			}
			ans = max(ans, sum_speed*workers[i].first);
		}
		return ans % (int)(1e9 + 7);
	}
};

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

LeetCode Balance a Binary Search Tree

1382. Balance a Binary Search Tree

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

Constraints:

  • The number of nodes in the tree is between 1 and 10^4.
  • The tree nodes will have distinct values between 1 and 10^5.

给定一棵二叉搜索树,要求把这棵二叉搜索树进行平衡化处理。一棵平衡二叉搜索树首先要是一棵二叉搜索树,其次要是平衡的,平衡的意思是左右子树的高度差不超过1。

要构造一棵平衡二叉搜索树,其树的根节点应该是整个有序数组的中位数。所以先对原来的二叉搜索树先序遍历,得到有序数组,然后取数组中位数作为根节点,在左右子数组中递归构造二叉搜索树。

完整代码如下:

class Solution {
public:
	void preIter(TreeNode* root, vector<int> &nums) {
		if (root == NULL)return;
		preIter(root->left, nums);
		nums.push_back(root->val);
		preIter(root->right, nums);
	}
	TreeNode* constructBST(vector<int> &nums, int l, int r) {
		if (l > r)return NULL;
		if (l == r)return new TreeNode(nums[l]);

		int mid = l + (r - l) / 2;
		TreeNode* root = new TreeNode(nums[mid]);
		root->left = constructBST(nums, l, mid - 1);
		root->right = constructBST(nums, mid + 1, r);
		return root;
	}
	TreeNode* balanceBST(TreeNode* root) {
		vector<int> nums;
		preIter(root, nums);
		int n = nums.size();
		return constructBST(nums, 0, n - 1);
	}
};

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