中国珂学院💭

引言 正常情况下，scanf 会跳过空白读入且遇到空白读入会停止，即遇到形如 abc def 这种输入时，如果我们仅仅使用 scanf("%s", str) 这种输入格式，只能读到前面的 abc ，如果我们想读入整行，只能采用 get 函数来解决。 现在，我们引入关于 scanf 的正则表达式用法，来完成之前无法完成的一些任务。 正则用法 1scanf("%[^\n]", str); ^ 表示逻辑运算符 “非”, [^\n] 表示遇到换行字符就结束读入。 我们都知道, scanf 是无法接受空白符的，一旦接收到空格就停止读入（%c 用法除外），我们可以用这种方式来读取一行； * 表示把该输入项读入后舍去，不存入任何变量中，所以我们可以使用 scanf("%[^\n]%*c", str); 这种用法来读取一行变量，并吸掉末尾的换行符。 举例 123456789101112#include <stdio.h>int main(void) { char s[100], s1[100], s2[10 ...

引入 transform是 C++ 中对应函数式编程 Map 操作的标准库函数。 提供两种调用方式： 第一形式有 4 个参数，把源区间的元素转换到目标区间。也就是说，复制和修改元素一气呵成； 第二形式有 5 个参数，将前两个源序列中的元素合并，并将结果写入目标区间。 下面分别介绍一下两种形式的用法。 1. 用法一 transform(sourceBeg, sourceEnd, destBeg, opfunction) 参数解释 transform 会针对区间 [sourceBeg, sourceEnd) 中的每一个元素均调用一次 opfunction，并将返回结果写到以destBeg为起始地址的目标区间内； 每对一个元素进行操作后，destBeg会后移一位，最终 transform会返回目标区间内 最后一个被转换元素的下一个位置； sourceBeg和destBeg可以相同，所以可以使用 opfunction对当前区间的元素进行变换； 如果想用某个值替换符合某个条件的元素，应该用 replace()函数替代； 时间复杂度：区间长度 nnn，opfunction时间复杂度为Θ(m) ...

引言 目前国内大量高校和教材的C语言以及数据结构等代码中，还存在在各种不珂学的写法，准备做一系列文章来对国内教材等内容进行一些 指指点点。 首先批判一下大量教材中 C 语言中的 malloc用法。 例子 假设我们有一个结构体： 1234typedef struct { char name[100]; int a;} Node; 然后我们需要动态分配长度为 n 的结构体数组： 1234int main() { int n = 10; Node* arr = (Node*)malloc(sizeof(Node) * n);} 问题分析1 留意一下这个代码，有什么问题吗？ 第一个问题是，在调用malloc的时候，我们并没有做原型声明，即使用#include <stdlib.h> 或者#include <malloc.h>，在旧式的编译器中，如果没有原型声明的函数，默认返回值就是 int类型。 所以，在 64 位操作系统上，int一般是 4 字节的，而指针类型是 8 字节的，这样做强制类型转换，实际上是将int类型转换成v ...

1.二分搜索算法简介 在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）[1]、对数搜索算法（英语：logarithmic search algorithm）[2]，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。（摘自维基百科） 二分算法的最坏时间复杂度是 Θ(logn)\Theta(logn)Θ(logn)的，空间复杂度是Θ(1)\Theta(1)Θ(1)。其应用范围广泛，如分块算法中就应用了二分算法的思想，还有二叉搜索树和B+树等等。 2. 二分搜索算法思想 二分搜索算法在大部分情况下只对有单调性的问题有效（如元素有序等等），每次取中点元素进行判断： 如果中点元素值等于目标值，则直接返回其在 ...

引言 在目前的大部分编程语言中，浮点数的实现标准都是以 IEEE-754 的标准实现的。所以，在比较两个浮点数大小关系时，直接进行比较可能会获得意料之外的答案。所以浮点数在四则运算中是不满足分配律和结合律的。 这里 IEEE-754 标准就不具体叙述了，见上面维基百科。 2 进制的浮点数表示有一个很大的问题：它并不能精确表示所有实数。只有可以写成2a+2b+2c+...2^a+2^b+2^c+...2a+2b+2c+... 这种形式，并且精度要求不是特别高的实数才可以用浮点数来精确表示。所以大多数实数仅仅保存了一个四舍五入后的近似值。比如，0.1 在单精度浮点数中实际值是 0.100000001490116119384765625。 如何进行比较呢？ 正因为上述原因，所以实际上我们对两个浮点数进行比较时，是利用做差的方式来比较。 假设有两个浮点数 a 和 b，假设我们要求精度保证是4位，那么我们可以设置一个误差值eps。 一般它的值为1e-(要求精度 + 2)，我们这里 eps = 1e-6。 那么这个误差值有什么用呢？这个误差是用来进行精度保证的。 这样，我们可以假设 a - b的值 ...

