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

之前参加了阿里的笔试和电面,让后天那个敏感的日子去参加现场面,就去看了一下那天笔试的最后一道综合题,看着网上清一色最后一道题不知道从哪转的答案,不忍直视,一看代码就是错的,最直接的就是求中位数连奇偶性都不判断,直接处以2..这,另外当在无法整除的情况下,数据结果错误。   这道题的大意是:有一个淘宝商户,在某城市有n个仓库,每个仓库的储货量不同,现在要通过货物运输,将每次仓库的储货量变成一致的,n个仓库之间的运输线路围城一个圈,即1->2->3->4->…->n->1->…,货物只能通过连接的仓库运输,设计最小的运送成本(运货量*路程)达到淘宝商户的要求,并写出代码。 解题思路: 假设n个仓库的初始储货量分别为warehouse[1],warehouse[2],…,warehouse[n] 计算平均储货量 average = (warehouse[1]+warehouse[2]+…+warehouse[n])/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):需要花费代价为 |warehouse[1]-average-k| 也就是从1向2伙从2向1运输 第2步(确保仓库2的余量为average):代价为 |warehouse[2]+warehouse[1]-average-k-average|=|warehouse[1]+warehouse[2]-2*average-k| … n-1.第n-1步:代价为 |warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k| 此时,仓库n剩下的货物量: (warehouse[n]+k)+warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k=(warehouse[1]+warehouse[2]+…+warehouse[n])-(n-1)*average=average 刚好也满足,其实这里不用推导,因为平均值是算好的,所以最胡一定是刚好完成的。 总的代价为: |k|+|warehouse[1]-average-k|+|warehouse[1]+a[2]-2*average-k|+…+|warehouse[1]+warehouse[2]+…+warehouse[n-1]-(n-1)*average-k| 不妨令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个数的中位数。至此问题解决。 给出详细注释代码:   #include “stdafx.h” #include <iostream> #include <algorithm> #include<string> using namespace std; const int X = 100000; double sum[X],warehouse[X]; int n; double Abs(double x) { return max(x,-x); } int _tmain(int argc, _TCHAR* argv[]) { while(true) { double total = 0; double mid=0; cout<<“请输入仓库数目:”; cin>>n; //读入n个仓库的值,并计算总数 for(int i=1;i<=n;i++) { cout<<“请输入第”<<i<<“个仓库的存量:”; cin>>warehouse[i]; total += warehouse[i]; } //计算每个仓库应该最终存储的值 double average = total/n; //计算sum数组 for(int i=1;i<n;i++) sum[i] = warehouse[i]+sum[i-1]-average; //排序后打算去中位数 //sort采用半开半闭区间,所以排序为0~n-1 sort(sum,sum+n); //这个可以自己举个数字就知道了 if(n%2! [Read More]

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

很早以前写的代码了,贴出来做个备份吧。用向量来存储一条邻接链表,存储可连通值。实现了判断是否连通,添加边,添加顶点的功能。 UnDirectGraph.h #pragma once #include “stdafx.h” #include <vector> using namespace std; class UnDirectGraph { private: int vCount; vector<int> *adj; public: int GetVCount(); UnDirectGraph(int vCount); void AddEdge(int v,int w); vector<int> &Vadj(int v); bool IsConnected(int v,int w); }; UnDirectGraph.cpp #pragma once #include “stdafx.h” #include “UnDirectGraph.h” using namespace std; UnDirectGraph::UnDirectGraph(int _vCount) { this->vCount=_vCount; adj=new vector<int>[vCount]; for (int i=0;i&lt;vCount;i++) { adj[i].clear(); } } void UnDirectGraph::AddEdge(int v,int w) { adj[v].push_back(w); adj[w].push_back(v); } vector<int>& UnDirectGraph::Vadj(int v) { return adj[v]; } [Read More]

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

