人生如逆旅,我亦是行人人生如逆旅,我亦是行人
转载请注明出处
该笔记只是用于记录和梳理CMake中比较重要的知识,并不会写得很详细(比如不会写出使用project()命令后会创建哪些变量)。学完本笔记即可上手使用CMake,一些很细的知识可以在遇到所用的场景时自行查阅官方资料。
基础框架
最基本的CMake项目是由单个源代码文件构建可执行文件,对于这种简单的项目,只需要给 CMakeLists.txt 文件提供三个命令:
1 2 3 4 5 6 7 8 9 cmake_minimum_required(VERSION x.xx) # 指定CMake最低版本 project( ProjectName # 项目名称 VERSION x.x.x # 项目版本 LANGUAGES CXX # 项目语言, CXX表示C++ ) add_executable(ExecutableName SourceCodePath) # 设置可执行文件的名称和源代码路径 例如:
1 2 3 4 5 6 7 8 9 cmake_minimum_required(VERSION 3.15) project( MBFF VERSION 0.1.12 LANGUAGES CXX ) add_executable(MBFF src/main.cpp) 这样我们就可以产生一个名为MBFF的可执行文件。
其中 cmake_minimum_required()和project()命令需要在项目的顶级CMakeLists.txt给出(当项目十分复杂时,会存在多个CMakeLists.txt文件)。
cmake_minimum_required(): 该命令是CMakeLists.txt中第一条执行的命令,用于控制CMake的版本,禁用一些已启用的特性 project(): 设置项目的相关属性,可以只设置项目名称,但推荐按上面的写法来用 add_executable(): 产生可执行文件,没有该命令是不会产生可执行文件的 注意:CMakeLists.txt的命令执行顺序是从上往下的,所以要有逻辑的编写命令。
使用上面的命令足够处理一些基本情况了,但是当我们在代码中使用了一些C++17或更高标准的特性后,会发现编译失败,这是因为编译器会使用默认标准(通常为 C++98/GCC 或 C++14/Clang, 可通过输出变量 CMAKE_CXX_STANDARD_DEFAULT 的值查询默认值)来进行编译,导致不存在这些特性。这时,就需要使用 set() 命令来进行相关设置:
zyz 发布于 收录于 算法题目
思路
该题就是给定一个编码后的字符串,然后返回解码后的字符串。
由题可知要处理嵌套的情况,即要先解决内层的$k[encoded_string]$,再解决外层,即后进先出,很适合用栈来解决。而且其结构为$k[encoded_string]$,很适合用双栈来解决,一个为数字栈用来存储重复几次,一个为字符串栈用来存储每一层进入 $[$ 时,之前构造的字符串。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution { public: string decodeString(string s) { string cur_str, pre_str, temp; stack<int> s_n; // 数字栈,存储重复几次 stack<string> s_s; // 字符串栈,存储前面的字符串 for (size_t i = 0; i < s.
zyz 发布于 收录于 算法题目
思路
暴力法,先计算出中位数是第几个元素,然后使用双指针分别指向两个数组的开头元素,然后不断将指向较小元素的指针往后移,直到移到中位数即可,时间复杂度为$O(m + n)$,不符合题目要求。
进一步思考中位数的作用是什么?中位数的作用就是:
将一个集合划分为两个等长的子集,且其中一个子集的元素总是小于另一个子集的元素。
所以,对于这道题来说,我们需要分别在两个数组中找到一条分割线,使得这两条分割线左边的元素个数等于右边的元素个数,且左边集合的最大值小于等于右边集合的最小值。
切割好后,如果两数组长度和为偶数,那么中位数为: $$ median = \frac{max(left\_part) + min(right\_part)}{2} $$
长度和为奇数(为了便于处理,我们将中位数划分给左边部分。当然也可以划分给右边部分),那么中位数为: $$ median = max(left\_part) $$
确定好怎么计算中位数后,我们只需要考虑怎么去寻找这两条切割线了。首先,设数组A的分割线位置为$i$,数组B的分割线位置为$j$(即数组A中下标为$[0, i)$的元素属于其左部分,$[i, lenA)$属于其右部分,数组B同理),根据上面的分析可知: $$ \begin{cases} i + j = m - i + n - j & \text{当 } m+n \text{ 为偶数} \\ i + j = m - i + n - j + 1 & \text{当 } m+n \text{ 为奇数} \end{cases} \Rightarrow \begin{cases} i + j = \frac{m + n}{2} & \text{当 } m+n \text{ 为偶数} \\ i + j = \frac{m + n + 1}{2} & \text{当 } m+n \text{ 为奇数} \end{cases} $$
zyz 发布于 收录于 算法题目
思路
最开始想的是先通过二分来找到最大值位置,确定$right$和$left$的值,再使用一次二分来进行查询。但仔细观察题目发现只需进行一次二分查找算法就可以解决问题了,因为 「该旋转后的数组从中间分开后,左右部分中必定有一个部分是有序的」。
那么我们就可以借助这个有序数组来直接进行二分查找,采用下面的方式来更新$left$和$right$的值:
左边部分有序 target在这个有序区间内,则可以直接抛弃右边部分。反之,抛弃左边部分。 右边部分有序 target在这个有序区间内,则可以直接抛弃左边部分。反之,抛弃右边部分。 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public: int search(vector<int>& nums, int target) { int mid, left = 0; int right = nums.
zyz 发布于 收录于 算法题目
思路
这道题挺简单的,但是一开始想复杂了,故在此记录一下。
题目的意思就是将字符串$s$进行分割,且分割出来的每一个子串都必须时回文串。最简单有效的思路就是依次分割,先分割出第一个子串,在未分割的子串中再分割出第二个子串,……,依次这样下去,直到不存在未分割的子串。而对于每个要分割出来的子串我们都需要遍历其全部形式。
具体来说,设$s = “abcde”$,那么分割出来的第一个子串的形式有$a, ab, abc, abcd, abcde$,其对应的未分割子串依次为$bcde, cde, de, e, null$。所以,直接采用回溯法来做,直接看代码。
PS: 仔细思考会发现存在大量的字符串被反复判断是否是回文串,故可以采用动态划规($dp[i][j]$ 表示$s[i]$~ $s[j]$组成的子串是否是回文串)来提前记录每个子串是否是回文串,加速运行速度。这里就不给出具体代码了,请读者自行编写。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 class Solution { public: vector<vector<string>> ans; vector<string> output; string str; bool judge(const string& s) { int f = 0, b = s.
zyz 发布于 收录于 算法题目
思路
做这道题首先要知道什么是回溯法。
设数组大小为$n$,这个问题可以视为有$n$个排成一行的空格,依次为每个位置选择一个未被选的数来填充。那么可以直接想到一种穷举法,就是从左往右依次往空格中填入数字,全部空格填完就是一种答案。这里我们就可以使用回溯法来完成这一过程。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: vector<vector<int>> ans; vector<int> output; // 存储当前的组合 void backtrace(vector<int>& nums, vector<bool>& used) { // 判断是否已经组合完毕 if (output.size() == nums.size()) { ans.emplace_back(output); return; } // 依次将每个元素放到当前位置 for (size_t i = 0; i < nums.
zyz 发布于 收录于 算法题目
思路
读完题后发现:所谓的路径就是指以某一个结点为根,往左和右各走一边,路径和就是这条路径上的结点值之和。要寻找最大路径和就需要计算每个结点为根时的路径和,选取其中的最大值,这就需要遍历,而且很明显应该使用后序遍历来处理,因为只有当节点的左右子树都处理完了,我们才能计算以当前节点为根的最大路径和是多少,即: $$ 以当前结点为根的最大路径和 = 当前结点值 + 左边的贡献 + 右边的贡献 $$ 那么左右贡献是什么呢?想一想处理完一个结点,要向它的父节点返回什么信息呢?那就是以当前结点为根时的最大单边路径和(因为路径不能分叉),这样才能计算其父节点为根时的最大路径和。但需要注意的时,如果最大单边路径和为负,则需要丢弃,因为其会拉低父节点的最大路径和,父节点是不会考虑连接这条路径的。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int dfs(TreeNode* root, int& ans) { if (!root) { return 0; } int left = dfs(root->left, ans); // 存储左边的贡献 int right = dfs(root->right, ans); // 存储右边的贡献 ans = max(ans, left + right + root->val); // 寻找最大路径和 /** * max({ left, right, 0 }) 是为了找到当前结点的左右最大贡献值(因为只能取一边),如果都为负,则丢弃 * max(max({ left, right, 0 }) + root->val, 0) 是为了判断以当前结点为根时的最大路径和,丢弃负值 * 因为我们要寻找的是最大路径和,负值就会使得路径和变小 */ return max(max({ left, right, 0 }) + root->val, 0); } int maxPathSum(TreeNode* root) { int ans = INT_MIN; dfs(root, ans); return ans; } };