- 博客(356)
- 收藏
- 关注
RSS订阅
原创 新博客地址： https://sanzo.top
这两天整了一个博客，地址为sanzo.top，使用hexo搭建，主题采用的是hexo-theme-yun。欢迎访问，并交换友链~
2021-06-15 08:00:16
503
1
原创 Locality Sensitive Hashing
https://sanzo.top/Algorithm/Locality-Sensitive-Hashing/试想你有一些文本它们可能有所重复，你需要对他们进行去重处理，传统的做法是O(N2)O(N^2)O(N2)，即对所有的文本对进行相似度的计算，然后进行排序得到结果。假设N=106N=10^6N=106，需要进行N(N−1)2=5×1011\frac{N(N-1)}{2} = 5\times10^{11}2N(N−1)=5×1011次计算，在果每秒计算10610^6106次，一天大概10510^5
2021-10-01 19:36:29
274
原创 树莓派小车(远程控制、PWM变速、超声波自动避障)
效果展示代码地址：github.com/Sanzo00/pi-carGPIOpinoutsudo apt install python3-gpiozeropinoutgpio readallwget https://project-downloads.drogon.net/wiringpi-latest.debsudo dpkg -i wiringpi-latest.deb材料与安装名称数量规格树莓派4B14GL298N电机驱动模块1..
2021-08-19 22:36:07
3731
7
原创 pybind11简单使用
https://sanzo.top/Default/pybind11pybind11介绍github.com/pybind/pybind11使用pybind11可以将C++库绑定到Python，即在Python内调用C++代码，同样也可以在C++中调用Python代码。编译安装# install pytestpip install pytest# install pybind11git clone https://github.com/pybind/pybind11.gitcd pyb
2021-08-03 08:36:46
1201
1
原创 shared_ptr的删除器
new/delete对于对象来说：new操作先分配空间，再执行构造函数。delete操作先执行析构函数，再释放空间。在删除对象数组时，要使用delete[]，否则会造成内存泄露，因为对象数组在分配空间的时候，会额外记录数组的长度信息，使用delete[]可以释放数组中所有对象的空间。Deletershared_ptr，在构造或者reset时，可以指定删除器，用于对象的释放，用于自定义的对象数组的空间释放。#include <iostream>#include <
2021-05-12 10:44:36
2809
原创 Gemini论文笔记
论文地址：osdi16/osdi16-zhu.pdf介绍（1）Gemini采用稀疏-稠密、信号-槽抽象，将push-pull混合模型从共享内存扩展到分布式场景。（2）基于块划分模式，是一种低开销的扩展设计同时保持了顶点的局部访问。（3）采用压缩顶点索引的双模式（4）基于NUMA感知的子分区使节点内的访问更加高效（5）位置感知的块划分和细粒度的work-stealing同时提高了节点内和节点间的负载平衡。图处理抽象顶点保存信息，边是不可修改的对象。支持双向边和单向边，双向边转化为一对有向边。
2021-05-06 12:59:12
1453
原创 swap分区
kswapd0最近在跑程序的时候总是死机，以为是程序的bug，后来看了下进程的运行情况，出现kswapd0把cpu占完了。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8oeia1cp-1616144119637)(img/linux/image-20210319164107308.png)]kswapd0是在物理内存不足(阈值判断)的情况下，通过swap分区进行页面交换缓解内存压力。swap是linux的交换分区，在内存不足的情况下，将一些不常用的程序放到swap分
2021-03-19 16:56:49
668
1
原创 搭建git服务器
git服务器安装gitsudo apt install git新建git用户sudo adduser git公钥登录将设备的id_rsa.pub文件导入到服务器的home/git/.ssh/authorized_keys中。如果本地的用户名和服务器的用户名不一致，需要配置/home/user/.ssh/config文件Host server # 别名 HostName 192.168.1.101 # 服务器ip User git # 用户名初始化选定服务器的/srv
2021-02-09 23:37:28
124
原创 滑动窗口/二分 - 尽可能使字符串相等
题目链接滑动窗口class Solution {public: int equalSubstring(string s, string t, int maxCost) { int n = s.size(); int cost = 0; int left = 0; int ans = 0; for (int i = 0; i < n; ++i) { cost += abs(s[i] -
2021-02-05 22:14:24
146
原创 滑动窗口 - 替换后的最长重复字符
题目链接维护一个滑动窗口，记录窗口中出现频率最高的次数maxCnt，当窗口大小(right−left)>maxCnt+k(right - left) > maxCnt + k(right−left)>maxCnt+k时，表示当前无法通过替换k个字符满足要求，这时需要将窗口左边界右移。在编写代码时，虽然不能保证窗口中maxCnt的正确性，但是只有当前窗口中出现频率最高的次数达到上一次的maxCnt，才会有更优解，所以并不影响最终解。class Solution {public:
2021-02-04 23:51:37
171
原创 cuda临界区问题的总结
Critical Sectiongpu在多线程处理数据的时候，可能会同时访问到同一个数据，这就会出现临界区的处理问题。cuda提供了多个atmoic原子操作，但是只支持一些基础的数据类型，不能自定义结构体。对于多种数据的同步操作，就可能受到影响。另一种解决临界区的方法就是使用锁的方法保护临界区。下面是在论坛找到的一些关于临界区的讨论：code1https://stackoverflow.com/questions/2021019/implementing-a-critical-section-i
2021-01-28 10:21:23
504
原创 并查集 - 由斜杠划分区域
题目链接求划分区域的个数，也就是求连通分量的个数，将每个单元格划分为4个部分，分别根据空格、斜杠、反斜杠进行合并。单元格之间也要合并，上下、左右各选一个方向即可。class UnionFind{public: UnionFind(int n): count(n), parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); } int find(int x) { r
2021-01-27 23:02:51
99
原创 用CUDA实现Bellman-Ford
最近在看CUDA，刚好有一个类似的项目，就拿来练练手。项目地址：github.com/Sanzona/Bellman-FordBellman FordBellman Ford是求最短路的算法，可以处理带有负边的图，也可以用来判断负环。算法的主要思想是：每次遍历所有的边并更新每条边相邻的点，遍历N-1次后就可以得到源点到其他点的最短路，对于N个点的图任意两点的最短路径长度不超过N-1。CUDACUDA（Compute Unified Device Architecture，统一计算架构），是一种
2021-01-24 23:36:39
438
1
原创 拓扑排序 - 项目管理
题目链接项目之间存在依赖关系，所以项目要进行拓扑排序。同一组的项目要拍在一起，所以组也要拓扑排序。对于没人接管的项目，给他一个新的编号。最后将拓扑排序之后的项目按照项目的拓扑排序结果进行分配。class Solution {public: vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
2021-01-12 22:20:39
247
原创 并查集 - 交换字符串中的元素
题目链接用并查集维护相互可以交换的索引，然后同一并查集上的字符放到小顶堆，每次取堆顶的字符重构字符串。class Solution {public: string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) { int n = s.size(); int m = pairs.size(); unordered_map<int,
2021-01-11 12:38:02
179
原创 动态规划 - 买卖股票的最佳时机 III
每天结束，一共有5种状态：没有操作(可以不记录，收益为0)buy1：第一次买入sell1：第一次卖出（完成一次交易）buy2：第二次买入sell2：第二次卖出（完成两次交易）状态转移：buy1 = max(buy1, -prices[i]);sell1 = max(sell1, buy1 + prices[i]);buy2 = max(buy2, sell1 - prices[i]);sell2 = max(sell2, buy2 + prices[i]);因为当天买入再卖出收益为0，
2021-01-09 20:26:52
160
原创 并查集 - 除法求值
题目链接将所有等式关系转化为同一变量的倍数。class Solution {public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { int n = equations.size()
2021-01-06 08:57:18
174
原创 优先队列/单调队列 - 滑动窗口最大值
题目链接优先队列class Solution {public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); priority_queue<pair<int,int>> q; for (int i = 0; i < k; ++i) { q.emplace
2021-01-02 10:54:25
265
1
原创 动态规划/贪心 - 无重叠区间
动态规划dp[i]dp[i]dp[i]表示以区间iii结尾，可以共存最多的区间数量。dp[i]=max(dp[i],dp[j]+1)dp[i] = max(dp[i], dp[j] + 1)dp[i]=max(dp[i],dp[j]+1)，区间jjj满足右边界≤\le≤区间iii的左边界。class Solution {public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { .
2020-12-31 14:30:57
230
1
原创 贪心 - 按要求补齐数组
题目链接当[1, x]的数字全部存在时，可以得到[1, 2x-1]的数字。贪心的枚举x，如果x存在就扩展成新的范围，如果不存在就补上对应的x。class Solution {public: int minPatches(vector<int>& nums, int n) { int ret = 0; long long x = 1; int idx = 0; int sz = nums.size();
2020-12-29 08:57:25
137
原创 动态规划 - 买卖股票的最佳时机 IV
题目链接使用两个辅助数组buy[i][j]buy[i][j]buy[i][j]表示前iii个股票发生jjj次交易且手上有一只股票的最大收益。sell[i][j]sell[i][j]sell[i][j]表示前iii个股票发生jjj次交易且手上没有股票的最大收益。状态转移为：buy[i][j]=max(buy[i−1][j],sell[i−1][j]−price[i])buy[i][j]=max\big(buy[i−1][j],sell[i−1][j]−price[i]\big)buy[i][j]=m
2020-12-28 16:12:21
87
1
原创 贪心/单调栈 - 最大矩形
题目链接贪心假设当前点为最大矩阵的右下角，向上扩展每次取长度的最小值作为矩阵的长。class Solution {public: int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.empty()) { return 0; } int r = matrix.size(), c = matrix[0].size();
2020-12-26 11:08:26
170
原创 MapReduce论文笔记
介绍MapReduce是一个将数据分布到大型集群上计算的一种方案。MapReduce最核心的就是map和reduce。map函数的任务是从输入文件中获取<key, value>，reduce函数的任务是合并所有可相同的value值。一个简单的例子用mapreduce处理单词计数。input1: I like sport.input2: I like watch movice.map: <I, 1>，<like, 1>，<sport, 1>，
2020-12-25 10:34:55
237
原创 贪心 - 分发糖果
题目链接两次遍历，首先初始化所有的糖果为1，然后从左向右遍历，满足ratings[i]>ratings[i−1], num[i]=num[i−1]+1ratings[i] > ratings[i-1],\ \ num[i] = num[i-1] + 1ratings[i]>ratings[i−1], num[i]=num[i−1]+1。同理从右向左遍历。最终的结果是，要么是从1连续递增，要么是从n连续递减到1。class Solutio
2020-12-25 09:58:18
138
原创 贪心/栈 - 去除重复字母
题目链接对于一个字符串，删除满足s[i]>s[i+1]s[i] > s[i+1]s[i]>s[i+1]且iii最小的那个字符，使得删除后的字典序最小，基于这个思路，可以在遍历的时候判断如果前面的字符字典序大就删除它。另外还要满足每个元素只出现一次。class Solution {public: string removeDuplicateLetters(string s) { vector<int> cnt(26), vis(26);
2020-12-20 12:23:15
182
1
原创 数组 - 旋转图像
题目链接顺时针旋转的数学表示为：matrix[row][col]=>matrix[col][n−row−1]matrix[row][col] => matrix[col][n-row-1]matrix[row][col]=>matrix[col][n−row−1]可以通过上下翻转+对角线翻转来实现。class Solution {public: void rotate(vector<vector<int>>& matrix) {
2020-12-19 17:30:05
164
1
原创 贪心/动态规划 - 买卖股票的最佳时机含手续费
题目链接贪心每次只能交易一个股票，最优的选择就是低买高卖。不过每次交易股票都有一次手续费。可以把手续费算到买入的价格里。只要能收益就交易。每次卖出一个股票就拥有了原价购买股票的机会。这样就能在具有手续费的前提下低买高卖。class Solution {public: int maxProfit(vector<int>& prices, int fee) { int profit = 0; int buy = prices[0] +
2020-12-17 15:29:10
197
原创 贪心/动态规划 - 摆动序列
摆动序列题目链接贪心尽可能多的选择波峰波谷。class Solution {public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); if (n < 2) { return n; } int pre = nums[1] - nums[0]; int ret = pre ==
2020-12-12 17:52:15
156
原创 贪心 - Dota2 参议院
Dota2 参议院贪心+循环队列对于当前参议院来说，他的最优选择是禁止下一个最先出现的敌方参议员，这样才能保证己方参议院的安全。具体的实现采用循环队列。class Solution {public: string predictPartyVictory(string senate) { int n = senate.size(); queue<int> R, D; for (int i = 0; i < n; ++i)
2020-12-11 18:20:02
129
原创 树莓派 - 设置只读文件系统，避免分区错误
树莓派直接断电可能会导致SD分区损坏，从而导致无法正常开机，如果修复失败就只能重新刷系统，希望你对系统做了备份…SD卡本身不适合长时间读写操作，正常情况下到了一定时间都可能会发生数据读写错误。一个避免上述问题的方法是把系统设置为只读系统，这样就不会在突然断电的情况下导致系统出现错误。 参考链接：Protect your Raspberry PI SD card, use Read-Only filesystem参考链接：How to make your Raspberry Pi file syste
2020-12-10 21:09:50
2235
原创 LeetCode面试必刷题目总结 持续更新中...
多数元素题目链接找到数组中众数（出现次数>⌊n2⌋>\lfloor\frac{n}{2}\rfloor>⌊2n⌋ ）排序返回中间的数。O(nlogn)O(nlogn)O(nlogn)哈希表（unordered_map）统计每个数出现的次数。O(n)O(n)O(n)随机找众数，期望是线性。O(n)O(n)O(n)Boyer-Moore 摩尔投票算法，维护一个候选变量和它出现的次数cnt，遍历数组，如果出现的数字不同，cnt–，如果相同cnt++，如果cnt=0就
2020-10-27 13:19:48
1130
原创 跳表
跳表思想和二分类似，普通链表查询的复杂度是O(n)O(n)O(n)，跳表另外建立了索引逐层的查找效率高些。跳表每层建立的索引没有严格按照二分的要求，即每层减少一般，它是采用一种随机的方式，当插入一个数据时随机的确定他的层数，每次随机的概率时0.5。理论上和二分的效率相同。struct Node{ int val, level; Node* levels[16];};class SkipList{private: int MAX_LEVEL = 16; int c
2020-10-22 18:40:31
117
原创 贪心 - 划分字母区间
题目链接class Solution {public: vector<int> partitionLabels(string S) { vector<int> pos(26, 0); int n = S.size(); for (int i = 0; i < n; ++i) { pos[S[i] - 'a'] = i; } vector<int> r
2020-10-22 10:51:58
128
原创 双指针 - 长按键入
题目链接class Solution {public: bool isLongPressedName(string name, string typed) { int n1 = name.size(); int n2 = typed.size(); int l = 0, r = 0; while (r < n2 && l < n1) { if (typed[r] == name[l
2020-10-21 12:17:02
134
原创 LeetCode每日一题 143. 重排链表
题目链接思路双指针class Solution {public: void reorderList(ListNode* head) { vector<ListNode*> v; ListNode* tmp = head; while (tmp) { v.push_back(tmp); tmp = tmp->next; } int l = 0, r
2020-10-20 11:01:06
109
原创 LeetCode每日一题 844. 比较含退格的字符串
题目链接思路class Solution {public: bool backspaceCompare(string S, string T) { int n1 = S.size(); int n2 = T.size(); init(S, n1); init(T, n2); int l = 0, r = 0; while (l < n1 && r < n2) {
2020-10-19 13:57:05
102
原创 LeetCode每日一题 19. 删除链表的倒数第N个节点
题目链接思路双指针，保持两个指针距离为n。引入头节点方便统一处理。class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummy = new ListNode(0, head); ListNode* L = dummy, *R = head; for (int i = 0; i < n; ++i) R = R->
2020-10-18 17:01:26
51
原创 LeetCode每日一题 52. N皇后 II
题目链接思路暴搜二进制class Solution {public: vector<int> row, col; int totalNQueens(int n) { int ret= 0; row.resize(n, -1); col.resize(n, -1); ret += dfs(0, n); return ret; } int dfs(int x, int n
2020-10-17 10:58:11
129
原创 LeetCode每日一题 977. 有序数组的平方
题目链接思路双指针找绝对值最大的，最后反转数组。class Solution {public: vector<int> sortedSquares(vector<int>& A) { vector<int> ret; int l = 0, r = A.size()-1; while (l <= r) { if (abs(A[l]) > abs(A[r])) {
2020-10-16 10:32:01
122
原创 LeetCode每日一题 116. 填充每个节点的下一个右侧节点指针
题目链接思路层序遍历，记录每个节点的层数，另外使用一个前驱节点，判断层数是否相同，如果在同一层就修改next。class Solution {public: Node* connect(Node* root) { if (!root) return root; pair<Node*, int> pre = make_pair(nullptr, -1); queue<pair<Node*, int>> q;
2020-10-15 09:48:26
135
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人