很对人讲了二分的过程，但没有讲为什么，我搜了一些用自己的话描述出来，有不恰当的地方请见谅。新建一个 low 数组，low中的数组有序，且都是low数组最后数插入后目的数组最小值，这样才能发现最长的子序列。例如：1 4 7 2 5 9 10 3 的最短子序列为 1 4 7 9 10 或 1 2 5 9 10 或 1 4 5 9 10，low数组就为1 2 3 9 10更新过程如下： A[1] = 1，把1放进B[1]，此时B[1] = 1，B[ ] = {1}，len = 1 A[2] = 4，把4放进B[2]，此时B[2] = 4，B[ ] = {1,4}，len = 2 ...

不需要数组，如果数组长度大于2，就记录两个变量f，g。f为到达当前位置的消费，g为f前一个位置的消费。f就为当前位置的最小消费，可得递推公式。然后把 g 向前推进一位就行：。 int minCostClimbingStairs(int* cost, int costLen ) { // write code here if(costLen <= 2) return 0; int f = 0, g = 0; for(int i = 2; i <= costLen; i++){ int tmp = f; f = g + c...

int Fibonacci(int n ) { // write code here int f = 0, g = 1; while(n--){ f = f + g; g = f - g; } return f; }

递归 三种情况： 当前结点值小于q，p，就在当前结点的左子树寻找最近公共祖先。 当前结点值大于q，p，就在当前结点的右子树寻找最近公共祖先。 p，q 包含了当前结点值，即 q<=val<=p，或 q>=val>=p，那么公共祖先就是该节点。 class Solution { public: int lowestCommonAncestor(TreeNode* root, int p, int q) { // write code here if (p > root->val && q > ...

C++中函数共有3中参数传递的方式，每种传递方式的原理都有很大差别，每种方式的应用场景也不同，今天就带大家来详细解析一下。 在介绍函数传递之前，先了解一下形参与实参的概念，了解形参与实参是学习传参的基础。 形参（形式参数）：在函数定义首部所声明的参数，或简称为参数，一定要注意：形式参数是额外分配的内存实参（实际参数）：实际调用函数所提供的参数。 看下图示例： void func(int n); //形参 void func2(){ func(1); //实参 } 传值参数 值传递用起来非常明了。当然缺点也有很多，就是慢、占用空间还有不能修改实参。因为所谓的值传参是把实参...

介绍并行算法中的压缩与规格化 背景 稀疏矩阵是很多元素是 0 的矩阵。下图是一个简单地例子。 利用稀疏行压缩格式保存稀疏矩阵时不保存 0 元素。数组 data[ ] 保存非零元素。另外，还需要两个辅助数组来保留原本矩阵的结构。第一个是列索引数组 col_index[ ]，这个数组记录原矩阵中非零元的纵向索引。第二个数组 row_ptr 记录了原矩阵每行的非零元素在数组 data[ ] 中的起始位置，元素个数比行数多一，多出来的元素往往用来作为行结束的标志。上面矩阵的 CSR 存储格式如下图所示： （五）中讨论过，矩阵通常用来解决形如 的 N 元 N 次方程组，其中 A 是 的矩阵， X ...

本文介绍原子操作和私有化前面讲的几个并行模式都是将计算元素的任务分配到各各线程，线程之间不会相互干扰。但在实践中，很多并行计算模式的输出会受到其他线程的影响，并行直方图计算就是其中的一个例子，它的输出结果可能会被所有线程修改。因此，在线程更新输出元素时，必须协调线程之间的关系。下面将介绍一种基线方法，它使用原子操作来序列化对每个元素的更新，但基线方法的效率很低。此外还有一种高效的私有化方法，可以显著提高执行速度。 背景 直方图以连续的数值间隔显示数据出现的频率。在最常见的直方图形式中，值区间沿横轴绘制，每个区间中数据项的频率表示为从横轴上升的矩形(或条形图)的高度。比如大规模并行处理器的英文：...

背景 前缀和（prefix sum）也叫扫描（scan），闭扫描（inclusive scan）操作对 n 元数组[x0, x1, x2, ..., xn-1] 进行二元运算#，返回输出数组 [x0, (x0#x1),..., (x0#x1#x2# ...# xn-1)]。开扫描(exclusive scan) 与闭扫描类似，返回数组 [0, x0, (x0#x1),..., (x0#x1#x2# ...# xn-2)]。将闭扫描输出数组全部右移一位，第 0 个数组赋 0 即得到开扫描的输出数组。 闭扫描算法的串行实现： void sequential_scan(float *x, flo...

1.性能优化里面的两个归约 kernel 函数在使用线程时很浪费，每个块中有一半线程根本没执行。修改 kernel 来消除这种浪费现象。给出 kernel 启动时与之相关的配置参数的值。在运算操作方面是否需要更多额外成本？这种修改能消除哪种类型的资源限制？ 答：修改后的第一个： unsigned int t = threadIdx.x * 2; for(int stride = 1;stride <= blockDim.x;stride <<= 1){ if(t % (2*stride) == 0){ partialSum[t]...

@[TOC](NVIDIA CUDA 高度并行处理器编程（六）：并行模式：卷积)介绍常数存储器和高速缓存 后面几个文章介绍一些重要的并行计算模式。这些模式是很多并行算法的基础。先介绍卷积，卷积广泛应用于信号处理、图像处理和计算机视觉。卷积通常涉及每个元素上的大量算术运算，比如清晰的图像和视频，计算量很大，不过还好每个输出元素的计算都是相互独立的，我们可以应用并行处理。另一方面，输入元素之间有一定程度的数据共享，还存在一些颇具挑战的边界条件，这使得卷积成为复杂分块方法和输入数据分段的一个重要案例。 背景 卷积是一种数组操作，每个输出元素都是周围输入元素的加权总和。权重是由一个输入掩码数组也叫卷积...

const限定符的用途很广，普通变量、指针与引用、函数与函数参数、类成员变量成员函数都能用const修饰。虽然const能用的地方很多，但是大都万变不离其宗，它的作用也比较单一，今天博仔就带你来详细解析 const。 1、变量中的const 编写程序过程中，我们有时不希望改变某个变量的值。此时就可以使用关键字 const 对变量的类型加以限定。 1.1 普通变量 直接在普通变量类型声明符前加上 const，可以将声明为 const 类型： const int a = 0; 这样就把 a 声明成了一个 const 类型的常量，所以我们不能再改变它的值了，所以下面试图改变 a 的语句将会编译报错...