669. Trim a Binary Search Tree -----(Medium)

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

 

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 104
• The value of each node in the tree is unique.
• root is guaranteed to be a valid binary search tree.
• 0 <= low <= high <= 104

A:

递归啊，没别的方法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        return helper(root, low, high);
    }
private:
    TreeNode* helper(TreeNode* root, int low, int high ){
        if(!root)
            return root;
        if(root->val < low){
            return helper(root->right, low, high);
        }else if(root->val > high){
            return helper(root->left, low, high);
        }else{ // root->val is in range,  we then need delete both child-tree
            root->left = helper(root->left, low, high);
            root->right = helper(root->right, low, high);
            return root;
        }
    }
};

上面的代码，很快就过了。但是有 memory leak。  真正的工作代码中，应该加上delete（）
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        return helper(root, low, high);
    }
private:
    TreeNode* helper(TreeNode* root, int low, int high ){
        if(!root)
            return root;
        if(root->val < low){
            auto res = helper(root->right, low, high);
            deleteTree(root->left);
            delete(root);
            return res;
        }else if(root->val > high){
            auto res = helper(root->left, low, high);
            deleteTree(root->right);
            delete(root);
            return res;
        }else{ // root->val is in range,  we then need delete both child-tree
            root->left = helper(root->left, low, high);
            root->right = helper(root->right, low, high);
            return root;
        }
    }
    
    void deleteTree(TreeNode* root){
        if(!root)
            return;
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
    }
};

但是上面的代码，在LC中，有error，显示： 判题器可能还在用root指针。 
从error message 来看，leetcode会帮忙删除这些内存。
因此面试的时候，可以说。但是不需要写了

661. Image Smoother

Q:

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:

Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Note:

1. The value in the given matrix is in the range of [0, 255].
2. The length and width of the given matrix are in the range of [1, 150].

A:

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int m = M.size(), n = M[0].size();
        vector<vector<int> > res(m, vector<int>(n,0));
        for(int i =0;i<m;++i)
            for(int j =0;j<n;++j)
            {
                int c = 0, sum =0;
                for(int a=-1;a<=1;++a)
                    for(int b = -1;b<=1;++b)
                    {
                        if(i+a>=0 && i+a<m && j+b >=0 && j+b <n){
                            ++c;
                            sum += M[i+a][j+b];
                        }
                    }
                res[i][j] = sum/c;
            }
        return res;        
    }
};

657. Robot Return to Origin -E

Q:

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.

Note: The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.

Example 1:

Input: "UD"
Output: true 
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

 

Example 2:

Input: "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

A:

class Solution {
public:
    bool judgeCircle(string moves) {
        int H = 0, V = 0;
        for(char ch:moves)
        {
            if(ch == 'L')
                --H;
            else if(ch == 'R')
                ++H;
            else if(ch =='U')
                ++V;
            else // (ch == 'D')
                --V;
        }
        return H==0 && V == 0;
    }
};

645. Set Mismatch ----E

Q:

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

1. The given array size will in the range [2, 10000].
2. The given array's numbers won't have any order.

A:

不用XOR，还要分。  就用a-b                 a^2 - b^2 

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        long n = nums.size();
        long sum=0, sum2 = 0;
        for(auto k : nums){
            sum += k;
            sum2 += k*k;
        }
        long t1= (1+n)* n /2;
        long t2 = n*(n+1)*(2*n+1)/6;
        
        int subOf2 = sum - t1; // dup - miss = sum - t1
        // dup^2 - miss^2 = sum2 - t2
        int addOf2 = (sum2-t2) / (sum - t1);
        int dup = (subOf2 + addOf2) / 2;
        int miss = (addOf2 - subOf2) / 2;
        vector<int> res{dup, miss};
        return res;
    }
};

错误：

int 相乘的时候，中间结果依然会用int。因此为防溢出，直接用long

------------------------解法 2   自己以前的思路，看见一个就找到其对应的位置------------

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        int dup = 0;
        for(int i =0;i<n;i++){
            if(nums[i] != i+1){
                int nextIndex = nums[i] - 1;
                if(nums[i] == nums[nextIndex]){
                    dup = nums[i];
                    break;
                }
                nums[i] = nums[nextIndex];
                nums[nextIndex] = nextIndex + 1;
                --i;
            }            
        }
        int diff = accumulate(nums.begin(), nums.end(),0) - n*(n+1)/2;
        int miss = dup - diff;
        vector<int> res{dup,miss};
        return res;
    }
};

Errors:

忘了做 --i;

628. Maximum Product of Three Numbers --E

Q:

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

 

Example 2:

Input: [1,2,3,4]
Output: 24

 

Note:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

 

A:

注意vector 排序的语法

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(nums[0]>=0 || nums[n-1]<=0)
            return nums[n-1] * nums[n-2] * nums[n-3];
        int v1 = nums[n-1] * nums[n-2] * nums[n-3];  // trhe possible Positive
        int v2 = nums[n-1] * nums[1] * nums[0];    // two negative + 1 positive
        return max(v1,v2);        
    }
};

606. Construct String from Binary Tree -------E

Given the root node of a binary tree, your task is to create a string representation of the tree following a specific set of formatting rules. The representation should be based on a preorder traversal of the binary tree and must adhere to the following guidelines:

• Node Representation: Each node in the tree should be represented by its integer value.

• Parentheses for Children: If a node has at least one child (either left or right), its children should be represented inside parentheses. Specifically:

  • If a node has a left child, the value of the left child should be enclosed in parentheses immediately following the node's value.
  • If a node has a right child, the value of the right child should also be enclosed in parentheses. The parentheses for the right child should follow those of the left child.

• Omitting Empty Parentheses: Any empty parentheses pairs (i.e., ()) should be omitted from the final string representation of the tree, with one specific exception: when a node has a right child but no left child. In such cases, you must include an empty pair of parentheses to indicate the absence of the left child. This ensures that the one-to-one mapping between the string representation and the original binary tree structure is maintained.

  In summary, empty parentheses pairs should be omitted when a node has only a left child or no children. However, when a node has a right child but no left child, an empty pair of parentheses must precede the representation of the right child to reflect the tree's structure accurately.

 

Example 1:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

Example 2:

Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except the () after 2 is necessary to indicate the absence of a left child for 2 and the presence of a right child.

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -1000 <= Node.val <= 1000

A:

关键是仔细分析理解，从树的角度来看，如果只有左子树，那么右子树可以不管

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
        if(t == nullptr)
            return "";
        if(t->left == nullptr && t->right == nullptr)
            return to_string(t->val);
        else if(t->right == nullptr)
            return to_string(t->val) + "(" + tree2str(t->left) + ")";
        else 
            return to_string(t->val) + "(" + tree2str(t->left) + ")" + "(" + tree2str(t->right) + ")";
    }
};

---------------这次，为了谨慎起见， 确保root不为null----------------

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

string tree2str(TreeNode* root) {// root is not null

if(!root->left && !root->right){

return to_string(root->val);

}else if(!root->left && root->right){

return to_string(root->val)+"()"+"(" + tree2str(root->right) +")";

}else if(root->left && !root->right){

return to_string(root->val)+ "(" + tree2str(root->left) +")";

}else{

return to_string(root->val)+ "(" + tree2str(root->left) +")("+ tree2str(root->right) +")";

}

}

};