作者查詢 / ddavid

總覽項目：發文 | 留言 | 暱稱

作者 ddavid 在 PTT [ Prob_Solve ] 看板的留言(推文), 共90則

限定看板：Prob_Solve

看板排序：

全部TypeMoon9289H-GAME4300GO3873GameDesign2664FATE_GO2575JinYong2086FBG1867AC_In1774nobunyaga1708LoL1533Wrestle1251StarCraft879Poker815Python767Detective650CGI-Game645C_Chat531Steam414Old-Games345Magic338DMM_GAMES336OverWatch317Little-Games303C_and_CPP266historia256Inference253DataScience231WorldCup222RealPlaying221Programming196TRPG182ToS118Olympics_ISG114Expansion07109Prob_Solve90PathofExile85Salary53eSports47marvel41BattleRoyale35PUBG33C_Sharp30BlizzHeroes26NDS26SLG26NTUCCG25Palmar_Drama23politics23LeafKey18basketballTW17KanColle16Web_Design15ck51st31614Gossiping14PhD14NTU-Fantasy11mud10AndroidDev6Baseball6CS_IGO6KS92-3196AHQ4Ahqwestdoor4MATLAB4Toy4b885060xx3cat3CVS3HotBloodYuan3joke3LGS3NTUEE108HW3NTUVGC3SuperIdol3XiangSheng32nd_NTUCCC2AC_Music2b90902xxx2ck55th3332CLHS-50-142DummyHistory2FJU-ACC90a2FJU-AM-902GAMEMUSIC2japanavgirls2JD_Lover2KS93-3042NBA2NCCU08_SW2NTUST-DT92-12OrangeRoad2SC-91-3012SCU_Talk2tabletennis2talk2Viator94Ding2About_Clubs1AngelPray1b89902xxx1b92902xxx1C_GameBoard1CCU_COMM_ANT1cksh83rd3031CMWang1CSMU-MED901Dynasty1G-REX1HatePolitics1Hunter1KS94-3101Mabinogi1MobileComm1NDHU-His961PuzzleDragon1sex1SOFTSTAR1specialman1Sportcenter1SYSOP1WomenTalk1<< 收起看板(120)

首頁

尾頁

[問題] 類似dp問題...？

[ Prob_Solve ]9 留言, 推噓總分: +3

作者: Aa841018 - 發表於 2021/06/20 01:45(4年前)

5^F推ddavid: 你可以先自己舉出一個例子，把式子列出來，然後看看如果是06/21 11:25

6^F→ddavid: 人來解會怎麼解法，你應該就會發現這是個什麼問題06/21 11:25

9^F推ddavid: 樓上正解，這根本用不到啥規劃07/02 12:43

[閒聊] Hamiltonian Cycle Problem is in P？

[ Prob_Solve ]10 留言, 推噓總分: +2

作者: alan23273850 - 發表於 2021/05/19 12:48(4年前)

6^F推ddavid: 沒有到量子電腦不用研發那個程度啦05/24 04:51

7^F→ddavid: 即便P = NP，也不代表那個P是容易快速處理的問題，量子電05/24 04:55

8^F→ddavid: 腦的運算能力仍然有其研發必要性05/24 04:55

[問題] 最長回文子字串的最快演算法

[ Prob_Solve ]10 留言, 推噓總分: +3

作者: alan23273850 - 發表於 2021/04/29 13:51(4年前)

4^F推ddavid: 你這問題不就是要維護的字串數量最壞情況跟n有關嗎，除非04/29 16:34

5^F→ddavid: 你能把維護字串數量壓到常數才可能變成O(n)啊04/29 16:34

9^F推ddavid: 所以Manacher才高明啊04/30 00:37

[問題] 01背包的分堆變形題

[ Prob_Solve ]12 留言, 推噓總分: +5

作者: fatcat8127 - 發表於 2020/10/08 16:36(5年前)

2^F推ddavid: leetcode有簡單題也有難題，樓上你想問什麼10/21 09:06

4^F推ddavid: 看你找什麼工作，還有演算法題從來就不只是為了讓你背題到10/21 13:34

5^F→ddavid: 時工作解一模一樣的問題10/21 13:35

