jhhuangのblog

二叉树理论基础 满二叉树 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。 完全二叉树 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层（h从1开始），则该层包含1~2^(h-1)个节点。 优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。 二叉搜索树 前面的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 平衡二叉搜索树 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 C++中map、set、multimap、multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn， unordered_map、unordered_se ...

刷题笔记day13 239.滑动窗口最大值 文章讲解：代码随想录 是否自己做出来通过全部用例：否 遇到的困难/犯的错误 自己构造MyQueue的逻辑没有理顺。 pop()中条件是if不是while，只用删除一次而不是像front中一样需要进行排序所以while循环。 自己写的代码 参照题解写的代码： class Solution { public: class Myqueue { public: void pop(int x) { if (! deq.empty() && x == deq.front()) { deq.pop_front(); } } void push(int x) { while (! deq.empty() && x > deq.back()) { ...

配置环境变量 vsomeip应用启动时以下的环境变量会被读取： VSOMEIP_APPLICATION_NAME，赋予当前程序在vsomeip中使用的名字。vsomeip会通过改名字在配置文件中进行匹配查找。该名字与二进制可执行文件的名字是不一样的。 VSOMEIP_CONFIGURATION，vsomeip默认会使用配置文件/etc/vsomeip.json或者包含配置文件的文件夹/etc/vsomeip。你可以通过该变量使vsomeip使用自定义的配置文件。 VSOMEIP_MANDATORY_CONFIGURATION_FILES，vsomeip允许使用mandatory配置文件来加快应用的启动速度(此时，除负责连接某些外部设别的程序之外，其他所有程序运行时都需要按照mandatory配置文件工作)。默认mandatory配置文件是：vsomeip_std.json，vsomeip_app.json和vsomeip_plc.json。 基础知识： 析构函数： 对象离开其作用域：当一个局部对象的作用域结束时（例如在函数执行结束或代码块结束时），其析构函数会被自动调用。 动态 ...

刷题笔记day11 20.有效的括号 文章讲解：代码随想录 是否自己做出来通过全部用例：是 遇到的困难/犯的错误 这题面试时候遇到过，当时没做出来，事后做过功课，算是回顾了一下。 自己写的代码 class Solution { public: bool isValid(string s) { stack<char> stk; for (auto c : s) { if (c == '(' || c == '[' || c == '{') { if (c == '(' ) { stk.push(')'); } else if (c == '[') { stk.push(']'); } el ...

栈与队列理论基础 deque为缺省指定底层实现的stack和queue的默认底层结构。 STL中栈和队列不被归为容器，而被归为容器适配器。 栈先进后出，队列先进先出。 刷题笔记day10 232.用栈实现队列 文章讲解：代码随想录 是否自己做出来通过全部用例：是 遇到的困难/犯的错误 创建两个stack，相当于倒序排列来获取头部元素。 自己写的代码 class MyQueue { public: stack<int> stin; stack<int> stout; MyQueue() { } void push(int x) { stin.push(x); } int pop() { if (stout.empty()) { while (!stin.empty()) { int out = stin.top(); ...

刷题笔记day9 KMP算法 文章讲解：代码随想录 是否自己做出来通过全部用例：否 看了题解后的收获 大致浏览了一下，以后有时间再回来啃这道题。 字符串总结 文章讲解：代码随想录 看了总结后的收获 回顾双指针法/局部反转+整体反转实现反转字符串操作。 双指针回顾 文章讲解：代码随想录 看了回顾后的收获 通过两个指针在一个for循环下完成两个for循环的工作。 很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。 不要随便用erase()，其时间复杂度为O(n)。 反转链表：只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。 环形链表：使用快慢指针（双指针法），分别定义fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果fast和slow指针在途中相遇，说明这个链表有环。 三数、四数之和：使用双指针法比哈希法更容易。 总结：除了链表一些题目一定要使用双指针，其他题目都是使用双指针来提高效率，一般是将O(n^2)的时间复杂度，降为O(n)。

刷题笔记day8 344.反转字符串 文章讲解：代码随想录 是否自己做出来通过全部用例：是 遇到的困难/犯的错误 这题很简单，双指针法。 自己写的代码 class Solution { public: void reverseString(vector<char>& s) { int left = 0; int right = s.size() - 1; while (right > left) { char temp = s[left]; s[left] = s[right]; s[right] = temp; --right; ++left; } } }; 看了题解后的收获 数组存储在连续空间，反转比链表简单。 541.反转字符串II 文章讲解：代码随想录 是否自己做出来通过全部用例：否 遇到的困难 ...

刷题笔记day7 454.四数相加II 文章讲解：代码随想录 是否自己做出来通过全部用例：否 遇到的困难/犯的错误 没有好思路。 自己写的代码 看了题解后写的代码： class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { int sumAB, sumCD; unordered_map<int, int> umap; for (auto A : nums1) { for (auto B : nums2) { sumAB = A + B; ++umap[sumAB]; }  ...

C/C++编译过程详解 gcc 将C/C++编译成可执行文件的过程 预处理，将#开头的指令，如头文件和宏定义进行文本替换，生成预处理后的代码。 编译：预处理后，gcc将处理后的代码编译成汇编语言代码，生成.s文件。 汇编：生成的汇编代码被汇编器转换为机器码（二进制指令）的目标文件。 链接：最后一步是链接，链接器（ld）将编译生成的目标文件与系统库文件和其他必要的目标文件进行链接。 用gcc将test.c进行编译、汇编、链接 编译 gcc -c test.c -o test.o -c代表只进行除链接外的编译操作 汇编 gcc -S test.c -o test.s -S代表只进行编译为汇编语言的操作，不进行进一步的汇编和链接。 链接 不包含库文件： gcc test.o -o test 调用额外的库文件： gcc object1.o object2.o -L/path/to/library -lexample -o executable 将.o转换为可执行文件。 平时编译的时候如果不需要中间文件（.s，.o）可以使用gcc直接一步到位生成可执行文件： gcc source_file ...

Linux常用命令 mkdir（make directory） 基本语法：mkdir [选项] 目录名 创建一个新目录：mkdir my_directory 递归地创建一个包含多个层级的目录：mkdir -p path/to/my_directory 创建一个具有特定权限模式的目录：mkdir -m 755 my_directory tar（tape archive）归档 基本语法：tar [选项] [归档文件] [文件或目录...] 其中，[选项]用于指定命令的行为，[归档文件]是要创建或操作的归档文件的名称，[文件或目录…]是要添加到归档文件中的文件或目录列表。 常用的tar命令选项包括： -c：创建新的归档文件。 -x：从归档文件中提取文件。 -f：指定归档文件的名称。 -v：显示详细的操作过程。 -z：使用gzip压缩或解压缩归档文件。 -j：使用bzip2压缩或解压缩归档文件。 -C：切换到指定目录后执行操作。 创建一个新的归档文件：tar -cvf archive.tar file1 file2 directory/ 提取一个归档文件：tar -xvf ar ...