NO IMAGE

這篇部落格記錄了我在跟著《演算法筆記》以及習題冊《演算法筆記 上機實踐指南》刷了PAT的題目之後的一些解題方法的總結與心得。

第三章 入門模擬

1. 簡單模擬

一般解題思路

這一小節的題目只需根據題目描述(一般規則很簡單),用程式碼實現即可;有些題目在用到一下知識點之後變得更簡便。

學到的知識點

  1. /和%運算子的強大作用
  2. 陣列下標對映打表
  3. 迴圈問題的解題思路(left to right = sum – (right to left))
    注:知識點的具體運用可以進入下面題目的題解檢視。

題目彙總

PAT-B 1001 害死人不償命的(3n 1)猜想 (15)
PAT-B 1011.A B和C (15)
PAT-B 1016. 部分A B (15)
PAT-B 1026. 程式執行時間(15)
PAT-B 1046. 划拳(15)
PAT-B 1008. 陣列元素迴圈右移問題 (20)
PAT-B 1012. 數字分類 (20)
PAT-B 1018. 錘子剪刀布 (20)
PAT-A 1042. Shuffling Machine (20)
PAT-A 1046. Shortest Distance (20)
PAT-A 1065. A B and C (64bit) (20)
PAT-B 1010. 一元多項式求導 (25)
PAT-A 1002. A B for Polynomials (25)
PAT-A 1009. Product of Polynomials (25)

2. 查詢元素

一般解題思路

在“查詢元素”這個小節的題目中,一般會有兩種思考的角度:

角度1. 將所有輸入讀入並儲存,遍歷所有輸入,找到需要查詢的元素
角度2. 一邊讀入一邊覆蓋,最後儲存的就是需要查詢的元素

題目彙總

PAT-B 1041. 考試座位號(15)
PAT-B 1004. 成績排名 (20)
PAT-B 1028. 人口普查(20)
PAT-B 1032. 挖掘機技術哪家強(20)
PAT-A 1011. World Cup Betting (20)
PAT-A 1006. Sign In and Sign Out (25)
PAT-A 1036. Boys vs Girls (25)

3. 圖形輸出

一般思路

圖形列印這類題一般有兩種做法:
1. 將要輸出的內容填充到二位陣列中,輸出二維陣列
2. 直接輸出需要輸出的東西

法二探索:
對於第二種方法,我認為有三要素:需要列印的行數、需要列印的列數、每行列印的規則。 一旦這三要素確定了,圖形基本就出來了。

三要素的獲取方法,遇到的兩種較多的型別是找規律數學推算

法一探索:
對於第一種方法,二維陣列的填充,也是通過找到規律,填充進去。這種情況用在每一行的規律不是那麼好找的情況下,利用二維陣列可隨機訪問的性質,將資訊填入陣列,這樣就便利得多。題目彙總的第二題有所體現。

類似“沙漏”這種稜角分明的圖形規律尋找:
這種圖形的規律一般可以拿出邊界線(較簡單的情況為直線)的直線方程,通過直線方程x,y(控制輸出的迴圈變數)的大小關係來控制輸出資訊。
如果可以比較容易的看出規律或輸出變數之間的關係當然更便捷。

題目彙總

PAT-B 1027. 列印沙漏(20)
PAT-A 1031. Hello World for U (20)

4. 日期處理

在《演算法筆記》中,“日期處理”的問題分類在“入門模擬”章節,解決這類題目不易出錯、方便理解的方法也的確是通過“模擬”現實世界的日期更近的情況(時間都是一秒一秒往前走的),來知道程式碼的實現。

下面題目彙總的第一題有非常好的體現。

題目彙總

codeup 1928 日期差值

新穎的日期比較方法:long long 型資料直接比較法。(這種思想在“查詢元素”小節也用到很多)

5. 進位制轉換

這一小節的題目比較少且有固定方法可尋,所以當時做完非常開心,忘記記錄了,距離今日已經較久遠(從家到學校到現在馬上要上第二週的課,時間過得真快),當時做題的感受有些記不太清楚,只能憑藉題解記錄來找回一些做題的記憶志之,日後若有新的收穫再記之。

