>

剑指Offer第四章:消除面试题的笔触

- 编辑:555彩票 -

剑指Offer第四章:消除面试题的笔触

前一阵子看到了一个Golang的JSON库go-simplejson,用来封装与解析匿名的JSON,说白了就是用map或者slice等来解析JSON,觉得挺好玩,后来有个项目恰好要解析JSON,于是就试了试,不小心看了一眼源代码,发现竟然是用的Golang自带的encoding/json库去做的解析,而其本身只是把这个库封装了一层,看起来更好看罢了。于是心想能不能徒手写一个解析器,毕竟写了这么多年代码了,也JSON.parseJSON.stringify了无数次。捣腾了两天,终于成了,测试了一下,性能比自带的库要高很多,速度基本上在1.67倍之间(视JSON串的大小和结构而定),所以决定写这篇文章分享一下思路。

  1. 想清楚再编码
  2. 分析方法:举例子、画图

先插一个段子,作为一个已经完完整整写了将近三年代码的老码农,前一段面试,不止一次有面试官问我:如何深拷贝一个对象(JS),我笑笑说写一个Walk函数递归一下就行了啊,如果要考虑到Stackoverflow,那就用栈+迭代就好了。然后他们老是问我,有没有更好的办法,然后自言自语的说你可以用JSON先序列化一遍再反序列化……

对于二叉树、二维数组、链表等问题,都可以采用画图的方法来分析,例如:

  • 面试题19二叉树的镜像:通过画图发现,实质就是在遍历树的同时交换非叶节点的左右子节点。
  • 面试题20顺时针打印矩阵:通过画图发现,实质就是一圈一圈的打印数组。
  • 面试题26复杂链表的复制:画图,发现复制链表的过程,分三个步骤:复制节点,设置random指针,拆分两个链表。

项目取名cheapjson,意思是便宜的,因为你不光不需要定义各个struct,性能还比原生的快,所以很便宜。地址在 https://github.com/acrazing/cheapjson,有兴趣的可以看看~

面试题 19:二叉树的镜像

题目:请完成一个函数,输入一个二叉树,该函数输出它的镜像。

题目分析

LeetCode 226. Invert Binary Tree何为镜像:即照镜子得到的像,与原像是左右颠倒的。求二叉树镜像:即反转二叉树。求解思路:对于每个非叶子节点,反转其左右孩子节点。既可以用递归也可以用迭代。题目典故:著名的Homebrew的作者 Max Howell在面试Google时被问到这题,并且没有做出来,原推文

  • Google: 90% of our engineers use the software you wrote , but you can’t invert a binary tree on a whiteboard so fuck off.

题目考点及相关题目

问题本质:树的DFS或BFS遍历。扩展:掌握非递归的实现。

我的代码如下:

1.递归方法:

public class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return root; TreeNode temp = root.left; root.left = invertTree(root.right); root.right = invertTree; return root; }}

2.非递归DFS:

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } final Deque<TreeNode> stack = new LinkedList<>(); stack.push; while(!stack.isEmpty { final TreeNode node = stack.pop(); final TreeNode left = node.left; node.left = node.right; node.right = left; if(node.left != null) { stack.push(node.left); } if(node.right != null) { stack.push(node.right); } } return root; }

3.非递归BFS:

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } final Queue<TreeNode> queue = new LinkedList<>(); queue.offer; while(!queue.isEmpty { final TreeNode node = queue.poll(); final TreeNode left = node.left; node.left = node.right; node.right = left; if(node.left != null) { queue.offer(node.left); } if(node.right != null) { queue.offer(node.right); } } return root; }

JSON value

首先既然是便宜的,便和反射无关了,所以void *是必需的,当然在Golang里面是interface{},然后需要一个结构来保存必需的信息,进行类型判断以及边界检查。如果是C的话,数组大小,字符串长度,对象Key/Value映射都是必需的工作。不过在Golang里面就不需要了,编译器已经搞定了所有的工作。