看到的一道题,给出答案 问题:找出整数1~N范围和为N的所有集合,集合里的数不允许重复。 解答:递归吧 代码如下: #include “stdafx.h” #include <iostream> using namespace std; void PrintResult(int *log,int index) { for (int i = 0; i <index; ++i) { cout<<log[i]<<” “; } cout<<endl; } void CalCombination(int* log,int startNum,int N,int &index) { if (N==0) { PrintResult(log,index); } else { for (int i = startNum; i &lt;= N; ++i) { log[index++]=i; CalCombination(log,i+1,N-i,index); } } index--; } int _tmain(int argc, _TCHAR* argv[]) { cout<<“请输入N:“; int N=20; cin>>N; int *log=new int[N]; int index=0; CalCombination(log,1,N,index); } 要是允许重复,也简单,将递归中的这句话改为: CalCombination(log,i,N-i,index); 同理,还可以解决类似给定一个数组,让求和为N的元素组合,只需要现将元素排个序,然后思路相同。 [Read More]

引用和指针(C++)

今天在整理收藏夹的时候,又看到了这两篇非常不错的文章,关于指针和引用的,我就不翻译了,文章很简单,不过把其中我觉得很有意思的两部分结合我的理解希望说的更清楚,假定你读这篇文章之前已经知道指针,但是不是很清楚其中的部分。 首先是关于指针的一个直观的一个认识. #include <iostream> int main() { using namespace std; // 声明并初始化指针. unsigned short int * pPointer = 0; // 定义一个unsigned short int 变量 值为35698 unsigned short int twoInt = 35698; // 定义一个unsigned short int 变量 值为 77 unsigned short int oneInt = 77; // 使用&操作符将twoInt的地址赋给指针 pPointer = &twoInt; // pPointer 现在的值就是twoInt的地址了 // 打印 cout << “pPointer的内存地址:\t\t” << &pPointer << endl; cout << “oneInt的内存地址:\t” << &oneInt << “\t整数值:\t” << oneInt << endl; cout << “twoInt的内存地址:\t” << &twoInt << “\t整数值:\t” << twoInt << endl; cout << “pPointer所指向的地址(也就是pPoint的值):\t” << pPointer << “\t整数值:\t” << *pPointer << endl; [Read More]

