- 博客(570)
- 收藏
- 关注
RSS订阅原创 树形dp 打家劫舍Ⅲ+监控二叉树
树形dp，递归调用栈把中间计算结果暂存了，子调用的结果交给父调用，它就销毁了，不需要记忆化。解题时确定每个节点的所有状态，并从子调用逐个返回。
2022-09-18 16:17:37
193
1
原创 python crawler - selenium + xpath爬取用户详情页信息 + 分类存储excel
爬取网站地址明显看到是控制具体页数的，得到每页的信息；但是动态加载数据的，没法直接抓网页采用selenium + 枚举id的方式，枚举所有用户详情页（不得已最后根据是否售出存到对应sheet中爬取网站链接这个很简单，没有js动态加载，完全能通过接口收到所有想要的角色信息，直接访问用户详情页都省了。直接解析返回数据json：...
2022-07-12 17:59:58
742
原创 Redis设计与实现 -读书笔记
2. 简单动态字符串（SDS）定义：struct sdshdr { int len; // buf中已使用字节数量（不包括末尾'\0'） int free; // 未使用字节 char buf[]; // 字节数组，用于保存字符串};被用于保存数据库中的字符串值，或用作缓冲区。与C字符串区别：常数复杂度获取字符串长度；缓冲区不会溢出可用空间不够 会扩展空间减少修改字符串的内存重分配次数空间预分配（free，不够就分配min(1MB, len)）惰性空间释放（收
2022-01-22 21:10:05
618
原创 康托展开及逆康托展开 + leetcode60. 排列序列
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。康托展开：X=an(n−1)!+an−1(n−2)!+...+a1∗0!X = a_n(n-1)! + a_{n-1}(n-2)! +... + a_1*0!X=an(n−1)!+an−1(n−2)!+...+a1∗0!其中，ai为整数，且0≤ai<i,1≤i≤n其中，a_i为整数，且0 \leq a_i \lt i,1 \leq i \leq.
2022-01-07 15:37:20
283
原创 24点游戏 输出所有表达式（括号精简化 但 没对表达式去重）
leetcode679. 24 点游戏class Solution {public: static constexpr double eps = 1e-6; //const string sign[4] = {"+", "-", "*", "/"}; bool judgePoint24(vector<int>& cards) { vector<double>tmp; vector&
2021-12-14 17:27:43
2577
原创 剪绳子（整数拆分使最大化乘积）问题 数学+dp解法
问题描述：将一段绳子剪成aaa段，长度分别为n1,n2,n3...nan_1, n_2, n_3 ... n_an1,n2,n3...na求max(n1∗n2∗n3∗na)max(n_1* n_2 * n_3 * n_a)max(n1∗n2∗n3∗na) , 其中，a>=2a >= 2a>=2动态规划解法dp[i] : 长度为 i 绳子的拆分得到的最大乘积为dp[i]假设第一次剪断后两段绳子分别为j 、 i-j ， 有2种情况：Ⅰ 不剪了： dp[i]
2021-12-13 15:23:01
508
原创 多线程经典哲学家就餐问题 C++11 3种实现
leetcode1226.哲学家就餐问题核心是 避免死锁同时拿起左右叉子class DiningPhilosophers {public: DiningPhilosophers() { } void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()>
2021-12-09 16:56:58
1337
原创 leetcode887. 鸡蛋掉落 谷歌经典面试题的一般情况
leetcode887题意：用k个蛋测试n层楼的f值，求最坏情况（所有蛋碎蛋不碎的情况中）的最小测试次数。f值表示在f及以下层蛋扔下去都不会碎，之上都会碎。一、一个蛋的情况只能从1楼逐层往上尝试，结果为楼层数。二、2个蛋的情况（谷歌面试题的形式）以100层楼为例：将楼层分为10等分，1，10，20，30…100A操作是测试1, 10, 20, 30… 100 扔下，蛋是否会碎掉B操作是从x1,x2,x3…x9逐层测试蛋是否碎当A操作不碎，一直进行A；当A操作在碎掉，就在之前的9层逐层尝试
2021-12-02 15:45:54
407
原创 数据流中的中位数 自建堆
LeetCode295. 数据流的中位数主要思路是 一个大顶堆，一个小顶堆。大顶堆内元素都比小顶堆小，预设小顶堆元素数和大顶堆相等或者小顶堆元素数多1个。每次添加元素：先根据个数判断添加到maxn还是minu；添加到大顶堆就比较添加数与小顶堆堆顶数大小；添加到小顶堆就比较添加数与大顶堆堆顶数大小，以此决定真正要添加的数。另外就是练习一下自建堆的操作，使用模板减少冗余代码。// 1. 自建堆操作template<class Compare>class HEAP {publi
2021-11-12 21:53:24
241
原创 环形链表及其变形 Floyd判圈 +快慢指针
环形链表环形链表Ⅱ**思路：**利用快慢指针从head处往后走，相遇时两指针分别从head及相遇点单步向后走，相遇处即为环入口。证明：因为快慢指针的步差为1，慢指针相对静止，快指针步长1追赶，因此快慢指针必定在环内相遇。设链表外部长度a,环(长度b+c)入口到相遇点的长度b 环剩余长度c快指针速度是慢指针的两倍：故相遇时路程关系为2倍：a + ( b + c ) * n + b == 2 * (a + b)=》a = (b + c) * (n - 1) + c因此从相遇点和hea.
2021-11-09 16:24:46
397
原创 html 标签内部onclick调用原理 及指定匿名函数
onclick函数内部包含着指定给onclick的函数，所以当触发了onclick事件的时候，onclick函数就执行，这时候因为fn在onclick函数内部，才得以执行。因此指定要加括号。function onclick(event) { fn();}不加括号执行的话就是：function onclick(event) { fn;}因此不会执行fn；当写出匿名函数时，也要加上括号才会被执行。var pre_str = '<a class="Warning_Table" οn
2021-11-08 20:53:25
2371
原创 leetcode72 + NC35 最小编辑代价 最小编辑距离 及其 空间优化
编辑距离题意：利用三种操作，将word1变为word2的最小步数。思路：设dp[i][j] 为将word1前i个字符变为word2前j个字符所需的最小步数。三种操作：插入：前i个和前j-1个编辑次数+1 ->dp[i][j-1] + 1删除：前i-1个和前j个的编辑次数+1 ->dp[i-1][j] + 1替换：前i-1个和前j-1个的编辑次数+1 -> dp[i-1][j-1] + 1class Solution {public: int minDistance
2021-10-19 11:30:00
189
原创 蓄水池采样算法
问题场景：在未知长度的序列中随机选取（序列每个元素被选中概率相同）K个元素蓄水池采样算法过程：先选取前K个元素；从K+1个元素开始，等概率（KN\frac{K}{N}NK , N为当前已读取元素个数）决定该元素是否选择以和已选择的K个元素替换。证明：1.读前K行时，每个元素被选中概率均为1；2.假设读到第n-1个，每个元素选中概率均为Kn−1\frac{K}{n-1}n−1K ；3.当读到第n个元素时，选择第n个元素的概率是Kn\frac{K}{n}nK （n个元素选K个，选中
2021-09-16 16:51:31
203
原创 设计数据结构小专题
设计数据结构 - leetbook栈&队列主要思想就是两个栈/队列 互相倒腾，何时倒腾决定了均摊时间复杂度能否达到O(1)栈实现队列两个栈：in、out栈，in负责放入数据，out负责读出。当out为空时，将in的数据读出放到out中。class MyQueue {public: /** Initialize your data structure here. */ MyQueue() { } void utils() { whi
2021-07-14 16:01:07
103
1
原创 gdb调试常用命令总结
gdb调试常用命令总结：回车 默认将最近的命令执行一遍在调试程序加上调试符号信息：加参数-g, 作用是加上了可执行程序和源码之间的映射关系如果之后源码位置改变，可以通过dir命令更改源码存放目录，以重新设置映射关系（可指定多个路径，:隔开）1.启动gdb调试gdb filename : 启动未启动程序进行调试（需要run）gdb attach pid：对已经启动的程序调试， detach让gdb调试器与程序分离gdb corename: 调试core文件ulimit -c查看cor
2021-07-04 21:00:48
3549
原创 背包问题复习总结
关于初始化// dp[V] : 背包容量V获得的最大价值dp[i] = 0 => 背包容量最大Vdp[i] = -inf => 背包要求装满01背包dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]);例题 #include <bits/stdc++.h> using namespace std; int main() { int n, V; int c, v, w; cin >
2021-06-10 15:43:06
154
原创 实现一个操作系统 (1) - 过程记录blog
MBR编写MBR这个程序是独立于操作系统的，能够直接在裸机上运行.MBR 的大小必须是512字节，这是为了保证0x55 和0xaa这两个魔数恰好出现在该扇区的最后两个字节处，即第510 字节处和第511 字节处，这是按起始偏移为0 算起的.0x10中断是最为强大的BIOS 中断了，调用的方法是把功能号送入寄存器，其他参数按照BIOS 中断手册的要求放在适当的寄存器中，随后执行int 0x10 即可。; 在屏幕上打印字符串“ 1 MBR ”， 背景色为黑色，前景色为绿色。;BIOS由jmp 0
2021-06-04 16:48:36
556
2
原创 C++编译链接模型精要 - 个人笔记
C语言编译器采用单遍编译的方法，只能根据目前看到的代码作出决策；C++为了兼容，也继承了单遍编译，但由于有前向声明这样的存在（函数声明相当于前向声明，还有class的前向声明减少编译时的依赖），不可能完全是单遍编译。C不支持函数重载（从其目标文件中可以看到，其中生成的函数名字不带参数）。C语言采取的是，传统的one-pass链接器, 使用时要让越基础的库放在后面，保证每个未决符号都能在后面出现的库中找到。这样的顺序使得链接器只需要记住尚未定义的符号，若反过来则需要更多的内存（链接器不知道哪些符号
2021-05-17 16:16:53
252
原创 muduo源码学习笔记
1.大并发服务器架构介绍服务器性能杀手：数据拷贝：缓存环境切换：理性创建线程)该不该用多线程，单线程好还是多线程好，单核服务器（采用状态机编程，效率最佳)内存分配：内存池锁竞争...
2021-04-24 20:39:11
144
原创 组合数学 - 计算母函数对应项系数实现
计算诸如下列形式的母函数对应指数项的系数：G(x) = (1+x+x^2+x^3...)*(1+x^2+x^4+x^6....)*(1+x^3+x^6+x^9.....)*(1+x^4+x^8+x^12.....)*...就是模拟每个表达式的乘法过程。// tmp存储每乘完一个表达式的结果，赋给res// 整数拆分样例code，将tar拆分成nums所包含数字的做法class Solution {public: typedef long long LL; int solve(ve
2021-04-24 15:34:30
345
原创 enum局限性 及 C++11 enum class(struct)
enum局限性 及 C++11enum class(struct)enum存在向整形的隐式转换，可能造成整形提升问题（一个char类型、short类型、位域（不论是有符号还是无符号）或是一个枚举体，都可以在int或是unsinged int可以使用的表达式中使用。）可以将enum封装在类内解决enum无法指定底层使用的数据类型（根据编译器不同而不同，会造成移植性问题）enum作用域不局限在{}内，不同enum想要有同名成员，需要放在不同命名空间新的enum class NAME : T
2021-03-11 18:27:27
195
原创 基本计算器（‘(‘ ‘)‘ ‘+‘ ‘-‘ ‘*‘ ‘/ ‘ 正负数）思路及通用实现整理
- 使用双栈计算表达式结果（存符号、数字） - 空格: 直接忽略 - ( : 入栈 - ) : 计算结果直到遇到 ( - 数字： 累计记录当前数字 - 栈顶运算符优先级高于/同等 当前运算符，就一直弹出 - 注意事项 - “-2 + 1”，先在nums栈加上0，防止第一个就是 "-" class Solution {public: // 这里最初是预防(-2+1)这种情况的，但在nums栈先加0，(-2+1)和-2+1似乎是没区别了 void init(stri.
2021-03-11 11:33:23
608
原创 more effective C++ 学习总结
1.区别pointers和references引用总是指向最初获得的对象（必须被初始化）当需要指向某个东西，且绝不会改变其指向 或者 实现一个操作符而其语法需求无法由pointers完成时选择references，其他时候，选择pointers.如 vector 的 operator[]返回references , 使用时可以v[0] = 1; , 若返回指针，则需要比较奇怪的形式：*v[0] = 1....
2021-02-24 22:42:29
481
原创 Universal References in C++11 ( auto&&, T&&
universal reference：If a variable or parameter is declared to have type T&& for some deduced type T, that variable or parameter is a universal reference.deduced type TTemplate parameter、auto declaration, ect.Widget&& var1 = so..
2021-01-30 19:02:39
196
原创 左值、右值、右值引用、移动、引用坍缩和完美转发
Reference此篇基本是上述内容备份。标准里关于值的分类：一个 lvalue是通常可以放在等号左边的表达式，左值(左值 lvalue 是有标识符、可以取地址的表达式.在函数调用时，左值可以绑定到左值引用的参数，如T&。一个常量只能绑定到常左值引用，如 const T&。变量、函数或数据成员的名字返回左值引用的表达式，如 ++x、x = 1、cout << ’ '(x = 1 和 ++x 返回的都是对 x 的 int&。x++ 则返回的是 i
2021-01-24 20:33:04
696
原创 理解并简单实现智能指针（暂不考虑多线程安全
智能指针就是RAII资源管理的自然体现。首先，一个简易的auto_ptr，包含初始化、拷贝、赋值等基本操作。#include <iostream>using namespace std;class shape {public: virtual ~shape() {}};class circle : public shape {public: ~circle() { puts("~circle()"); }};template<typename T>cla.
2021-01-24 15:53:03
166
1
原创 effective C++ 学习总结
effective C++ 43条，三种访问模板基类中，使用this->访问的方法template<typename T>class A{ public: void f() { cout << "A::f()" << endl; }}template<typename T>class B:public A<T>{ public: void f() { .
2021-01-23 10:01:22
484
原创 TCP/IP网络编程 - 自用理解笔记（续）
CSDN一篇文章内容多了一丢丢竟然会很卡…新开一篇…12 I/O复用构建并发服务器时，只要客户端请求就会创建新进程。这样的方式需要极大代价（大量运算和内存空间，IPC也会增加程序编写难度）。I/O复用实现在不创建进程的同时向多个客户端提供服务。int select(int maxfd, fd_set *readset, fd_set *writeset, fd_set *exceptset, const struct timeval *timeout)将多个文件描述符集中在一起统一监视。（
2021-01-11 17:14:52
232
原创 linux网络编程 - gethostbyname() + gethostbyaddr() + 使用 gethostbyaddr() 返回为空
struct hostent * gethostbyaddr(const char *addr, socklen_t len, int family);gethostbyaddr.c采用这种方法获取信息，需要将不成功的 ip与对应域名添加到hosts文件,否则会失败（如下百度ip失败，本地成功）将百度ip与域名对应关系添加到/etc/hosts中，就可以成功了。没找到源码，不知道是怎么实现的，为什么已经有了ip，程序还会去hosts文件内查询呢？不过似乎不成功的原因是目标ip不支持这种查询方
2021-01-08 17:59:56
744
2
原创 TCP/IP网络编程 - 自用理解笔记
服务器端的clnt_sock负责数据交换，serv_sock负责与客户端建立连接。具体的read() , write()执行过程。回声服务器端echo_server.c#include <stdio.h>#include <stdlib.h>#include <string.h>#include <unistd.h>#include <arpa/inet.h>#include <sys/socket.h>c
2020-12-30 17:05:33
263
原创 STL源码剖析 - sort() ， __final_insertion_sort 解析
只接受RandomAccess Iterator , list 和 slist使用自己提供的member functions sort()STL - Sort():数据量大时采用Quick Sort 分段递归排序；分段后的数据量小于某个门槛，为避免递归调用的额外负荷，改用Insertion Sort;若递归层次过深，改用Heap Sort实现如下：template <class RandomAccessIterator>inline void sort(RandomAcce.
2020-11-28 17:14:19
289
原创 向控制台输出中文乱码 + 向文件写入中文乱码解决方案
解决编码问题的关键就是统一编码。字符编码介绍系列场景一：向控制台输出中文乱码cpp文件编码utf-8,控制台编码GBKcout << "咯咯哒" << endl;输出乱码。此时，解决思路是统一控制台和文件编码。1. 只需要将cpp文件的编码改为以下任一种即可；2. 更改控制台编码为utf-8.在控制台每次都chcp 65001或者在cpp开始system("chcp 65001");场景二：cpp文件是utf-8编码，读写的文件格式是utf-8,
2020-11-24 22:38:44
714
原创 C语言结构体与文件之间的读写 及 结构体不一致导致的读写失败
A文件 - > 写入结构体内容到文件#include <bits/stdc++.h>using namespace std ;// COOtypedef struct { int r , c ; char s[100] ; }Triple ;typedef struct { Triple data[100] ; // 大小100 int mn , nm , tu ; }TriSprMatrix ;TriSprMatrix a ;Triple b ;int
2020-11-17 23:58:27
617
原创 STL源码剖析 - 关联式容器自用笔记
一般，关联式容器的内部结构是一个平衡二叉树，有良好的搜寻效率。AVL-tree、RB-tree、AA-tree等特殊结构都可实现出平衡二叉搜索树。它们比一般的平衡二叉树复杂，故插入节点和删除节点的平均时间比较长，但可以避免极难应付的最坏（高度不平衡）情况。其元素访问时间较少（一般节省25%左右）。...
2020-11-14 11:31:59
139
原创 STL源码剖析 - 序列式容器自用笔记
vectorarray是静态空间，没有ctor（构造函数）、dtor（析构函数）。vector是动态连续线性空间，以普通指针为迭代器，其实现关键在于对大小的控制以及重新配置时数据移动效率扩充空间 :配置新空间数据移动释放旧空间空间配置策略：增加新元素时，若超过当前容量，则容量capacity会扩充至两倍，若仍不足，则扩张至足够大的容量。（原大小是0，则配置1个元素大小）。insert_aux() : 同时被push_back(), insert()调用，故其采取以下策略：还有
2020-11-10 21:24:25
163
原创 STL源码 - traits技术
iterator traitsiterator必须提供的5种相关类型：iterator_category：iterator的移动性质value_type：iterator所指元素本身类型difference_type：两个iterator之间的距离可以用何种类型表示pointer：reference：算法与迭代器的关系：如下图，算法通过迭代器获取这几种相关类型信息整个的流程如下图，算法对所需类型信息提问，迭代器回答。但对于原生指针（相当于退化的iterator），其无
2020-11-07 15:02:36
141
原创 使用 size_t 类型的意义
使用size_t可能会提高代码的可移植性、有效性或者可读性。在32位系统中，size_t是unsigned int（4字节）在64位系统中，size_t是unsigned long long（8字节）在标准C库中的许多函数使用的参数或者返回值都是表示的用字节表示的对象大小。如:// 按字节拷贝，从s2拷贝n个字节到s1地址void *memcpy( void *s1 , const void *s2 , size_t n)第三个参数若采用unsigned int , 在16..
2020-11-06 20:15:43
676
原创 AC自动机字符串匹配百万模式串 获取数量及位置 结构体排序交换指针
这是个计算机应用编程课的作业，对于小数据其实很简单，就是AC自动机模板题目。但作业要求是1G的主串（汉字+字母+数字），120w+的模式串，得到每个模式串的出现次数及位置，并将结果排序。因为数据问题就会出现不好处理的点，如结构体排序效率，汉字编码等的处理等细节问题。感觉写完对面向对象编程以及指针等的处理更加了解，对我这种基础不牢固的人还是有些帮助，因此记录下来。主要部分：AC自动机+手写结构体的堆排序+手写数组实现的循环队列+汉字utf-8编码大致逻辑：读取字符串时采用逐行读取，编码utf-8
2020-11-06 16:42:16
250
原创 二进制读取文件（中英数字字符串）并编码十六进制，最后写入文件
//读size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream) //写size_t fwrite(void *ptr, size_t size, size_t nmemb, FILE *stream) #include <bits/stdc++.h>using namespace std ;// 例程,二进制读取文件（中英数字字符串）并编码十六进制，最后写入文件int main() { const ch
2020-11-06 16:18:58
285
原创 值传递 引用传递 、内置类型的值传递效率往往高于引用传递
对于一般的类对象而言，值传递方式会调用多次构造函数和析构函数。而引用传递的方式则回避了所有构造和析构动作。当采用值传递的方法时，可能会造成切割问题。如将子类对象值传递到基类类型中去，子类特有的部分将被切割掉。引用传递，真正传递的是指针。当对内置类型的值进行引用传递，其相对于值传递多了一次寻址操作，最终还要通过指针（引用传递过来的）访问内存中的值。如果在函数中多次用到这个内置类型变量，可能就多次访问寄存器(按值传递)，或者多次访问内存（按引用传递）。在这种情况下按值传递更优？因为..
2020-10-27 17:19:06
762
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人