6^F→ddavid: 到時工作你不會直接看到背包問題，卻會用到解題思維以及動10/21 13:36

7^F→ddavid: 態規劃、greedy、divide and conquer、tree、graph等等概10/21 13:37

8^F→ddavid: 念，寫演算法題是為了讓你懂得怎麼自己思考應用這些概念10/21 13:38

9^F→ddavid: 當然你可找個用不上解題思維的工作，但這個版就是解題版XD10/21 13:40

10^F推ddavid: 看到你在別的版也問過leetcode的問題，也許我在Python以前10/21 13:44

11^F→ddavid: 這篇拋磚的文章可以給你一點參考？XD #1UQl27Mt (Python)10/21 13:45

[問題] 關於運算式的相等

[ Prob_Solve ]17 留言, 推噓總分: +6

作者: nevikw39 - 發表於 2020/06/01 12:47(5年前)

13^F推ddavid: 樓上那個裡面只有+，難度差距很大06/10 15:28

14^F→ddavid: 我在想有沒有可能算出其中一邊的變數次方數跟乘除關係後，06/10 15:33

15^F→ddavid: 能用多點例證法甚至大數值的單點例證法直接證明相等？06/10 15:34

[問題] 想問一個與這個問題相同的題目

[ Prob_Solve ]40 留言, 推噓總分: +10

作者: s4300026 - 發表於 2020/05/07 10:38(5年前)

6^F推ddavid: 樓上，這問題跟k-partition好像也不是全等的05/07 16:56

7^F→ddavid: 1.要求相等的目標是平均相等而非總和相等，這表示每一堆的05/07 16:57

8^F→ddavid: 大小不能直接用sum/k來預估05/07 16:57

9^F→ddavid: 2.目標是求出「最多可以分幾組」而不是給定k分k組05/07 16:58

10^F推ddavid: 直覺上解法是把所有數全部減去平均值成為一組新數列，然後05/07 17:09

11^F→ddavid: 不斷從這組新數列中取出加總為0且個數盡可能少的數就成為05/07 17:10

12^F→ddavid: 平均會符合條件的一組，看能夠取出幾組。05/07 17:11

13^F→ddavid: 例：3 2 4 1 5 3 -> 0 -1 1 -2 2 005/07 17:12

14^F→ddavid: 兩個0可以直接獨立成為兩組，剩下1 -1，2 -2各一組，對應05/07 17:13

15^F→ddavid: 回去就是3 24 15 3共四組05/07 17:13

16^F→ddavid: 那問題就變成某種zero-sum problem了吧？05/07 17:19

17^F推ddavid: 講錯了，應該是Subset sum problem05/07 17:26

20^F推ddavid: 啊，對耶，我瞎了沒注意n XD05/07 21:37

21^F→ddavid: 抱歉啊m(_ _)m05/07 21:38

28^F推ddavid: 對了，其實這仍然不是k-partition problem，因為05/08 10:35

29^F→ddavid: 1.k-partition problem並沒有要求每一組的數字個數相同05/08 10:35

30^F→ddavid: 2.這問題並沒有保證所有數字會分完，只是說最多能找出幾組05/08 10:36

31^F推ddavid: 所以感覺可以反覆執行Subset sum problem的做法一次找一組05/08 10:38

32^F→ddavid: 出來，但是中間會需要解決一個問題，就是需要證明能有某種05/08 10:41

33^F→ddavid: 取組的順序不會導致如果有某一組取走特定某些數會導致整體05/08 10:42

34^F→ddavid: 組數變少05/08 10:42

35^F→ddavid: 因為n限制的原因，直觀上我覺得不會發生這個問題，但還是05/08 10:43

36^F→ddavid: 需要證明05/08 10:44

40^F推ddavid: 啊，確實如此，一錯再錯XD05/10 12:08

[問題] SVD影像壓縮

[ Prob_Solve ]7 留言, 推噓總分: +2

作者: j0958322080 - 發表於 2019/06/20 00:02(6年前)

2^F推ddavid: 比起其他壓縮，SVD壓縮相對比較注重原圖的特徵保存06/23 02:57

3^F→ddavid: 因此，當你的應用並不是單純只想節省空間然後圖片大概可以06/23 02:57

