标签归档:data-structure

Algorithms-Python中数据结构和算法的最小示例

Python数据结构和算法

Python3中数据结构和算法的最小且干净的示例实现

贡献

感谢您对投稿的兴趣!有很多方式可以为这个项目做出贡献。Get started here

测试

使用单元测试

要运行所有测试,请写下:

$ python3 -m unittest discover tests

要运行某些特定测试,您可以执行以下操作(例如:排序):

$ python3 -m unittest tests.test_sort

使用pytest

要运行所有测试,请写下:

$ python3 -m pytest tests

安装

如果您想在代码中使用API算法,只需如下所示:

$ pip3 install algorithms

您可以通过创建一个python文件进行测试:(例如:USEmerge_sort在……里面sort)

from algorithms.sort import merge_sort

if __name__ == "__main__":
    my_list = [1, 8, 3, 5, 6]
    my_list = merge_sort(my_list)
    print(my_list)

卸载

如果要卸载算法,只需执行以下操作:

$ pip3 uninstall -y algorithms

实现列表

贡献者

感谢all the contributors帮助建立回购的人

Interactive-coding-challenges-120+交互式Python编码面试挑战(算法和数据结构)

交互式编码-挑战

120多项持续更新、交互式和测试驱动的编码挑战,具有Anki flashcards

挑战集中在算法数据结构在以下位置找到编码面试

每个挑战都有一个或多个参考解决方案,它们是:

  • 全功能
  • 单元测试
  • 通俗易懂

Challenges将很快提供按需服务incremental hints以帮助您获得最佳解决方案

笔记本还详细介绍了:

  • 约束条件
  • 测试用例
  • 算法
  • 大O时空复杂性

还包括单元测试的参考实现各式各样的data structuresalgorithms

挑战解决方案

Anki抽认卡:编码与设计

提供的Anki flashcard deck使用间隔重复来帮助您记住关键概念

非常适合在旅途中使用

设计资源:系统设计入门

寻找资源来帮助您准备系统设计面向对象的设计访谈

查看姊妹回购The System Design Primer,其中包含其他Anki甲板:

笔记本结构

每个挑战有两个笔记本,一个挑战笔记本有要解决的单元测试和解决方案笔记本以供参考

问题陈述

  • 陈述要解决的问题

约束条件

  • 描述任何约束或假设。

测试用例

  • 描述将在单元测试中评估的常规测试用例和边缘测试用例。

算法

  • [挑战笔记本]空,如果需要提示,请参阅解决方案笔记本算法部分
  • [解决方案笔记本]一个或多个算法方案讨论,时间和空间复杂度大O

提示

  • [挑战笔记本]提供按需服务incremental hints来帮助你找到最优的解决方案。马上就来!

代码(挑战:实现我!)

  • [挑战笔记本]供您实现的骨架代码
  • [解决方案笔记本]一个或多个参考解决方案

单元测试

  • [挑战笔记本]代码的单元测试。预计在你解决挑战之前都会失败
  • [解决方案笔记本]参考解决方案的单元测试

索引

挑战类别

格式化:挑战类别-挑战数量

挑战总数:120项

参考实现:数据结构

以下数据结构经过单元测试、功能齐全的实现:

参考实现:算法

以下算法经过单元测试、功能齐全的实现:

参考实现:TODO

安装和运行挑战

杂项

挑战

Image Credits

数组和字符串

挑战 静电笔记本
确定字符串是否包含唯一字符 ChallengeSolution
确定一个字符串是否为另一个字符串的排列 ChallengeSolution
确定一个字符串是否为另一个字符串的旋转 ChallengeSolution
压缩字符串 ChallengeSolution
颠倒字符串中的字符 ChallengeSolution
给定两个字符串,找到单个不同的字符 ChallengeSolution
查找两个总和为特定值的索引 ChallengeSolution
实现哈希表 ChallengeSolution
实施冒泡嗡嗡声 ChallengeSolution
查找字符串中的第一个非重复字符 ContributeContribute
删除字符串中的指定字符 ContributeContribute
颠倒字符串中的单词 ContributeContribute
将字符串转换为整数 ContributeContribute
将整数转换为字符串 ContributeContribute
添加质询 ContributeContribute

链表

挑战 静电笔记本
从链接列表中删除重复项 ChallengeSolution
查找链表最后一个元素的第k个元素 ChallengeSolution
删除链表中间的节点 ChallengeSolution
围绕给定值对链表进行分区 ChallengeSolution
将数字存储在链表中的两个数字相加 ChallengeSolution
查找链接列表循环的起点 ChallengeSolution
确定链表是否为回文 ChallengeSolution
实现链表 ChallengeSolution
确定列表是循环的还是非循环的 ContributeContribute
添加质询 ContributeContribute

堆栈和队列

