algo calisthenics

算法和數據結構

我打算將此存儲庫用作練習遊樂場（KATA），並提醒一些常見，簡單但功能強大的算法。在這裡，我將使用Clojure傳感器，這是處理序列的絕佳電動工具。雖然該文檔似乎詳盡，但我打算將其用作我需要學習的任何時間都可以回來的列表。我還沒有實施此處列出的所有內容。

寫作風格

這裡的代碼不是我將用於專業編碼的樣式的形狀。每個團隊都有關於代碼風格的文化和意見，最好堅持這些常見的準則。此外，代碼主要旨在由其他人閱讀，否則我們所有人都將在組裝中進行編​​碼，如果我們僅針對機器讀者群體，則可以最大程度地績效。作為團隊的一部分，我編寫的代碼可能是該團隊中其他任何人都可以寫的。

此處的代碼是用雜物編程編寫的，這要歸功於Emacs和org模式。這意味著用Clojure編寫的代碼是從解釋其背後原因的文本文件中得出的。我希望它使閱讀更容易。

Python

為新問題做準備

./dev-resources/new-problem.sh 
  --problem-path neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups

參見--help 。

當初始化腳本完成後，建議的測試命令將出現在最後：

poetry run ptw -- -- 
  src/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups.py 
  tests/neetcode_practice_2024/arrays_and_hashing/problem_4_anagram_groups_test.py

與詩歌和詩歌互動

例如，在開發時觀看測試：

poetry run ptw
poetry run ptw -- -- --memray
poetry run ptw -- -- --benchmark-only
poetry run ptw -- -- --benchmark-skip

可能避免了周圍的小舞蹈-- --但我寧願對跑步的方式非常明確，因此我將poetry作為最左翼的陣線爭論。

要獲取內存火焰：

poetry run memray run -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4 "
poetry run python -m memray flamegraph memray-neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate.554244.bin

要獲取CPU FlameGraph（或其他圖）：

poetry run python -m cProfile -o program.prof -m neetcode_practice_2024.arrays_and_hashing.problem_1_contains_duplicate --integer_array " 1, 2, 3, 4, 4 "
poetry run snakeviz program.prof

運行基準並獲得圖形摘要：

poetry run pytest --benchmark-only --benchmark-histogram

研究清單

排序算法

• 從頭開始實施：氣泡排序，合併排序，快速排序，堆排序。
• 給定一個整數陣列，使用快速選擇算法找到kth最小的元素。
• 實現計數排序算法以對具有已知值範圍的整數數組進行排序。
• 使用快速排序解決“三向分區”問題，以有效地對具有重複值的數組進行排序。

搜索算法

• 從頭開始實現：二進制搜索（用於排序的數組），線性搜索。
• 給定一個旋轉的排序陣列，請使用修改後的二進制搜索找到目標元素。

遍歷遍歷的圖​​形，樹和算法

• 從頭開始實施：廣度優先搜索（BFS），深度優先搜索（DFS），Dijkstra的算法，Bellman-Ford算法。
• 實施不同的表示：鄰接矩陣，鄰接列表。
• 使用Dijkstra的算法找到加權圖中兩個節點之間的最短路徑。
• 實現二進制搜索樹並執行基本操作，例如插入，刪除和搜索。
• 給定一個有向圖，請檢查兩個節點之間是否有路由。
• 在無向圖中找到連接組件的數量。
• 實施定向無環圖（DAG）的拓撲排序。
• 在二進制樹上找到兩個節點的最低祖先（LCA）。
• 給定二進制樹，檢查它是否是有效的二進制搜索樹（BST）。
• 鑑於圖，請使用Kosaraju的算法或Tarjan的算法找到所有緊密連接的組件（SCC）。
• 實現Floyd-Warshall算法，以在加權圖中找到最短的全對路徑。
• 給定n- ary樹，執行級別的遍歷或深度優先的遍歷（例如，預訂，後階）。

動態編程

• 了解將問題分解為較小的重疊子問題的概念，並使用回憶或製表。
• 使用遞歸和動態編程方法解決經典的“斐波那契”問題。
• 給定一組具有權重和值的項目，請使用0-1 knapsack問題找到可以通過給定最大權重獲得的最大值。

