devbox
代码吟游诗人
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

剑指Offer C++ --- 数组篇_右偏树

作者：代码吟游诗人 | 2024-01-29 17:11:10

赞

踩

右偏树

唉，真的是没有办法啊，只要是稍微大一点的公司都是先笔试，再面试，笔试过不了，八股背的再多，理解的再怎么透彻也没有发挥空间，只能硬着头皮刷题，我对算法真的很抵触，很苦恼，为了工作不得不做，废话不多说，直接开搞！今日目标20个题！

1. 数组重复的数字

  1. int findRepeatNumber(vector<int>& nums) 
  2. {
  3.     unordered_map<int,bool> map;
  4.     for(auto x : nums)
  5.     {
  6.         if(map[x])
  7.         {
  8.            return x;
  9.         }
  10.         map[x] = true;
  11.     }
  12.     
  13.     return -1;
  14. }

利用哈希表，很容易！

map[x] 的位置没有元素时，容器会默认添加一个key = x，val = 0的元素

2.二维数组的查找

  1. bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
  2. {
  3.      int i = matrix.size();
  4.      int j = 0;
  5.  
  6.      while(i>=0 && j<matrix[0].size)
  7.      {
  8.          //去掉一列
  9.          if(matrix[i][j] < target)
  10.          {
  11.             j++;
  12.          }
  13.          //去掉一行
  14.          else if(matrix[i][j] > target)
  15.          {
  16.             i--;
  17.          }
  18.          else
  19.          {
  20.             return false;
  21.          }
  22.  
  23.      }
  24.  
  25.      return true;
  26. }

二分查找的变形，从左下角开始，此元素大于target，向上走一行，此元素小于target向右走一列

3.BST树：非递归删除

如果通过二分查找，找到待删除结点和其双亲节点

分为：三种情况

第一种：待删除结点没有孩子结点，直接将其双亲结点指向它的地址域置nullptr

第二种：待删除结点只有一个孩子结点，那就将其挂接在双亲结点指向待删除结点本身的地址域

第三种：待删除结点有两个孩子结点，找到待删除结点左子树中最大的结点或者右子树中最小的结点，将其data覆盖待删除结点的data，这样就转化为第一种或者第二种情况（即就是处理叶子结点）

特殊情况：对于左偏树，或者右偏树，删除根节点，需要重置根节点为其第一个非空孩子结点

  1. bool  n_remove(Node& val)
  2. {
  3.    Node* cur = root_;
  4.    Node* parent = nullptr;
  5.    
  6.    //空树直接返回
  7.    if(root_ == nullptr)
  8.    {
  9.       return false;
  10.    }
  11.    
  12.    while(cur != nullptr)
  13.    {
  14.        if(cur—>data < val.data)
  15.        {
  16.             parent = cur;
  17.             cur = cur->right;
  18.        }
  19.        else if(cur->data > val.data)
  20.        {
  21.             parent = cur;
  22.             cur = cur->left;
  23.        }
  24.        else 
  25.        {
  26.             break;  //找到待删除结点
  27.        }
  28.    }
  29.  
  30.    if(cur == nullptr)
  31.    {
  32.        return false;
  33.    }
  34.  
  35.    //先处理第三种情况
  36.    if(cur->left != nullptr && cur->right != nullptr)
  37.    {
  38.        //找到待删除结点左子树中最大的结点
  39.        parent = cur;
  40.        Node* pre = cur->left
  41.        while(pre->right!=nullptr)
  42.        {
  43.           parent = pre;
  44.           pre = pre->right;
  45.        }
  46.        cur->data = pre->data;
  47.        cur = pre;
  48.    }
  49.  
  50.    //合并只有一个孩子是左孩子，还是右孩子，或者没有孩子的情况
  51.    Node* child = cur->left;
  52.    if(child == nullptr)
  53.    {
  54.       child = cur->right;
  55.    }
  56.    
  57.    //处理左偏树或者右偏树
  58.    if(parent == nullptr)
  59.    {
  60.       root_ = child;
  61.    }
  62.    else
  63.    {
  64.       //用待删除结点的孩子结点，覆盖其在双亲结点的地址域
  65.       if(parent->left == cur)
  66.       {
  67.         parent->left = child;
  68.       }
  69.       else
  70.       {
  71.         parent->right = child;
  72.       }
  73.  
  74.    } 
  75.    delete cur;
  76.    return true;
  77. }