倒水问题求解(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快哦 [Read More]

一道笔试指针题目详解

看到本题是在搜狗某年的笔试题上,看也没人给出非常详细的讲解,直接给出了答案,我来尝试写一写, 貌似本题来源自<The C Puzzle Book> ,搜狗也只是换了一下字符串,直接看题吧 #include <stdio.h> char *c[]={“ENTNG”, “NST”,“AMAZI”,“FIRBE”}; char** cp[]={c+3, c+2, c+1, c}; char *cpp= cp; int main() { printf(“%s”,++cpp); printf(“%s “,–++cpp+3); printf(“%s”,*cpp[-2]+3); printf(“%s”,cpp[-1][-1]+1); } <span style="font-family: Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif; font-size: 13px; line-height: 19px;">请写出程序的执行结果....</span> 首先从左到右看: char *c[]= { “ENTNG”, “NST”, “AMAZI”, “FIRBE” }; *c[] 是一个字符,因此,c[]是指向该字符,c就是一个数组(数组的内容为指向字符的指针),c已经被初始化了. char** cp[]={c+3, c+2, c+1, c}; 再看第二行,**cp[]是一个字符,*cp[]就是一个指针,指向该字符,cp[]就是一个指针,指向该指针,而cp就成为了指针数组,内容是指向字符的指针的指针。并且通过c的元素进行了初始化 char cpp= cp; 第三行,cpp是一个字符,**cpp指向该字符,*cpp指向该指针,cpp就指向该字符的指针的指针. 然后我画一张图表示初始的情况看看 然后对于下面的输出语句,通过操作符优先级使用括号来区分一下: ((++cpp)); 这个嘛,就是把cpp后移(注意cpp已经改变了)然后就指向了cp[1],然后两次取其值即可得到AMAZI 推导过程如下: ++cpp -> cp[1] // cp[1] -> c+2 ++cpp = &cp[1] // &(c+2) *++cpp = *(&c+2) // c[2] **++cpp = &c[2] 然后看第二个 ((–(*(++cpp))))+3; 加括号后如上,cpp再加一,就指向了cp[2],取一次值(也就是号)就变成了c[1],然后–c[1]就指向了c[0],取值就成了c[0]的地址,然后地址+3,就是NG了 ((cpp[-2]))+3; 上面,cpp指向cp[2]了,然后呢,cpp[-2] 相当于*(cpp-2),间接引用cp[2],这样cpp[-2]就指向了cp[0]了,然后,就是FIRBE了,加3就是BE了 [Read More]

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

模板优先级队列,数组实现,再熟悉一下常用算法,同时简单的堆排序应用 写了一个是队列自增长,另一个为了演示我还添加了一个叫做FillPq的方法,这个方法可以使用一个数组直接填充到优先级队列里,此时,优先级队列并不优先,然后进行下滤调整,之后建堆完成,输出即可 #include “stdafx.h” template< class T> class PriorityQueue { private: T *pq; int N; int capacity; public: PriorityQueue(void); ~PriorityQueue(void); void Insert(T x); T DelTop(); void Swim(int k); void Sink(int k); bool Less(int i,int j); void Swap(int i,int j); bool Resize(); void FillPq(T arr[],int size); }; template< class T> void PriorityQueue<T>::FillPq( T arr[],int size ) { N=size; capacity=2*size; for (int i=0;i<size;i++) { pq[i+1]=arr[i]; } } template< class T> PriorityQueue<T>::PriorityQueue(void) { pq=new T[10]; N=0; capacity=10; } [Read More]

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

栈直接用链表实现,这个比较简单,不多说,不过C++写程序,IDE的错误检测不是很给力。 至于给定一个中缀表达式,如何不转换成后缀表达式,直接求值,方法就是使用两个栈,一个操作符栈,一个操作数栈,然后从左到右扫描表达式,我这里中缀表达式计算实现的很简单,不完整,大家可以扩展。栈的实现是我想写的,思路如下: 1.如何是操作数,压入操作数栈 2.如果是操作符,压入操作符栈 3.如果是左括号,直接忽略 4.如果是有括号,弹出操作符栈栈顶元素,然后弹出操作数栈两个元素,进行操作以后结果压入操作数栈   看个图就好了   最后给出栈顶实现代码 #include “stdafx.h” #pragma region Node定义 template <class T> class Node { template<class T> friend class Stack; private: T m_data; Node *pNextNode; public: Node(); Node(T d); }; template <class T> Node<T>::Node() { m_data=default(T); pNextNode=NULL; } template <class T> Node<T>::Node(T d) { m_data=d; pNextNode=NULL; } #pragma endregion #pragma region Stack定义 template <class T> class Stack { private: Node<T> *m_pTopNode; int m_nNodeCount; public: Stack(); ~Stack(); bool IsEmpty(); bool Push(T e); T Pop(); int Size(); }; [Read More]

并查集(C++实现)

并查集这个很有意思,并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。昨天看书看到了,然后用C++简单实现了下。在Dijkstra算法中,用来判断两个顶点是否在同一个集合里。 里面定义了两个类,都是并查集,一个是QuickFind,查找很快,一个是QuickUnion,合并较快。写了一些注释,有一些优化的提示.看代码吧,有什么问题指出来吧。 QuickFind的实现 #include “QuickFind.h” QuickFind::QuickFind(int N) { size=N; id=new int[N]; for(int i=0;i<N;i++) { id[i]=i; } } bool QuickFind::Find(int p,int q) { return id[p]==id[q]; } void QuickFind::Unite(int p,int q) { int pid=id[p]; for(int i=0;i<size;i++) if(id[i]==pid) id[i]=id[q]; } QuickFind::~QuickFind(void) { delete []id; } QuickUnion的实现 #include “QuickUnion.h” QuickUnion::QuickUnion(int N) { size=N; id=new int[N]; for(int i=0;i<N;i++) { id[i]=i; } } int QuickUnion::root(int i) { while (i!=id[i]) { //id[i]=id[id[i]]; 若添加这句话则为压缩路径 i=id[i]; } return i; } bool QuickUnion::Find(int p,int q) { return root(p)==root(q); } [Read More]

和 浅析

这两个转义字符最初学习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++来说明

如:

int main()
{
   cout << “leaver.me” << “\r” << “bystander” ;
   return 0;
}
 

最后只显示 bystander 而 leaver.me 背覆盖了

\n 是换行,系统会将其替换成回车+换行 把光标 先移到 行首 然后换到下一行 也就是 下一行的行首拉

int main()
{
   cout << “leaver.me” << “\n” << “bystander” ;
   return 0;
}
则 显示

leaver.me

bystander

一句话,这看起来是一个历史遗留问题……