包含标签 C++ 的文章

阿里巴巴5月5日综合算法题详解

之前参加了阿里的笔试和电面,让后天那个敏感的日子去参加现场面,就去看了一下那天笔试的最后一道综合题,看着网上清一色最后一道题不知道从哪转的答案,不忍直视,一看代码就是错的,最直接的就是求中位数连奇偶性都不判断,直接处以2..这,另外当在无法整除的情况下,数据结果错误。  这道题的大意是:有一个淘宝商户,在某城市有n个仓库,每个仓库的储货量不同,现在要通过货物运输,将每次仓库的储货量变成一致的,n个仓库之间的运输线路围城一个圈,即1->2->3->4->…->n->1->…,货物只能通过连接的仓库运输,设计最小的运送成本(运货量*路程)达到淘宝商户的要求,并写出代码。 解题思路: 假设n个仓库的初始储货量分别为warehouse[1],warehouse[2],…,warehouse[n] 计算平均储货量 就算出来了最终的结果中,每个仓库应该有的存量 首先,从仓库1向仓库n运送k; 然后,从1到n-1,依次向下运送某一特定值,使得每一个仓库的余量都为average,剩下的问题就是求总代价的最小值了。 设第0步从1仓库向n仓库(注意因为是圆圈,所以路径长度是1)运出k存量,k可以为负,如果为负数,意味着从n向1运输|k|存量,然后从循环,从(1到n-1),从i仓库向i+1仓库运输,运输的量需要保证i仓库在运输完毕后等于average 第0步(从仓库1向仓库n运送k):花费代价为 |k|, 第1步(确保仓库1的余量为average):需要花费代价为 也就是从1向2伙从2向1运输 3. 第2步(确保仓库2的余量为average):代价为 … n-1.第n-1步:代价为 此时,仓库n剩下的货物量: 刚好也满足,其实这里不用推导,因为平均值是算好的,所以最胡一定是刚好完成的。 总的代价为: 不妨令sum[i] = warehouse[1]+warehouse[2]+…+warehouse[i]-i*average 则,总代价可表示为:|k|+|sum[1]-k|+|sum[2]-k|+…+|sum[n-1]-k| 这个式子可以看成在水平数轴上寻找一个点k,使得点k到点0,sum[1],sum[2],sum[3],…,sum[n-1]的距离之和最小,显然k应该取这n个数的中位数。至此问题解决。 给出详细注释代码:  思路借鉴了:http://hi.baidu.com/hujunjiehit/item/54204f01931ee6c49157184c 错误之处欢迎留言指出..……

阅读全文

邻接表实现无向图(C++)

很早以前写的代码了,贴出来做个备份吧。用向量来存储一条邻接链表,存储可连通值。实现了判断是否连通,添加边,添加顶点的功能。 UnDirectGraph.h UnDirectGraph.cpp 代码还算清晰,就不解释了,有问题留言反馈。谢谢。……

阅读全文

求整数1-N范围和为N的所有组合

看到的一道题,给出答案 问题:找出整数1~N范围和为N的所有集合,集合里的数不允许重复。 解答:递归吧 代码如下: 要是允许重复,也简单,将递归中的这句话改为: 同理,还可以解决类似给定一个数组,让求和为N的元素组合,只需要现将元素排个序,然后思路相同。  ……

阅读全文

引用和指针(C++)