4.BST树递归层序遍历

  1. //计算树高
  2. int heigh(Node* node)
  3. {
  4.     if(node == nullptr)
  5.     {
  6.        return 0;
  7.     }
  8.  
  9.     int left = heigh(node->left);
  10.     int right = heigh(node->right);
  11.     return left>right ? left+1 : right+1;
  12. }
  13.  
  14. //计算树的结点个数
  15. int nums(Node* node)
  16. {
  17.     if(node == nullptr)
  18.     {
  19.        return 0;
  20.     }
  21.  
  22.     int left = nums(node->left);
  23.     int right = nums(node->right);
  24.     
  25.     return left + right + 1;
  26. }
  27.  
  28.  
  29. void levelOrder(Node* node,int i)
  30. {
  31.     if(node == nullptr)
  32.     {
  33.        return;
  34.     }
  35.  
  36.     if(i == 0)
  37.     {
  38.        cout << node->data << "  ";
  39.        return;
  40.     }
  41.  
  42.     levelOrder(node->left,i-1);
  43.     levelOrder(node->right,i-1);
  44.  
  45. }
  46.  
  47.  
  48. void levelOrder()
  49. {
  50.     int n = heigh(node);
  51.    
  52.     //用i来控制递归的层数
  53.     for(int i = 0;i<n;++i)
  54.     {
  55.        levelOrder(node,i);
  56.     }
  57.  
  58.     cout << endl; 
  59. }

5.BST树递归插入

  1. Node* insert(Node* node,int val)
  2. {
  3.    if(node == nullptr)
  4.    {
  5.       return new Node(val);
  6.    }
  7.    
  8.    //不插入相同的元素
  9.    if(node->data == val)
  10.    {
  11.       return node;
  12.    }
  13.    else if(node->data < val)
  14.    {
  15.       node->right = insert(node->right,val);
  16.    }
  17.    else
  18.    {
  19.       node->left = insert(node->left,val);
  20.    }
  21.  
  22.    return node;
  23. }

6.BST树的递归删除

  1. Node* remove(Node* node, int val)
  2. {
  3.     if(node == nullptr)
  4.     {
  5.        return nullptr;
  6.     }
  7.     
  8.     //找到待删除结点
  9.     if(node->data == val)
  10.     {
  11.         //三种情况处理
  12.         if(node->left != nullptr && node->right != nullptr)
  13.         {
  14.            Node* pre = node->left;
  15.            //待删除结点左子树中最大的结点
  16.            while(pre->right != nullptr)
  17.            {
  18.                pre = pre->right;
  19.            }
  20.  
  21.            //递归直接删除---待删除结点
  22.            node->data = pre->data;
  23.            node->left = remove(node->left,pre->data);
  24.         }
  25.         else
  26.         {
  27.             //只有一个孩子结点
  28.             if(node->left != nullptr)
  29.             {
  30.                Node* left = node->left;
  31.                delete node;   
  32.                return left;     
  33.             }
  34.             else if(node->right != nullptr)
  35.             {
  36.                Node* right = node->right;
  37.                delete node;
  38.                return right;
  39.             }
  40.             //没有孩子结点
  41.             else
  42.             {
  43.                delete node;
  44.                return nulllptr;
  45.             }
  46.         }
  47.     }
  48.  
  49.     else if(node->data < val)
  50.     {
  51.         node->right = remove(node->right,val);
  52.     }
  53.  
  54.     else
  55.     {
  56.         node->left = remove(node->left,val);
  57.     }
  58.  
  59.     return node;
  60. }

7.BST树非递归前序遍历（单栈）

  1. void preOrder()
  2. {
  3.     if(root_ == nullptr)
  4.     {
  5.        return nullptr;
  6.     }
  7.  
  8.     stack<Node*> st;
  9.     st.push(root_);
  10.  
  11.     while(!st.empty())
  12.     {
  13.         Node* node = st.top();      //v
  14.         st.pop();
  15.         cout << node->data << "  ";
  16.         
  17.         if(node->right != nullptr)
  18.         {
  19.            st.push(node->right);    //L
  20.         }
  21.         
  22.         if(node->left != nullptr)   //R
  23.         {
  24.            st.push(node->left);
  25.         }
  26.     }
  27.  
  28.     cout << endl;
  29. }

思路：每循环一次先将栈顶元素出栈，输出栈顶元素，再将栈顶元素的右孩子先入栈，再将其左孩子入栈

8.BST树的中序遍历（单栈）

  1. void inOrder()
  2. {
  3.    if(root_ == nullptr)
  4.    {
  5.        return;
  6.    }
  7.    
  8.    stack<Node*> st;
  9.    Node* cur = root_;
  10.  
  11.    while(!st.empty() || cur != nullptr)
  12.    {
  13.       if(cur!=nullptr)
  14.       {
  15.          st.push(cur);
  16.          cur = cur->left;
  17.       }
  18.       else
  19.       {
  20.          cur = st.top();
  21.          st.pop();
  22.          cout << cur->data << "  ";
  23.          cur = cur->right;
  24.       }
  25.    }
  26.    
  27.    cout << endl;
  28. }

思路：先将左侧的结点入到栈里，如果左侧结点遇到nullptr，弹出栈顶元素并输出，转而入弹出元素的右侧结点

9.BST树的后序遍历 （双栈)

思路：将LRV 转化为 VRL 输出的时候又转化为 LRV

