Daily C/C++ 可怜的小猪 今天这个文章思路来源于leetcode的每日一题 题目链接 万能的网友们给出了各种各样的解题方法，这里我也提两种我认为比较有意思的方法 首先一个通用的前提是，我们对于题目中给出的时间限制，我们可以令stage = ceil(minToTest / minToDie) 即我们一共有stage轮操作的机会 这里，我们将bucket个桶分成一个k维的超立方体，或者是一个k维的矩阵。他们的长度都是stage + 1 因为每个小猪在每一轮都有可能死掉，所以一个小猪在stage轮中的状态为第…
Daily C/C++ 接雨水 leetcode的题，这道题算是十分经典的一道题了，有很多种解法 题目链接 对于单调栈的做法来说，我们维护的是每个元素两边比他大的第一个元素的值以及位置，然后用值乘上这两个比他大的元素划分出来的范围，就是结果 这种做法更像是把答案用高度来进行横向的切割 而更加简单的思路是维护每个元素的两边的最大值，然后每个元素的贡献就是两个最大值之间较小的那一个减去当前元素的高度 这种做法是把答案纵向切割，单独考虑每个位置，长度永远就都是1 这里想说的是维护最大值的算法的一个优化版，就是利用双指针维…
Daily C/C++ 位运算的妙用 这个文章的思路来自于今天的每日一题 题目链接 虽然是有点脑筋急转弯的题目，不过看到这样巧妙的利用位运算我还是想来分享一下这个做法 题目大意就是数组中只有两个元素的个数是1，其他元素的个数都是2。也就是只有两个元素没有重复，叫我们找出这两个元素 这个是之前题的进阶版，如果只有一个元素没有重复，那我们可以把整个数组异或一遍，重复的元素就会相互抵消，最终就剩下了答案 对于这个题来说，我们都异或一遍以后，得到的是 x = x1 \oplus x2 那我们如何充分利用这里的信息呢 对于这…
Daily C/C++ 更简单的加法模拟 本题来自leetcode链接 原始的思路就是一位一位的模拟加法器的运算 这样我们从最低位开始，每次维护进位的信息。循环32次即可 这里有一个更巧妙的实现方法，有点并行的那个感觉 先贴代码 unsigned int res = a; unsigned int nxt = b; while (nxt) { unsigned int tmp = (res & nxt) << 1; res ^= nxt; nxt = tmp; } 首先是对于这种位运算我们先转化…
Daily C/C++ 利用值域节省空间 这个文章内容会比较少，是我在做leetcode题中遇到的 但是无论如何也是新学习到的东西，所以这里简单记录一下 题目链接 就是一个数组，叫我们找出其中任意一个重复的数 如果值域较大的话，我们可以用哈希表来解决 这道题有个特殊的点就是他的值域是小于给出数组大小的，这也启发了我们可以进行原地修改来帮我们记录信息 这里的技巧就是，对于当前扫描到的数x，我们去找数组中对应下标的位置nums[x]，如果nums[x]是正数，那么我们将它变成负数，否则我们就找到了一个重复的数 这里重点…
Daily C/C++ 利用mutex实现简单的读写锁 之前我们有说过条件变量相关的东西，他可以帮助我们控制线程的执行 今天这里，我们就说一种简单的利用mutex和条件变量实现读写锁的方法 这里的实现其实就是CMU15445的bustub中的实现，如果有兴趣的同学可以自己去看相关的代码 首先我们要明确，我们希望实现的读写锁的性质。比如他是按照队列一个一个分配的吗？他是读者优先还是写者优先？ 这里，我们要实现的读写锁是写者优先，即如果当前有写者在等待，那么新到来的读者也会被阻塞。 如果当前有写者的时候，我们又来一个写…
Daily C/C++ condition_variable 之前有说要出一个条件变量的讲解 说到头我还是感觉cppreference讲的好，这里就总结一下 参考文章 条件变量也是一种用于同步的对象，他能够阻塞多个线程，直到另一个线程修改了共享变量并通知条件变量 这是啥意思呢，我们先来一个例子 #include <iostream> #include <string> #include <thread> #include <mutex> #include <co…
Daily C/C++ 弹性数组 参考文章 之前在写CMU15445的lab的时候遇到的，弹性数组指的是结构体中，长度为0的数组 举个例子 struct foo { int a; char b[0]; //或者写成 char b[]; } 当我们分配了一块内存给这个结构体的时候，b的长度就会随着我们分配内存大小的改变而改变 比如我们分配了一个128字节的内存给这个结构体，那么前四个字节就会映射到a中，而后面的124个字节就会映射到b中，此时b就是一个长度为124的数组 这样我们就可以通过灵活改变分配给foo的内存来…
Daily C/C++ 并发编程基础 今天这篇文章是简要的介绍一下并发编程中的用于控制同步的对象 参考文章是CMU15445的project4中andy推荐的一篇文章 锁 锁是一个抽象的概念，用来保护资源的，当你持有锁的时候，你就可以去访问受保护的资源。当你没有持有锁的时候，你就不能去访问对应的资源 锁本身的含义也隐喻了独占的意味。当你尝试去获取一个锁，却失败的时候，要么你会阻塞住，一直等到你可以获得这个锁为止。要么你会返回一些错误码等东西来表示获取失败 最常见的一种就是简单的计数，一个锁可以有一个上限的值。当我们…