美文网首页
Day23 对称的二叉树 + 不用加减乘除做加法 + 数据流中的

Day23 对称的二叉树 + 不用加减乘除做加法 + 数据流中的

作者: 吃掉夏天的怪物 | 来源:发表于2021-07-06 14:39 被阅读0次

    TODO:*
    都不大会做都重做一遍吧!

    剑指 Offer 28. 对称的二叉树(简单)

    方法一

    class Solution {
    public:
        bool is(TreeNode* L, TreeNode* R){
            if(L==nullptr && R==nullptr) return true;
            else if(L == nullptr || R == nullptr ||(L->val != R->val)) return false;
            return is(L->left,R->right) && is(L->right,R->left);
        }
        bool isSymmetric(TreeNode* root) {
            if(root == nullptr) return true;
            return is(root->left,root->right);
        }
    };
    

    剑指 Offer 65. 不用加减乘除做加法(简单)

    题解

    《C++ Primer》当我们赋给无符号类型一个超出它表示范围的值时,结果是初始值对无符号类型表示数值取模后的余数。
    当我们给带符号类型一个超出它表示范围的值时,结果是未定义的。

    ❗ 如果不加unsigned Leetcode会觉得越界访问从而报错。


    image.png

    1)在c 中左移也就是所说的逻辑移位,右端补0;
    而右移是算数移位,左端补齐的是最高位的符号位。
    2)故负数左移,有可能变成正数;但负数右移,肯定还是负数。

    class Solution {
    public:
        int add(int a, int b) {
            int c =0,  add = 0;       
            while(a){
                add = (unsigned int)(a&b)<<1;//⭐
                c = a^b;
                a = add;
                b = c;
            }
            return b;
        }
    };
    

    剑指 Offer 41. 数据流中的中位数(困难)

    sort方法是nlogn的时间复杂度使用它会超时。这里借助堆,可使时间复杂度降为logn。大小根堆入堆出堆问题想了好久。
    题解

    class MedianFinder {
    public:
        /** initialize your data structure here. */
        priority_queue<int,vector<int>,greater<int>> max_que;
        priority_queue<int>min_que;
        MedianFinder() {
        }
        
        void addNum(int num) {
            int min_sz = min_que.size();
            int max_sz = max_que.size();
            if(min_sz == max_sz){
                min_que.push(num);
                int t = min_que.top();
                min_que.pop();
                max_que.push(t);
            }else{
                max_que.push(num);
                int t = max_que.top();
                max_que.pop();
                min_que.push(t);
            }
        }
        
        double findMedian() {
            bool flag = (min_que.size()+max_que.size())%2 == 0?true:false;
            return flag?(min_que.top()+max_que.top())*1.0/2:max_que.top();
        }
    };
    

    相关文章

      网友评论

          本文标题:Day23 对称的二叉树 + 不用加减乘除做加法 + 数据流中的

          本文链接:https://www.haomeiwen.com/subject/xvipyltx.html