【剑指offer】让抽象问题具体化

Keagan 发布于2019-08-23 15:15 / 2747人阅读

摘要：假设压入栈的所有数字均不相等。注意这两个序列的长度是相等的思路借助一个辅助栈来存储数据。当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。若存在，左右子树，递归检测左右子树是否复合规范。

1.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路

1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数据进栈时栈的最小值.

2.每次数据进栈时，将此数据和最小值栈的栈顶元素比较，将二者比较的较小值再次存入最小值栈.

4.数据栈出栈，最小值栈也出栈。

3.这样最小值栈的栈顶永远是当前栈的最小值。

代码

var dataStack = [];
var minStack = [];
 
function push(node)
{
    dataStack.push(node);
    if(minStack.length === 0 ||  node < min()){
        minStack.push(node);
    }else{
        minStack.push(min());
    }
}
function pop()
{
    minStack.pop();
    return dataStack.pop();
}
function top()
{
    var length = dataStack.length;
    return length>0&&dataStack[length-1]
}
function min()
{
    var length = minStack.length;
    return length>0&&minStack[length-1]
}

2.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路

1.借助一个辅助栈来存储数据。

2.将pushV中的数据依次入栈。

3.出栈有可能在任意一次入栈后进行，当出栈数据不再位于栈顶，继续入栈。

4.所以设置一个索引，记录当前出栈的位置，每次出栈索引+1。

5.当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。

代码

    function IsPopOrder(pushV, popV) {
      if (!pushV || !popV || pushV.length == 0 || popV.length == 0) {
        return;
      }
      var stack = [];
      var idx = 0;
      for (var i = 0; i < pushV.length; i++) {
        stack.push(pushV[i]);
        while (stack.length && stack[stack.length - 1] == popV[idx]) {
          stack.pop();
          idx++;
        }
      }
      return stack.length == 0;
    }

3.题二叉树的后续遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路

1.后序遍历：分成三部分：最后一个节点为跟节点，第二部分为左子树的值比跟节点都小，第三部分为右子树的值比跟节点都大。

2.先检测左子树，左侧比跟节点小的值都判定为左子树。

3.除最后一个节点外和左子树外的其他值为右子树，右子树有一个比跟节点小，则返回false。

4.若存在，左、右子树，递归检测左、右子树是否复合规范。

代码

    function VerifySquenceOfBST(sequence) {
      if (sequence && sequence.length > 0) {
        var root = sequence[sequence.length - 1]
        for (var i = 0; i < sequence.length - 1; i++) {
          if (sequence[i] > root) {
            break;
          }
        }
        for (let j = i; j < sequence.length - 1; j++) {
          if (sequence[j] < root) {
            return false;
          }
        }
        var left = true;
        if (i > 0) {
          left = VerifySquenceOfBST(sequence.slice(0, i));
        }
        var right = true;
        if (i < sequence.length - 1) {
          right = VerifySquenceOfBST(sequence.slice(i, sequence.length - 1));
        }
        return left && right;
      }
    }

4.二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路

1.使用前序遍历

2.使用一个辅助栈来存储当前路径里的数据

3.记录一个当前路径的和

4.遍历到当前节点后，当前值入路径栈，和加当前值

5.递归左孩子右孩子节点

6.遍历完一个节点，退回到上一个节点，从路径栈中移除当前的值，和减当前值

代码

    function FindPath(root, expectNumber) {
      var result = [];
      if (!root) {
        return result;
      }
      findPath(root, expectNumber, [], 0, result);
      return result;
    }

    function findPath(node, expectNumber, vector, sum, result) {
      vector.push(node.val);
      sum += node.val;
      var isLeaf = !node.left && !node.right;
      if (isLeaf && sum === expectNumber) {
        result.push(vector.slice(0));
      }
      if (node.left) {
        findPath(node.left, expectNumber, vector, sum, result);
      }
      if (node.right) {
        findPath(node.right, expectNumber, vector, sum, result);
      }
      vector.pop();
    }

云服务器 GPU云服务器具体问题分析问题的具体方法剑指 offer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101756.html

从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试 ...

tracymac7 2019-08-15 17:57 评论0 收藏0
从简历被拒到收割今日头条 offer，我用一年时间破茧成蝶！

摘要：正如我标题所说，简历被拒。看了我简历之后说头条竞争激烈，我背景不够，点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收，也不过个月的时间，但这都是建立在我过去一年的积累啊。本文是无精疯同学投稿的面试经历关注微信公众号：进击的java程序员K，即可获取最新BAT面试资料一份在此感谢无精疯同学的分享目录：印象中的头条面试背景准备面试头条一面（Java+项目）头条...

wdzgege 2019-08-19 11:43 评论0 收藏0
【剑指offer】一个数的二进制序列中1的个数

摘要：图解第二种算法图解代码示例算法如果为真，说明拿到的是二进制序列的个数为算法为的时候说明已经拿完了，循环终止二进制序列中的个数以上代码，还可做优化在此仅作参考，若有更好的算法，还望能够私信告知，多谢各位。 ✨前言✨：算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算...

weknow619 2021-09-02 15:15 评论0 收藏0
《剑指offer》分解让复杂问题更简单

摘要：拆分链表，将和进行拆分，保证原始链表不受影响。要求不能创建任何新的结点，只能调整树中结点指针的指向。输入一个字符串长度不超过可能有字符重复字符只包括大小写字母。递归，记录一个当前节点的位置，该位置指向最后一个节点时记录一次排列。 1.复杂链表的复制输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的hea...

wawor4827 2019-08-23 15:27 评论0 收藏0