iT邦幫忙

3

系列篇章統整: 程式解題平台解題記錄

本文收集線上程式解題平台的各種問題,
涵蓋leetcode, zerojudge, codeWar, ...
目標希望可以將相同類型的問題儘量統整,
達到舉一反三的練習效果

整理自舊連結:

返回主頁- 心原一馬的個人部落格文章的分門別類整整理 #歡迎追蹤收藏

LeetCode題解

LeetCode是近幾年著名的刷題網站,
許多人去科技公司面試前,
都會將它當做一個練習的平台

LeetCode題目增加速度快,當今已經有一千五百多題。
這邊有人刷完前九百題的題解- LeetCode All in One
超推!此網站有919題前的每題詳解,還有多種思路解法,而且是中文的,若練習Leetcode卡關可到這邊學習

雖說leetcode非常有名,也可以google到很多leetcode的題目解析,
但小馬還是試著寫自己的版本,畢竟寫過一遍才能內化為自己的功力

字串

【小馬的LeetCode練功坊】兩道anagram問題- 49. Group Anagrams 和 438. Find All Anagrams in a String
【小馬的LeetCode練功坊】316, 1081, 1163題- 在字串中找最小、最大的subsequence,找最大的substring
【小馬的LeetCode練功坊】(相當難!) 1044題- 最長的重複字串,用RabinKarp算法做字串匹配
【小馬的LeetCode練功坊】1147. Longest Chunked Palindrome Decomposition- 字串分解成最多區塊成為迴文
【小馬的LeetCode練功坊】139, 140 Word Break,依單字清單斷句
【LeetCode練功坊】205, 1153題- 字串同構與字串變換

曆法

【小馬的LeetCode練功坊】曆法問題- 1154. Day of the Year, 1185. Day of the Week

DFS

【小馬的LeetCode練功坊】22. Generate Parentheses (Medium)
【小馬的LeetCode練功坊】733. Flood Fill (Easy)

greedy

【小馬的LeetCode練功坊】55. Jump Game

位元運算

【小馬的LeetCode練功坊】1009. Complement of Base 10 Integer

數學

【小馬的LeetCode練功坊】醜數(Ugly Number)系列- 263,264,313,1201題
【小馬的LeetCode練功坊】621. Task Scheduler (Medium) ,排程問題,每項工作有冷卻時間,要多長時間做完?

二分搜索

【leetcode練功坊】python廣義的二分搜索法概念

資料結構

資料結構的概念統整: 資料結構觀念統整,無程式碼解說常見觀念: 二分搜索、linked list、stack、queue、graph、tree、二分搜索樹、heap、Hash Table

linked list

【leetcode練功坊】常見linked list操作技巧都都收在此了

stack

資結經典題目: 用stack 解括號配對問題
資結經典題目: 用stack計算逆波蘭表達式
資結經典題目: 計算字串四則運算的結果

heap

資結經典題目: 用heap找前k個最小的數對

tree

資結經典題目: 在二元樹中找最長路徑和

trie

資結經典題目: 實作一個Trie (又稱prefix tree、字典樹、前綴樹)

graph

資結經典題目: 實作Dijkstra's algorithm,求graph中其中一個點到其它點的最短距離

經典遊戲解謎

【小馬的LeetCode練功坊】leetcode教你解字謎遊戲- 79. Word Search,212. Word Search II

無明顯可分類

【leetcode練功坊】665. Non-decreasing Array,答對率最低的一道Easy題

巧妙的解法

【小馬的LeetCode練功坊】858. Mirror Reflection (Medium)
【小馬的LeetCode練功坊】巧妙解法- 差分陣列 1109. Corporate Flight Bookings
【LeetCode巧解欣賞】1049. Last Stone Weight II,石頭對撞問題
【LeetCode巧解欣賞】457. Circular Array Loop

實用情境題

【小馬的LeetCode練功坊】121, 122, 123,188,309,714題- 最佳買賣股票的時機

動態規劃(Dynamic Programming)

聽起來好像很厲害,
不過其實就是若一個問題可以透過相似的小問題得到答案,
那麼就算是一個動態規劃解法

一般來說,動態規劃解題有二個步驟:

  1. 定義大問題與小問題的關係
  2. 使用陣列儲存小問題的解,由小到大填陣列的數值(在只需要記錄最後答案,不必記錄過程的情況下,常常可以很好的節省空間,不必把整個陣列都記下來)

動態規劃在程式領域中是一個非常好用的解題技巧,
值得一學

另,推薦閱讀黃建庭的教學網站>> C++演算法解題(1)>> 動態規劃(Dynamic Programming)
這個教學網站教動態規劃的基礎觀念,講的蠻好的

超簡易範例- 費式數列

在數學上有一個有名的費式數列「1,1,2,3,5,8,13,21,…」
特色是從第三項開始,其值為前兩項的總和,
試寫程式求費式數列的第50項
想法: 用一個陣列F儲存費式數列的值,F[n]表示第n+1個費式數字
一開始將F[0],F[1]的值設成1,
然後大問題F[n]可以由小問題F[n-2],F[n-1]的值得到,
接著就由小到大填表格
範例程式:

#include <iostream>
using namespace std;
int main(){
    long long F[50];
    F[0]=1;
    F[1]=1;  
    for(int i=2;i<50;i++){ 
        F[i]=F[i-1]+F[i-2];
    }
    cout<<F[49]<<endl; //印出12586269025
}

動態規劃題目收集

動態規劃經典題: 最大子陣列之和
動態規劃經典題: 循環陣列的最大子陣列之和
動態規劃經典題: 最長公共子序列(LCS)
動態規劃經典題: 最短路徑之和
動態規劃經典題: 最大正方形面積
動態規劃經典題: 帕斯卡三角形
動態規劃經典題: 01背包問題(knapsack problem)
動態規劃經典題: 給定公差,在陣列中求最長的等差子序列
動態規劃經典題: 計算有幾個正方形
動態規劃經典題: 兩道換零錢問題
動態規劃創意題: 拯救公主問題

其它解題平台題解(如: zerojudge, CodeWar)

除了leetcode外,zerojudge也是個不錯的解題平台,
但zerojudge的題目難度落差極大,
初學做為練習用需慎選問題

c/c++ 特化的I/O優化題

攻略: 怎麼優化你的程式(C++篇)
其實光是試著把cin, cout換成scanf, printf就有不錯的成效
【解題分享】zerojudge上的惡龍題- e307: 請讓我留在你的回憶裡,c++到底怎樣讀字串才快
【zerojudge惡龍題】- e446: 排列生成,你知道其實一直printf很耗時嗎?

有趣的遊戲謎題

【zerojudge惡龍題】- d762: 10344 - 23 out of 5,用五個數字湊出23
【zerojudge惡龍題】- d872: 過橋問題


1 則留言

1
bluegreenking2
iT邦新手 5 級 ‧ 2020-08-11 23:42:41

搶個沙發~
早些日子就聽過一馬的厲害
最喜歡的是邏輯測驗(但想很久還是解不出來
果然好厲害!!

心原一馬 iT邦研究生 5 級 ‧ 2020-08-12 20:08:28 檢舉

謝謝您的欣賞哦~

我要留言

立即登入留言