leetcode 563

563. Binary Tree Tilt

Input:

         1

       /   \

      2     3

Output: 1

Explanation:

Tilt of node 2 : 0

Tilt of node 3 : 0

Tilt of node 1 : |2-3| = 1

Tilt of binary tree : 0 + 0 + 1 = 1

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

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

 * };

 */

class Solution {

public:

    int findTilt(TreeNode* root) {

        if(root == NULL) return ;

        int res = ;

        postorder(root, res);

        return res;

    }

private:

    int postorder(TreeNode* root, int& res){

        if(root == NULL) return ;

        int leftsum= postorder(root->left,res);

        int rightsum = postorder(root->right,res);

        res += abs(leftsum - rightsum);

        return leftsum + rightsum + root->val;

    }

};

566. Reshape the Matrix

class Solution {

public:

    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {

        int m = nums.size(), n = nums[].size(), o = m * n;

        if (r * c != o) return nums;

        vector<vector<int>> res(r, vector<int>(c, ));

        for (int i = ; i < o; i++) res[i / c][i % c] = nums[i / n][i % n];

        return res;

    }

};

572. Subtree of Another Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

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

 * };

 */

class Solution {

    vector<TreeNode*> nodes;

public:

    bool isSubtree(TreeNode* s, TreeNode* t) {

        if (!s && !t) return true;

        if (!s || !t) return false;

        getDepth(s, getDepth(t, -));

        for (TreeNode* n: nodes)

            if (identical(n, t))

                return true;

        return false;

    }

    int getDepth(TreeNode* r, int d) {

        if (!r)

            return -;

        int depth = max(getDepth(r->left, d), getDepth(r->right, d)) + ;

        // Check if depth equals required value

        // Require depth is -1 for tree t (only return the depth, no push)

        if (depth == d)  //递归回去得时候，从树下开始记达到深度位d时记下

            nodes.push_back(r);

        return depth;

    }

    bool identical(TreeNode* a, TreeNode* b) {

        if (!a && !b) return true;

        if (!a || !b || a->val != b->val) return false;

        return identical(a->left, b->left) && identical(a->right, b->right);

    }

};

581. Shortest Unsorted Continuous Subarray

Input: [2, 6, 4, 8, 10, 9, 15]

Output: 5

Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

class Solution {

    public int findUnsortedSubarray(int[] A) {

    int n = A.length, beg = -1, end = -2, min = A[n-1], max = A[0];

    for (int i=1;i<n;i++) {

      max = Math.max(max, A[i]);

      min = Math.min(min, A[n-1-i]);

      if (A[i] < max) end = i;

      if (A[n-1-i] > min) beg = n-1-i;

    }

    return end - beg + 1;

}

}

594. Longest Harmonious Subsequence

Input: [1,3,2,2,5,2,3,7]

Output: 5

Explanation: The longest harmonious subsequence is [3,2,2,2,3].

int findLHS(vector<int>& nums) {

        unordered_map<int,int>m;

        for(auto i: nums)

            m[i]++;

        int res = 0;

        for(auto it:m)

            if(m.count(it.first-1)>0)

                res = max(res, it.second+m[it.first-1]);

        return res;

    }

///////////////////////

int findLHS(vector<int>& nums) {

        unordered_map<int,int>m;

        int res = 0;

        for(auto i: nums){

            m[i]++;

            if(m.count(i+1))

                res = max(res, m[i] + m[i+1]);

            if(m.count(i-1))

                res = max(res, m[i] + m[i-1]);

        }

        return res;

    }