在JSON当中,一个完整的JSON应该包含一个value,这个value的类型可能是nulltruefalsenumberstringarray以及 object共6种。而arrayobject还有可能包含子value结构。这些类型的值映射到Golang当中,便是nil, bool, bool, int64/float64, string, []interface{}, map[string]interface{},用一个union结构便可以搞定。注意这里的number有可以转换成整数或者是浮点数,在JavaScript中,全部用64位双精度浮点数储存,所以最大的精确整数也就是非规约数是尾数部分2^53 - 1,已经远远大于int32了,所以这里将整数映射成了int64而不是int,因为在部分机器上可能溢出,严格的区分一个IEEE-754格式的整数和浮点数并不是一件轻松的事情,这里简化成了如果尾数中的小数部分以及指数部分均不存在,则认为是一个整数,此外,为了简化操作,对于任何不合法的UTF-16字符串,都认为结构有问题,而终止解析。为了方便,定义一个结构来保存一个JSON的value

type struct Value {
  value interface{}
}

结构中的value字段保存这个JSONValue的实际值,通过类型判定来确定其类型。因此会有很多的判定,赋值,以及取值函数,比如针对一个string类型的Value需要有判定是否为string的操作IsString(),赋值AsString(),以及获取真实值的操作String()

// 判定是否为string,如果是,则返回true,否则返回false
func (v *Value) IsString() bool {
  if _, ok := v.value.(string); ok {
    return true
  }
  return false
}

// 将一个Value赋值为一个string
func (v *Value) AsString(value string) {
  v.value = value
}

// 从一个string类型的Value中取出String值
func (v *Value) String() string {
  if value, ok := v.value.(string); ok {
    return value
  }
  // 如果不是一个string类型,则报错,所以需要先判定是否为string类型
  panic("not a string value")
}

针对这样的操作还有很多,可以参考 cheapjson/value.go.

面试题 20:顺时针打印矩阵

题目:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

题目分析

LeetCode 54. Spiral Matrix顺时针打印矩阵:即螺旋矩阵输出。规律:一圈一圈的输出数组里的数据,注意边界条件不好确定时,多画几个图就很清楚了。边界: “上”肯定要打印,打印“右”的条件是至少有两行,打印“下”至少两行两列;打印“左”至少要有三行两列。

题目考点及相关题目

多画图,帮助理解。相关题目有:LeetCode 59. Spiral Matrix II

我的代码如下:解法一:

public class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<Integer>(); if(matrix.length <= 0) return res; int m = matrix.length, n = matrix[0].length; int min = Math.min; int k = min%2 == 0 ? (min/2 - 1) : min/2; for(int i = 0; i <= k; i ++) spiral(matrix, i, res, m, n); return res; } public void spiral(int[][] matrix, int k, List<Integer> res, int m, int n){ // 上 for(int i = k; i < n - k; i ++) res.add(matrix[k][i]); // 右 for(int i = k + 1; i < m - k; i ++) res.add(matrix[i][n-k-1]); // 下(加判断条件,排除两种情况:只有一列时,只有一行时) if(k < n - k - 1 && k < m - k - 1){ for(int i = n - k - 2; i >= k; i --) res.add(matrix[m-k-1][i]); } // 左(加判断条件,排除两种情况:只有一列时,只有不超过2行时) if(k < n - k - 1 && k < m - k - 2){ for(int i = m - k - 2; i > k; i --) res.add(matrix[i][k]); } }}

解法二:

public class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<Integer>(); if (matrix.length == 0) { return res; } int rowBegin = 0; int rowEnd = matrix.length-1; int colBegin = 0; int colEnd = matrix[0].length - 1; while (rowBegin <= rowEnd && colBegin <= colEnd) { // Traverse Right for (int j = colBegin; j <= colEnd; j ++) { res.add(matrix[rowBegin][j]); } rowBegin++; // Traverse Down for (int j = rowBegin; j <= rowEnd; j ++) { res.add(matrix[j][colEnd]); } colEnd--; if (rowBegin <= rowEnd) { // Traverse Left for (int j = colEnd; j >= colBegin; j --) { res.add(matrix[rowEnd][j]); } } rowEnd--; if (colBegin <= colEnd) { // Traver Up for (int j = rowEnd; j >= rowBegin; j --) { res.add(matrix[j][colBegin]); } } colBegin ++; } return res; }}

通过举例子,理解题目意思并找到规律;最后也以用例子来测试程序是否完善。