利用栈1存储 LRV， 按顺序转入栈2后，变为 VRL

  1. void postOrder()
  2. {
  3.     if(root_ == nullptr)
  4.     {
  5.         return;
  6.     }
  7.     
  8.     stack<Node*> st1;
  9.     stack<Node*> st2;
  10.     st1.push(root_);
  11.     
  12.     while(!st1.empty())
  13.     {
  14.        Node* node = st1.top();
  15.        st1.pop();
  16.        st2.push(node);
  17.        if(node->left != nullptr)
  18.        {
  19.           st1.push(node->left);
  20.        }
  21.        
  22.        if(node->right != nullptr)
  23.        {
  24.           st2.push(node->right);
  25.        }
  26.     }
  27.  
  28.     while(!st2.empty)
  29.     {
  30.        cout <<st2.top()->data << " ";
  31.        st2.pop();
  32.     }
  33.     cout << endl;
  34. }

10.BST树的广度优先遍历

  1. void levelOrder()
  2. {
  3.     if(root_ == nullptr)
  4.     {
  5.        return nullptr;
  6.     }
  7.  
  8.     queue<Node*> q;
  9.     q.push(root_);
  10.  
  11.     while(!q.empty())
  12.     {
  13.        Node* node = q.front();
  14.        q.pop();
  15.        cout << node->data << "  ";
  16.        if(node->left!=nullptr)
  17.        {
  18.           q.push(node->left);
  19.        }
  20.  
  21.        if(node->right!=nullptr)
  22.        {
  23.           q.push(node->right);
  24.        }
  25.     }
  26.     cout << endl;
  27. }

11.已知二叉树的前序中序遍历，重建二叉树

思路：采取分治的思想

 

i与j之间的距离要与m到n之间的距离一致

先序遍历第一个结点为根节点

在中序遍历中找到根节点，从第一个结点到根结点（不含根节点）全部都是左子树序列，从根节点（不含根节点）到末尾全部都是右子树序列

对应到先序遍历的序列中，按照相对位置计算，根节点到左子树序列的最后一个结点的距离等于中序遍历左子树序列的长度

首先可以先确定根结点的位置，那么下一个左子树的结点一定在先序序列根节点的下一个位置，对应到中序遍历应该是在中序遍历开始到根节点的位置-1之间，相应的就可以缩减先序序列的范围，起始位置+1到末尾距离要等于中序遍历开始到根节点的位置-1的距离

先序序列和中序序列，只要其中有一个错开，表示范围内没有合适的元素了

因为在中序遍历中下一个根节点一定在上一个根节点的左侧，而先序序列查找的范围距离要与中序序列查找范围的距离相等

  1. TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
  2. {
  3.     return rebuild(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
  4. }
  5.  
  6.  
  7. TreeNode* rebuild(vector<int>& preorder,int i,int j,vector<int>& inorder,int m,int n)
  8. {
  9.     if(i>j || m>n)
  10.     {
  11.        return nullptr;
  12.     }
  13.    
  14.     TreeNode *node = new TreeNode(preorder[i]);
  15.     for(int k = m; k<=n; k++)
  16.     {
  17.         node->left = rebuild(preorder,i+1,i+k-m,inorder,m,k-1);
  18.         node->right = rebuild(preorder,i+k-m+1,j,inorder,k+1,n);
  19.         return node;
  20.     }
  21.     return node;
  22. }

12.旋转数组的最小数字

O(n)复杂度

思路：可看作两个分别递增的数组

 

  1.    int minArray(vector<int>& numbers) 
  2.     {
  3.         int i = numbers.size()-1;
  4.         if(numbers[0] < numbers[i])
  5.         {
  6.            return numbers[0];
  7.         }
  8.  
  9.         while(i>0)
  10.         {
  11.            if(numbers[i-1]<numbers[i])
  12.            {
  13.                --i;
  14.            }   
  15.            else
  16.            {
  17.                return numbers[i];
  18.            }
  19.         } 
  20.         return numbers[i];
  21.     }

O(logn)

m = (i + j) / 1;

nums[m] > nums[j]    旋转点在【m+1，j】  i = m+1

nums[m] < nums[j]   旋转点【i，m】   j = m

nums[m] == nums[j]  不确定     j =  j-1

  1. int minArray(vector<int>& numbers) 
  2. {
  3.     int i = 0;
  4.     int j = numbers.size()-1;
  5.     
  6.      
  7.     while(i < j)
  8.     {
  9.        int m = i+(j-i)/2;
  10.        if(numbers[m] < numbers[j])
  11.        {
  12.           j = m;
  13.        }   
  14.        else if(numbers[m] > numbers[j])
  15.        {
  16.           i = m+1;
  17.        }
  18.        else
  19.        {
  20.           j -= 1;
  21.        }
  22.     }
  23.  
  24.     return numbers[i];
  25. }

 当范围只剩下一个元素时，即是最小值

很遗憾今天只写了12道，明天继续加油吧！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/43705
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号