///////////////////////////////////////

 int findLHS(vector<int>& nums) {

        sort(nums.begin(),nums.end());

        int len = 0;

        for(int i = 1, start = 0, new_start = 0; i<nums.size(); i++)

        {

            if (nums[i] - nums[start] > 1)

                start = new_start;

            if (nums[i] != nums[i-1])

                new_start = i;

            if(nums[i] - nums[start] == 1)

                len = max(len, i-start+1);

        }

        return len;

599. Minimum Index Sum of Two Lists

Input:

["Shogun", "Tapioca Express", "Burger King", "KFC"]

["KFC", "Shogun", "Burger King"]

Output: ["Shogun"]

Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

  vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {

        vector<string>res;

        unordered_map<string,int>m;

        int min = INT_MAX;

        for(int i = ; i < list1.size(); i++) m[list1[i]] = i;

        for(int i = ; i < list2.size(); i++)

            if(m.count(list2[i]) != )

                if(m[list2[i]] + i < min) min = m[list2[i]] + i, res.clear(), res.push_back(list2[i]);

                else if(m[list2[i]] + i == min) res.push_back(list2[i]);

        return res;

    }

606. Construct String from Binary Tree

Input: Binary tree: [1,2,3,4]

       1

     /   \

    2     3

   /

  4     

Output: "1(2(4))(3)"


Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

class Solution {

public:

    string tree2str(TreeNode* t) {

        return !t ? "" : to_string(t->val) + (t->left ? "(" + tree2str(t->left) + ")" : t->right ? "()" : "")

                                           + (t->right ? "(" + tree2str(t->right) + ")" : "");

    }

};

617. Merge Two Binary Trees

Input:

	Tree 1                     Tree 2

          1                         2

         / \                       / \

        3   2                     1   3

       /                           \   \

      5                             4   7

Output:

Merged tree:

	     3

	    / \

	   4   5

	  / \   \

	 5   4   7

class Solution {

public:

    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

        if (!t1 || !t2) return t1 ? t1 : t2;

        TreeNode* node = new TreeNode(t1->val + t2->val);

        node->left = mergeTrees(t1->left, t2->left);

        node->right = mergeTrees(t1->right, t2->right);

        return node;

    }

};

633. Sum of Square Numbers

Input: 5

Output: True

Explanation: 1 * 1 + 2 * 2 = 5

bool judgeSquareSum(int c) {

        for(int i=;i<=sqrt(c);i++) {

            int t=sqrt(c-i*i);

            if(t*t==c-i*i) return true;

        }

        return false;

    }

637. Average of Levels in Binary Tree

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

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

 * };

 */

class Solution {

public:

       vector<double> averageOfLevels(TreeNode* root) {

        vector<double> res;

        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty()) {

            long temp=;

            int s=q.size();

            for(int i=;i<s;i++) {

                TreeNode* t=q.front();

                q.pop();

                if(t->left) q.push(t->left);

                if(t->right) q.push(t->right);

                temp+=t->val;

            }

            res.push_back((double)temp/s);

        }

        return res;

    }

};

645. Set Mismatch

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

Output: [2,3]

思路：使数组按123。。。n来排序，如果当前的内容和index不匹配，则交换

vector<int> findErrorNums(vector<int>& nums) {

        for(int i = ; i<nums.size(); i++){

            while(nums[i] != nums[nums[i] - ])swap(nums[i], nums[nums[i] - ]);

        }

        for(int i = ; i<nums.size() ; i++){

            if(nums[i] != i + )return {nums[i], i + };

        }

    }

653. Two Sum IV - Input is a BST

Input:

    5

   / \

  3   6

 / \   \

2   4   7

Target = 9

Output: True

//方法一：使用map来进行一次遍历
bool findTarget(TreeNode* root, int k) {

        unordered_set<int> set;

        return dfs(root, set, k);

    }

    bool dfs(TreeNode* root, unordered_set<int>& set, int k){

        if(root == NULL)return false;

        if(set.count(k - root->val))return true;

        set.insert(root->val);

        return dfs(root->left, set, k) || dfs(root->right, set, k);

    }

/////////////////////////////////////////////////////

//方法二：先使用中序遍历使其按小到大来排序，然后对排序后的数组进行首尾相加

bool findTarget(TreeNode* root, int k) {

        vector<int> nums;

        inorder(root, nums);

        for(int i = , j = nums.size()-; i<j;){

            if(nums[i] + nums[j] == k)return true;

            (nums[i] + nums[j] < k)? i++ : j--;

        }

        return false;

    }

    void inorder(TreeNode* root, vector<int>& nums){

        if(root == NULL)return;

        inorder(root->left, nums);

        nums.push_back(root->val);

        inorder(root->right, nums);

    }

///////////////////////////////////////////////////////

 bool findTarget(TreeNode* root, int k) {

        return dfs(root, root,  k);

    }

    bool dfs(TreeNode* root,  TreeNode* cur, int k){

        if(cur == NULL)return false;

        return search(root, cur, k - cur->val) || dfs(root, cur->left, k) || dfs(root, cur->right, k);

    }

    bool search(TreeNode* root, TreeNode *cur, int value){

        if(root == NULL)return false;

        return (root->val == value) && (root != cur)

            || (root->val < value) && search(root->right, cur, value)

                || (root->val > value) && search(root->left, cur, value);

    }

巴特西

leetcode 563 - 653

633. Sum of Square Numbers

637. Average of Levels in Binary Tree

645. Set Mismatch

653. Two Sum IV - Input is a BST

最新文章

热门文章