Estom的博客

零钱兑换问题描述给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 假设每一种面额的硬币有无限个。  1234567输入：amount = 5, coins = [1, 2, 5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1 问题分析 典型的动态规划 典型的完全背包问题 策略选择 动态规划 采取两个方向上的动态规划。两个方向上的动态规划是非等价独立的。 数组矩阵线性数据结构 算法设计 阶段划分：规模增长的方向有两个。第一个规模增长的方向是硬币的种类。第二个规模增长的方向是金钱的总量。 状态变量dp[i][j]表示使用第i个硬币，达到j分钱所有的可能。 状态转移方程 if k*coins[i]== amount dp[i][j]++; if kcoins[i]<amount dp[i][j]+=dp[i-1][j-kconis[i]] foreac...

最大公约数循环法1234567891011121314151617181920212223242526272829303132#include<iostream>using namespace std;int gcd1(int x,int y){ if(x%y==0){ return y; } return gcd1(y,x%y);}int gcd2(int x,int y){ int r = x % y; while( r ) { x = y; y = r; r = x % y; } return y;}int lcm(int x,int y){ int k = gcd2(x,y); return x*y/k;}int main(){ int x=60,y=95; cout<<gcd1(x,y); return 0...

一致性哈希算法一致性Hash算法背景一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。 但现在一致性hash算法在分布式系统中也得到了广泛应用，研究过memcached缓存数据库的人都知道，memcached服务器端本身不提供分布式cache的一致性，而是由客户端来提供，具体在计算一致性hash时采用如下步骤： 首先求出memcached服务器（节点）的哈希值，并将其配置到0～232的圆（continuum）上。然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。 从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率，但Consistent Has...

1 allocalloc是向栈申请内存，因此无需释放。 功能：返回一个指向n个连续字符存储单元的指针。利用afree§释放已经分配的存储空间，以便以后使用。 函数原型: char *alloc(int n); 2 malloc(memeory allocation,动态内存分配)malloc分配的内存是位于堆中的，并且没有初始化内存的内容，因此基本上malloc之后，调用函数memset来初始化这部分的内存空间。 功能 用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存，且分配的大小就是程序要求的大小。 函数原型： void *malloc(unsigned int size) 工作机制 malloc函数的实质体现在，他有一个将可用的内存块连接为一个常常的链表的所谓空闲链表。调用malloc函数是，他沿着连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那...

动态内存管理 参考文献 SLBA的原理和使用 SLBA教程 1 SLBA分配器概念在linux内核中伙伴系统用来管理物理内存，其分配的单位是页，但是向用户程序一样，内核也需要动态分配内存，而伙伴系统分配的粒度又太大。 由于内核无法借助标准的C库，因而需要别的手段来实现内核中动态内存的分配管理，linux采用的是slab分配器。 slab分配器不仅可以提供动态内存的管理功能，而且可以作为经常分配并释放的内存的缓存。通过slab缓存，内核能够储备一些对象，供后续使用。需要注意的是slab分配器只管理内核的常规地址空间（准确的说是直接被映射到内核地址空间的那部分内存包括 ZONE_NORMAL和ZONE_DMA ）。 优点采用了slab分配器后，在释放内存时，slab分配器将释放的内存块保存在一个列表中，而不是返回给伙伴系统。在下一次内核申请同样类型的对象时，会使用该列表中的内存开。slab分配器分配的优点： 可以提供小块内存的分配支持 不必每次申请释放都和伙伴系统打交道，提供了分配释放效率 如果在slab缓存的话，其在CPU高速缓存的概率也会较高。 伙伴系统的操作队系统的数据...

多进程多线程多协程异步IO/事件驱动IO/IO多路复用

AboutNikhil Marathe在某一个下午(June 16, 2012)开始写这本书。当他在写node-taglib的时候苦于没有好的libuv文档。虽然已经有了官方文档，但是没有好理解的教程。本书正是应需求而生，并且努力变得准确。也就是说，本书中可能会有错误。所以鼓励大家Pull requests。你当然可以直接给他发email，告诉他错误。 Nikhil从Marc Lehmann的关于libev的手册中讲解libev和libuv的不同点的部分，获取了不少的灵感。 本书的中文翻译者在这里。同样欢迎您的Pull requests来改进本书的翻译工作。 LicensingThe contents of this book are licensed as Creative Commons - Attribution. All code is in the public domain.