- 博客(247)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 C+17 新特性
#include <any>#include <iostream>#include <string>#include <vector>#include <algorithm> using namespace std; struct Point { int x; int y; }; Point func() { return {1, 2}; } template <typename ..
2022-05-25 22:03:10
296
原创 Python函数与方法
函数类似于C++得全局方法方法分为类方法（C++的静态成员方法），实例方法（C++的非静态成员方法），静态方法（形式上更像嵌入在类中的全局方法）参考链接Difference between staticmethod and classmethod...
2021-04-27 15:14:13
212
原创 leetcode90. 子集 II
题目给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: [1,2,2]输出:[ [2], [1], [1,2,2], [2,2], [1,2], []]思路1.类似leetcode78. 子集,但要去重2.先排序3.当连续重复数字时， 允许1 1 1 0 0,不允许 1 0 1 0 1或者1 0 0 1 1，即前一个重复数字未选取时，当前数字选取会造成重复实现// 去重：当连续重复数字
2021-01-10 23:34:30
244
原创 leetcode99. 恢复二叉搜索树
题目给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？示例 1：输入：root = [1,3,null,null,2]输出：[3,1,null,null,2]解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。示例 2：输入：root = [3,1,4,null,null,2]输出：[2,1,4,nu
2021-01-10 23:28:04
180
1
原创 leetcode236. 二叉树的最近公共祖先
题目给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]示例 1:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节
2021-01-10 23:09:28
106
原创 leetcode124. 二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1：输入：[1,2,3] 1 / \ 2 3输出：6示例2:输入：[-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7输出：42思路dfs的过程中会经历每个父节点，并计算出经过该父节点的最
2021-01-10 17:36:22
119
原创 leetcode152. 乘积最大子数组
题目给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。思路1.f(n)与f(n - 1)有关，且存在重复计算，考虑动态规划2.这里主要比较f(n - 1)与包括第n个元素在内的子数组的乘积， 如果每次遍历相乘会超
2021-01-10 17:00:21
99
原创 leetcode95. 不同的二叉搜索树 II
题目给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。示例：输入：3输出：[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]解释：以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2
2021-01-10 16:04:25
88
原创 leetcode96. 不同的二叉搜索树
题目给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2
2021-01-10 15:46:20
92
原创 2进制数字改变某位值
第n位置1val |= (1 << n);第n位置0val &= ~(1 << n);查看第n位是否是1if (((val >> n) & 1) == 1) //b位是1else //b位不是1将第n位1变0, 或0变1val ^= (1 << n);
2021-01-07 00:14:11
967
原创 this指针
this 指针是一个隐含于每一个非静态成员函数中的特殊指针，它指向调用该成员函数的那个对象。当对一个对象调用成员函数时，编译程序先将对象的地址赋给 this 指针，然后调用成员函数，每次成员函数存取数据成员时，都隐式使用this 指针。this 并不是一个常规变量，而是个右值，所以不能取得 this 的地址（不能 &this）...
2021-01-05 21:25:27
151
原创 Ptmalloc与Tcmalloc浅析
Ptmalloc内存分配内存优化总结:ptmalloc、tcmalloc和jemalloc内存释放所有调用delete释放的内存，并不是立即调用brk(sbrk)归还给操作系统，而是先将这个内存块挂在free-list(bins)里面，然后进行内存归并(可选操作，相邻的可用内存块合并为更大的可用内存块)，并检查是否达到malloc_trim的threshhold，如果达到了，则调用malloc_trim归还部分可用内存给操作系统。glibc中，设置了默认进行malloc_trim的threshh
2020-12-29 01:42:17
1336
1
原创 虚拟内存和物理内存
概念物理内存就是指内存条，虚拟内存是逻辑概念。每个进程都有自己独立的虚拟地址空间，32位有4G大小，64位有256T大小。一个进程同一时刻不可能所有变量数据都会访问到，只需要在访问某部分数据时，把这一块虚拟内存映射到物理内存，其他没有实际访问过的虚拟地址空间并不会占用到物理内存，这样对物理内存的消耗就大大减少了 。虚拟内存划分从虚拟地址的角度来看，内存空间如下划分：32位系统最高的1G空间保留给内核使用，多个进程共享；64位系统最高的128T空间保留给内核使用并且不被进程共享栈，栈向低地址方向
2020-12-28 23:56:14
991
原创 常用lock-free编程
RCURCU 的关键思想有两个：1）COW,复制后更新；2）延迟回收内存。典型的RCU更新时序如下:复制：将需要更新的数据复制到新内存地址；更新：更新复制数据，这时候操作的新的内存地址；替换：使用新内存地址指针替换旧数据内存地址指针(内存地址替换操作是原子的)，此后原有读者访问旧数据，新的读者将访问新数据;等待: 所有访问旧数据的读者进入静默期(QS)，说明之前的reader都离开了临界区, 这个时候访问旧数据完成；回收：当所有的CPU都至少经历过一次QS后, 意味着宽限期的结束，因此就进行回
2020-12-21 23:27:05
698
原创 leetcode451. 根据字符出现频率排序
题目给定一个字符串，请将字符串里的字符按照出现的频率降序排列。示例 1:输入:"tree"输出:"eert"解释:'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。示例 2:输入:"cccaaa"输出:"cccaaa"解释:'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。注意"cacaca"是不正确的，因为相同的字母必须放在一起。示例 3:输入:"Aabb"输出
2020-12-10 20:58:59
188
原创 C++并行编程
相关概念并发：宏观上是同时,微观上仍是顺序执行并行：同时间执行数据安全访问方式样例备注lock互斥锁，读写锁，自旋锁锁的切换有开销memory barrier内存屏障编译器与cpu无法乱序执行，无法得到相应加速效果atomicatomic适用于基本类型CAScpu层面原子指令修改内存，内存栅栏保障修改可见，必要时锁总线1.适合冲突较少的简单对象的操作，如果太多线程同时自旋，那么长时间循环会导致 CPU 开销大; 2.ABA问题（引入变量版本号解
2020-12-09 00:17:37
552
原创 leetcode92. 反转链表 II
题目反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL思路与反转链表类似，单要注意边界条件leetcode92. 反转链表 II实现/** * Definition for singly-linked list. * struct ListNode {
2020-12-07 13:23:26
107
原创 剑指 Offer 54. 二叉搜索树的第k大节点
题目给定一棵二叉搜索树，请找出其中第k大的节点。示例 1:输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1输出: 4思路思路1.中序遍历后为升序数组，取第k大的元素思路2. 反中序遍历+计数器时间复杂度：
2020-10-27 20:59:04
73
原创 特定深度节点链表
题目给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。示例：输入：[1,2,3,4,5,null,7,8] 1 / \ 2 3 / \ \ 4 5 7 / 8输出：[[1],[2,3],[4,5,7],[8]]思路1.类似于二叉树的层次遍历，借助队列和两个计数器2.区别点是这里需要根据每层
2020-10-27 20:13:33
164
原创 leetcode240. 搜索二维矩阵 II
题目编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例:现有矩阵 matrix 如下：[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5，返回 true。
2020-10-26 22:07:20
101
原创 leetcode141.环形链表
题目给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 。进阶：你能用 O(1)（即，常量）内存解决此问题吗？示例 1：输入：head = [3,2,0,-4]
2020-10-26 21:10:38
62
原创 leetcode86. 分隔链表
题目给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:输入: head = 1->4->3->2->5->2, x = 3输出: 1->2->2->4->3->5思路设置三个辅助节点1.虚拟头节点vir，方便函数的返回值2.小于x的节点中最靠近x的节点 left，作用是插入下一个小于x的节点3.当前节点的前置节点pre，删除当
2020-08-14 00:22:41
98
原创 leetcode75. 颜色分类
题目给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。注意:不能使用代码库中的排序函数来解决这道题。示例:输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]思路初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中
2020-08-12 00:03:08
124
原创 leetcode61. 旋转链表
题目给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1:输入: 1->2->3->4->5->NULL, k = 2输出: 4->5->1->2->3->NULL解释:向右旋转 1 步: 5->1->2->3->4->NULL向右旋转 2 步: 4->5->1->2->3->NULL示例 2:输入: 0->1->2-&
2020-08-11 22:53:42
86
原创 leetcode79. 单词搜索
题目给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。思路回溯递归实现class Solution {public: bool exist(vector<vector<char>>& board, string word) { for(int i = 0; i < board.size(
2020-08-06 00:39:02
121
原创 leetcode60. 第k个排列
题目给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：“123”“132”“213”“231”“312”“321”给定 n 和 k，返回第 k 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1:输入: n = 3, k = 3输出: "213"示例 2:输入: n = 4, k = 9输出: "2314"思路1.固定第一位，比较k
2020-08-04 00:26:42
161
原创 leetcode40.组合总和 II
题目给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]示例 2:
2020-07-29 23:48:12
104
原创 leetcode398. 随机数索引
题目给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。示例:int[] nums = new int[] {1,2,3,3,3};Solution solution = new Solution(nums);// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。solution.pick(3);// pick(1) 应该返回 0。因为
2020-07-28 01:04:38
108
原创 leetcode382. 链表随机节点
题目给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？示例:// 初始化一个单链表 [1,2,3].ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);Solution solution = new Solution(head);//
2020-07-28 01:02:03
190
原创 leetcode18.四数之和
题目给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]
2020-07-23 00:31:07
159
1
原创 leetcode16.最接近的三数之和
题目给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。示例：输入：nums = [-1,2,1,-4], target = 1输出：2解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。思路数组排序+双指针，参考leetcode15.三数之和实现class Solution {public: int threeSumC
2020-07-22 01:34:29
166
原创 leetcode15.三数之和
题目给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2]]来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/3sum著作权归领扣网
2020-07-22 01:32:42
179
原创 leetcode4.寻找两个正序数组的中位数
题目给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5思路1.转化为取第k大的数2.每次从两个数组中取k / 2大的数做比较，
2020-06-30 00:03:43
185
原创 struct和class的区别
访问权限继承访问权class默认的是private,strcut默认的是public。访问权struct默认的数据访问控制是public的，class默认的成员变量访问控制是private的。模版参数class可用于定义模板参数，就像typename，但struct不能这样用。更详细的参考struct和class的区别The real difference between...
2020-04-29 23:18:00
151
原创 zookeeper浅析
连接超时问题在session timeout时间内重连成功客户端连上时立刻收到事件type=session_event(-1),state=connected_state(3)，不需要重新注册watcher，已创建的节点仍在存在。超过session timeout时间后重连成功客户端连上立刻收到事件type=session_event(-1),state=session_expired_s...
2020-04-29 23:00:56
385
原创 vim常用指令
指令作用gf跳转头文件ctrl + ]方法跳转Ctrl- 6跳到上一个文件ctrl + o跳回g；回到上一次修改:vs打开多个文件ctrl + N单词补全ctrl + L整行补全:!ls列出文件:!rm删除文件gg + :dG清空整个文件...
2020-04-03 00:00:44
109
原创 c++ 双冒号和单冒号的区别
双冒号域操作符声明了一个类A，在类A中声明一个成员函数void foo()，但没有在类A的声明中给出函数foo的定义，那么在类外定义foo时，就要写成下面这样，表示foo()函数是类A的成员函数。void A::foo()引用成员函数和变量System::Math::Sqrt()单冒号构造函数初始化列表struct foo{ foo() ...
2020-03-28 23:46:49
654
原创 c++11 emplace_back和push_back
有移动构造函数#include <iostream>#include <cstring>#include <vector>using namespace std; class A {public: A(int i){ str = to_string(i); cout << "构造函数" <&...
2020-03-14 00:36:09
260
原创 const在c++中的作用
const一个变量加上const修饰后，就变成了只读变量（不等于常量），一般不可以被修改。比如：const int *p和int const *p两条语句等价,const修饰 *p，即 *p不可被修改， p可以被修改。const与宏常量的区别const常量有数据类型，宏常量没有数据类型，所以没有类型的检查，是不安全的；const可以进行调试，宏不可以调试，无法检查错误。const...
2020-03-12 19:51:56
1752
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人