Skip to content

Latest commit

 

History

History
234 lines (205 loc) · 6.2 KB

2020.11.09~2020.11.15.md

File metadata and controls

234 lines (205 loc) · 6.2 KB
Raw

2020.11.09~2020.11.15

Andrewsher

508. 出现次数最多的子树元素和

题目描述：给你一个二叉树的根结点，请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

/**
 * 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:
    void getTreeSum(TreeNode* root, int& res, unordered_map<int, int>& umap) {
        if(root == nullptr) return;
        int leftSum = 0, rightSum = 0;
        if(root->left) getTreeSum(root->left, leftSum, umap);
        if(root->right) getTreeSum(root->right, rightSum, umap);
        res = leftSum + rightSum + root->val;
        umap[res]++;
        return;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int, int> umap;
        int root_sum;
        getTreeSum(root, root_sum, umap);
        int maxRes = 0;
        for(auto i = umap.begin(); i != umap.end(); i++) {
            maxRes = maxRes > i->second? maxRes: i->second;
        }
        vector<int> res;
        for(auto i = umap.begin(); i != umap.end(); i++) {
            if(i->second == maxRes) res.push_back(i->first);
        }
        return res;
    }
};

525. 连续数组

  • 给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        /* umap[i]存储前缀和[i]第一次出现的位置 */
        unordered_map <int, int> umap;
        umap[0] = -1;
        int curPrefixSum = 0;
        int res = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 1) curPrefixSum++;
            if(nums[i] == 0) curPrefixSum--;
            // curPrefixSum += nums[i];
            if(umap.find(curPrefixSum) != umap.end()) {
                res = res < (i - umap[curPrefixSum])? i - umap[curPrefixSum]: res;
            }
            else {
                umap[curPrefixSum] = i;
            }
        }
        return res;
    }
};

int main() {
    Solution S;
    vector<int> nums = {0, 1, 0};
    cout << S.findMaxLength(nums) << endl;
    return 0;
}

Kayden

110. 平衡二叉树

  • 给定一个二叉树，判断它是否是高度平衡的二叉树。
  • 本题中，一棵高度平衡二叉树定义为：
  • 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def getDepth(node, cur=0):
            if not node: return cur
            return max(getDepth(node.left, cur)+1, getDepth(node.right, cur)+1)

        if not root: return True
        else:
            if abs(getDepth(root.left)-getDepth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right):
                return True
            else: return False

面试题 04.03. 特定深度节点链表

  • 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    vector<ListNode*> listOfDepth(TreeNode* tree) {
        vector<ListNode*> ans;
        queue<TreeNode*> q;
        q.push(tree);
        while(!q.empty()) {
            ListNode* head = new ListNode(0);
            ListNode* tmp = head;
            int qz = q.size();
            while(qz--) {
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
                tmp->next = new ListNode(cur->val);
                tmp = tmp->next;
            }
            ans.push_back(head->next);
            delete head;
        }

        return ans;
    }
};

面试题 02.02. 返回倒数第 k 个节点

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        vector<int> ans;
        ListNode* tmp = head;
        while(tmp) {
            ans.push_back(tmp->val);
            tmp = tmp->next;
        }
        return ans[ans.size()-k];
    }
};
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(k--) fast = fast->next;
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow->val;
    }
};

24. 两两交换链表中的节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return head;
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};

525. 连续数组

  • 给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        vector<int> count_place(2*nums.size()+1, -2); 
        count_place[nums.size()] = -1;
        int ans = 0, count = 0;
        for(int i=0; i<nums.size(); i++) {
            if(nums[i]==0) count--;
            else count++;
            if(count_place[count+nums.size()] >= -1) ans = max(i-count_place[count+nums.size()], ans);
            else count_place[count+nums.size()] = i;
        }
        return ans;
    }
};

Heitao