4^F→ddavid: 看就好，而是比較強調壓小了之後還是能保存主要特徵的話，06/23 02:58

5^F→ddavid: SVD壓縮可能相對符合需求06/23 02:58

[問題] 面試寫到的難題 (Solved)

[ Prob_Solve ]46 留言, 推噓總分: +21

作者: phoenixrace - 發表於 2018/09/02 03:40(7年前)

2^F推ddavid: 直覺是先跑個O(n)把奇偶分開，奇數那邊跑DP解出k個以下奇09/02 04:23

3^F→ddavid: 數所有可能，再接上偶數那邊的所有可能性09/02 04:24

4^F→ddavid: 因為偶數那邊的可能性數量可以統計好不同值的個數後組合公09/02 04:25

5^F→ddavid: 式解，所以實際上不需要暴力法處理，DP的部分也因為只需要09/02 04:26

6^F→ddavid: 知道種類數，因此也可以省去列出可能性的步驟09/02 04:26

7^F→ddavid: 等等不對，如果沒要印出所有可能性只需要知道可能性總數的09/02 04:27

8^F→ddavid: 話，好像連DP都不需要嘛？09/02 04:28

26^F推ddavid: 傻了，原來是連續的，完全搞錯題意XD09/02 21:34

[請益] 四元樹找鄰

[ Prob_Solve ]33 留言, 推噓總分: +7

作者: WoodChen - 發表於 2018/04/03 07:57(7年前)

10^F推ddavid: 總覺得如果用二元編碼後會有某種程度的公式解找到同層鄰居04/06 01:55

11^F→ddavid: ，再利用鄰居的父親若非自己的父親則必也為鄰居、上鄰居的04/06 01:57

12^F→ddavid: 下方子節點也必為上鄰居之類的性質好像有可能從同層鄰居把04/06 01:58

13^F→ddavid: 所有鄰居推出來，然而我不知道效率好不好04/06 01:58

14^F→ddavid: 這邊講到二元編碼是上下1 bit、左右1 bit，所以右上、右下04/06 02:00

15^F→ddavid: 、左上、左下分別為01 11 00 1004/06 02:00

16^F→ddavid: 然後可能就可以依目標的某些特性，用改變其中幾個bit的公04/06 02:01

17^F→ddavid: 式取得四個方向的同一層（即大小相等的）鄰居04/06 02:02

18^F→ddavid: 只是我沒有去仔細推敲是否確實可行以及效率04/06 02:03

25^F推ddavid: 其他所有鄰面必然是同層鄰居的子或父節點，所以要找出所04/12 15:55

26^F→ddavid: 有都是可以從同層的出發04/12 15:55

27^F→ddavid: 而且有一些方向關係可以肯定，比如A是B的上方同層鄰居，則04/12 15:55

28^F→ddavid: A所有只往下方走（包括左下跟右下）的子孫節點都同樣是B04/12 15:55

29^F→ddavid: 的鄰居04/12 15:55

30^F→ddavid: 這就是上面講編碼方便的其中一個地方，找到上同層鄰居A以04/12 15:56

31^F→ddavid: 後，我在A編碼後面無限制接上10或11全都自然是B的鄰居04/12 15:56

32^F→ddavid: 父親方向也不難，一直往上推，直到共同祖先出現以前都會是04/12 15:56

33^F→ddavid: 鄰居04/12 15:56

[問題] 13張牌的題目

[ Prob_Solve ]11 留言, 推噓總分: +4

作者: sgcob187575 - 發表於 2018/04/10 08:43(7年前)

5^F推ddavid: 基本上十三張的分堆本來就沒有最佳解，所以單純greedy找最04/11 18:10

6^F→ddavid: 大的開始分，符合條件就夠了04/11 18:10

7^F推ddavid: 簡單講就是13張拿來從最大的牌型開始找看存不存在，找到存04/11 18:21

8^F→ddavid: 在的最大五張牌型就分成第一墩，從剩下8張再重跑一次同樣04/11 18:21

9^F→ddavid: 搜尋，找到就是第二墩的五張，剩下三張自然成墩就好04/11 18:22

11^F推ddavid: 這題目並沒有要求更佳打牌策略，就無視吧XD04/12 15:38

首頁

尾頁