美团网哈工大研发2014笔试
转载请注明引用 ：blog.csdn.net/makamus 版权所有@makamus欢迎大家关注本人博客，技术交流请加QQ:508742012

1、一堆硬币，一个机器人，如果是反的就翻正，如果是正的就抛掷一次，无穷多次后，求正反的比例
首先设硬币的正反概率分别为p正 、 p反 ，第一次后p正1= p反+1/2p正 ，p反1= 1/2p正 2、概率题：一个汽车公司的产品，甲厂占40%，乙厂占60%，甲的次品率是1%，乙的次品率是2%，现在抽出一件汽车是次品，问是甲生产的可能性
甲的次品占公司40%* 1%=0.004；乙次品占公司产品60%*2%=0.012；总次品占所有产品为0.016；现已知是次品，则为甲的概率为1/4=25%。
3、 有100盏灯（它们的位置编号为1， 2 .. 99，100），刚开始全都是灭着的。第一次把所有的灯都打开，第二次把偶数位置上的灯灭了，第三次把位置是3的倍数的灯原来灭的打开，原来打开着的，灭了。第N次把位置是N的倍数的灯原来灭的打开，原来打开着的，灭了。问第100次后还有多少盏灯亮着的？
int arrDeng[101];void doWithArr(int arr[],int n){/*memset(arr,0,101);*/int k;for(int i=1;i<=100;i++){k=1;while(i*k<=100){if(arr[i*k]==0){arr[i*k]=1;}else{arr[i*k]=0;}k++;}}for(int i=1;i<=100;i++){if(arr[i]==1){printf("%d",i);}
}}

来源于[http://www.howwant.com/category/brain-food/]有100盏灯，从1~100编上号，开始时所有的灯都是关着的。
第一次，把所有编号是1的倍数的灯的开关状态改变一次；
第二次，把所有编号是2的倍数的灯的开关状态改变一次；
第三次，把所有编号是3的倍数的灯的开关状态改变一次；
以此类推，直到把所有编号是100的倍数的灯的开关状态改变一次。
问，此时所有开着的灯的编号。

【分析】

由于最开始灯是灭的，那么只有经过奇数次改变开关状态的灯是亮的。根据题意可知一个数字有多少约数就要开关多少次，所以最后亮着的灯的数学解释就是：灯的编号有奇数个不同的约数。
一个数的约数按出现的奇偶个数分为以下两种：
 约数是成对出现的，比如8的约数对为：（1，8）、（2，4）。
 约数是单个出现的，比如36的约数对为：（1，36）、（2，18）、（3，12）、（4，9）、（6）。
可以看出6自己单独是36的约数，而不是和别的数连在一起。所以只有平方数才会有奇数个整型约数，才满足本题的要求。从1到100的平方数为：
1，4，9，16，25，36，49，64，81，100。
所以只有这些灯是亮的。

【答案】

编号为1，4，9，16，25，36，49，64，81，100的灯是亮的。

说明：本题是一道数学类型题目，但是绝对不能用简单的计算法来解决本题，那样的计算量太庞大，所以用分析法加计算法来分析才是正确简单的解决本题的最佳途径。

4、链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现

struct ListNode{ int m_nValue; ListNode* m_pNext;};
ListNode* reverse(ListNode **head){ListNode *p,*r,*pHead=*head;if(pHead&&pHead->m_pNext){p=pHead;r=p->m_pNext;p->m_pNext=NULL;while(r){p=r;r=r->m_pNext;p->m_pNext=pHead;pHead=p;}}return pHead;}
ListNode* reversePerKNode(ListNode* head,int k){if(head==NULL||k<2)return head;int i=0;ListNode *p=head,*pre=NULL,*tp=NULL;while(p){ ListNode *PH=p; i=0; while(p&&i<k){i++;pre=p;p=p->m_pNext; } pre->m_pNext=NULL; if(i==k){ if(tp==NULL){ tp=reverse(&PH); head=tp; tp=PH; }else{ tp->m_pNext=reverse(&PH); tp=PH; } }else{ tp->m_pNext=PH; }
}return head;}5、一个函数access(),调用频率不能超过R次/sec，用程序实现一个函数，当超过R次/sec时返回access false，不超过时返回success
int g_count;access(){ g_count++;}

bool method(){ time_t start,finish; time(&start); delay(5); time(&finish); if(g_count/(finish-start)>R) return false;
else return success;}
6、一个m*n的矩阵，从左到右从上到下都是递增的，给一个数elem，求是否在矩阵中，给出思路和代码首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找数（6）的小就往下走，直到找到要找的数字（6）为止bool findFun(int *arr,int m,int n,int t){int i=0,j=n-1;while(i<m&&j>=0){if( *(arr+i*n+j)>t)j--;else if(*(arr+i*n+j)<t)i++;elsereturn true;}return false;}JAVA版 public static int find(int arr[][],int m,int n, int t){ int i=0,j=n-1; while(i<m&&j>=0){ if(arr[i][j]>t)j--; else if(arr[i][j]<t)i++; elsereturn 1; } return -1; }