两道疼迅实习笔试题

今天去笔试了，碰到几道有意思的题来和大家讨论讨论

啦啦啦啦啦啦啦啦啦啦啦这个没有保密协议吧23333

处理json数字类型

附加题第一题，实际上我们就是要做一个语法分析器，用的方法（我只能想到）状态机了。

↑这是题目中附的图，来自json官网

方法签名给的是类似parse(const char*s, double* d)，也就是逼你用C/C++

首先理一下思路，每一个分支都可以看成一个状态转移；以最正常正整数作为主线，把状态标上号

需要注意的是，各状态出现的顺序，即5不能出现在4之前，1只能出现在最开头

完整代码我就不给了，考试这么短的时间，还是手写，要考虑完整太难了；不过可以附一份考完之后我回想起来的代码，你可以看看我还有什么没考虑到的地方

附件：json_num_src

直方图求最大矩形

附加题第二题，差不多是这个样子，随机直方图，求其中最大连续矩形（图网上抓的

搜了一下才发现以前被好多地方考过了orz，这就是不好好学算法的后果啊QAQ

有几种方法

1. 从第一个矩形开始，寻找以它为高度时的最大宽度，计算面积，比较所有结果(http://blog.csdn.net/sunnyyoona/article/details/16931047)；这种方法思路比较清晰；目测时间复杂度在n~(n^2)/2之间？
2. 从第一个开始，以自己高度为准，往右延伸，直到碰到比自己矮的，计算面积；以那个矮的为高，继续延伸，直到碰到更矮的，再计算面积；到底后，从上一次延伸时第一个碰到的矮的开始继续上述操作；稍后上代码，先睡觉去了ww