今天在整理收藏夹的时候,又看到了这两篇非常不错的文章,关于指针和引用的,我就不翻译了,文章很简单,不过把其中我觉得很有意思的两部分结合我的理解希望说的更清楚,假定你读这篇文章之前已经知道指针,但是不是很清楚其中的部分。 首先是关于指针的一个直观的一个认识. 上面这段代码,声明了一个指针,和两个整数,指针指向第一个整数,然后输出结果(每个人的输出结果不一样)是: 这张图是这几个变量的内存分布图,上面一排是内存地址编号,正对我们的是该处的值 指针pPointer这个变量从最左边0xbff43314这个内存位置开始,占用了四个字节,这个一个指针占四个字节,大家都知道的,这个变量的值是一个地址,也就是他的指向地址。 pPointer 所指向的地址呢,是一个short int 类型的值所在的位置,在这里就是我们的twoint,twoint在内存中呢,是从0xbff4331a开始的,也就是说,我们的pPointer指向了twoint所在的地址, 注意,看一下左边四个方块前面的二进制数,转换成16进制就是0xbff4331a了 因此,取指针所指向的值就是35698了。指针本身的值则是0xbff4331a,指针所在的位置是0xbff43314。 参考文章:C++ : Understanding pointers  另一个呢是关于引用的实现原理 大家都知道,引用就是别名,比如下面这段代码 输出结果肯定一目了然,其中的原理想过没 其实,引用和指针的工作原理类似,引用变量存储了其引用变量的地址,看图  refNumber这个引用变量在内存中的值就是number这个被引用变量的地址.但和指针不同的是,引用是对一个地址的命名常量,因此,必须在声明引用的时候初始化。并且取值的时候,也不需要像指针一样加*,而是当作一个普通变量,直接用就行了。 参考文章:Pointers, References and Dynamic Memory Allocation   ……

阅读全文

倒水问题求解(C++)

明天要去参加微软面试,不求顺利,但求体验。 这个题目答题的意思是: 给你一个容量为A升的桶和一个容量为B升的桶,水不限使用,要求精确得到Q升水.请说明步骤 当数字比较小的时候,我们可以通过大脑穷举来得到结果,但这里有两个问题,当数字很大的时候怎么解?题目给定的数据是否有解? 首先判断是否有解? 题目可以理解为,x为用A的次数,y为用B的次数,Q为目标值 Q = A * x + B * y Q =目标值. Q必须是 Gcd(A,B)(也就是A,B的最大公约数)的倍数,否则无解,如果 Gcd(A,B) == 1, 任何Q都是可解的 最简单的方法就是把A的水不断的向B中倒(B向A中倒也行),知道得到最终结果,如果桶满了,就清空该桶.举个例子 A = 3, B = 4 并且 Q = 2 重复得从 A->B A B 0 0 4 0 1 3 1 0 0 1 4 1 2 3 <-A桶中得到2了 试试从 B->A A B 0 0 0 3 3 0 3 3 4 2 <- B中也得到了2 但是注意,从 B->A 比从 A->B快哦 然后我贴出代码 运行结果如下: 关于如何求最少的步数来求解这个问题,希望有朋友能够留言指教。……

阅读全文

一道笔试指针题目详解

看到本题是在搜狗某年的笔试题上,看也没人给出非常详细的讲解,直接给出了答案,我来尝试写一写, 貌似本题来源自<**The C Puzzle Book> ,**搜狗也只是换了一下字符串,直接看题吧 <span style="font-family: Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif; font-size: 13px; line-height: 19px;">请写出程序的执行结果....</span> 首先从左到右看: 再看第二行,**cp[]是一个字符,*cp[]就是一个指针,指向该字符,cp[]就是一个指针,指向该指针,而cp就成为了指针数组,内容是指向字符的指针的指针。并且通过c的元素进行了初始化 第三行,***cpp是一个字符,**cpp指向该字符,*cpp指向该指针,cpp就指向该字符的指针的指针. 然后我画一张图表示初始的情况看看 然后对于下面的输出语句,通过操作符优先级使用括号来区分一下: 这个嘛,就是把cpp后移(注意cpp已经改变了)然后就指向了cp[1],然后两次取其值即可得到AMAZI 推导过程如下: 最后  cpp还是之前的cp[2],cpp[-1][-1]相当于*(*(cpp-1)-1),先减1指向了cp[1],取一次值就是c[2]了,然后c[2]-1就成为c[1]了,然后+1之后就是ST了. 所以,最后输出就是 AMAZINGBEST 错误之处还望指正.   ……

阅读全文

模板优先级队列及堆排序(C++实现)

