Skip to content

yi-ge/cpp-practice

Repository files navigation

C++ 算法练习

license GitHub Actions Test Results Coveralls github GitHub last commit Gitpod Ready-to-Code

C++ 基础算法、数据结构练习,包含 LeetCode 或其它算法练习记录。

此为个人练习仓库,代码中对重要思想进行了注释,会尽量补充解题思路。

每一道题都对应写有测试用例,但可能不够完整。如果您发现错误,欢迎给我留言,谢谢!

安装以下测试环境后,运行yarn start可以自动从LeetCode获取代码函数和用例说明。保存文件后将自动同步到浏览器。

特别说明:题目截图仅为了方便在代码编辑器中直接预览从而优化编码体验,题目以LeetCode官方页面为准,题目著作权及其他权利以LeetCode官方说明为准或属于LeetCode。请大家尊重版权,共同维护良好网络环境。

测试环境

如果你使用VSCode进行开发,那么可以安装CMake ToolsclangdC++ TestMate以获得更好的单元测试体验。

注意,由于此项目使用LLVM,因此推荐使用与之对应的clangd插件,所以您不应当再安装C/C++插件。

以下是各个平台安装依赖的说明。

MAC

brew install cmake node zlib yarn llvm ninja

echo 'export PATH="/opt/homebrew/opt/llvm/bin:$PATH"' >> ~/.zshrc
echo 'export LDFLAGS="-L/opt/homebrew/opt/llvm/lib"' >> ~/.zshrc
echo 'export CPPFLAGS="-I/opt/homebrew/opt/llvm/include"' >> ~/.zshrc

安装完成后执行yarn安装依赖。

VSCodeCmake Tools插件选择active kitClang

Linux

参考https://apt.llvm.org/安装LLVM 16(clang-16)。

以Ubuntu Jammy (22.04) LTS为例,安装LLVM 16:

wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key 2>/dev/null | sudo apt-key add -
sudo add-apt-repository 'deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-16 main' -y
sudo apt-get update -q
sudo apt-get install -y clang-16 llvm-16 lld-16 libc++-16-dev libc++abi-16-dev clang-tools-16 clang-16-doc wasi-libc llvm-16-doc binutils ninja-build
sudo update-alternatives --config c++
wget https://github.com/Kitware/CMake/releases/download/v3.23.2/cmake-3.23.2-linux-x86_64.sh
sudo chmod +x cmake-3.23.2-linux-x86_64.sh
sudo ./cmake-3.23.2-linux-x86_64.sh --prefix=/usr

以Kali Rolling(Debian)为例,安装LLVM 16:

wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key 2>/dev/null | sudo apt-key add -
sudo apt-key export AF4F7421|sudo gpg --dearmour -o /etc/apt/trusted.gpg.d/llvm.gpg
sudo bash -c "echo  'deb [arch=amd64 signed-by=/etc/apt/trusted.gpg.d/llvm.gpg] http://apt.llvm.org/unstable/ llvm-toolchain-16 main' >> /etc/apt/sources.list"
sudo apt-get update -y
sudo apt-get install -y clang-16 llvm-16 lld-16 libc++-16-dev libc++abi-16-dev clang-tools-16 clang-16-doc wasi-libc llvm-16-doc binutils ninja-build
sudo update-alternatives --config c++

执行最后一行命令后,提示选择C++编译器,选择clang++。

如果是Kali 2022之前的版本,需要加载对应版本的源,参考https://apt.llvm.org/进行配置。

根据https://nodejs.org/en/download/package-manager/安装Node.js环境。根据安装时的提示安装yarn

安装完成后执行yarn安装依赖。

VSCodeCmake Tools插件选择active kitClang

Windows

执行winget install CMake安装最新版cmake

执行winget install Node.js安装最新版node

执行winget install Ninja-build.Ninja安装最新版ninja

安装LLVM,方法一:

执行winget install --id LLVM.LLVM安装最新版LLVM,并将C:\Program Files\LLVM\bin路径添加到系统Path

安装LLVM,方法二:

安装 Visual Studio 2022,并在Visual Studio Installer勾选使用C++的桌面开发中的适用于Windows的C++ Clang工具(15.0.1+)。

安装LLVM后,在VSCodeCmake Tools插件选择active kit版本为Clang,例如:Clang 16.0.1 x86_64-pc-windows-msvcClang 15.0.1 (GNU CLI) for MSVC 17.5.33530.505。或者手动执行的时候使用对应版本的llvm clang

需要特别注意的是,在Windows平台,Microsoft Visual Studio的MSVC标准库和LLVM的Clang标准库之间可能会产生冲突,需要根据具体情况进行调整。

上述安装完成后执行yarn安装依赖。

Windows下中文乱码?

需要在 Windows 中设置使用 Unicode UTF-8 提供全球语言支持,请按照以下步骤操作:

1. 打开“控制面板”。 2. 单击“时钟和区域”,然后单击“区域”。 3. 在“区域”窗口中,转到“管理”选项卡。 4. 单击“更改系统区域设置…”。 5. 在新弹出的“区域设置”窗口中,勾选“Beta 版:使用 Unicode UTF-8 提供全球语言支持(可能会影响与某些老应用程序的兼容性)”复选框。 6. 点击“确定”保存更改。系统可能需要重启以使更改生效。

已解决此问题,无论是否启用使用 Unicode UTF-8 提供全球语言支持,均可展示正确的中文内容。请在测试资源管理器刷新测试,查看TestMate C++下的测试集,将会展示正确的中文内容。

基础排序算法

排序算法 时间复杂度 (平均) 时间复杂度 (最坏) 时间复杂度 (最好) 原地排序 空间复杂度 稳定性
插入排序 (O(n^2)) (O(n^2)) (O(n)) (O(1))
冒泡排序 (O(n^2)) (O(n^2)) (O(n)) (O(1))
选择排序 (O(n^2)) (O(n^2)) (O(n^2)) (O(1))
快速排序 (O(n \log n)) (O(n^2)) (O(n \log n)) (O(\log n))
归并排序 (O(n \log n)) (O(n \log n)) (O(n \log n)) (O(n))
堆排序 (O(n \log n)) (O(n \log n)) (O(n \log n)) (O(1))

基础数据结构

C++标准库中的数据结构(部分)

C++标准库提供的数据结构实在是太多了,参考C++标准库头文件,仅列举常见的:

通过C++实现的数据结构及其常见操作

算法题

字符串

数组/队列/集合/映射

链表

排序

其它