author avatar

Liu Bang

总共 53 篇文章

False Positive Rate

$m$: 表示BloomFilter bit array的长度;
$k$: 表示hash函数个数;
$n$: 表示插入元素的个数;

假设hash函数以等概率选择bit array的下标,那么经过$k$个hash函数之后,某个bit位未被设置为1的概率为:

$$ (1 - \frac{1}{m})^k $$

在插入$n$个元素之后,某个bit位仍然没有被设置为1的概率为:

$$ (1 - \frac{1}{m})^{kn} $$

因此在插入$n$个元素之后,某个bit位被设置为1的概率为:

$$ p = 1 - (1 - \frac{1}{m})^{kn} $$

对于一个不存在于集合中的元素,...

libFuzzer 简介

LLVM libFuzzer 是 LLVM 生态系统中的一个fuzzy test工具,用于自动化地发现软件程序中的漏洞和错误。它通过生成大量的随机输入数据并观察程序的行为来进行fuzzy test。 libFuzzer 是一个基于内存的fuzzy test引擎,使用 LLVM 的插桩技术和代码优化功能来提高测试效率和覆盖率。

以下是 libFuzzer 的一些功能特点:

  1. 自动化fuzzy test:libFuzzer 提供了一种自动化的fuzzy test方法,可以生成大量的随机输入数据,并在每个输入上运行目标函数进行测试。它通过观察程序的崩溃、断言失败、未定义行为等反馈来发现潜在的问题。
  2. 内存安全...

题目描述

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。

题解

  1. 定义状态:

$dp[i]$表示用所给的面值的硬币凑成金额$i$所需的最少的硬币个数。

  1. 设计状态转移方程:

$$ \forall coin \in coins, 当 i \geqslant coin,且 dp[i - coin] \neq -1 时, dp[i] = std::min(dp[i], dp[i - coin] + 1) $$

  1. 初始化:

对于 amount...

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

题解

这道题是一个非常典型而且很简单的动态规划题目。我们可以根据动态规划题目解题的一般思路来分析:

  1. 定义状态:

$dp[i]$表示爬到第$i$级楼梯的不同方法数。由于每次可以选择爬 $1$ 级或者 $2$ 级楼梯, 所以爬到第 $i$ 级楼梯的方法数等于爬到第 $i-1$ 级楼梯和第 $i-2$ 级楼梯的方法数之和。 根据这个关系,我们可以使用动态规划的方式从 $1$ 级楼梯开始逐步计算到第 $n$ 级楼梯的方法数,最终返回 $dp[n]$即为结果。

  1. 设计状态转移方程:

$$dp[i] =...

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

题解

由题可知,数组nums非空,所以分割后的两个子集也必然非空,由于都是正整数,所以nums中元素之和必然为偶数。

这道题是典型的 01 背包问题,假设$dp[i][j]$表示nums中前$i$个元素是否包含和为$j$的子集,那么:

  1. nums[i] = j的时候,dp[i][j] = true
  2. nums[i] > j的时候,dp[i][j] = dp[i - 1][j]
  3. nums[i] < j的时候,dp[i][j] = dp[i - 1][j] || dp[i -...

题目描述

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化 void push(int val) 将元素推入堆栈 void pop() 删除堆栈顶部的元素 int pop() 获取堆栈顶部的元素 int getMin() 获取堆栈中的最小元素

题解:

这道题首先要满足堆栈的特性 LIFO,其次是能够在常数时间内获取当前栈中最小的元素,因此我们可以用堆栈保存 个二元组,二元组的第一个元素是存入栈中的值,第二个元素是当前元素作为栈顶元素的时候,栈中的最小值。有 了这个思路,代码实现起来就很简单了。

 1class MinStack...

题目描述

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。

解法一:暴力求解

主要思路是,遍历每个柱子,然后往柱子左右两边寻找比当前柱子矮的位置,从而计算出,以当前柱子为高度,所能围成的最大面积。 然后将这些面积中最大的值返回即可。暴力求解的时间复杂度为O(n^2)

不过我尝试过各种暴力求解,在 leetcode 中提交后都会超时。

 1class Solution {
 2public:
 3    int largestRectangleInHistogram(const std::vector<int>&...

题目描述

给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ,则返回 true 。 否则,返回 false 。

解法一:hash 法

hash 法是我们在判断重复元素类问题中最常用的方法。针对链表是否有环来说,我们可以遍历链表,并用std::set 存放遍历过的元素,判断是否存在重复元素,如果存在则表示有环,如果遍历结束且不存在重复,则没有环。

题目描述

给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。

解法一:stack

这道题目是典型的堆栈数据结构的应用,虽然思路很清晰,代码也很简单,但是要注意逻辑的严谨性。尤其是在判断 栈顶元素是否匹配之前,要先判断栈是否为空。

 1class Solution {
 2public:
 3    bool...

题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

解法一:迭代

迭代法应该是我们最容易想到的常规方法,也比较符合人的思维逻辑。其核心思想就是通过两个指针移动,来 一个一个的修改链表的指向方向。

 1class Solution {
 2public:
 3    ListNode* reverseList(ListNode* head) {
 4        if (!head || !head->next) return head;
 5        ListNode* prev = nullptr;
 6        ListNode* cur = head;
 7...