挑战 静电笔记本
使用单个数组实施n个堆栈 ChallengeSolution
实现跟踪其最小元素的堆栈 ChallengeSolution
实现包装容量受限堆栈列表的一组Stacks类 ChallengeSolution
使用两个堆栈实现一个队列 ChallengeSolution
使用另一个堆栈作为缓冲区对堆栈进行排序 ChallengeSolution
实现堆栈 ChallengeSolution
实现一个队列 ChallengeSolution
实现由数组支持的优先级队列 ChallengeSolution
添加质询 ContributeContribute

图形和树

挑战 静电笔记本
在树上实现深度优先搜索(前、中、后顺序) ChallengeSolution
实现树的广度优先搜索 ChallengeSolution
确定树的高度 ChallengeSolution
从排序数组创建高度最小的二叉搜索树 ChallengeSolution
为二叉树的每个级别创建链表 ChallengeSolution
检查二叉树是否平衡 ChallengeSolution
确定树是否为有效的二叉搜索树 ChallengeSolution
在二叉搜索树中查找给定节点的有序后继节点 ChallengeSolution
查找二叉树中的第二大节点 ChallengeSolution
找到最底层的共同祖先 ChallengeSolution
反转二叉树 ChallengeSolution
实现二叉搜索树 ChallengeSolution
实现最小堆 ChallengeSolution
实现Trie ChallengeSolution
在图上实现深度优先搜索 ChallengeSolution
实现图的广度优先搜索 ChallengeSolution
确定图中的两个节点之间是否存在路径 ChallengeSolution
实现图形 ChallengeSolution
在给定项目和依赖项列表的情况下查找构建顺序 ChallengeSolution
在加权图中查找最短路径 ChallengeSolution
在未加权图中查找最短路径 ChallengeSolution
添加质询 ContributeContribute

排序

挑战 静电笔记本
实现选择排序 ChallengeSolution
实现插入排序 ChallengeSolution
实现快速排序 ChallengeSolution
实现合并排序 ChallengeSolution
实现基数排序 ChallengeSolution
对字符串数组进行排序,以便所有字谜都相邻 ChallengeSolution
在排序的旋转数组中查找项 ChallengeSolution
在排序矩阵中搜索项目 ChallengeSolution
在n个整数的输入中查找不是的整数 ChallengeSolution
给定排序数组A、B,按排序顺序将B合并到A中 ChallengeSolution
实现稳定选择排序 ContributeContribute
使不稳定排序稳定 ContributeContribute
实现高效的就地版本的快速排序 ContributeContribute
给定两个排序的数组,按排序顺序将一个合并到另一个 ContributeContribute
在经过旋转和排序的整数数组中查找元素 ContributeContribute
添加质询 ContributeContribute

递归与动态规划

挑战 静电笔记本
递归、动态和迭代地实现Fibonacci ChallengeSolution
最大化放置在背包中的物品 ChallengeSolution
最大化放置在背包中的无界项目 ChallengeSolution
查找最长的公共子序列 ChallengeSolution
找出最长的递增子序列 ChallengeSolution
最小化矩阵乘法的成本 ChallengeSolution
在给定k个交易的情况下最大化股票价格 ChallengeSolution
在给定一组硬币的情况下,找出表示n美分的最小方法数 ChallengeSolution
在给定一组硬币的情况下,找出表示n美分的唯一数量的方法 ChallengeSolution
打印n对括号的所有有效组合 ChallengeSolution
在迷宫中导航 ChallengeSolution
打印集合的所有子集 ChallengeSolution
打印字符串的所有排列 ChallengeSolution
在数组中查找魔术索引 ChallengeSolution
找出运行n个步骤的方式的数量 ChallengeSolution
用3个塔和N个圆盘实现河内之塔 ChallengeSolution
递归、动态和迭代地实现阶乘 ContributeContribute
对已排序的整数数组执行二进制搜索 ContributeContribute
打印字符串的所有组合 ContributeContribute
实现绘画填充功能 ContributeContribute
给出1、5、10、25美分硬币,找出代表n美分的所有排列 ContributeContribute
添加质询 ContributeContribute

数学与概率

挑战 静电笔记本
生成素数列表 ChallengeSolution
找到数字根 ChallengeSolution
在O(1)中创建支持插入、最大、最小、平均、模式的类 ChallengeSolution
确定一个数字是否为2的幂 ChallengeSolution
将不带+或-号的两个数字相加 ChallengeSolution
减去两个不带+或-号的数字 ChallengeSolution
检查数字是否为质数 ContributeContribute
确定笛卡尔平面上的两条直线是否相交 ContributeContribute
仅使用整数的加法、减法和除法实现乘法、减法和除法 ContributeContribute
找出第k个数,使其唯一的素因数为3、5和7 ContributeContribute
添加质询 ContributeContribute

位操作

