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；

（此处列出的工具可能特定于某些语言）