A Code

Code ( Language :C++) ( Judger :cloudjudge-cluster-9) Edit class Solution { public : /** * @param s: the given string * @return: whether this string is valid */ bool checkValidString ( string &s) { // Write your code here const int size = s.size(); if (size == 0 ){ return true ; } int left = 0 ; for ( int i = 0 ; i < size; i++){ if (s[i] == '(' || s[i] == '*' ){ left++; } else { left--; } if (left < 0 ){ return false ; } } int right = 0 ; for ( int i = size - 1 ; i >= 0 ; i--){ if (s[i] == ')' || s[i] == '*' ){ right++; } else { right--; } if (right < 0 ){ retur...

这题要注意的是用一个map< int, int >来存储id和machine之间的映射关系。注意不能用map< int, vector > 来存储一个machine和一串id，这样就没法找某个id对应哪个machine了。 另外还要 用一个set来存储已经用过的id。 另外再强调map和set的key都是默认从大到小排序的。记得lower_bound()这个函数非常非常有用！map和set都可以用！ class Solution { public:     int n, k;     map<int, int> shards;   //stores id<->machine mapping, multiple ids to one machine     set<int> ids; //stores ids to make sure it is not reused     /*      * @param n: a positive integer      * @param k: a positive integer      * @return: a Solution object      */     static Solution create(int n, int k)  {         Solution sol = Solution();         sol.n = n;         sol.k = k;         return sol;     }     /*      * @param machine_id: An integer   ...

priority queue 实现的数据结构是红黑树，balanced binary search tree。 471. Top K Frequent Words Code ( Language :C++) ( Judger :ip-172-31-12-4) Edit class Solution { public : /** * @param words: an array of string * @param k: An integer * @return: an array of string */ struct cmp { bool operator () ( const pair< string , int > &a, const pair< string , int > &b) { return a.second > b.second || (a.second == b.second && a.first < b.first); } }; vector < string > topKFrequentWords( vector < string > &words, int k) { // write your code here unordered_map < string , int > mp; for ( auto s : words){ mp[s]++; } priority_queue<pair< string , int >, vector <pair< string , int >>, cmp> pq; for ( auto i : mp){ pq.push({i.first, i.second}); if (pq.size...

Code ( Language :C++) ( Judger :ip-172-31-21-252) Edit // Forward declaration of the knows API. bool knows ( int a, int b) ; class Solution { public : /** * @param n a party with n people * @return the celebrity's label or -1 */ int findCelebrity ( int n) { // Write your code here int i = 0 ; for ( int j = 1 ; j < n; j++){ i = knows(j, i) ? i : j; } for ( int j = 0 ; j < n; j++){ if (i == j){ continue ; } if (knows(i, j) || !knows(j, i)){ return -1 ; } } return i; } };

9/15/2019 三种方法： 方法1：iteration，使用inorder iteration模板。时间复杂度O(n)，空间复杂度O(height), genrally O(logN). class Solution { public: /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ bool isValidBST(TreeNode * root) { // write your code here stack<TreeNode *>stk; TreeNode *pre = NULL; TreeNode *p = root; while(!stk.empty() || p != NULL){      while(p != NULL){           stk.push(p);           p = p->left;       }        TreeNode *tmp = stk.top();        stk.pop(); if(pre != NULL){ if(pre->val >= tmp->val){ return false; } } pre = tmp; p = tmp->right; } return true; } }; 方法二：recursion，需要另外一个helper函数辅助。和iteration的思路一致，用recursion方式（占用stack内存）替代方法一stack（占用heap内存）。一般recursion都可以对应一个带有stack的iteration方...

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all of its descendants. Here's an example: 10 / \ 5 15 / \ \ 1 8 7 The Largest BST Subtree in this case is the highlighted one.  The return value is the subtree's size, which is 3. Hint: You can recursively use algorithm similar to  98. Validate Binary Search Tree  at each node of the tree, which will result in O(nlogn) time complexity. Follow up: Can you figure out ways to solve it with O(n) time complexity? class Solution { public : int largestBSTSubtree(TreeNode* root) { if (!root) return 0 ; if (isValid(root, INT_MIN, INT_MAX)) return count(root); return max(largestBSTSubtree(root->left), largestBSTSubtree(root-> right)); } bool isValid(TreeNode* root, int mn, int mx) { if (!root) return true ;...

Code ( Language :C++) ( Judger :ip-172-31-21-252) Edit /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public : /** * @param root: a TreeNode * @return: a list of integer */ void findLeaves (TreeNode *root, vector < int > &res) { if (root == NULL ){ return ; } if (root->left == NULL && root->right == NULL ){ res.push_back(root->val); } findLeaves(root->left, res); findLeaves(root->right, res); return ; } vector < int > boundaryOfBinaryTree(TreeNode * root) { // write your code here //这种题就要拼思路了，有思路很简单。没思路现象，容易走错路。 //1, 找leaves。 //2, 找左边界。 //3, 找右边界。 vector < ...

443. String Compression (如果没有把大的逻辑先定下来，写这种题就是找死啊) Easy 437 1387 Favorite Share Given an array of characters, compress it  in-place . The length after compression must always be smaller than or equal to the original array. Every element of the array should be a  character  (not int) of length 1. After you are done  modifying the input array  in-place , return the new length of the array.   Follow up: Could you solve it using only O(1) extra space? class Solution { public:     int compress(vector<char>& chars) {         int i = 0;         const int size = chars.size();         if(size < 2){             return size;         }         int cnt = 1;         for(int j = 1; j < size; j++){             if(chars[j] == chars[j ...

Code ( Language :C++) ( Judger :cloudjudge-cluster-5) Edit class Solution { public : /** * @param s: the IP string * @return: All possible valid IP addresses */ vector < string > restoreIpAddresses( string &s) { // write your code here vector < string > res; const int size = s.size(); if (size < 4 || size > 12 ){ return res; } vector < string > resElem; dfs(s, res, resElem, 0 ); return res; } void dfs ( string &s, vector < string > &res, vector < string > &resElem, int start) { int size = s.size(); if (start == s.size()){ if (resElem.size() == 4 ){ res.push_back(resElem[ 0 ] + "." + resElem[ 1 ] + "." + resElem[ 2 ] + "." + resElem[ 3 ]); } return ; } if (resElem.size() > 4 ){ ...

Code ( Language :C++) ( Judger :ip-172-31-5-19) Edit //OOD design //注意throw exception的操作。 class GameEndException { public : string what () { return "Game is ended!" ; } } gameEndException; class AlreadyTakenException { public : string what () { return "Already taken!" ; } } alreadyTakenException; class TicTacToe { private : //std::vector<vector<char>> board(3, vector<char>(3); char board[ 3 ][ 3 ]; char curPlayer; bool gameEnd; public : /** Initialize your data structure here. */ TicTacToe() { initialize(); } void initialize () { for ( int i = 0 ; i < 3 ; i++){ for ( int j = 0 ; j < 3 ; j++){ board[i][j] = '-' ; } } curPlayer = 'X' ; gameEnd = false ; } void changePlayer () { if (curPlayer == 'X' ){ ...

Code ( Language :C++) ( Judger :cloudjudge-cluster-6) Edit class Solution { public : /** * @param source: List[str] * @return: return List[str] */ vector < string > removeComments( vector < string > &source) { // write your code here vector < string > res; bool blocked = false ; string out = "" ; for ( string line : source) { for ( int i = 0 ; i < line.size(); ++i) { if (!blocked) { //区分是否 blocked，即是否在/*里面 if (i == line.size() - 1 ) { out += line[i]; } else { string t = line.substr(i, 2 ); if (t == "/*" ) { blocked = true ; ++i; } else if (t == "//" ) break ; ...