  • 面试题22栈的压入、弹出序列:通过举实际栈的例子,来模拟栈的压入和弹出操作,就能发现隐藏的规律。
  • 面试题24二叉搜索树的后序遍历序列:理解后续遍历的特点,并找到递归方法的思路。
  • 面试题21包含min函数的栈:用一个栈来专门来存储当前栈中的最小值。

JSON parser

对于string, true, false, null, number这样的值,都属于字面量,即没有深层结构,可取直接读取,并且中间不可能被空白字符切断,所以可以直接读取。而对于一个array或者object,则是一个多层的树状结构。最直接的想法肯定是用递归,但是大家都知道这是不可行的,因为在解析大JSON的时候很可能栈溢出了,所以只能用栈+迭代的办法。

学过编译原理的人都知道,做AST分析的时候首先要分析Token,然后再分析AST,在解析JSON的时候也应该这样,虽然Token比较少:只有几个字面量以及{, [, :, ], }几个界定符。可惜我并没有学过编译原理,上来就拿状态机来迭代了。因为JSON是一棵树,其解析过程是从树根一直遍历到各个叶节点再返回树根的过程。自然就会涉及到栈的压入及弹出操作。具体来讲,就是在遇到arrayobject的子节点的时候要压入栈,遇到一个value的结束符的时候要弹出栈。同时还要保存栈结点对应的Value以及其状态信息。所以我定义了一个栈结点结构:

type struct state {
  state int
  value *Value
  parent *state
}

其中state表示当前栈节点的状态,value表示其所代表的值parent表示其父节点,根节点的父节点为nil。当要压入栈时,只需要新建一个节点,将其parent设置为当前节点即可,要弹出时,将当前结点设置为当前结点的parent。如果当前节点为nil,则表示遍历结束,JSON自身也应该结束,除了空白字符外,不应该还包含任何字符。

一个节点可能的状态有:

const (
    // start of a value
    stateNone = iota
    stateString
    // after [ must be a value or ]
    stateArrayValueOrEnd
    // after a value, must be a , or ]
    stateArrayEndOrComma
    // after a {, must be a key string or }
    stateObjectKeyOrEnd
    // after a key string must be a :
    stateObjectColon
    // after a : must be a value
    // after a value, must be , or }
    stateObjectEndOrComma
    // after a , must be key string
    stateObjectKey
)

状态的含义和字面意思一样,比如对于状态stateArrayValueOrEnd表示当前栈节点遇到了一个array的起始标志[,在等待一个子Value或者一个array的结束符],而状态stateArrayEndOrComma表示一个array已经遇到了子Value,在等待结束符]或者Value的分隔符,。因此,在解析一个数组的时候,完整的栈操作过程是:遇到[,将当前结点的状态设置为stateArrayValueOrEnd,然后过滤空白字符,判定第一个字符是]还是其它字符,如果是],则array结束,弹出栈,如果不是,则将自身状态修改为stateArrayEndOrComma,并压入一个新栈结点,将其状态设置为stateNone,重新开始解析,此结点解析完成之后,弹出此结点,判定是,还是],如果是],则结束弹出,如果是,则不改变自身状态,并重新一个新栈结点,开始新的循环。完事的状态机如下:

555彩票 1

state.png

其含义如下:

首先初始化一个空节点,状态设置为stateNone,然后判断第一个非空字符,如果是t/f/n/[-0-9],则直接解析字面量,然后弹出,如果是[,则将状态设置为stateArrayValueOrEnd,然后判定第一个字符,如果是],则结束弹出,否则压入新栈,并将自身状态设置为stateArrayEndOrComma,开始新的循环,如果是{,则将状态设置为stateObjectKeyOrEnd,如果下一个非空字符为},则结束弹出,否则解析key,完成之后,压入新栈,并将自身状态设置为stateObjectEndOrComma

比较特殊的是stateString,按道理其也是一个字面量,不需要到一个新的循环里面去解析。但是因为一个objectkey也是一个string,为了复用代码,并避免调用函数产生的性能开销,将string类型和object的key当作同一类型来处理,具体如下:

root := &state{&Value{nil}, stateNone, nil}
curr := root
for {
  // ignore whitespace
  // check curr is nil or not
  switch curr.state {
    case stateNone:
      switch data[offset] {
        case '"':
          // go to new loop
          curr.state = stateString
          continue
      }
    case stateObjectKey, stateString:
      // parse string
      if curr.state == stateObjectKey {
        // create new stack node
      } else {
        // pop stack
      }
  }
}

此外比较特殊的是在解析完一个object的key之后,立即压入了一个新栈结点,并将其状态设置为stateObjectColon,同时将自身的状态设置为stateObjectEndOrComma,在解析完colon之后再这个节点的状态设置为stateNone,开始新的循环,具体来说:

if curr.state == stateObjectKey {
  curr.state = stateObjectEndOrComma
  curr = &state{&Value{nil}, stateObjectColon, nil}
  continue
}

这是因为在:之前和之后都可能有空白字符,这里是为了复用代码逻辑:即在每一次迭代开始之时都把所有的空白过滤掉。

for {
  LOOP_WS:
  for ; offset < len(data); offset++ {
    switch data[offset] {
    case 't', 'r', 'n', ' ':
      continue
    default:
      break LOOP_WS
  }
  // do staff
}

在过滤掉空白后,如果当前栈为nil,则不应该有字符存在,整个解析结束,否则一定有字符,并且需要进行解析:

for {
  // ignore whitespace
  if curr == nil {
    if offset == len(data) {
      return
    } else {
      // unexpected char data[offset] at offset
    }
  } else if offset == len(data) {
    // unexpected EOF at offset
  }
  // do staff
}

随后便是根据当前状态来进行相应的解析了。

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

题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该函数中,调用min、push、及pop的时间复杂度都是$O$。

题目分析

LeetCode 155. Min Stack

  1. 555彩票,使用两个栈,一个数据栈,一个最小数栈
  2. 每次存放数据时,若存放的数据比此时最小栈中的栈顶值要大,那么将最小数栈栈顶元素再存一次(即增加一个栈顶元素),如果要存的数据比栈顶元素小,那么就将此值也存入最小值栈。
  3. 出栈时,两栈都要同时出数据,使得最小数栈的栈顶元素总是目前数据栈中的最小值。两个栈中的元素个数总是保持相等。

题目考点及相关题目

用一个辅助栈来存储最小值元素。相关题目:LeetCode 239. Sliding Window Maximum

我的代码如下:

class MinStack { Stack<Integer> data; Stack<Integer> min; public MinStack() { // do initialize if necessary data = new Stack<Integer>(); min = new Stack<Integer>(); } public void push { if (!min.isEmpty() && min.peek min.push(min.peek; else min.push; data.push; } public void pop() { min.pop(); data.pop(); } public int top() { return data.peek(); } public int getMin() { return min.peek(); }}

后记

从目前的开源项目上来看,性能上应该还有优化的空间,毕竟有人已经做到号称2-4x的速度,而且现在已经有很多项目在搞将Golang的Struct先编译一遍,再调用生成的函数针对特定的结构进行解析,速度更快,不过既然就预先编译了,干嘛还要用JSON啊,直接PB/MsgPack得了。特别是djson这个库,解析小JSON的时候速度是原生的3-4倍,但是大的时候只有2倍,而cheapjson则在解析大JSON的时候性能几乎是原生的7倍,相当搞笑。而从测试结果上来看,整体上性能和内存都还可以,但是在解析数组的时候比原生的还要差。所以值得改进,尤其是频繁的创建和销毁state节点这一点,还有数组的动态扩容等。

以后有空再慢慢搞吧,我不想白头发越来越多了。

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

题目:输入两个整数序列,第一个序列表示 栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列,序列4、5、3、2、1是该压栈序列对应的一个弹出序列,但4、3、5、1、2就不可能是该压栈序列的弹出序列。

题目分析

用一个辅助栈stack来存储压栈序列,如果下一个弹出的数字刚好是辅助栈顶数字,那么直接弹出,并将辅助栈内栈顶数字也弹出;如果下一个弹出的数字不在辅助栈顶,我们把压栈序列中还没有入栈的数字压入辅助栈,直到下一个需要弹出的数字压入栈顶为止。如果 所有的数字都 压入栈了仍然没有找到下一个弹出的数字,那么该序列不可能是一个弹出序列。

题目考点及相关题目

栈的压入、弹出操作。

我的代码如下:

 public boolean isPopOrder(List<Integer> push, List<Integer> pop){ if(pop.size() != push.size return false; Stack<Integer> stack = new Stack<Integer>(); while(!pop.isEmpty{ if(stack.isEmpty stack.push(push.remove; while(stack.peek() != pop.get && !push.isEmpty stack.push(push.remove; if(push.isEmpty() && stack.peek() != pop.get return false; else{ stack.pop(); pop.remove; } } return true; }

本文由搞笑发布,转载请注明来源:剑指Offer第四章:消除面试题的笔触