看完題解發現有兩點比較關鍵的:

  1. 下面的“題目彙總”第一題題解記載了該類問題的一般解法
  2. 一般解法的關鍵其實還是建立在充分理解除法和取餘運算以及迴圈思想

題目彙總

PAT-B 1022. D進位制的A B (20) → 記錄了“進位制問題的一般方法”
PAT-B 1037. 在霍格沃茨找零錢(20)
PAT-A 1019. General Palindromic Number (20)
PAT-A 1027. Colors in Mars (20)
PAT-A 1058. A B in Hogwarts (20)

6. 字串處理

字串處理的題目應該算這一章最難的了,可以說這類題目真的是千變萬化,沒有什麼固定思想。需要我非常仔細的觀察題目中的輸入和輸出的通知,還需要注意很多細節以及邊界條件,常常是邏輯非常麻煩。

目前這一小節有題目在未解佇列裡。

題目彙總

PAT-B 1006. 換個格式輸出整數 (15)
PAT-B 1021. 個位數統計 (15)
PAT-B 1031. 查驗身份證(15)
PAT-B 1002. 寫出這個數 (20
PAT-B 1009. 說反話 (20)
PAT-B 1014. 福爾摩斯的約會 (20)
PAT-A 1061. Dating (20)
PAT-B 1024. 科學計數法 (20)
PAT-B 1048. 數字加密(20)
PAT-A 1005. Spell It Right (20)
PAT-A 1001. A B Format (20)
PAT-A 1035. Password (20)
PAT-A 1077. Kuchiguse (20)
1082. Read Number in Chinese (25) → 入隊

第四章 演算法初步

1、排序

這一章運用在題中主要還是sort函式的使用,其中最為重要的是sort函式的cmp函式的編寫。

cmp函式的編寫有時候需要考慮“分類”這樣的概念,比如下面題目彙總的第一題。
cmp函式的編寫記憶規律是:若return a < b,則表示左小右大,從小到大排序;a>b則表示從大到小排序。

題目彙總

PAT-B 1015. 德才論 (25)
PAT-A 1062. Talent and Virtue (25)
1016. Phone Bills (25) -> 入隊
PAT-A 1025. PAT Ranking (25)
PAT-A 1028. List Sorting (25)
PAT-A 1055. The World’s Richest (25)
PAT-A 1075. PAT Judge (25)
PAT-A 1083. List Grades (25)
PAT-A 1080. Graduate Admission (30) ->有測試點沒過
PAT-A 1095. Cars on Campus (30) ->入隊

2、雜湊

這一章主要涉及到是字串的雜湊,並且是簡單雜湊,只需要打一張hashTable就可以。

題目彙總

PAT-B 1029. 舊鍵盤(20)
PAT-A 1084. Broken Keyboard (20)
PAT-B 1033. 舊鍵盤打字(20)
PAT-B 1039. 到底買不買(20)
PAT-A 1092. To Buy or Not to Buy (20)
PAT-B 1042. 字元統計(20)
PAT-B 1043. 輸出PATest(20)
PAT-B 1047. 程式設計團體賽(20)
PAT-A 1041. Be Unique (20)
PAT-A 1050. String Subtraction (20)
PAT-B 1005. 繼續(3n 1)猜想 (25)
PAT-A 1048. Find Coins (25)

3、遞迴

暫且不多說,心累……
這裡

4、貪心

貪心是一種演算法思想。對於貪婪的人類,在想獲得“最大利益”的時候,總是需要在每個環節都拿到“最高分”,這就是貪心的本質。所以貪心的思想不難,因為基本貫徹了人的一生;想到貪心的策略,一般也不太難;難點在於對策略的證明。
好在程式中不需要有證明過程,只需要確切保證策略的正確性即可。

題目彙總

PAT-B 1023. 組個最小數 (20)
PAT-B 1020. 月餅 (25)
PAT-A 1070. Mooncake (25)
PAT-A 1033. To Fill or Not to Fill (25)
PAT-A 1037. Magic Coupon (25)
PAT-A 1067. Sort with Swap(0,*) (25)
PAT-A 1038. Recover the Smallest Number (30)

5、二分查詢

二分查詢這麼幾道題刷了好久……手動哭泣,有幾題需要注意的比較多。不過終於是全都AC了,沒有進佇列了,嘻嘻。
在《演算法筆記》中的這一小節,晴神講了不少東西,題目中遇到了的是兩種情況:
1. 二分查詢一個數
2. 二分查詢一個數,這個數是第一個滿足某條件的位置
這兩種問題寫法上有差別,暫時不記錄了,有時間回來記錄吧。

刷PAT的時間也馬上到頭了,有現階段更加重要和緊急的事情需要處理。擼PAT的這段時間感覺非常好,喜歡~感謝晴神!我一定還會接著刷,以及刷第二遍,第三遍的……

題目彙總

PAT-B 1030. 完美數列(25)
PAT-A 1085. Perfect Sequence (25)
PAT-A 1010. Radix (25)
PAT-A 1044. Shopping in Mars (25)
PAT-A 1048. Find Coins (25)

6、two pointers

有了前面的難受,這一節要好很多,並且很多都是之前的題目,two pointers 真是一種強大的思想。

暫且不描述什麼是two pointers,從題目中去體會吧。

題目彙總

PAT-B 1030. 完美數列(25)
PAT-A 1085. Perfect Sequence (25)
PAT-A 1089. Insert or Merge (25)
PAT-A 1029. Median (25)
PAT-A 1048. Find Coins (25)

7、其他高效技巧與演算法

在這一節中,《演算法筆記》介紹了:
1. 打表
2. 遞推
3. 隨機選擇演算法

其中打表 遞迴解決了下面“題目彙總”的前兩道題,將時間複雜度降到了O(N)。

隨機選擇演算法《演算法筆記》(PAT題解)暫時沒有對應題目,等遇上題目再總結。主要解決的是“求一個序列中第K大的數”這樣的一個問題。

題目彙總

PAT-B 1045. 快速排序(25)
PAT-A 1101. Quick Sort (25)
PAT-B 1040. 有幾個PAT(25)
PAT-A 1093. Count PAT’s (25)

第五章 數學問題

這一章的習題(除去小節“大整數運算”)在一年前做的,大部分都做了題解,但是解題之後的感想已經記不得了,所以下面直接給出分類,相信在題解記錄中也會找到當時的痕跡。

1、簡單數學

PAT-B 1003. 我要通過!(20)
PAT-B 1019. 數字黑洞 (20)
PAT-A 1069. The Black Hole of Numbers (20)
PAT-B 1049. 數列的片段和(20)
1104. Sum of Number Segments (20)(同上題)
PAT-A 1008. Elevator (20)
1049. Counting Ones (30)(忘了當時是未解 還是 入隊了,總之現在是進入 入隊 狀態)

2、最大公約數與最小公倍數

在演算法筆記中有一題歸在此類(1008. 陣列元素迴圈右移問題 (20)),但是這個題目不用書中題解中的思想也能AC。題解記錄

3、分數的四則運算

分數四則運算相關知識點 請看這裡

PAT-A 1081. Rational Sum (20)
PAT-B 1034. 有理數四則運算(20)
PAT-A 1088. Rational Arithmetic (20)

4、素數

相關知識點:Eratosthenes篩法求素數表

題解記錄:
PAT-B 1007. 素數對猜想 (20)
PAT-B 1013. 數素數 (20)
PAT-A 1015. Reversible Primes (20)
PAT-A 1078. Hashing (25)

5、質因子分解

相關知識點:質因子分解

題解記錄:
PAT-A 1096. Consecutive Factors (20)
PAT-A 1059. Prime Factors (25)

6、大整數運算

相關知識點: 大整數運算

題解記錄:
PAT-B 1017. A除以B (20)
PAT-A 1023. Have Fun with Numbers (20)
PAT-A 1024. Palindromic Number (25)

更新記錄

2017-03-26
這篇部落格暫時停更,希望回來接著更新的時候,自己依然是條好漢!!!為自己加油~

ps:《演算法筆記》(胡凡 著)是本好書,推薦買來看,哈哈。


2018-01-08
久別快一年了,話不多說,默默更新好了。

先是整理了一下之前刷過的題,有些沒有整理進來,打算先刷一段時間,等感覺慢慢回來之後,再將那部分整理進來,現在還是邊刷邊整理吧~

新的一年,需要更加努力呀~


2018-01-12
整理完了之前沒有整理上來的內容(第五章 數學問題)