Re: [問題] 如何再精進?

看板Prob_Solve (計算數學 Problem Solving)作者 (雲川閒步)時間5年前 (2019/05/28 14:09), 編輯推噓0(000)
留言0則, 0人參與, 最新討論串2/3 (看更多)
※ 引述《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
文章代碼(AID): #1SxD2RxC (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容:
以下文章回應了本文
完整討論串 (本文為第 2 之 3 篇):
文章代碼(AID): #1SxD2RxC (Prob_Solve)