模板优先级队列,数组实现,再熟悉一下常用算法,同时简单的堆排序应用 写了一个是队列自增长,另一个为了演示我还添加了一个叫做FillPq的方法,这个方法可以使用一个数组直接填充到优先级队列里,此时,优先级队列并不优先,然后进行下滤调整,之后建堆完成,输出即可 然后是堆排序  ……

阅读全文

模板栈以及中缀表达式求值(C++实现)

栈直接用链表实现,这个比较简单,不多说,不过C++写程序,IDE的错误检测不是很给力。 至于给定一个中缀表达式,如何不转换成后缀表达式,直接求值,方法就是使用两个栈,一个操作符栈,一个操作数栈,然后从左到右扫描表达式,我这里中缀表达式计算实现的很简单,不完整,大家可以扩展。栈的实现是我想写的,思路如下: 1.如何是操作数,压入操作数栈 2.如果是操作符,压入操作符栈 3.如果是左括号,直接忽略 4.如果是有括号,弹出操作符栈栈顶元素,然后弹出操作数栈两个元素,进行操作以后结果压入操作数栈  看个图就好了  最后给出栈顶实现代码 然后是main函数代码 另外,今天是博客建站一周年.加油!……

阅读全文

并查集(C++实现)

并查集这个很有意思,并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。昨天看书看到了,然后用C++简单实现了下。在Dijkstra算法中,用来判断两个顶点是否在同一个集合里。 里面定义了两个类,都是并查集,一个是QuickFind,查找很快,一个是QuickUnion,合并较快。写了一些注释,有一些优化的提示.看代码吧,有什么问题指出来吧。 QuickFind的实现 QuickUnion的实现 参考文档(英文):UnionFind.pdf 工程代码下载:并查集Demo……

阅读全文

和 浅析

这两个转义字符最初学习C++的时候看到了,当时没多想,后来某一天突然想起来,回车不就是换行吗?这不是多此一举吗?今天又看到,索性查了下相关资料,整理一下,留作记录. 关于“回车”(carriage return)和“换行”(line feed)这两个概念的来历和区别。 在计算机还没有出现之前,有一种叫做电传打字机(Teletype Model 33)的玩意,每秒钟可以打10个字符。但是它有一个问题,就是打完一行换行的时候,要用去0.2秒,正好可以打两个字符。要是在这0.2秒里面,又有新的字符传过来,那么这个字符将丢失。 于是,研制人员想了个办法解决这个问题,就是在每行后面加两个表示结束的字符。一个叫做“回车”,告诉打字机把打印头定位在左边界;另一个叫做“换行”,告诉打字机把纸向下移一行(这句的意思是把纸向上拉,然后打印头就定位到了下一行),可以想象一下,这个打印头只能在一个固定的水平线上左右移动,而不能上下移动,我们通过移动纸来完成打印下一行。 不明白的我在youtube上找到一个这种打字机的演示视频,为了方便读者观看,我提供一个下载地址。 后来,计算机发明了,这两个概念也就被般到了计算机上。那时,存储器很贵,一些科学家认为在每行结尾加两个字符太浪费了,加一个就可以。于是,就出现了分歧。 Unix系统里,每行结尾只有”<换行>",即”\n”; Windows系统里面,每行结尾是”<换行><回车>",即”\n\r”; Mac系统里,每行结尾是”<回车>",不过mac基于unix,所以换行也应该是可以的。 一个直接后果是,Unix/Mac系统下的文件在Windows里打开的话,所有文字会变成一行;而Windows里的文件在Unix/Mac下打开的话,在每行的结尾可能会多出一个^M符号。这个如果你在windows下使用vim也会发现这个情况 用C++来说明 如:  最后只显示 bystander 而 leaver.me 背覆盖了 \n 是换行,系统会将其替换成回车+换行 把光标 先移到 行首 然后换到下一行 也就是 下一行的行首拉 则 显示 leaver.me bystander 一句话,这看起来是一个历史遗留问题…………

阅读全文