- 博客(100)
- 收藏
- 关注
RSS订阅原创 git常用命令
开发流程git clone xxxgit fetchgit checkout {迭代分支}git checkout -b {开发分支} {迭代分支}git add xxxgit commit -m 'xxx'git fetch origin {迭代分支}:tempgit log tempgit merge tempgit push -u origin {开发分支}git branch -d {开发分支} 删除开发分支(-D强行删除)撤销操作git ckeckout -- {fil
2022-03-11 14:37:38
166
转载 十大排序算法总结
零、什么是排序算法0.1、排序定义对一序列对象根据某个关键字进行排序。0.2、排序术语稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度： 一个算法执行所耗费的时间。...
2020-02-13 11:45:23
489
原创 C++虚继承和虚基类详解
1.多继承与菱形继承多继承（Multiple Inheritance）是指从多个直接基类中产生派生类的能力，多继承的派生类继承了所有父类的成员。尽管概念上非常简单，但是多个基类的相互交织可能会带来错综复杂的设计问题，命名冲突就是不可回避的一个。多继承时很容易产生命名冲突，即使我们很小心地将所有类中的成员变量和成员函数都命名为不同的名字，命名冲突依然有可能发生，比如典型的是菱形继承，如下图所示：...
2020-02-04 23:53:37
425
转载 Nginx负载均衡中4层代理和7层代理对比
1.四层代理和七层代理什么意思？这里的层是OSI 7层网络模型，OSI 模型是从上往下的，越底层越接近硬件，越往上越接近软件，这七层模型分别是物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。4层是指传输层的 tcp / udp7层是指应用层，通常是http2.代理原理：4层用的是NAT技术。NAT英文全称是“Network Address Translation”，中...
2020-01-15 22:15:32
2148
1
原创 TCP连接为什么是三次握手？断开为什么是四次挥手？
1.三次握手TCP连接换成四次握手行不行？为什么？换成两次握手行不行？为什么？ 这是我面试时遇到的原题 首先来说一下三次握手，为什么需要三次握手呢？因为TCP提供的是可靠传输服务，因此它在传输之前必须要进行传输的可靠性测试和一些信息的同步，反观UDP就不用这些握手操作。三次握手正好使双方都能测试传输的可靠性，同时也能进行信息同步，三次握手过程如下：那么三次握手到底是在握什么呢？抓包测试一...
2020-01-15 16:58:30
1935
1
转载 成员函数的重载、覆盖与隐藏
成员函数的重载、覆盖（override）与隐藏很容易混淆，C++程序员必须要搞清楚概念，否则错误将防不胜防。重载与覆盖成员函数被重载的特征：相同的范围（在同一个类中）函数名字相同参数不同（参数类型或参数个数）virtual 关键字可有可无const属性也可构成重载，返回值不能构成重载覆盖是指派生类函数覆盖基类的virtual函数，特征是：不同的范围（分别位于派生类与基类）...
2019-12-17 15:23:38
205
转载 C++ 内存对齐原则及作用
struct/class/union内存对齐原则有四个：数据成员对齐规则：结构（struct/class）的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员，比如说是数组，结构体等）的整数倍开始（比如int在32位机为４字节, 则要从４的整数倍地址开始存储），基本类型不包括struct/class/unio...
2019-12-15 12:27:23
1368
转载 网络知识重点总结
五层协议应用层: 为特定的应用传输数据. HTTP, SMTP, DNS传输层: 实现进程到进程之间的通信. TCP/UDP 协议网络层: 实现主机到主机之间的通信. IP, ICMP, ARP, OSPF协议.链路层: 为同一链路的主机提供服务. PPP协议, MAC协议物理层: 在传输媒体上传输比特流, 尽可能为数据链路层屏蔽不同通信设备的差异. RJ45, IEEE802.3协议...
2019-12-09 22:55:51
276
转载 使用enable_shared_from_this的注意事项
在学习muduo网络库源码时，其中大量使用了shared_from_this()，尤其是在连接断开时，后端处理流程比较复杂，其主要原因是要管理TcpConnection的生存期，因此大量使用了shared_from_this()。原文：https://www.cnblogs.com/codingmengmeng/p/9123874.html...
2019-12-09 22:03:12
265
原创 TCP、UDP、ICMP协议抓包详解
这里使用tcpdump对TCP、UDP、ICMP协议进行抓包，并详细解析其内容1.实验源码TCP和UDP抓包时使用以下tcp_echoserver.c、tcp_echoclient.c、udp_echoserver.c和udp_echoclient.c进行实验tcp_echoserver.c#include <arpa/inet.h>#include <signal.h...
2019-11-29 18:21:31
2980
转载 g++链接动态库和静态库问题
在用g++编译链接C++程序时，当我们其中有包含第三方库的时候，需要我们手动的指定我们需要的库文件。库文件有两种，一种为动态库，一种为静态库，具体的区别很简单，通俗的讲，动态库是在运行时动态加载，静态库是在链接的时候直接把库文件复制到程序中，运行的时候不再依赖库文件。例如我们在程序中用到libtiff库和libxml2库:1.动态库的链接g++ *.cpp -o main -I./kufil...
2019-11-22 17:11:20
1492
原创 leetcode 146——LRU缓存机制
题目描述：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近...
2019-11-18 08:42:15
171
转载 leetcode 76——最小覆盖子串
题目描述：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。示例：输入: S = "ADOBECODEBANC", T = "ABC"输出: "BANC"说明：如果 S 中不存这样的子串，则返回空字符串 “”。如果 S 中存在这样的子串，我们保证它是唯一的答案。解题思路：题目不难理解，就是说要在 S(source) 中找到包含 T(...
2019-11-16 11:03:17
383
原创 leetcode 494——目标和
题目描述：给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例 :注意:数组非空，且长度不会超过20。初始的数组的和不会超过1000。保证返回的最终结果能被32位整数存下。解题思路：原问题等...
2019-11-16 09:05:46
124
原创 leetcode 292——Nim游戏
Nim游戏题目描述：你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。示例:解题思路：在我赢的情况下，最后一次一定是我拿，那么对手给我留下的一定只能是1~3个石头，那么怎样才能保证对手最多留下3个...
2019-11-15 09:31:33
277
原创 leetcode 560——和为k的子数组
题目描述：给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :说明：数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。解题思路：扫描一遍数组, 对每个元素累加到sum，同时寻找map中是否有 sum-k 的元素，如果有则将答案加上 sum-k 的个数，最...
2019-11-13 09:08:32
190
原创 leetcode 416——分割等和子数组
题目描述给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意:每个数组中的元素不会超过 100数组的大小不会超过 200示例 1:示例 2:解题思路：这道题是0-1背包问题 我用到了动态规划中备忘录的方法 通过记录每种子集的情况来解题(其实就是枚举了所有的情况 不过复杂度没有那么高)首先进行两次特判 即原来数组长度为0,1,2...
2019-11-11 08:44:51
677
转载 【动态规划】01背包问题
问题描述有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？为方便讲解和理解，下面讲述的例子均先用具体的数字代入，例如：number＝4，capacity＝8i（物品编号）1234w（体积）2345v（价值）3456总体思路根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满...
2019-11-09 14:05:46
293
原创 leetcode 662——二叉树的最大宽度
题目描述：给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。示例 1:示例 3:解题思路：如果是求树中每一层非空节点的最大宽度那么很简单，但这里要算上中间的空节点，因此...
2019-11-05 09:26:47
397
原创 leetcode 449——序列化和反序列化二叉搜索树
题目描述：序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。编码的字符串应尽可能紧凑。注意：不要使用类成员/全局/静态变...
2019-10-31 10:14:42
185
原创 leetcode 501——二叉搜索树中的众数
题目描述：给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。假定 BST 有如下定义：结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树示例：给定 BST [1,null,2,2]解题思路：最简单的方式是中序遍历二叉树，将结果保存到一个数组中，然后转化为求这个数组中的众...
2019-10-30 11:44:56
140
原创 leetcode 437——路径总和III
题目描述： 给定一个二叉树，它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。示例：解题思路：首先我们想一下，如果是求 “从根节点出发，求根节点到任意节点和为sum...
2019-10-30 10:26:37
171
原创 leetcode 124——二叉树中的最大路径和
题目描述：给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例1：示例2：输出：48解题思路：在示例1中，我们感觉好像就是求子树的最大值，但从示例2中我们可以看出，当左右子树和都大于0的时候，我们只能选择左右子树中和最大的子树去组成更大的子树，于是我们形成以下思路：以后序遍历整棵...
2019-10-29 15:26:13
192
原创 leetcode 382——链表中的随机节点（蓄水池抽样法）
题目描述：给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？解题思路：这道题最简单的解法应该是用一个vector保存所有节点的值，然后在vector中求取随机值就相当容易了，但如进阶条件所说，当链表十分大的时候时间复杂度和空间复杂度都是O(n).这时我们就要用到蓄水池...
2019-10-26 11:13:47
175
原创 leetcode 378——有序矩阵中第k小的数
题目描述：给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。示例:matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15]],k = 8,返回 13。解释：排序后的数组为{1, 5, 9, 10, 11, 12, 13, 13, 1...
2019-10-26 09:33:38
556
原创 C++hash_map实现
hash_map除了不具备map自动排序的功能以外，具有map所有的特性。hash_map使用hashtable作为底层容器，hashtable提供了所有hash_map需要的操作，hash_map不允许键值重复，使用hashtable的insert_unique来插入元素代码实现：https://github.com/inmail/mySTL/blob/master/mySTL/19stl_h...
2019-10-17 10:43:09
278
原创 C++hash_set实现
运用set，为的是能够快速搜寻元素，这一点不论是rb-tree和hashtable都能够达到目的，但前者有自动排序功能而hashtable没有。hash_set使用hashtable作为底层容器，hashtable提供了所有hash_set需要的操作，hash_set不允许键值重复，使用hashtable的insert_unique来插入元素代码实现：https://github.com/inm...
2019-10-17 10:42:00
1010
原创 C++hashtable实现
二叉搜索树具有对数平均时间的表现，但这样的表现是构造在一个假设上的：输入的数据具有足够的随机性，对于hashtable，它在插入、删除、搜寻等操作上也具有“常数平均时间”的表现，而且这种次表现是以统计为基础，不需要依赖数据输入的随机性。hashtable可提供对任何有名项的存取操作和删除操作，所以hashtable也可以被看做一种字典结构。相较于rb-tree，当hashtable负载因子过大时，...
2019-10-17 10:40:46
381
原创 C++map的实现
map的特性是：所有元素都会根据元素的键值被自动排序，map的所有元素都是pair，同时拥有实值（value）和键值（key），pair的第一元素被视为键值，第二元素被视为实值，通常通过仿函数select提取出节点的键值进行比较，我们能修改节点的实值但不能修改其键值，对其他元素操作时，其之前和之后的迭代器也都不回失效。map使用rb-tree作为底层容器，rb-tree提供了所有map需要的操作，...
2019-10-17 10:39:18
2914
原创 C++set的实现
set提供快速的查找功能，其特性是：所有元素都会根据元素的键值自动排序，对set执行添加或删除操作时，操作之前的所有迭代器和操作之后的所有迭代器都依然有效。set使用rb-tree作为底层容器，rb-tree提供了所有set需要的操作，set不允许键值重复，使用rb-tree的insert_unique来插入元素代码实现：https://github.com/inmail/mySTL/blob/...
2019-10-17 10:37:02
1859
原创 C++红黑树实现
红黑树是一种运用及广的自平衡二叉搜索树，可提供对数时间的插入和访问操作，其平衡性不如AVL树高，因此其维护平衡性的成本也不如AVL树高，相当于在平衡性和效率之间取了折中。这里主要实现了红黑树的数据结构、旋转算法、插入算法、删除算法等，其中删除算法是最难但又必须使用的，对于删除过程不了解的同学请查看https://blog.csdn.net/qq_40843865/article/details/1...
2019-10-17 10:34:22
180
原创 红黑树删除节点——这一篇就够了
红黑树红黑树常用的操作是插入、删除和查找，并且它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保，对于红黑树的概念、性质、插入、查找和旋转等这里不再多讲，不了解的请点击wikipedia rb-tree，这里重点讲一下红黑树的删除，这是红黑树中最难但又必须使用的操作。红黑树的5条性质:节点是红色或黑色。根是黑色。所有叶子都是黑色（叶子是NIL节点）。每个红色节点的父子节点都...
2019-10-11 20:58:59
11711
24
原创 leetcode 260——只出现一次的数组III
题目描述： 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。示例： 输入: [1,2,1,3,2,5] 输出: [3,5]注意：结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？解题思路： 在leetcode136 只出...
2019-10-11 10:40:26
156
原创 leetcode 238——除自身以外数组的乘积
题目：给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例: 输入: [1,2,3,4] 输出: [24,12,8,6]说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。解题思路：两遍dp法dp1[i]保存[0,i)内元素的乘积，dp2[i...
2019-10-10 09:48:24
94
原创 leetcode 222——完全二叉树的节点个数
最简单的办法就是递归，代码如下：class Solution {public: int countNodes(TreeNode* root) { if (!root) return 0; return 1 + countNodes(root->left) + countNodes(root->right); }...
2019-10-09 09:31:31
102
原创 leetcode 213——打家劫舍II
这个题和打家劫舍I思路相同，只不过这里分两种情况：盗第一间和不盗第一间（至于最后一间根据dp进行选择）进行dp即可。//思路和198题类似，只不过这里分两种情况讨论：盗第一间和不盗第一间class Solution {public: int rob(vector<int>& nums) { if (nums.empty()) ...
2019-10-09 00:29:02
94
原创 leetcode 198——打家劫舍
这是一个简单题，思路为动态规划根据dp方程 dp[i] = max(dp[i-2]+nums[i], dp[i-1]) 进行计算即可//思路为动态规划：dp 方程 dp[i] = max(dp[i-2]+nums[i], dp[i-1])class Solution {public: int rob(vector<int>& nums) { i...
2019-10-09 00:24:52
103
原创 高性能定时器——时间轮
在上一篇基于升序链表的定时器踢掉空闲连接中，添加定时器的时间复杂度为O(n)，删除定时器的时间复杂度为O(1)，执行定时任务的时间复杂度为O(1)，可以看出添加定时器的执行效率很低，下面讨论的时间轮定时器管理工具可以有效的解决这个问题。时间轮示例： 在上图所示的时间轮内，指针(实线)指向轮子上的一个槽(slot)。 它以恒定的速度顺时针转动，每转动一步就指向下一个槽(虚线指针指向的槽...
2019-10-08 17:18:14
777
2
原创 C++ slist实现
slist和list最大的区别在于，前者的迭代器属于单向的ForwardIterator，而后者是双向迭代器BidirectionalIterator。因此slist的功能就受到很多限制，但slist消耗的空间更少。和list一样，它们的插入、移除、接合等操作不会造成原有的迭代器失效。注意：根据STL的习惯，插入操作会将元素插入到迭代器所指位置之前而不是之后，但slist没办法快速找到其前一个节...
2019-10-08 16:24:47
1342
原创 C++ priority_queue实现
优先级队列的实现，这是一个配接器而不是一个容器，它默认以vector为底层容器，通过heap调用相关算法，维持底层容器中的元素保持堆的特性代码实现：https://github.com/inmail/mySTL/blob/master/mySTL/9stl_priority_queue.h...
2019-10-08 14:49:28
537
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人