[問題] 類似最大子陣列的一個問題 huhunhiaccc PTT批踢踢實業坊

[問題] 類似最大子陣列的一個問題

作者: huhunhiaccc (chchch) 2021-06-10 17:16:48

大家好
先說一下題目是輸入一個二維char陣列{"111","123","321","2132"}
要找每組最多可以分割成幾塊，對分割的每一塊做排序完成後
使得整組也是排序完成，要找最多可以分割幾塊
所以上面的輸出[3,3,1,2]
舉例21 32各自排序=>12 23整組排序完成
不知道這樣講清不清楚@@
我現在的問題是我只能寫出全部一樣的case還有剛好陣列第一個數是最大的case
想問各位大大另外幾種case除了遞迴以外有別的做法嗎@@
因為我只有想到遞迴可是因為函數要傳char[][10]
所以我被指標搞得好頭痛呀...
以下是我的code
https://ideone.com/8eLkTs

作者: LPH66 (-6.2598534e+18f) 2021-06-10 18:22:00

提示: 每一塊的排序前和排序後各個數字的數量不變而排序後的數字數量是可以追蹤的

作者: hsnuyi (羊咩咩~) 2021-06-10 22:32:00

這是面試題喔~ 可goo到

作者: ckvir (ckvir) 2021-06-10 22:44:00

看不懂意思幾組幾塊完全不知指什麼

作者: sarafciel (Cattuz) 2021-06-10 23:04:00

https://tinyurl.com/y95t9p5z 可以想一下快選的觀念

作者: LPH66 (-6.2598534e+18f) 2021-06-10 23:10:00

Um, 這跟快選其實不一樣...這裡是自己找分塊快選則是依某個元素為基準分塊, 策略是不一樣的原 PO 已經知道輸入已排序的答案, 那可以進一步思考:如果輸入是除了頭兩個對調外都是排序好的答案是什麼?再進一步, 思考要怎麼構造一個只能用某個方法分塊的輸入?這樣就能找得到要用什麼基準去找分塊了

作者: hsnuyi (羊咩咩~) 2021-06-10 23:42:00

我沒理解錯的話去看看LC768

作者: LPH66 (-6.2598534e+18f) 2021-06-11 00:03:00

樓上沒錯 (應該說就是這題一模一樣)

作者: huhunhiaccc (chchch) 2021-06-11 03:49:00

小弟真的是很感謝樓上各位大大！真的跟leetcode題一模一樣0.0不過我還是會再進一步思考的，謝謝！

作者: hsnuyi (羊咩咩~) 2021-06-11 23:24:00

LC害人不淺看到題目就想起在LC QQ

作者: xanxus27 (XANXUS) 2021-06-12 06:45:00

樓上我該去做LC嗎

作者: hsnuyi (羊咩咩~) 2021-06-12 23:47:00

... 誰知我寫LC是興趣我根本不想當工程師

繼續閱讀