• leetcode每日一题复盘(10.2~10.8)

    leetcode 347 前k个高频元素 

    关键词:堆排序,优先队列,小根堆

    这道题真没想出来怎么做,只能想到哈希统计数目,对优先队列还不是很熟悉,后来看了详解自己重写了一遍

    主要思路是用哈希统计每个元素出现次数,再利用优先队列的性质创建小根堆(优先队列默认是从大到小排序,将是一个大根堆,因此需要重写比较函数cmp)

    题目要求是前k个元素,因此我们维护一个大小为k的队列,每次插入元素队列自动排序将最小的排在堆顶,当数量>k时弹出堆顶元素,继续排序直到全部元素都遍历过

    最后用vector存放堆中元素即可

    为什么创建小根堆是a.second>b.second?

    这个与优先队列的底层代码有关,其他数据结构a.second>b.second表示的是从大到小,只需要记住优先队列是相反的就可以了

    leetcode 145 二叉树的后序遍历 

    二叉树的后序遍历和144的前序遍历,94的中序遍历大同小异,这里就放一起当作一个题目来讲了

    递归法

    优点是代码简洁易写,但是效率差点,虽然时间复杂度都是O(n)

    贴一个递归算法的代码,把递归顺序改一下就可以是其他遍历了

    1.  void traversal(TreeNode*node,vector<int>&v)
    2.     {
    3.         if(node==nullptr)
    4.         {
    5.             return;
    6.         }
    7.         traversal(node->left,v);
    8.         traversal(node->right,v); 
    9.         v.emplace_back(node->val);
    10.     }
    11.   vector<int> postorderTraversal(TreeNode* root) {
    12.         vector<int>res;
    13.         traversal(root,res);
    14.         return res;
    15. }

    迭代法

    递归是隐式地调用栈,而迭代法就是显式地调用栈,将调用栈的过程以代码呈现出来

    前序遍历

    也就是我们的说的根左右,因为根在前,所以我们在遍历到根的时候就可以把根处理了(结果数组中插入根的值,不着急弹出根因为后面还要从根的右子树进行遍历)

    先将根入栈,然后一直其根的左子树入栈,直到左子树为空就换成在右子树遍历,右子树遍历完后将根弹出,完成一个树遍历

    1.  vector<int> preorderTraversal(TreeNode* root) {
    2.         vector<int>res;
    3.         stackNodestack;
    4.         while(root!=nullptr||!Nodestack.empty())
    5.         {
    6.             while(root)
    7.             {
    8.                 Nodestack.push(root);
    9.                 res.emplace_back(root->val);
    10.                 root=root->left;
    11.             }
    12.             root=Nodestack.top()->right;
    13.             Nodestack.pop();
    14.  
    15.         }
    16.         return res;
    17.     }

    后序遍历

    后序是左右根,因此根要放到最后才处理(也就是说,根最后才加入结果数组)

    先将根的左子树全部入栈,直到root为空,此时将栈顶(左边最后一个根)设为root,再遍历其右子树,如果右子树为空,则可以将根加入结果数组中了

    1. vector<int> postorderTraversal(TreeNode* root) {
    2.         vector<int>res;
    3.         stackNodestack;
    4.         TreeNode*pre=nullptr;
    5.         while(root!=nullptr||!Nodestack.empty())
    6.         {
    7.             while(root)
    8.             {
    9.                 Nodestack.push(root);
    10.                 root=root->left;
    11.             }
    12.             root=Nodestack.top();
    13.             Nodestack.pop();
    14.             if(root->right==nullptr||root->right==pre)
    15.             {
    16.                 res.emplace_back(root->val);
    17.                 pre=root;
    18.                 root=nullptr;
    19.             }
    20.             else
    21.             {
    22.                 Nodestack.push(root);
    23.                 root=root->right;
    24.             }
    25.  
    26.         }
    27.         return res;
    28.     }

    当然也有一种方法,可以将前序的遍历顺序换一下再reverse结果数组,就可以将前序遍历变成后序遍历

    中序遍历

    中序遍历的算法和前序遍历差不多,不过是根的处理时间换了一下

    先遍历完左子树,再将根处理,再遍历右子树

    1. vector<int> inorderTraversal(TreeNode* root) {
    2.         vector<int>res;
    3.         stackNodestack;
    4.         while(root!=nullptr||!Nodestack.empty())
    5.         {
    6.             while(root)
    7.             {
    8.                 Nodestack.push(root);
    9.                 root=root->left;
    10.             }
    11.             root=Nodestack.top();
    12.             res.emplace_back(root->val);
    13.             Nodestack.pop();
    14.             root=root->right;
    15.            
    16.         }
    17.         return res;
    18.     }

    统一遍历法

    具体可看代码随想录 (programmercarl.com)

    leetcode 199 二叉树的右视图

    经典的bfs广度优先算法,这类题目都可以套模板做

    这题本质上还是考察层序遍历,想到层序遍历就不难做, 只要把每一层最后一个元素取下来即可

    层序遍历模板代码

    1. vectorint>> levelOrder(TreeNode* root)
    2.     {
    3.         queueque;
    4.         if(root)que.push(root);
    5.         vectorint>> ans;
    6.         while(!que.empty())
    7.         {
    8.             int size=que.size();
    9.             vector<int>res;
    10.             for(int i=0;i
    11.             {
    12.                 TreeNode*node=que.front();
    13.                 que.pop();
    14.                 res.push_back(node->val);
    15.                 if(node->left){que.push(node->left);}
    16.                 if(node->right){que.push(node->right);}
    17.             }
    18.             ans.emplace_back(res);
    19.         }
    20.         return ans;
    21.     }

     leetcode 429 N叉树的层序遍历

    这个是层序遍历的变式,改变的是子节点传入队列的方式,本质上还是层序遍历

    Node类中包含了子节点的指针数组(代替了原来的左右子树),只要遍历数组就可以访问N个子节点,这样就完成了从二到N的转变 

    leetcode 111 二叉树的最小深度 

    这一题用层序遍历模板的方法做很容易能写出来,但递归的方法代码量少而且效率更高,这里讲一下

    递归的方法

    首先root为空的情况返回0就不用说了(确定递归的结束条件)

    其次确定递归的参数是root节点的左右子树(确定参数)

    最后是递归单层的处理(确定单层递归的逻辑)

    单层递归:

    我们将树的root节点分成三种情况:

    root无子树         root只有一个子树         root有两个子树

    惯性思维我们会将有子树和无子树进行分类然后写递归代码,但是这样写是错误的

    两个子树的情况可以独立出来,用min()挑选左右子树中短的那一棵

    有一个子树和无子树的情况是一样的,因为题目是求最小深度而不是最大深度,无子树是叶子节点,有一个子树的root并不是叶子节点,而我们写的代码很可能会用min()处理有一个子树的情况从而取到为空的子树(即算法找到最短的路径但不是叶子节点),因此我们要将一个子树的情况和无子树的情况当作同一种,用max()来挑选有叶子节点的子数 

    写递归不要用从头开始的思想写,从结果"归"的思想写更容易

  • 相关阅读:
    反弹shell脚本（php-reverse-shell）
    Vue.prototype详解
    .net core跨平台桌面程序 avalonia：从项目创建到打包部署linux-arm系统ubuntu
    前端应该掌握的浏览器调试技巧
    STM32单片机蓝牙APP智能急救手表跌倒报警心率报警MAX30102
    2.CSS选择器
    AI项目十一：Swin Transformer训练
    x64dbg 2022 最新版编译方法
    Ubuntu中为Python2.7安装pip
    Linux C 网络编程概述
  • 原文地址：https://blog.csdn.net/vh_127/article/details/133520704