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

啦啦啦啦啦啦啦啦啦啦啦這個沒有保密協議吧23333

處理json數字類型

附加題第一題,實際上我們就是要做一個語法分析器,用的方法(我只能想到)狀態機了。

↑這是題目中附的圖,來自json官網

方法簽名給的是類似parse(const char*s, double* d),也就是逼你用C/C++

首先理一下思路,每一個分支都可以看成一個狀態轉移;以最正常正整數作為主線,把狀態標上號

number

 

需要注意的是,各狀態出現的順序,即5不能出現在4之前,1隻能出現在最開頭

完整代碼我就不給了,考試這麼短的時間,還是手寫,要考慮完整太難了;不過可以附一份考完之後我回想起來的代碼,你可以看看我還有什麼沒考慮到的地方

附件:json_num_src

直方圖求最大矩形

附加題第二題,差不多是這個樣子,隨機直方圖,求其中最大連續矩形(圖網上抓的

barchat

 

搜了一下才發現以前被好多地方考過了orz,這就是不好好學演算法的後果啊QAQ

有幾種方法

  1. 從第一個矩形開始,尋找以它為高度時的最大寬度,計算面積,比較所有結果(http://blog.csdn.net/sunnyyoona/article/details/16931047);這種方法思路比較清晰;目測時間複雜度在n~(n^2)/2之間?
  2. 從第一個開始,以自己高度為準,往右延伸,直到碰到比自己矮的,計算面積;以那個矮的為高,繼續延伸,直到碰到更矮的,再計算面積;到底後,從上一次延伸時第一個碰到的矮的開始繼續上述操作;稍後上代碼,先睡覺去了ww