引言 在大量的算法教材和课程中，基本都会提到程序的时间和空间是可以互换的，但很少有教材来解释这个问题，下面我们就以一个例子来理解一下什么叫时间和空间是可以互换的。 在一个程序中，数据实际上可以和函数一一对应。 例子 最简单的比方，就用下面一个例子： 1234567// 假设我们有一个数组int arr[100];// 还有一个函数:int func(int index) { return arr[idx];} 这样，就是一个最简单的映射关系，相当于：(arr[index] -> arr(index)) 数组 -> 下标 -> 值 函数 -> 参数 -> 值 观察上述两个不同的资源，我们可以将其归为两类： 存储资源（如变量以及数组等数据结构），代表着程序的需要的内存空间大小 计算资源（函数、方法等），代表着程序需要的运行时间的大小 这就是时间和空间可以互换的原理。 假设从数组中取值需要 1 个单位的时间，将参数传入函数中并进行计算，获得返回值的时间需要 100 个单位的时间（并且计算过程中包含这大量的重复子问题），我们需要进行 ...

引言 在工程中，有些地方不可避免的需要使用到 goto语句和 if else嵌套语句，但往往这样会让代码的可读性变得极差，所以我们需要一种方法来消除上述两种语句，这就是下面要介绍的 do while(false)。 条件语句嵌套的例子 123456789101112if (one == true) { // operation if (two == true) { // operation if (three == true) { // operation //第三个依赖第二个判断结果，第二个依赖第一个判断结果。 //... } }} 这样过多的括号嵌套，会使得可读性变得极差，这个时候，我们就可以利用防御性编程的一些技巧，来消除这种嵌套。 1234567891011121314do { if (one == false) { // operation ...

引言 在并发数量较大的情况下，我们应该尽可能的让临界区变的小，减少资源竞争的时间，提高性能。 在 Glang 中，如果我们使用 defer unlock() 操作，会让临界区编程从lock()开始到整个函数结束，会影响性能。 最初版本 1234567891011121314151617181920212223242526272829303132333435type Counter struct { count int mutex sync.Mutex}func(c *Counter) Incr() { // mutex开始 c.mutex.Lock() defer c.mutex.Unlock() c.count++ fmt.Println(c.count) // mutex结束}func(c *Counter) Get() int { c.mutex.Lock() defer c.mutex.Unlock() return c.count}func main() { var wg sync.WaitGroup wg ...

1. 水塘抽样算法简介 水塘抽样（英语：Reservoir sampling）是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到内存的情况。最常见例子为Jeffrey Vitter在其论文[1]中所提及的算法R。（摘自维基百科） 因为他可以处理 n 很大甚至未知的情况，所以在大数据中应用广泛，比如 Flink 就用到了这个算法。 2. 水塘抽样思想 假设我们有一个 Steam, 简称为 S，我们需要从S中选取 k 个元素，并且要保证每一个元素取到的可能性相等。 当 n 已知时，为了保证每一个元素取到的概率均相同，我们可以使用随机数生成的方法来解决这个问题，但是当 n 未知时又如何保证呢？如果我们先去遍历一次获取数据的总长度，在面对大数据的场景下，未免过于费时间，若去估计整体数据的规模，则可能最后采样的结果分布并不是均匀的。 所以，这里，水塘抽样算法就派上用场了，这里用自然语言来描述一下整个过程： 采样过程： 集合中总元素个数为 n，随机选取 k 个元素。 step1： 首先将前k个元素全部选取； st ...

引文 前几天有个学弟来问我为什么用 Golang 语言写的一个算法题，用原生二维数组类型就不超时，而使用嵌套的 slice反而超时。 于是我利用 Golang的 benchmark测试以及 unsafe.pointer 来分别测试连续和随机访问性能以及分配的内存地址是否连续这两个因素。 地址分配 首先，二维数组的地址肯定是连续分配的，这个就不用再进行测试了，这里针对 Slice列数的两种情况分别进行测试。 test1: 每一个子Slice的维数均相同的情况 123456789101112131415161718192021222324func main() { slice := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} fmt.Println(slice) fmt.Printf("%x\n", unsafe.Pointer(&slice[0][0])) fmt.Printf("%x\n", unsafe.Poi ...