239. Sliding Window Maximum

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> q; vector<int> ret; for (int i = 0; i < nums.size(); i++) { while (!q.empty() && nums[i] >= nums[q.back()]) q.pop_back(); q.push_back(i); while (i >= k && i - k >= q.front()) q.pop_front(); if (i >= k - 1) ret.push_back(nums[q.front()]); } return ret; } };

240. Search a 2D Matrix II

class Solution { private: int nrow, ncol; public: bool searchMatrix(vector<vector<int>>& matrix, int target) { nrow = matrix.size(); if (nrow == 0) return false; ncol = matrix[0].size(); if (ncol == 0) return false; for (int r = 0; r < nrow; r++) { vector<int> &tmp = matrix[r]; int ll = 0, rr = ncol - 1; while (ll <= rr) { int mid = ll + (rr - ll) / 2; if (tmp[mid] > target) rr = mid - 1; else if (tmp[mid] == target) return true; else ll = mid + 1; } } return false; } };

241. Different Ways to Add Parentheses

/** * 思路：tokenize+DFS暴力运算符先后顺序(permutation of operators) */ class Solution { private: vector<string> tokenize(string &input) { stringstream ss(input); vector<string> ret; int tmp; ss >> tmp; ret.push_back(to_string(tmp)); while (!ss.eof()) { char c; ss >> c >> tmp; string str; str.push_back(c); ret.push_back(str); ret.push_back(to_string(tmp)); } return ret; } int calculate(int lhs, string &op, int rhs) { if (op == "+") return lhs + rhs; else if (op == "-") return lhs - rhs; else if (op == "*") return lhs * rhs; } // [left, right] vector<int> dfs(vector<string> &tokens, int left, int right) { if (left + 1 == right || left > right) return vector<int>(); // 非法输入 if (left == right) return vector<int>{stoi(tokens[left])}; // 终止条件 vector<int> ret; for (int i = left + 1; i < right; i += 2) { vector<int> ll = dfs(tokens, left, i - 1); vector<int> rr = dfs(tokens, i + 1, right); for (auto l: ll) { for (auto r: rr) { int val = calculate(l, tokens[i], r); ret.push_back(val); } } } return ret; } public: vector<int> diffWaysToCompute(string input) { vector<string> tokens = tokenize(input); vector<int> ret = dfs(tokens, 0, tokens.size() - 1); //for (auto t: tokens) cout << t << endl; sort(ret.begin(), ret.end()); //ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } };