A Code

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 :cloudjudge-cluster-5) 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: the root of binary tree * @param target: An integer * @return: all valid paths */ vector < vector < int >> binaryTreePathSum2(TreeNode * root, int target) { // write your code here vector < vector < int >> res; vector < int > path; dfs(root, target, res, path); return res; } void dfs (TreeNode *root, int target, vector < vector < int >> &res, vector < int > &path) { //int sum = 0; if (root == NULL ){ return ; } path.push_back(root->val); /...

class Solution { public : /** * @param inorder: A list of integers that inorder traversal of a tree * @param postorder: A list of integers that postorder traversal of a tree * @return: Root of a tree */ unordered_map < int , int > mp; TreeNode * buildTree ( vector < int > &preorder, vector < int > &inorder) { // write your code here // preorder: 根左右 // inorder: 左根右 // 根据preoder中的根，找到inorder中position, then the left side is the left substree, the right side is the right substree // recursion TreeNode *res; int sizeN = preorder.size(); if (sizeN == 0 ){ return NULL ; } for ( int i = 0 ; i < sizeN; i++){ mp[inorder[i]] = i; } return build(preorder, 0 , preorder.size() - 1 , inorder, 0 , inorder.size() - 1 ); } TreeNode * build ( vector < int > &preorder, int...

class Solution { public : /** * @paramn n: An integer * @return: A list of root */ vector <TreeNode *> generateTrees( int n) { // write your code here return generate( 0 , n - 1 ); } vector <TreeNode *> generate( int start, int end){ vector <TreeNode *> res; if (start > end){ res.push_back( NULL ); return res; } for ( int i = start; i <= end; i++){ vector <TreeNode *> left = generate(start, i - 1 ); vector <TreeNode *> right = generate(i + 1 , end); for ( int j = 0 ; j < left.size(); j++){ for ( int k = 0 ; k < right.size(); k++){ TreeNode * root = new TreeNode(i + 1 ); res.push_back(root); root->left = left[j]; root->right = right[k]; } } } } };

Code ( Language :C++) ( Judger :ip-172-31-21-252) Edit class Solution { public : /** * @param num: a string * @param k: an integer * @return: return a string */ string removeKdigits ( string &num, int k) { // write your code here //单调栈 stack < char > stk; string res; for ( int i = 0 ; i < num.size(); i++){ while (!stk.empty() && stk.top() > num[i] && k > 0 ){ stk.pop(); k--; } stk.push(num[i]); } while (!stk.empty()){ res = stk.top() + res; stk.pop(); } res = res.substr( 0 , num.size() - k); //corner case 重复的情况 int idx = 0 ; while (res[idx] == '0' && idx < res.size()){ //corner case 0打头 idx++; } res = res.substr(idx); return res.size() ? res : "0...

Code ( Language :C++) ( Judger :ip-172-31-18-231) Edit class Solution { public : /* * @param A: A list of integers * @param elem: An integer * @return: The new length after remove */ int removeElement ( vector < int > &A, int elem) { // write your code here int start = 0 ; for ( int i = 0 ; i < A.size(); i++){ if (A[i] != elem){ A[start++] = A[i]; } } return start; } };

Description 中文 English Given an array which consists of non-negative integers and an integer m, we are going to split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. If  n  is the length of array, assume the following constraints are satisfied: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n) Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input：[7,2,5,10,8], m = 2 Output：18 Explanation： There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18. Example 2: Input：[1,4,4], m = 3 Output：4 Explanation： There is a way to split nums into three subarrays. The best way is to split it into [1], [4] and [4], where the largest sum among the three subarrays is only 4. 这个题最优解法是binary search 这里用DP。 参考网上的n...

/** * 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 binary tree * @param sum: the sum * @return: the scheme */ vector < vector < int >> pathSum(TreeNode * root, int sum) { // Write your code here. vector < vector < int >> res; vector < int > resElem; helper(root, res, resElem, sum); return res; } void helper (TreeNode *root, vector < vector < int >> &res, vector < int > &resElem, int sum) { if (root == NULL ){ return ; } if (root->left == NULL && root->right == NULL && sum == root->val){ resElem.push_back(root->val); res.push...

class Solution { public : /** * @param A: an array * @return: is the number of global inversions is equal to the number of local inversions */ bool isIdealPermutation ( vector < int > &A) { // Write your code here // lacal is also global. But global with more than 1 interval is not local; int maxV = A[ 0 ]; for ( int i = 2 ; i < A.size(); i++){ if (maxV > A[i]){ return false ; } maxV = A[i - 2 ]; } return true ; } };