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方...