貪婪算法

• 了解在本地最佳選擇的問題會導致全球最佳解決方案。
• 為“活動選擇問題”實施解決方案，您需要選擇不重疊的最大活動數量。
• 給定一組具有不同面額和數量的硬幣，請找到使用貪婪的方法製作該數量所需的最小硬幣數量。

回溯算法

• 解決“ N-Queens”問題，將N Queens放在N×N棋盤上，而無需相互攻擊。
• 實施Sudoku求解器來解決部分填充的Sudoku難題。

字符串操縱算法

• 字符串匹配
• 字符串逆轉
• 回文檢查
• 給定兩個字符串，檢查一個字符串是否是另一個置換。
• 實現“ Rabin-karp”算法以在給定文本中找到模式。

位操縱算法

• 鑽頭操作，在數組中找到單個唯一元素。
• 給定一個數組，所有數字都發生了兩次，除一個數字外，請找到單個唯一數字。
• 實現一個函數來計算整數中設置為1的位數。

劃分和征服算法

• 二進制搜索，找到最大子陣列總和。
• 實施Karatsuba算法以快速乘以大整數。
• 使用鴻溝和征服方法在2D空間中的一組點中找到最接近的點。

隨機算法

• 隨機地將陣列隨機洗牌。
• 實現“隨機選擇”算法，以在數組中找到KTH最小的元素。

滑動窗口技術

• 給定一個整數陣列，找到大小k的任何連續子陣列的最大總和。
• 在給定的字符串中找到最長的基因帶有最多的k個不同字符。

間隔問題

• 給定間隔列表，合併重疊的間隔。
• 查找安排間隔列表所需的最少會議室數量。

嘗試

• 實施TRIE數據結構，以進行有效的字符串搜索和檢索。
• 給定單詞列表，請使用trie找到最長的常見前綴。
• 使用TRIE為給定的一組單詞實現自動完成功能。
• 給定單詞列表，找到所有單詞對，以使串聯形成單詞。

哈希

• 實施哈希功能，碰撞分辨率技術和用例。
• 實施具有碰撞解決方案的哈希表（例如，鏈接或開放尋址）。
• 使用哈希地圖在字符串中找到第一個未重複的字符。
• 實現Rabin-Karp算法，以匹配多個模式的字符串。
• 找到最長的子字符串，而無需使用哈希映射以獲取字符頻率。

堆

• 實施Min-Heaps和Max-Heaps及其應用（例如優先級隊列）。
• 從頭開始實施最小或最大岩。
• 給定一系列元素，使用基於堆的方法找到KTH最大元素。

矩陣操縱

• 給定M×N矩陣，將其旋轉90度。
• 給定0s和1s的矩陣，找到1S的最大正方形（最大大小的正方形子矩陣）並返回其面積。

紅黑樹或avl樹

• 為紅黑樹或AVL樹實施插入和刪除操作。
• 執行旋轉以平衡不平衡的二進制搜索樹。

數據結構實現

• 數組和列表：實現數組，鏈接列表及其操作。
• 堆棧和隊列：實施堆棧和隊列數據結構及其應用程序。
• 哈希地圖：實施哈希地圖並了解其時間複雜性。

工具

算法和數據結構是通過簡單的Restful API暴露的，以進行更現實的設置和更強大的測試：

• 表現

  • API負載：加特林，吉米特，蝗蟲；

  • 微標準：JMH，標準；

  • 資源： htop ， top ， vmstat ；

  • 記憶：objgraph，jamm;

• 行為

  • 測試：UNITSEST，MOCKITO，基於生成或基於屬性的測試，標準測試庫和實踐；

  • 靜態分析：Sonarqube；

  • 分析：框架圖，CPROFILE，VISUALVM，Spring Boot執行器，JSTACK；

• 代碼樣式

  • 突變測試：Lein突變，坑，宇宙射線；

  • 代碼覆蓋範圍：Clover，Coverage.py，Jacoco；

  • 代碼指標：ra，checkstyle，jqassistant；

• 可觀察性：Prometheus，Grafana；

（此處列出的工具可能特定於某些語言）