挑战 静电笔记本
实现常见的位操作操作 ChallengeSolution
确定要翻转以将a转换为b的位数 ChallengeSolution
在屏幕上画一条线 ChallengeSolution
翻转一位以最大化最长的1序列 ChallengeSolution
获取下一个最大和下一个最小的数字 ChallengeSolution
合并两个二进制数 ChallengeSolution
交换整数中的奇数位和偶数位 ChallengeSolution
打印介于0和1之间的数字的二进制表示法 ChallengeSolution
确定给定整数的二进制表示中的1的个数 ContributeContribute
添加质询 ContributeContribute

网上评委

挑战 静电笔记本
查找最多包含k个不同字符的最长子字符串 ChallengeSolution
找出三个数字的最高乘积 ChallengeSolution
通过1次买入和1次卖出最大化股票利润 ChallengeSolution
将列表中的所有零移动到末尾 ChallengeSolution
找出所有其他整数的乘积 ChallengeSolution
给出进场和出场的列表,找出最繁忙的时段 ChallengeSolution
确定岛屿的周长 ChallengeSolution
格式化许可证密钥 ChallengeSolution
查找最长的绝对文件路径 ChallengeSolution
合并元组范围 ChallengeSolution
分配Cookie ChallengeSolution
确定您是否可以在NIM中获胜 ChallengeSolution
检查一本杂志是否可能被用来制作赎金字条 ChallengeSolution
找出一个句子可以在屏幕上显示的次数 ChallengeSolution
乌托邦之树 ChallengeSolution
最大化异或 ChallengeSolution
添加质询 ContributeContribute

回购结构

interactive-coding-challenges        # Repo
├─ arrays_strings                    # Category of challenges
│  ├─ rotation                       # Challenge folder
│  │  ├─ rotation_challenge.ipynb    # Challenge notebook
│  │  ├─ rotation_solution.ipynb     # Solution notebook
│  │  ├─ test_rotation.py            # Unit test*
│  ├─ compress
│  │  ├─ compress_challenge.ipynb
│  │  ├─ compress_solution.ipynb
│  │  ├─ test_compress.py
│  ├─ ...
├─ linked_lists
│  ├─ palindrome
│  │  └─ ...
│  ├─ ...
├─ ...

*笔记本(.ipynb)读/写关联的单元测试(.py)文件

笔记本安装

零安装

本自述包含指向以下内容的链接Binder,哪些主机动态笔记本不需要安装的在线回购内容

木星笔记本

运行:

pip install jupyter

有关更优化地设置开发环境的详细说明、脚本和工具,请参阅dev-setup回购

有关笔记本安装的更多详细信息,请按照说明操作here

有关IPython/Jupyter笔记本的更多信息,请访问here

跑步挑战

笔记本电脑

挑战以以下形式提供IPython/Jupyter笔记本电脑一直以来都是使用Python 2.7和Python 3.x进行测试

如果您需要安装IPython/Jupyter笔记本,请参阅Notebook Installation部分

  • 本自述包含指向以下内容的链接nbviewer,哪些主机静电笔记本回购的内容
  • 中的元素进行交互或修改动态笔记本,请参阅以下说明

运行挑战笔记本:

$ git clone https://github.com/donnemartin/interactive-coding-challenges.git
$ cd interactive-coding-challenges
$ jupyter notebook

这将启动包含质询类别列表的Web浏览器:

  • 导航到挑战笔记本你想要解决
  • 运行挑战笔记本中的单元格(单元格->全部运行)
    • 这将导致预期的单元测试错误
  • 解决挑战并验证它是否通过了单元测试
  • 查看随附的解决方案笔记本以供进一步讨论

调试您的PDB解决方案,请参阅以下内容ticket

注意:如果您的解决方案与解决方案笔记本中列出的解决方案不同,请考虑提交Pull请求,以便其他人可以从您的工作中受益。回顾Contributing Guidelines有关详细信息,请参阅

未来发展方向

挑战、解决方案和单元测试以IPython/Jupyter笔记本电脑

  • 笔记本目前主要包含Python解决方案(在Python2.7和Python3.x上都进行了测试),但可以进行扩展以包括40+ supported languages
  • 回购将是不断更新新的解决方案和挑战
  • Contributions欢迎光临!

贡献

欢迎投稿!

回顾Contributing Guidelines有关如何执行以下操作的详细信息,请执行以下操作:

  • 提交问题
  • 为现有挑战添加解决方案
  • 添加新的挑战

学分

资源

图像

联系信息

请随时与我联系,讨论任何问题、问题或评论

我的联系信息可以在我的GitHub page

许可证

我在开放源码许可下向您提供此存储库中的代码和资源。因为这是我的个人存储库,您获得的我的代码和资源的许可证来自我,而不是我的雇主(Facebook)

Copyright 2015 Donne Martin

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

   http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.