美文网首页
剑指offer学习笔记:4.3 举例让抽象问题具体化

剑指offer学习笔记:4.3 举例让抽象问题具体化

作者: 小逗比儿 | 来源:发表于2020-06-27 00:11 被阅读0次

    面试题21:包含min函数的栈

    定义一个数据结构,请在该类型中实现一个能够得到栈中最小元素的min函数。在该栈中,调用min,push以及pop的时间复杂度都是o(1)。
    leetcode链接: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

    class MinStack {
    public:
       /** initialize your data structure here. */
       stack<int> s1;
       stack<int> s2;
       MinStack() {
       }
       void push(int x) {
           s1.push(x);
           if (s2.empty())
           {
               s2.push(x);
               return;
           }
           int tmp = s2.top();
           if (x < tmp)
           {
               s2.push(x);
           }
           else
           {
               s2.push(tmp);
           }
       }   
       void pop() {
           s1.pop();
           s2.pop();
       }   
       int top() {
           return s1.top();
       }  
       int getMin() {
           return s2.top();
       }
    };
    /**
    * Your MinStack object will be instantiated and called as such:
    * MinStack* obj = new MinStack();
    * obj->push(x);
    * obj->pop();
    * int param_3 = obj->top();
    * int param_4 = obj->getMin();
    */
    

    解题思路:一个正常栈,一个辅助栈。辅助栈与正常栈同步进出。辅助栈判断新入栈元素和当前栈顶元素大小,当大于栈顶元素,仍压入栈顶元素,因为此时最小值不变。当小于栈顶元素,压入当前元素。
    分析栈内压入3,4,2,1之后连续两次弹出,再压入0时数据栈状态

    步骤 操作 数据栈 辅助栈 最小值
    1 压入3 3 3 3
    2 压入4 34 33 3
    3 压入2 342 332 2
    4 压入1 3421 3321 1
    5 弹出 342 332 2
    6 弹出 34 33 3
    7 压入0 340 330 0

    面试题22:栈的压入,弹出序列

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为栈的弹出顺序。假设压入栈的数字君不相等。
    leetcode链接 https://leetcode-cn.com/problems/validate-stack-sequences/

    class Solution {
    public:
       bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
           stack<int> tmp;
           int popNumber = 0;
           for(int i = 0; i < pushed.size(); i++)
           {
               if (pushed[i] != popped[popNumber])
               {
                   tmp.push(pushed[i]);
               }
               else
               {
                   popNumber++;
                   while(true)
                   {
                       if (tmp.empty())
                       {
                           break;
                       }
                       if (popped[popNumber] == tmp.top())
                       {
                           tmp.pop();
                           popNumber++;
                       }
                       else
                       {
                           break;
                       }
                   }
               }
           }
           for(int i = popNumber; i < popped.size(); i++)
           {
               if (tmp.top() != popped[popNumber])
               {
                   return false;
               }
               tmp.pop();
           }
           return true;
       }
    };
    

    解题思路:用一个辅助栈。按入栈数组顺序入栈,当当前入栈元素为要弹出数组中第一个元素,不入栈,同时判断栈顶和出栈数组中第二个元素,若相同出栈。后面元素同理。若不同,继续入栈。此时,出栈数组应理解为减去刚刚已出栈元素之后的数组。当元素全部入栈后,再将栈弹出,与出栈数组进行比对,完全吻合,则为true。

    面试题23:从上到下打印二叉树

    从上到下打印二叉树的每个节点,每一层按从左往右顺序进行打印
    牛客链接 https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&&tqId=11175&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

    /*
    struct TreeNode {
       int val;
       struct TreeNode *left;
       struct TreeNode *right;
       TreeNode(int x) :
               val(x), left(NULL), right(NULL) {
       }
    };*/
    class Solution {
    public:
       vector<int> PrintFromTopToBottom(TreeNode* root) {
           vector<int> result;
           if (root == NULL)
           {
               return result;
           }
           queue<TreeNode*> tree;
           tree.push(root);
           while(!tree.empty())
           {
               result.push_back(tree.front()->val);
               if (tree.front()->left)
               {
                   tree.push(tree.front()->left);
               }
               if (tree.front()->right)
               {
                   tree.push(tree.front()->right);
               }
               tree.pop();
           }
           return result;
       }
    };
    

    解题思路:树的层次遍历,属于广度优先遍历。用队列。

    本题扩展:遍历有向图,没找到链接,不想写构建图,先不写了。思路个二叉树一样。

    面试题24:二叉搜索树的后序遍历序列

    输入某数组,判断该数组是不是某二叉搜索树的后序遍历
    leetcode链接 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

    class Solution {
    public:
       bool verifyPostorder(vector<int>& postoerder, int begin, int end)
       {
           if (begin >= end)
           {
               return true;
           }
           int root = postoerder[end];
           int i = begin;
           for(;i <= end - 1; i++)
           {
               if (postoerder[i] >= root)   // 找到左右子树分界点
               {
                   break;
               }
           }
           int sed = i;
           for(; i <= end - 1; i++)
           {
               if (postoerder[i] <= root)   // 发现本应是右子树的序列有小于根的元素
               {
                   return false;
               }
           }
           bool left = true, right = true;
           left = verifyPostorder(postoerder, begin, sed - 1);
           right = verifyPostorder(postoerder, sed, end - 1);
           return left && right;
       }
       bool verifyPostorder(vector<int>& postorder) {
           if (postorder.size() == 0)
           {
               return true;
           }
           return verifyPostorder(postorder, 0, postorder.size() - 1);
       }
    };
    

    解题思路:对于二叉搜索树,其特性为左节点小于根节点,右节点大于根节点。后序遍历的遍历顺序为左右根。结合来看,比如当前输入数组为{5,7,6,9,11,10,8},可判断根节点为8,左子树对应序列为{5,7,6},右子树对应序列为{11,10,8},递归调用建立左右子树,建立过程同上。当递归到某个序列,发现无法找到小于根节点和大于根节点的分解点时,即为该数组不合法。

    相关题目:输入一个整数数组,判断该数组是不是某二叉搜索树的前序遍历
    没找到链接,也不写了。思路是前序遍历是根左右。因为第一个元素是根,从第二个元素开始判断,小于根的子序列就是左子树,大于根的子序列就是右子树,利用递归,进行树的重建。当找不到左右子树分界点,代表数组不合法。
    当处理一个二叉树遍历序列,基本思路为找到根节点,并由此推出左右子树子序列,利用递归进行重建

    面试题25:二叉树中和为某一值的路径

    输入一个二叉树和一个整数,打印出二叉树中节点值的和胃输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
    leecode链接 https://leetcode-cn.com/problems/path-sum-ii/

    /**
    * 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 pathSum(TreeNode* root, vector<vector<int>>& result, stack<int>& curPath, int& curSum, const int sum)
       {
           if (root == NULL)
           {
               return;
           }
           if (root->left == NULL && root->right == NULL)
           {
               // cout << "leef: " << root->val << " cur: " << curSum << endl;
               if (curSum + root->val == sum)
               {
                   // cout << "here" << endl;
                   vector<int> tmp;
                   stack<int> tmpStack;
                   tmpStack = curPath;
                   tmp.push_back(root->val);
                   while(!tmpStack.empty())
                   {
                       tmp.push_back(tmpStack.top());
                       tmpStack.pop();
                   }
                   vector<int> path;
                   for(int i = tmp.size() - 1; i >= 0; i--)
                   {
                       path.push_back(tmp[i]);
                   }
                   result.push_back(path);
               }
               else
               {
                   return;
               }
           }
           curSum = curSum + root->val;
           curPath.push(root->val);
           if (root->left)
           {
               pathSum(root->left, result, curPath, curSum, sum);
           }
           if (root->right)
           {
               pathSum(root->right, result, curPath, curSum, sum);
           }    
           curPath.pop();
           curSum = curSum - root->val;  // 注意返回父节点前,要清当前节点
           return;
       }
       vector<vector<int>> pathSum(TreeNode* root, int sum) {
           vector<vector<int>> result;
           int curSum = 0;
           stack<int> curPath;
           // 栈这个结构其实选的不太好,中间保存的时候倒了两遍,影响了效率,其实可以直接用vector,暂时懒得改,后续再说
           pathSum(root, result, curPath, curSum, sum);
           return result;
       }
    };
    

    解题思路:前序遍历。递归时带着当前路径加和,每当遇到叶子节点,判断当前和+叶子节点值是否等于目标num,若等于,把当前路径push进result,若不等于,舍弃。递归返回叶子节点父节点,对另外一面进行判断。注意遍历完节点左右子树,要把该节点value从sum和路径中删除,之后再返回其父节点。

    相关文章

      网友评论

          本文标题:剑指offer学习笔记:4.3 举例让抽象问题具体化

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