A Code

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

Code ( Language :C++) ( Judger :cloudjudge-cluster-7) Edit class Solution { public : /** * @param S: a string * @param K: int * @return: the lexicographically smallest string */ string orderlyQueue ( string &S, int K) { // Write your code here. if (K > 1 ){ sort(S.begin(), S.end()); return S; } string res = S; for ( int i = 1 ; i < S.size(); i++){ res = min(res, S.substr(i) + S.substr( 0 , i)); } return res; } };

Code ( Language :C++) Edit class Solution { public : /** * @param n: a integer * @return: return a integer */ int countPrimes ( int n) { // write your code here if (n <= 2 ){ return 0 ; } std :: vector < bool > notPrime(n - 1 , false ); int res = 0 ; for ( int i = 2 ; i < n; i++){ if (notPrime[i] == false ){ res++; } for ( int j = 2 ; i * j < n; j++){ notPrime[i * j] = true ; } } return res; } };

Code ( Language :C++) Edit class Solution { public : /** * @param n: a number * @return: Gray code */ vector < int > grayCode( int n) { // write your code here int size = 1 << n; vector < int > res(size, 0 ); for ( int i = 0 ; i < size; i++){ res[i] = i ^ (i >> 1 ); } return res; } };

ode ( Language :C++) Edit class Solution { public : /** * @param S: a string * @param K: int * @return: the lexicographically smallest string */ string orderlyQueue ( string &S, int K) { // Write your code here. if (K > 1 ) { sort(S.begin(), S.end()); return S; } string res = S; for ( int i = 1 ; i < S.length(); i++) res = min(res, S.substr(i) + S.substr( 0 , i)); return res; } };

class Solution { public : /** * @param n: a number * @return: Gray code */ vector < int > grayCode( int n) { // write your code here int size = 1 << n; vector < int > res(size, 0 ); for ( int i = 0 ; i < size; i++){ res[i] = i ^ (i >> 1 ); } return res; } };

Code ( Language :C++) Edit class Solution { public : /** * @param accounts: List[List[str]] * @return: return a List[List[str]] */ vector < vector < string >> accountsMerge( vector < vector < string >>& accounts) { vector < vector < string >> res; unordered_map < string , string > root; unordered_map < string , string > owner; unordered_map < string , set < string >> m; //inital and prepare for ( auto account : accounts) { for ( int i = 1 ; i < account.size(); ++i) { root[account[i]] = account[i]; owner[account[i]] = account[ 0 ]; } } // establish connection for ( auto account : accounts) { string p = find(account[ 1 ], root); for ( int i = 2 ; i < account.size(); ++i) { root[find(a...

Code ( Language :C++) Edit class Solution { public : /** * @param A: an array * @param B: an array * @return: the minimum number of swaps to make both sequences strictly increasing */ int minSwap ( vector < int >& A, vector < int >& B) { //动态规划. //设定状态: //dp[i][0]表示A和B [0, i] 的元素交换至有序, 并且不交换 A[i], B[i] 时的最小交换次数 //dp[i][1]表示A和B [0, i] 的元素交换至有序, 并且交换 A[i], B[i] 时的最小交换次数 //因为题目数据保证有解, 所以以下两个条件至少成立其中之一: //1. A[i] > A[i - 1] && B[i] > B[i - 1] //2. A[i] > B[i - 1] && B[i] > A[i - 1] int n = A.size(); if (n == 0 ){ return 0 ; } vector < int > swap(n, n), noSwap(n, n); swap[ 0 ] = 1 ; noSwap[ 0 ] = 0 ; for ( int i = 1 ; i < n; ++i) { if (A[i] > A[i - 1 ] && B[i] > B[i - 1 ]) { swap[i] = swap[i - 1 ] + 1 ; //当前非得交换，前面也要交换 noSwap[i] = noSwap[i...

Code ( Language :C++) Edit Description There are a total of n courses you have to take, labeled from  0  to  n - 1 . Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:  [0,1] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. Example Given n =  2 , prerequisites =  [[1,0]] Return  [0,1] Given n =  4 , prerequisites =  [1,0],[2,0],[3,1],[3,2]] Return  [0,1,2,3]  or  [0,2,1,3] class Solution { public : /* * @param numCourses: a total of n courses * @param prerequisites: a list of prerequisite pairs * @return: the course order */ vector < int > findOrder( int numCo...

Code ( Language :C++) Edit class Solution { public : /** * @param numCourses a total of n courses * @param prerequisites a list of prerequisite pairs * @return true if can finish all courses or false */ bool canFinish ( int numCourses, vector <pair< int , int >>& prerequisites) { // Write your code here vector < vector < int >> graph(numCourses, vector < int >()); vector < int > in(numCourses); for ( auto a : prerequisites) { graph[a.second].push_back(a.first); ++in[a.first]; } queue < int > q; for ( int i = 0 ; i < numCourses; ++i) { if (in[i] == 0 ) q.push(i); //想到用indegree是关键 } int nodeN = 0 ; //另一种判断 while (!q.empty()) { nodeN++; //另一种判断 int t = q.front(); q.pop(); for ( auto a : graph[t]) { --in[a]; ...

Code ( Language :C++) Edit /** * Definition of Interval: * classs Interval { * int start, end; * Interval(int start, int end) { * this->start = start; * this->end = end; * } * } */ class Solution { public : /** * @param intervals: an array of meeting time intervals * @return: the minimum number of conference rooms required */ int minMeetingRooms ( vector <Interval> &intervals) { // Write your code here // sweep line? 此题要理解并背诵 vector < int > starts, ends; for ( auto i : intervals){ starts.push_back(i.start); ends.push_back(i.end); } sort(starts.begin(), starts.end()); sort(ends.begin(), ends.end()); int endPos = 0 , cnt = 0 ; for ( int i = 0 ; i < intervals.size(); i++){ if (starts[i] <= ends[endPos]){ cnt++; } else { ...