※ 引述《suhang (suhang)》之銘言：
: 我以前並沒有競賽經驗
: 為了工作面試而開始寫leetcode, 最早連recursion都寫得很痛苦
: 一邊練習也一邊跳槽，持續練習準備下次跳槽
: 也寫了600+題了，很多題都反覆練習，每天下班持續練習個五題十題
: 我自覺常用(考)的dfs, bfs, sort, tree, stack, queue
: binary search, trie, binary search tree
: 都算熟悉，都能很快寫出模板並了解為什麼，但似乎就卡在這
: 好像就只會寫模板題，常常稍有變化就卡住了
: (高手們的"基本結構/算法"一定包含更廣)
: 例如 https://leetcode.com/problems/ternary-expression-parser/
: 看了題我就直覺可以用 stack
: 因此我就從i=0 開始往後走，開始分析遇到 ? or : 該怎麼入棧出棧
: 但是越寫越雜，總是過不了，
: 瞄了別人的做法 (開心！的確也可以用 stack解)
: 別人從最後往前走，條理分明，20行解決
: 另外又一題，這個例子更糟，完全沒想法
: https://leetcode.com/problems/max-chunks-to-make-sorted/
: 看了解答才知道，主要精神是求區間最大值，有兩種主要做法
: 1 排序，然後對比原輸入(類似greedy的概念)
: 2 用兩個arr記錄位置i左邊最大的和右手邊最小的元素(有點類似dp的概念)
: 看了也能懂，而且他們也沒用更難的結構或是算法
: 但自己本身的狀況就是糟，因為完全沒有想法，
: 連掙扎都不知道怎麼抖，如果是面試，真的是乾整場
: 這些症頭該怎麼辦？我該怎麼更進一步？
看了一下第二題
你是看哪裡的解答啊？
排序？兩個arr?
這題用一個整數 記錄目前掃過的最大值 另一個整數記答案
然後掃過一次，當就好啦O(n), constant memory
個人看到題目都會先想辦法估計複雜度
然後想辦法找到這個複雜度下的演算法
比如說這題
很明顯當你掃到a_i的時候 就可以從前面的資料推論
是否從a_0到a_i可以當成一堆
如果不行就繼續掃下去
如果可以就output++
然後往後掃描也不需要再回去看前面的資料
因此可以推論這是linear time可解的題目
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 74.104.145.244
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1559023771.A.ECC.html