WhatGhost

leetcode 986 区间列表的交集 题目地址 由于每个列表的区间都是互不重叠且排好序的，所以可以利用归并排序的方法，从两个列表的头上取出来两个小区间判断 之后删除掉较小的那个 判断两个区间的交点的代码如下 12345int lo = max(firstList[p1][0],secondList[p2][0]);int hi = min(firstList[p1][1],secondList[p2][1]);if(lo<=hi){ ret.push_back({lo,hi});} 如果没有交点，lo会比hi大，否则证明二者有交点 最后去掉较小的区间，继续比较，就是个正常的归并排序 代码如下 1234567891011121314151617181920212223class Solution {public: vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, ve ...

leetcode 11 盛最多水的容器 题目链接 这个题目上来根本想不到用双指针的方法（还是见得少了），动态规划搞了半天才发现用双指针是这么的简介 双指针也很好理解，就是两个指针维护左右边界，由于盛水的量其实取决于短的那块板子，所以每次更新短的那块板子，就是向里移动一个位置，每这么更新一次就算一次盛水的容量看看是不是比之前的值更大。最后返回最大值 所以我们令left=0,right=size()-1,循环的条件自然而然的是left < right 代码如下 1234567891011121314class Solution {public: int maxArea(vector<int>& height) { int n=height.size(); int l=0,r=n-1; int ret=0; while(l<r){ ret=max(ret,(r-l)*min(height[l],height[r])); if( ...

leetcode 162 寻找峰值 题目原地址 题目比较简单，就是寻找数组中的极大值，由于假定数组的两端均为负无穷，所以如果数组为单调递增或者单调递减，极值就在数组的两端 如果遍历自然是很简单的，这里就不多说，这里说下logn复杂度的二分法解法 思路也比较简单，找到中点，然后判断中点与左右两边的大小， 如果比左右两边都大，则这就是极值点，返回 如果 nums[mid−1]>nums[mid]>nums[mid+1]nums[mid-1]>nums[mid]>nums[mid+1]nums[mid−1]>nums[mid]>nums[mid+1] 则令right=mid,极值点在左侧 如果 nums[mid−1]<nums[mid]<nums[mid+1]nums[mid-1]<nums[mid]<nums[mid+1]nums[mid−1]<nums[mid]<nums[mid+1] 则令left=mid,极值点在右侧 如果 比左右两侧都小，则随便往那一侧都可以（代码中默认往右） 结束的条件跟以往不同，如果le ...

leetcode 74 搜索二维矩阵 题目链接 本来没想做这个题的，但是想做其他题的hexo new的时候不小心new错了名字，所以就顺便一写 这个题目不知道怎么混到中等题里的，就是个简单的二分搜索，只不过从用一维数组改成了二维数组 如果传入的是类似于 int mat[M][N] 这样的二维数组,直接按一位数组来取就好了，因为底层其实就是个一维数组 如果传入的是vector，则需要做一下转换，初始的left依然是0，right则是M*N-1,算出来的mid需要转换为矩阵的行号和列号（具体转换方式可以看下面代码） 由于比较简单就不多啰嗦了，下面是代码，后面可能这种披着中等题的简单题或者思路比较直白的题就不更了。 12345678910111213141516171819202122class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); int n ...

leetcode 33 搜索旋转排序数组 题目原地址 这个题需要仔细思考一下判断的条件，由于不是完全有序而是部分有序，所以不能像普通二分一样简单的判断大小 举个简单的例子 对于数组**nums=[6,7,8,9,1,2,3,4]**来说 left=0,right=8 通过二分计算出的中点idx=4 ,值为1 ，如果中点就是target，这当然皆大欢喜，直接返回对应的坐标就好 如果不是，这时候中点将数组划分成了两部分，其中至少有一部分是有序的数组，在本例中，中点右侧的**[2,3,4]**有序 那该如何判断哪边的数组有序呢，也比较简单，只需要比较nums[mid]与nums[left]的大小即可，若 nums[mid]>nums[left]nums[mid]>nums[left]nums[mid]>nums[left],则mid左侧有序，否则右侧有序。 之后我们需要比较target与num[mid]的大小，这时候也会涉及到分类讨论，由于markdown这传图片麻烦得很，就不再赘述了，自己画画图就能方便的看出，也可以看我发的连接里的官方题解里的视频讲解，那里面有图方便理解 ...

leetcode 34 在排序数组中查找元素的第一个和最后一个位置 几个月前找实习的时候刷过这道题，这几天突然碰到了结果忘了，重新记录一下 leetcode题目地址 题目简单来说是在升序的数组中找到等于target的第一个元素和最后一个元素 思路也比较简单，第一个大于target的数的前一位就是最后一个元素 , 第一个小于target的元素的后一个就是第一个元素。 于是代码如下 123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution {public: //找到第一个小于target的后一个位置 int binarySearchEx1(vector<int>& nums, int target){ int l=0;int r=nums.size()-1; int ans=-1; while(l<=r){ int mid = ...

CUDA #pragma unroll #pragma unroll,顾名思义就是CUDA中用来建议编译器展开循环的指令 使用时需要放在需要展开的循环的前面，只对他紧跟的循环有效 1234#pragma unrollfor(int i=0;i<10;i++){ //do sth} #pragma unroll 后面可以跟一个数字来指示展开的层数 1234#pragma unroll 8for(int i=0;i<16;i++){ //do sth} 如果这个整数没有指定，则默认完全展开 如果指定成1，则代表不展开 如果指定成非正数或者超过int大小的数，则会忽略这个编译指令

CUDA 笔记 一些实用函数 在调优的时候能用得到，获取一些占用率相关的信息 cudaOccupancyAvailableDynamicSMemPerBlock ( size_t dynamicSmemSize, const void func, int numBlocks, int blockSize )** 返回在当前的numBlock下（numBlock/SM）每个block能用的SMem大小 cudaOccupancyMaxActiveBlocksPerMultiprocessor ( int numBlocks, const void func, int blockSize, size_t dynamicSMemSize )** 根据当前的使用的寄存器，SMem等信息判断每个SM上能驻存的Block数。 cudaOccupancyMaxPotentialBlockSize ( int minGridSize, int blockSize, T func, size_t dynamicSMemSize = 0, int blockSizeLimit = 0 ) [inli ...

CUDA 笔记 SIMT 最近在瞎看，整理了下看的结果，主要还是来源于NVIDIA的官方文档 GPU采用了SIMT(Single-Instruction, Multiple-Thread)的架构来管理大量的并行的线程。 单线程内的指令级并行（利用pipeline） 不同线程间的thread-level并行 由于GPU面相吞吐，在单核心的执行中，没有CPU端的乱序执行和分支预测机制，且采用小端表示法 SIMT 32个线程称为一个warp，在SM上加载的若干个block以warp的单位进行调度执行，调度器称为warp scheduler。每个warp中线程的id都是连续的。 但是同一个warp作为一个并行执行单元，其内部的所有线程的执行需要同步，也就是说存在分支发散的问题。分支执行中GPU会执行这个warp中所有线程的分支并且在执行其他线程的分支时让不执行这个分支的线程等待。也是就常说的 Branch divergence ，分支发散这里不详细讲，在GPU优化中这是个重要的部分，好的分支策略往往可以明显的提升加速比。 SIMT事实上是NVIDIA提出来的概念，可以理解成升级版SIMD ...

合并有序链表 最近被问到了这个题，要求不能用额外空间，这个题的思路比较简单，由于是有序的就做一个遍历就可以，当时时间比较急写的解法代码行数较多不够简洁，再次记录一个简介的版本 用规约的话其实很容易实现，代码简洁，但是链表长度太长规约就会崩溃，再次只放递归的版本，自己面试的时候写的垃圾代码就不放了 12345678910111213141516171819202122232425262728struct Node{ int val; Node *next; Node(int _v):val(_v),next(NULL){}};Node* mergeList(Node *l1,Node *l2){ if(!l1) return l2; else if(!l2) return l1; Node* head = new Node(-1); Node* p = head; while(l1&&l2){ if(l1->val<l2->val)& ...