兩道疼迅實習筆試題

今天去筆試了，碰到幾道有意思的題來和大家討論討論

啦啦啦啦啦啦啦啦啦啦啦這個沒有保密協議吧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