#218.天际线问题
经典分治算法，虽然是困难题但值得研究一下！！
public List<List<Integer>> getSkyline(int[][] buildings) {if(buildings.length == 0){return new ArrayList<>();}return merge(buildings, 0, buildings.length - 1);
}private List<List<Integer>> merge(int[][] buildings, int start, int end) {List<List<Integer>> res = new ArrayList<>();//只有一个建筑, 将 [x, h], [y, 0] 加入结果if (start == end) {List<Integer> temp = new ArrayList<>();temp.add(buildings[start][0]);temp.add(buildings[start][2]);res.add(temp);temp = new ArrayList<>();temp.add(buildings[start][1]);temp.add(00);res.add(temp);return res;}int mid = (start + end) >>> 1;//第一组解List<List<Integer>> Skyline1 = merge(buildings, start, mid);//第二组解List<List<Integer>> Skyline2 = merge(buildings, mid + 1, end);//下边将两组解合并int h1 = 0;int h2 = 0;int i = 0;int j = 0;while (i < Skyline1 .size() || j < Skyline2 .size()) {long x1 = i < Skyline1 .size() ? Skyline1 .get(i).get(0) : Long.MAX_VALUE;long x2 = j < Skyline2 .size() ? Skyline2 .get(j).get(0) : Long.MAX_VALUE;long x = 0;//比较两个坐标if (x1 < x2) {h1 = Skyline1 .get(i).get(1);x = x1;i++;} else if (x1 > x2) {h2 = Skyline2 .get(j).get(1);x = x2;j++;} else {h1 = Skyline1 .get(i).get(1);h2 = Skyline2 .get(j).get(1);x = x1;i++;j++;}//更新 heightint height = Math.max(h1, h2);//重复的解不要加入if (res.isEmpty() || height != res.get(res.size() - 1).get(1)) {List<Integer> temp = new ArrayList<>();temp.add((int) x);temp.add(height);res.add(temp);}}return res;
}
用扫描线思想：
class Solution {
public:vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {vector<pair<int,int>> h;multiset<int> m;vector<vector<int>> res;//1、将每一个建筑分成“两个部分”，例如:[2,9,10]可以转换成[2，-10][9,10]，我们用负值来表示左边界for(const auto& b:buildings){h.push_back({b[0], -b[2]});h.push_back({b[1], b[2]});}//2、根据x值对分段进行排序sort(h.begin(),h.end());int prev = 0, cur = 0;m.insert(0);//3、遍历for (auto i:h){if (i.second < 0) m.insert(-i.second); //左端点，高度入堆else m.erase(m.find(i.second)); //右端点，高度出堆cur = *m.rbegin(); //当前最大高度高度if (cur != prev) { //当前最大高度不等于最大高度perv表示这是一个转折点res.push_back({i.first, cur}); //添加坐标prev = cur; //更新最大高度}}return res;}
};
#227.基本计算器II
class Solution {
public:int calculate(string s) {long res = 0, curRes = 0, num = 0, n = s.size();char op = '+';for (int i = 0; i < n; ++i) {char c = s[i];if (c >= '0' && c <= '9') {num = num * 10 + c - '0';}if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {switch (op) {case '+': curRes += num; break;case '-': curRes -= num; break;case '*': curRes *= num; break;case '/': curRes /= num; break;}if (c == '+' || c == '-' || i == n - 1) {res += curRes;curRes = 0;}op = c;num = 0;} }return res;}
};