面试题

面试题

pc蛋蛋预测中奖95%软件群8887209-误会

回复

面试appoil 发起了问题 • 1 人关注 • 0 个回复 • 38 次浏览 • 5 天前 • 来自相关主题

『阿里面试题』组合排序问题

面试 回复了问题 • 17 人关注 • 6 个回复 • 3387 次浏览 • 2017-08-14 10:46 • 来自相关主题

廿青春,共前行——2018网易互联网校招内推开启

回复

内推小易推推 回复了问题 • 2 人关注 • 1 个回复 • 291 次浏览 • 2017-07-29 11:58 • 来自相关主题

新浪微博的机器学习工程师 和 阿里巴巴高德 的机器学习工程师 去哪个?技术哪个强一点?还有口碑什么的?多谢大神指教

面试寒老师 回复了问题 • 4 人关注 • 2 个回复 • 801 次浏览 • 2016-10-24 10:40 • 来自相关主题

一起刷leetcode(78):Subsets

leetcode/kaggleMrFat 回复了问题 • 6 人关注 • 3 个回复 • 1760 次浏览 • 2016-08-08 22:02 • 来自相关主题

C++面试知识点

回复

面试JoyceWYJ 发起了问题 • 4 人关注 • 0 个回复 • 823 次浏览 • 2016-07-08 12:47 • 来自相关主题

一起刷LeetCode(226): Invert Binary Tree

leetcode/kaggleJoyceWYJ 回复了问题 • 2 人关注 • 2 个回复 • 317 次浏览 • 2016-06-29 18:44 • 来自相关主题

干货分享——机器学习与大数据的面试问题与答题思路

面试wuyou123 回复了问题 • 12 人关注 • 2 个回复 • 1004 次浏览 • 2016-06-14 21:33 • 来自相关主题

阿里巴巴实习面经——天猫部

回复

面试JoyceWYJ 发起了问题 • 3 人关注 • 0 个回复 • 886 次浏览 • 2016-05-25 11:02 • 来自相关主题

[阿里]逆序打印整数,要求递归实现

面试小付fu 回复了问题 • 33 人关注 • 24 个回复 • 3802 次浏览 • 2016-03-14 21:15 • 来自相关主题

#每日一面BAT#第24题 约数博弈

面试hulala 回复了问题 • 7 人关注 • 2 个回复 • 1477 次浏览 • 2016-03-11 18:30 • 来自相关主题

抛个问题出来,大家想想

面试July 回复了问题 • 7 人关注 • 5 个回复 • 1853 次浏览 • 2015-10-05 14:44 • 来自相关主题

[大众点评]N个未排序的整数,在线性时间内,求N个整数在数轴上相邻两个数之间的最大差值。

面试邹博 回复了问题 • 5 人关注 • 3 个回复 • 1554 次浏览 • 2015-09-30 17:15 • 来自相关主题

[小米]首尾相连数组的最大子数组和

面试zhangenwei 回复了问题 • 4 人关注 • 2 个回复 • 1337 次浏览 • 2015-09-12 19:01 • 来自相关主题

【腾讯面试】 如何对1亿个QQ号进行排序

面试czmbit 回复了问题 • 42 人关注 • 15 个回复 • 6505 次浏览 • 2015-09-10 19:56 • 来自相关主题

【腾讯】新闻推荐中按照一定策略从排好序的新闻列表中选择新闻

面试pnghwang 回复了问题 • 5 人关注 • 2 个回复 • 1004 次浏览 • 2015-08-31 19:57 • 来自相关主题

[百度]随机播放音乐(随机数相关)

面试klzhan 回复了问题 • 74 人关注 • 25 个回复 • 7171 次浏览 • 2015-08-30 17:29 • 来自相关主题

腾讯面试题:字符串匹配。

面试lidasong 回复了问题 • 29 人关注 • 10 个回复 • 5210 次浏览 • 2015-08-27 09:35 • 来自相关主题

#每日一面BAT#第10题:汽车最大补给

算法zhouge 回复了问题 • 19 人关注 • 5 个回复 • 1682 次浏览 • 2015-08-26 19:39 • 来自相关主题

[阿里巴巴二面]两个字符串A、B,从A中剔除存在于B中的字符。

面试sd1527907 回复了问题 • 37 人关注 • 16 个回复 • 4183 次浏览 • 2015-08-26 17:11 • 来自相关主题

【微软】设计魔方的数据结构

面试solocode 回复了问题 • 9 人关注 • 2 个回复 • 1659 次浏览 • 2015-08-25 18:48 • 来自相关主题

#每日一面BAT#第23题 区间最大重叠

回复

面试cpcs 回复了问题 • 5 人关注 • 1 个回复 • 1694 次浏览 • 2015-08-22 22:36 • 来自相关主题

阿里面试题:强强对话的概率

面试rcgn 回复了问题 • 33 人关注 • 21 个回复 • 4250 次浏览 • 2015-08-20 17:00 • 来自相关主题

2015年阿里研发工程师实习笔试附加题

面试张小朋要奋斗 回复了问题 • 33 人关注 • 13 个回复 • 7050 次浏览 • 2015-08-19 11:42 • 来自相关主题

阿里云-多线程设计题

面试Wen_nian 回复了问题 • 9 人关注 • 2 个回复 • 1550 次浏览 • 2015-08-16 15:14 • 来自相关主题

设计题-服务器流量统计器

回复

面试talentlei 发起了问题 • 4 人关注 • 0 个回复 • 964 次浏览 • 2015-08-13 16:20 • 来自相关主题

#每日一面BAT#第22题 木杆蚂蚁

面试YangL 回复了问题 • 6 人关注 • 2 个回复 • 1320 次浏览 • 2015-08-13 08:46 • 来自相关主题

#每日一面BAT#第21题 下标三元组

回复

面试cpcs 回复了问题 • 7 人关注 • 1 个回复 • 1409 次浏览 • 2015-08-12 04:42 • 来自相关主题

#每日一面BAT#第11题 环形跑道

面试YangL 回复了问题 • 8 人关注 • 3 个回复 • 1870 次浏览 • 2015-08-11 21:04 • 来自相关主题

#每日一面BAT#第20题 绳子覆盖点

回复

面试cpcs 回复了问题 • 5 人关注 • 1 个回复 • 850 次浏览 • 2015-08-11 13:23 • 来自相关主题

2015阿里巴巴校招电面一面题目分享~求细致完整的解答~

面试YangL 回复了问题 • 16 人关注 • 4 个回复 • 2926 次浏览 • 2015-08-10 22:35 • 来自相关主题

#每日一面BAT#第19题 子序列的个数

回复

算法cpcs 回复了问题 • 6 人关注 • 1 个回复 • 1001 次浏览 • 2015-08-10 02:32 • 来自相关主题

#每日一面BAT#第18题 取石子游戏

面试柳梦璃 回复了问题 • 9 人关注 • 3 个回复 • 970 次浏览 • 2015-08-08 22:47 • 来自相关主题

#每日一面BAT#第17题 RGB字符串

面试天天 回复了问题 • 6 人关注 • 2 个回复 • 889 次浏览 • 2015-08-08 19:34 • 来自相关主题

#每日一面BAT#第1题:概率与集合元素个数

算法Janvn 回复了问题 • 10 人关注 • 4 个回复 • 1525 次浏览 • 2015-08-07 18:56 • 来自相关主题

#每日一面BAT#第16题 最大指数

面试EagleSky 回复了问题 • 5 人关注 • 1 个回复 • 952 次浏览 • 2015-08-07 10:18 • 来自相关主题

#每日一面BAT#第15题 a[x] == x

面试cpcs 回复了问题 • 5 人关注 • 2 个回复 • 943 次浏览 • 2015-08-06 17:08 • 来自相关主题

用公平的硬币模拟 1/Pi概率?

算法cpcs 回复了问题 • 5 人关注 • 2 个回复 • 1083 次浏览 • 2015-08-06 13:51 • 来自相关主题

#每日一面BAT#第14题 机器人指令序列

回复

面试cpcs 回复了问题 • 2 人关注 • 1 个回复 • 944 次浏览 • 2015-08-05 11:34 • 来自相关主题

#每日一面BAT#第3题:循环染色问题

算法天天 回复了问题 • 11 人关注 • 4 个回复 • 1895 次浏览 • 2015-08-04 23:34 • 来自相关主题

#每日一面BAT#第13题 方程的正整数解

面试cpcs 回复了问题 • 5 人关注 • 3 个回复 • 930 次浏览 • 2015-08-04 11:12 • 来自相关主题

2015百度校招一面题目分享~

面试园园啊圈圈_oo 回复了问题 • 15 人关注 • 3 个回复 • 3020 次浏览 • 2015-08-04 10:41 • 来自相关主题

『腾讯面试题』类成员存储问题。

面试天天 回复了问题 • 8 人关注 • 2 个回复 • 2425 次浏览 • 2015-08-03 23:56 • 来自相关主题

#每日一面BAT#第12题 文章与词

回复

面试cpcs 回复了问题 • 2 人关注 • 1 个回复 • 782 次浏览 • 2015-08-03 12:15 • 来自相关主题

[腾讯面试题]一个大小为N的数组,里面是N个整数,怎样去除重复。

面试天天 回复了问题 • 41 人关注 • 14 个回复 • 4882 次浏览 • 2015-07-28 09:10 • 来自相关主题

一道关于数据库的面试题

面试张_晓龙在人人 回复了问题 • 6 人关注 • 2 个回复 • 933 次浏览 • 2015-07-24 13:58 • 来自相关主题

[百度面试题]数组A中任意两个相邻元素大小相差1,在其中查找某个数。

面试Miku 回复了问题 • 42 人关注 • 19 个回复 • 4477 次浏览 • 2015-07-20 17:57 • 来自相关主题

腾讯面试题:给40亿个不重复的unsigned int的数,没排序,然后再给一个数,如何快速间断这个数是否在那40亿个数中

面试littletiger 回复了问题 • 14 人关注 • 5 个回复 • 4106 次浏览 • 2015-07-15 15:49 • 来自相关主题

#每日一面BAT#第9题:男女比例问题

算法邹博 回复了问题 • 9 人关注 • 5 个回复 • 1419 次浏览 • 2015-07-14 20:23 • 来自相关主题

#每日一面BAT#第2题:三字符构成的字符串个数

算法永不停息的狮子 回复了问题 • 20 人关注 • 6 个回复 • 2469 次浏览 • 2015-07-14 10:56 • 来自相关主题

条新动态, 点击查看
July

July 回答了问题 • 2015-01-24 13:02 • 7 个回复 不感兴趣

给你印象最深的一道面试题是什么?

赞同来自:

刚毕业那会,面过不少公司,没看到什么好的面试题。
稍有点印象的是杨氏矩阵查找。

在一个m行n列的二维数组中,每一行都按照从左到右递增的顺序排列,每一列都按照从上到下递增的顺序排列。现输入这样的一个二维数组和一个整数,请完成一个函数,判断数组中是否含有该整数。... 显示全部 »
刚毕业那会,面过不少公司,没看到什么好的面试题。
稍有点印象的是杨氏矩阵查找。

在一个m行n列的二维数组中,每一行都按照从左到右递增的顺序排列,每一列都按照从上到下递增的顺序排列。现输入这样的一个二维数组和一个整数,请完成一个函数,判断数组中是否含有该整数。
例如给定如下图所示的二维数组,它的每一行、每一列都递增排序。如果在这个数组中查找数字6,则返回true;如果查找数字5,则由于该数组不含有数字5,返回false。
** 插入的附件 **
虽然后来知道这题有两种解法:
解法一:分治法
以查找数字6为例,因为矩阵的行和列都是递增的,所以整个矩阵的对角线上的数字也是递增的,故我们可以在对角线上进行二分查找:如果要找的数的大小介于对角线上相邻的两个数之间,则可以排除掉左上和右下的两个小矩形,而在左下和右上的两个小矩形内继续递归查找。如下图所示:
** 插入的附件 **
解法二:定位法
如下图所示,首先直接定位到矩阵中最右上角的元素,如果这个元素比要找的数6大就往左走,比要找的数6小就往下走,直到找到要找的数字6为止。这个方法的时间复杂度是O(m+n)。
** 插入的附件 **
但当时确实没有想到解法二。
helifort

helifort 回答了问题 • 2015-01-28 18:40 • 6 个回复 不感兴趣

Yahoo on site 面试题2道 最新

赞同来自:

第一题,如果没有空间限制,最简单的是用一个stack 保存前半部分的节点,然后挨个比较后半部的节点,要注意如果奇数情况的处理

要求空间O(1)的话,就比较麻烦,算法是这样
1 快慢指针找到中点,把链表分成两部分
2 原地翻转后部分链表,重点是要原地翻转,所以... 显示全部 »
第一题,如果没有空间限制,最简单的是用一个stack 保存前半部分的节点,然后挨个比较后半部的节点,要注意如果奇数情况的处理

要求空间O(1)的话,就比较麻烦,算法是这样
1 快慢指针找到中点,把链表分成两部分
2 原地翻转后部分链表,重点是要原地翻转,所以不能用递归,不过我觉得递归还不好理解,循环好理解,以下是原地翻转链表的代码,是这个算法的核心,这个搞定其他都不是很麻烦。

{{{
ListNode current = head;
ListNode pre = null;
ListNode next = null;

while (current != null) {
//record second node
next = current.next;
current.next = pre;
pre = current;
current = next;
}
return pre;
}}}

3 比较前部分和翻转后的部分的节点是否相等
4 再把后部分翻转回来接上
1,对集合S进行排序(快排),从小到大排序
2,让C指向集合最后一个元素(最大元素)
3,让i指向S中第一个元素,让j指向C的前一个元素
4,如果,A[i]+A[j]==C则return C;
5,如果if(A[i]+A[j]<C)则i++;
6,如果i... 显示全部 »
1,对集合S进行排序(快排),从小到大排序
2,让C指向集合最后一个元素(最大元素)
3,让i指向S中第一个元素,让j指向C的前一个元素
4,如果,A[i]+A[j]==C则return C;
5,如果if(A[i]+A[j]<C)则i++;
6,如果if(A[i]+A[j]>C)则j--;
7,直道i>=j依然没有找到符合条件的元素,则C在S中向前移动一位,跳至步骤3

{{{
/+++++++++++++++++++++++++++++++++++++++++++++++++++++++
* 日期:2015-01-29
* 作者:SJF0115
* 题目: 在由N个正整数的集合S中,找出最大元素C,满足C=A+B,其中A,B都是集合S中的元素
* 来源:百度
* 博客:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
#include <iostream>
#include <algorithm>
using namespace std;

int FindSum(int A[],int n){
// 排序
sort(A,A+n);
int left,right,sum;
// i = C
for(int i = n - 1;i >= 2;--i){
left = 0,right = i - 1;
// 判断是否有A + B = i
while(left < right){
sum = A[left] + A[right];
if(sum == A[i]){
return A[i];
}//if
else if(sum > A[i]){
--right;
}
else{
++left;
}
}//while
}//for
return -1;
}

int main(){
int A[] = {5,7,3,0,9,11,8,13,100};
int n = 9;
cout<<FindSum(A,n)<<endl;;
return 0;
}

}}}
==========================
声明:以下是我不负责任的瞎扯
==========================

首先要知道一个东西:
要判断一个数字是否为素数所要花费的时间是O(1)
如果你不知道这个,那么随便拿一本厚一点的算法书(... 显示全部 »
==========================
声明:以下是我不负责任的瞎扯
==========================

首先要知道一个东西:
要判断一个数字是否为素数所要花费的时间是O(1)
如果你不知道这个,那么随便拿一本厚一点的算法书(注意,不是数据结构书),一般会在“随机算法”章节

==========================================
解法一(从素数角度出发):
首先,任何一个大于6的素数都可以写成6n±1的形式,为什么呢?因为任何一个数都可以写成6n, 6n+1,6n+2, 6n+3, 6n+4, 6n+5这几个形式,而其中6n, 6n+2, 6n+3, 6n+4这几个形式的数都不可能是素数,因为都能被2或3整除。而6n+5实际上也可以看做是6n-1,证明完毕。
但是这是一个必要不充分条件,也就是

一个数是素数,则一定可以写成6n±1中的一个形式
但是一个数可以写成6n±1形式,但他不一定是素数

所以我们要加入素性判断

然后你就在[6, N]这个区间中寻找满足6n±1形式的数,然后对这些数进行素性判断,最后就得到[6, N]区间的所有素数的
得到所有素素,只需要对他们两两求和就行啦。

复杂度分析比较麻烦,涉及到[6, N]中有多少个素数,我不会
但是其复杂度会在O(N)到O(N^2)以内

============================================
解法二(从和角度出发):
你听说过哥德巴赫猜想吗?

哥德巴赫猜想:任一大于2的整数都可写成两个质数之和。
欧拉对这个猜想等价出了另外一个版本:即任一大于2的偶数都可写成两个素数之和

所以,你只需要找到[6, N]区间内最大的两个素数,我假设为p和q,那么满足题目所求的数就在[18, p+q]区间内的所有偶数
注:18=7+11,此外这里有bug的,留后面说

现在的问题是,找到最大的那两个素数需要的时间是多久?
这涉及到一个问题:
两个相邻的素数间隔是多大?
这个问题似乎现在也没有解决,不过你可以从N往下一个一个按照6n±1地形式进行素性测试找出最大那两个的嘛(好丢脸的想法,逃)

好了,找到区间的上界了(也就是p+q),那么剩下一个BUG:题目说“两两之和”,所以这些偶数就不能是同一个素数相加啦,那你对这些偶数除2,然后素性判断就行啦(好丢脸,应该有更好的办法)



其实这里面最致命的BUG是:
我们使用了一个未被证明的猜想

但是你要这么想,我的算法是基于这个猜想了,要是出了问题能说明这个猜想不成立,那么...........................




你还去百度干什么

===================================

再次声明:
以上是我瞎扯的,别轻信=。=
升

回答了问题 • 2015-02-03 10:30 • 25 个回复 不感兴趣

[百度]随机播放音乐(随机数相关)

赞同来自:

(1)1000首歌曲编号,从1至1000
(2)产生一个1至1000的随机数,表示要播放的歌曲,这时,所有的歌曲被选中播放的概率是相同的
(3)假设选定的歌曲是54号,它的豆瓣评分是9.5分,那么此时再随机生成一个1至100的随机数,如果随机数小于等于95,那... 显示全部 »
(1)1000首歌曲编号,从1至1000
(2)产生一个1至1000的随机数,表示要播放的歌曲,这时,所有的歌曲被选中播放的概率是相同的
(3)假设选定的歌曲是54号,它的豆瓣评分是9.5分,那么此时再随机生成一个1至100的随机数,如果随机数小于等于95,那么就播放这首歌曲,如果随机数大于95,则重复1,2,3的步骤,直至找到一首可以播放的歌曲

备注:两首歌曲,评分分别为8.0,9.5,他们被选中的概率为1/1000,选中后还要产生一次随机数,被播放的概率分别为80%,95%,选中概率相同,播放概率比恰好是分数比值
jefflee

jefflee 回答了问题 • 2015-02-15 21:23 • 4 个回复 不感兴趣

一道有趣的面试题

赞同来自:

{{{
int randN( int n )
{
if( n == 0 )
return 0;
if( n < 0 )
return -randN(-n);
... 显示全部 »
{{{
int randN( int n )
{
if( n == 0 )
return 0;
if( n < 0 )
return -randN(-n);

int d = 0;
int n2 = n;

while( n2 > 0 ){
n2 = n2>>1;
d++;
}

int i, x;


while(1){
x = rand1();
for(i = 0; i < d - 1; i++){
x <<= 1;
x = x | rand1();
}
if( x <= n)
return x;
}
}
}}}
sjf0115

sjf0115 回答了问题 • 2015-02-14 11:04 • 10 个回复 不感兴趣

腾讯面试题:字符串匹配。

赞同来自:

**思路:**

假定字符串中都是ASCII字符。用一个数组来计数,前者加,后者减,全部为0则匹配。

**代码**
{{{
/*---------------------------------------------
* 日期:2015-02-14
*... 显示全部 »
**思路:**

假定字符串中都是ASCII字符。用一个数组来计数,前者加,后者减,全部为0则匹配。

**代码**
{{{
/*---------------------------------------------
* 日期:2015-02-14
* 作者:SJF0115
* 题目:字符串匹配
* 来源:腾讯
* 博客:http://blog.csdn.net/SunnyYoona/article/details/43816419
-----------------------------------------------*/
#include <iostream>
#include <cstring>
using namespace std;

class Solution {
public:
bool StrMatch(string str1,string str2){
int size1 = str1.size();
int size2 = str2.size();
if(size1 <= 0 || size2 <= 0 || size1 != size2){
return false;
}//if
int count[256];
// 初始化
memset(count,0,sizeof(count));
// 前者加
for(int i = 0;i < size1;++i){
++count[str1[i]];
}//for
//后者减
for(int i = 0;i < size2;++i){
--count[str2[i]];
}//for
// 全部为0则匹配
for(int i = 0;i < 256;++i){
if(count[i] != 0){
return false;
}//if
}//for
return true;
}
};


int main() {
Solution solution;
string str1("afafafa");
string str2("afafaf");
cout<<solution.StrMatch(str1,str2)<<endl;
}
}}}
如果A、B中出现的字符串有一个限制的话,比如都是ASCII码,那么我们可以做一个bitmap,开一个大小为N(如ASCII码N为127)的布尔数组分别表示N个字符是否在B中出现,然后扫描B一次扫描A一次就可以了,这样也算空间复杂度为o(1).

实在不行就先对... 显示全部 »
如果A、B中出现的字符串有一个限制的话,比如都是ASCII码,那么我们可以做一个bitmap,开一个大小为N(如ASCII码N为127)的布尔数组分别表示N个字符是否在B中出现,然后扫描B一次扫描A一次就可以了,这样也算空间复杂度为o(1).

实在不行就先对B做一遍快排,时间复杂度nlogn空间复杂度O(1),在对A中每个元素在B中做二分查找看是否有重复,这时最终的复杂度为(m+n)logn。
**根据 @Menson 建议优化**

{{{
if ( A[0]-t ) % 2 != 0:
i = 1
else:
i = 0
while i < len(A):
if A[i... 显示全部 »
**根据 @Menson 建议优化**

{{{
if ( A[0]-t ) % 2 != 0:
i = 1
else:
i = 0
while i < len(A):
if A[i] == t:
break
i += max( abs(A[i]-t), 2 )
}}}
最坏时间复杂度 O(N): 如在 [1,2,1,2,1,2,1,2,1,0] 里找0
如果限制范围是 0~(N-1)的话 (或者1~N,或者别的可以1-1映射到0~(N-1)的数,道理是一样的),可以用把i放到A[i]的做法来去重。
如果不限制范围,恐怕做不到时间O(n),空间O(1)
如果限制范围是 0~(N-1)的话 (或者1~N,或者别的可以1-1映射到0~(N-1)的数,道理是一样的),可以用把i放到A[i]的做法来去重。
如果不限制范围,恐怕做不到时间O(n),空间O(1)
Osiris

Osiris 回答了问题 • 2015-03-13 09:48 • 6 个回复 不感兴趣

『阿里面试题』组合排序问题

赞同来自:

搬运微博上一个思路。
@接下来的路才真正的开始 :4场。一共五个人,每2个人之间要打2场,分别是红蓝、蓝红,即一共要打(4+3+2+1)*2=20。如果1、4分组,每次打4场;如果2、3分组,每次打6场,故选2、3分组,最少要4场,才能大于20,所以4场。

... 显示全部 »
搬运微博上一个思路。
@接下来的路才真正的开始 :4场。一共五个人,每2个人之间要打2场,分别是红蓝、蓝红,即一共要打(4+3+2+1)*2=20。如果1、4分组,每次打4场;如果2、3分组,每次打6场,故选2、3分组,最少要4场,才能大于20,所以4场。

建议大家都在社区里讨论,方便知识沉淀。在微博讨论,容易把知识淹没。
wsk

wsk 回答了问题 • 2015-03-16 09:58 • 8 个回复 不感兴趣

[阿里]统计在线人

赞同来自:

uid是可以忽略的,就好像坐车一样,一个人上车,另一个人下车,车内总人数是不变的。
用bit 1代表登陆操作,0代表登出操作,整个可以表达为如下的数据结构
** 插入的附件 **
可以将log文件预处理一次,划分出m个时间段,预先统计出各个时... 显示全部 »
uid是可以忽略的,就好像坐车一样,一个人上车,另一个人下车,车内总人数是不变的。
用bit 1代表登陆操作,0代表登出操作,整个可以表达为如下的数据结构
** 插入的附件 **
可以将log文件预处理一次,划分出m个时间段,预先统计出各个时间段的初始状态,做分布查询
16个数两两比较,8次
胜出8个数再两两,4次
4个,2次,
2个,1次
得到最大A,第二大的应该是和A比较过的数,从第一轮开始共4个数,3次得到其中最大的,则为第二大
总共为18次?

没细想,回头验证正确性
16个数两两比较,8次
胜出8个数再两两,4次
4个,2次,
2个,1次
得到最大A,第二大的应该是和A比较过的数,从第一轮开始共4个数,3次得到其中最大的,则为第二大
总共为18次?

没细想,回头验证正确性
dugucloud

dugucloud 回答了问题 • 2015-03-24 15:04 • 24 个回复 不感兴趣

[阿里]逆序打印整数,要求递归实现

赞同来自:

{{{
>>> def revprint(x):
... str = chr(x % 10 + ord('0'))
... if x >= 10:
... str += revprint(x / ... 显示全部 »
{{{
>>> def revprint(x):
... str = chr(x % 10 + ord('0'))
... if x >= 10:
... str += revprint(x / 10)
... return str
...
>>> revprint(1243424)
'4243421'
>>>
}}}
我简单猜一下,1到50之间的奇数:

第1步、排除偶数
{{{
50个数,25个奇数,25个偶数

用1代表一个奇数,用0代表一个偶数,-代表二者的差的绝对值

1-0=1 消掉一个偶数
1-1=0 消掉两个奇数
... 显示全部 »
我简单猜一下,1到50之间的奇数:

第1步、排除偶数
{{{
50个数,25个奇数,25个偶数

用1代表一个奇数,用0代表一个偶数,-代表二者的差的绝对值

1-0=1 消掉一个偶数
1-1=0 消掉两个奇数
0-0=0 消掉一个偶数

只能成对地消掉奇数,因此25个奇数,导致最终剩下的数必是奇数
}}}
第2步、举例生成所有奇数
{{{
我们以47为例,49-2=47
48-1=47 50-3=47
4-3=1 6-5=1
...
45-44=1 47-46=1
两个47可以抵消,其他的我们将相邻两个取出,差为1,这些1一共有22组,可以全部抵消,因此47存在
按此方法应该可以生成1-49的奇数
}}}
cpcs

cpcs 回答了问题 • 2015-04-15 22:50 • 21 个回复 不感兴趣

阿里面试题:强强对话的概率

赞同来自:

个人观点 假设A, B, C是强队
D, E, F, G, H是弱队
我们把A B C找弱队匹配起来 (剩下的两个弱队匹配), 方案是P(5, 3) = 5 * 4 * 3 = 60种。
所有的match方法是 7 * 5 * 3 * 1 = 105种
所以... 显示全部 »
个人观点 假设A, B, C是强队
D, E, F, G, H是弱队
我们把A B C找弱队匹配起来 (剩下的两个弱队匹配), 方案是P(5, 3) = 5 * 4 * 3 = 60种。
所有的match方法是 7 * 5 * 3 * 1 = 105种
所以 有105 - 60 = 45 种方式强强联合
概率是 45 / 105 = 3 / 7
haoranliu1990

haoranliu1990 回答了问题 • 2015-04-22 22:07 • 15 个回复 不感兴趣

【腾讯面试】 如何对1亿个QQ号进行排序

赞同来自:

感觉可以有好几种方法。
1)楼主说的用位图。
2)外排。
3)1亿个qq号,按 1亿个unsigned int算,就是 4 bytes * 10 ^ 8 约等于400MB,直接内存里快排应该也行吧。
不知道面试官的要求和限制是什么。
感觉可以有好几种方法。
1)楼主说的用位图。
2)外排。
3)1亿个qq号,按 1亿个unsigned int算,就是 4 bytes * 10 ^ 8 约等于400MB,直接内存里快排应该也行吧。
不知道面试官的要求和限制是什么。
直接上位图了

开512M的空间, 刚好2^32个bit, 每个bit对应一个数, 一开始全为0
然后读这40亿个数, 读一个就把对应的bit置为1

然后直接查对应的bit是0还是1, 就好了
直接上位图了

开512M的空间, 刚好2^32个bit, 每个bit对应一个数, 一开始全为0
然后读这40亿个数, 读一个就把对应的bit置为1

然后直接查对应的bit是0还是1, 就好了
邹博

邹博 回答了问题 • 2015-07-01 19:03 • 4 个回复 不感兴趣

#每日一面BAT#第1题:概率与集合元素个数

赞同来自:

参考答案:
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
参考答案:
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
邹博

邹博 回答了问题 • 2015-07-03 09:52 • 6 个回复 不感兴趣

#每日一面BAT#第2题:三字符构成的字符串个数

赞同来自:

**参考答案解析:**

** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
[atta... 显示全部 »
**参考答案解析:**

** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
邹博

邹博 回答了问题 • 2015-07-05 00:29 • 4 个回复 不感兴趣

#每日一面BAT#第3题:循环染色问题

赞同来自:

@BobLee赞!
参考解析:
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
@BobLee赞!
参考解析:
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
** 插入的附件 **
警示:各位的所有作答结果我们都已在第一时间截图保存(如上述帖子的最下面所示),而根据比赛规则“答题有效时间2个小时(14:00~16:00),一经作答,不得修改(否则取消掉一二三等奖的评奖资格)”,故请作答后,切勿修改。
16:00整,有效答题时间截止,公布正... 显示全部 »
警示:各位的所有作答结果我们都已在第一时间截图保存(如上述帖子的最下面所示),而根据比赛规则“答题有效时间2个小时(14:00~16:00),一经作答,不得修改(否则取消掉一二三等奖的评奖资格)”,故请作答后,切勿修改。
16:00整,有效答题时间截止,公布正确答案,和一二三等奖的获得者3人。(更新:已经公布在上述帖子最后)
17:00整,公布被随机抽中的5位作答幸运者。
自己的回答,非标准,仅供参考。

1、构造新对象,将对象的数据成员赋初值
2、对象过期时,程序自动调用负责完成清理工作。析构函数先由用户代码释放对象堆内存,再程序自动释放对象栈内存。
3、内存分配方式有三种:
(1) 从静态存储区域分配。内存在程序编译的时候就... 显示全部 »
自己的回答,非标准,仅供参考。

1、构造新对象,将对象的数据成员赋初值
2、对象过期时,程序自动调用负责完成清理工作。析构函数先由用户代码释放对象堆内存,再程序自动释放对象栈内存。
3、内存分配方式有三种:
(1) 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static 变量。
(2) 在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
(3) 从堆上分配,亦称动态内存分配。程序在运行的时候用malloc 或new 申请任意多少的内存,程序员自己负责在何时用free 或delete 释放内存。
4、有两种主要体现:
  (1)方法的多态性:
  a)、重载
  b)、覆盖
 (2)对象的多态性
  a)、向上转型
  b)、向下转型
5、1、list是存储单列数据的集合,map是存储键和值这样的双列数据的集合,
2、List中存储的数据是有顺序,并且允许重复;Map中存储的数据是没有顺序的,其键是不能重复的,它的值是可以有重复的,是key-value组成的键值对;
3、List接口继承collection接口,Map是个顶级接口。List此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数 索引(在列表中的位置)访问元素,并搜索列表中的元素;map接口将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值
cpcs

cpcs 回答了问题 • 2015-08-02 00:21 • 3 个回复 不感兴趣

#每日一面BAT#第11题 环形跑道

赞同来自:

答案
如果把每个储油点的油量减去到下一个储油点的耗油量当成一个变量a[i],则我们有
a[1] + a[2] + ... + a[n] = 0 因为全部油刚好够一圈,问题是这个有正有负数。
我们假设A = a[1] + a[2] + ... + a[k -... 显示全部 »
答案
如果把每个储油点的油量减去到下一个储油点的耗油量当成一个变量a[i],则我们有
a[1] + a[2] + ... + a[n] = 0 因为全部油刚好够一圈,问题是这个有正有负数。
我们假设A = a[1] + a[2] + ... + a[k - 1]是前缀的最小值,并且假设A<0,因为如果A>=0,则从第一个储油点开始走,不会出现负数,这个储油点就是解了。
我们令B=a[k] + a[k + 1] + ... + a[n], 则B = -A >= 0
我们考虑 B的每个前缀
a[k], a[k] + a[k + 1], a[k] + a[k + 1] + a[k + 2],....,B, 这些前缀必须都是非负数,因为如果前缀有一个负数的x的话,从a[1]开始的前缀和A + x < A,与A最小矛盾。
我们再继续
B + a[1], B + a[1] + a[2], ..... B + A
因为从B开始加的那部分就是从a[1]开始的前缀,我们知道A是最小的,所以这串数的最小值是A + B = 0,这就证明了从a[k]开始出发,加出来的数不会出现负数。所以k是一个解。
我们这个算法的时间复杂度是O(n),因为我们只需要自己加一次把和最小的位置找出来就可以了。
另外,我们其实并没有规定顺时针还有逆时针行走,所以可以分别考虑求出不同方向行驶的出发点。
cpcs

cpcs 回答了问题 • 2015-08-03 12:15 • 1 个回复 不感兴趣

#每日一面BAT#第12题 文章与词

赞同来自:

答案: 对词建立倒排索引。
即 建立list
word1: p1,1, p1,2, p1,3...
word2: p2,1, p2,2, p2,3...
word3:...

word后面的列表表示这个词出现的位置。
假设要包含n个词,设置n个指针,从每个词的... 显示全部 »
答案: 对词建立倒排索引。
即 建立list
word1: p1,1, p1,2, p1,3...
word2: p2,1, p2,2, p2,3...
word3:...

word后面的列表表示这个词出现的位置。
假设要包含n个词,设置n个指针,从每个词的列表头开始指向。
可行的答案是max(P) - min(P)。
然后类似归并排序,每次移动位置最小的指针,让它沿着列表指向后一个位置……
如此不断移动指针,直到有一个列表走到末尾即可。
遂心---

遂心--- 回答了问题 • 2015-08-03 17:00 • 3 个回复 不感兴趣

#每日一面BAT#第13题 方程的正整数解

赞同来自:

整数划分问题:令y1 = x1 - 2 >= 0,y2 = x2 >= 0,y3 = x3 + 5 >= 0,y4 = x4 - 8 >= 0;故该问题可转换为y1 + y2 + y3 + y4 = 25的整数解,由整数划分公式num ... 显示全部 »
整数划分问题:令y1 = x1 - 2 >= 0,y2 = x2 >= 0,y3 = x3 + 5 >= 0,y4 = x4 - 8 >= 0;故该问题可转换为y1 + y2 + y3 + y4 = 25的整数解,由整数划分公式num = C(n + r - 1,r),其中n为变量的个数即4,r为25;故num = C(4 + 25 - 1,25) = (28 * 27 * 26)/6 = 3276,即选A。
cpcs

cpcs 回答了问题 • 2015-08-05 11:34 • 1 个回复 不感兴趣

#每日一面BAT#第14题 机器人指令序列

赞同来自:

答案: 连续模拟那个commend 至多5次,必然有两次朝向一样的,分析这两次,实际上有一个位移,如果这个位移是0,说明他在转圈,否则就相当于它不断沿着这个向量方向再走,直到无穷远……
答案: 连续模拟那个commend 至多5次,必然有两次朝向一样的,分析这两次,实际上有一个位移,如果这个位移是0,说明他在转圈,否则就相当于它不断沿着这个向量方向再走,直到无穷远……
EagleSky

EagleSky 回答了问题 • 2015-08-05 19:48 • 2 个回复 不感兴趣

#每日一面BAT#第15题 a[x] == x

赞同来自:

设整数\\(x_1 > x_2\\),并且有\\(x_1 = x_2 + d\\)。由于数组\\(a\\)是一个严格单调递增的整数数组,所以必然有\\(a[x_1] \geqslant a[x_2] + d\\)。
两边同时减去\\(x_1\\),即\\... 显示全部 »
设整数\\(x_1 > x_2\\),并且有\\(x_1 = x_2 + d\\)。由于数组\\(a\\)是一个严格单调递增的整数数组,所以必然有\\(a[x_1] \geqslant a[x_2] + d\\)。
两边同时减去\\(x_1\\),即\\(a[x_1] - x_1 \geqslant a[x_2] + d - x_2 -d = a[x_2] - x_2\\)。所以\\(f(x) = a[x] - x\\) 也是一个单调递增的函数。
那么原问题寻找\\(a[x] = x\\)的位置也就变成了查找单调递增函数\\(f(x) = 0\\)时对应的\\(x\\)。这样就可以直接使用二分查找来做了,时间复杂度为\\(O(\log{n})\\)

{{{
void find(int a[], int l, int r)
{
if (l > r)
return -1;
int k = (l + r) / 2;
if (a[k] == k)
return k;
else if (a[k] > k)
return find(a, l, k - 1);
else
return find(a, k + 1, r);
}
}}}
EagleSky

EagleSky 回答了问题 • 2015-08-06 10:34 • 1 个回复 不感兴趣

#每日一面BAT#第16题 最大指数

赞同来自:

UVa 10622 Perfect P-th Powers

简单来说,就是对\\(x\\)做质因数分解。
把\\(x\\)写成\\(p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\\)
那么\\(k_1,k_2,\cdots,k_n\\... 显示全部 »
UVa 10622 Perfect P-th Powers

简单来说,就是对\\(x\\)做质因数分解。
把\\(x\\)写成\\(p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\\)
那么\\(k_1,k_2,\cdots,k_n\\)的最大公约数就是对于x来说最大的可能的b。也即
\\(x = (p_1^{\frac{k_1}{b}}p_2^{\frac{k_2}{b}}\cdots p_n^{\frac{k_n}{b}})^b\\)

{{{
int maxPower(int x)
{
int a = abs(x);
std::map<int, int> pf; //计算x的绝对值的质因数分解
for (int i = 2; i <= a / i; i++)
{
while (a % i == 0)
{
pf[i]++;
a /= i;
}
}
if (a > 1) pf[a]++;
int mp = 32; //int长度表示整数为-2^31 - 2^31-1,所以mp最大为32
for (; mp >= 1; mp--) //计算质因数分解中所有指数的最大公约数
{
bool valid = true;
for (auto it = pf.begin(); it != pf.end(); ++it)
{
if (it->second % mp != 0)
{
valid = false;
break;
}
}
if (valid && (x > 0 || mp % 2 == 1)) //当x为负值时,需要保证mp为奇数
break;
}
return mp;
}
}}}
cpcs

cpcs 回答了问题 • 2015-08-08 13:07 • 2 个回复 不感兴趣

#每日一面BAT#第17题 RGB字符串

赞同来自:

答案
其实这题就是一个最短路
如果i < j
(1) S[i] = 'R', S[j] = 'G', 建立一条(i - j) * (i - j) 的边
(2) S[i] = 'G',S[j] = 'B', 建立一条(i - j) * (i - j) ... 显示全部 »
答案
其实这题就是一个最短路
如果i < j
(1) S[i] = 'R', S[j] = 'G', 建立一条(i - j) * (i - j) 的边
(2) S[i] = 'G',S[j] = 'B', 建立一条(i - j) * (i - j) 的边
(3) S[i] = 'B', S[j] = 'R', 建立一条(i - j) * (i - j)的边
求0到(n-1)的最短路。

当然 也可以动态规划
dp[x]表示到达x的最小代价
初值 dp[0] = 0
dp[j] = min(dp[i] + (i - j) * (i - j)) 如果i < j并且S[i] S[j]满足上面那个(1) (2) 或者(3)之一
求dp[n - 1]

其实两个方法是等价的……
YangL

YangL 回答了问题 • 2015-08-08 21:40 • 3 个回复 不感兴趣

#每日一面BAT#第18题 取石子游戏

赞同来自:

考虑Alice的必胜态:
当Alice取完本轮石子后,剩下的石子为3的倍数(3*n),那么无论Bob怎么取,Alice都会赢。
简单解释如下:
①n = 1时,即Alice取完后只剩下3颗,那么无论Bob怎么取,Alice... 显示全部 »
考虑Alice的必胜态:
当Alice取完本轮石子后,剩下的石子为3的倍数(3*n),那么无论Bob怎么取,Alice都会赢。
简单解释如下:
①n = 1时,即Alice取完后只剩下3颗,那么无论Bob怎么取,Alice下次取都会取到最后一颗,会赢。
②n >1时,即Alice取完后剩下3*n颗,当Bob取完后,剩下的石子数量总可以表示为:
3*k+1 或 3*k + 2(k >= 0),那么此时Alice可以将剩下的石子数重新变为3的倍数,如此递推下去。
...
最终剩下石子数量变为3。

也就是说,只要Alice取完后,剩下的石子数是3的倍数,那么Alice肯定会赢。

简单的C++实现代码如下:

{{{
//头文件 & 命名空间
#include <iostream>
using namespace std;

//石子数为n时 判定谁赢
void WhoWin(int n)
{
//Alice要先取
puts(n % 3 == 0? "Bob win" : "Alice win");
}

#主函数
int main(void)
{
int n;
while(cin >> n)
{
WhoWin(n);
}
return 0;
}
}}}
cpcs

cpcs 回答了问题 • 2015-08-10 02:32 • 1 个回复 不感兴趣

#每日一面BAT#第19题 子序列的个数

赞同来自:

答案:
这个题本身不难,但是分析清楚不容易。
我们首先假设子序列可以为空——最后减1就好了。
假设dp[i]表示数列前i项构成的不同子序列的个数。
初值:
dp[0] = 1 因为只有一个空子序列
我们现在考虑dp[i]
(1) 如果数列第i项在之前没有出现过... 显示全部 »
答案:
这个题本身不难,但是分析清楚不容易。
我们首先假设子序列可以为空——最后减1就好了。
假设dp[i]表示数列前i项构成的不同子序列的个数。
初值:
dp[0] = 1 因为只有一个空子序列
我们现在考虑dp[i]
(1) 如果数列第i项在之前没有出现过,是一个新数
显然dp[i] = dp[i - 1] * 2
这是因为前(i-1)项的子序列本身,以及添加上第i项,都是一个子序列,这是比较容易的情况。如果全是这样,人生就完美了……因为我们会推出dp[i] = 2 ^ i, 但还有讨厌的第二种情况。
(2)如果第i项在之前出现过,假设j是它最近一次出现的位置,我们有0<j<i (注意i,j都是项数,或者说下标从1开始的)
那么我们直接乘以2,有些会重复。哪些重复了呢?
原来的前(j-1)项的子序列末尾添加上第j项和添加上第i项是一样的,就这些是重复的。所以dp[j-1]是重复的。
此时 dp[i] = dp[i - 1] * 2 - dp[j - 1]

最后千万别忘记答案是dp[n] - 1因为我们考虑了空的子序列。
还有一种分析可以不考虑空的子序列,也是类似的。
cpcs

cpcs 回答了问题 • 2015-08-11 05:30 • 1 个回复 不感兴趣

#每日一面BAT#第20题 绳子覆盖点

赞同来自:

答案
O(n^2)枚举自然都能能想到。给个O(n)的想法。
以每个i为起点,只希望覆盖更多的点。
注意每次循环best和i都只增不减,尽管两个循环,复杂度还是O(n)的。

{{{

int calculate(int *a, int n, int L) {
... 显示全部 »
答案
O(n^2)枚举自然都能能想到。给个O(n)的想法。
以每个i为起点,只希望覆盖更多的点。
注意每次循环best和i都只增不减,尽管两个循环,复杂度还是O(n)的。

{{{

int calculate(int *a, int n, int L) {

int best = 0;
for (int i = 0; i + best < n; ++i) {
for (; (i + best < n) && (a[i + best] - a[i] <= L); ++best)
;
}
return best;
}

}}}
cpcs

cpcs 回答了问题 • 2015-08-12 04:42 • 1 个回复 不感兴趣

#每日一面BAT#第21题 下标三元组

赞同来自:

答案

解法1 O(n)时间 O(n)空间。
首先假设数组是a, 我们想找到这样3个index,比如3个index分别是i < j < k
我们看一下,当我们枚举j的时候,如果选取i和k? 一种可能是i选取a[0..j - 1]里面最小值的下标,... 显示全部 »
答案

解法1 O(n)时间 O(n)空间。
首先假设数组是a, 我们想找到这样3个index,比如3个index分别是i < j < k
我们看一下,当我们枚举j的时候,如果选取i和k? 一种可能是i选取a[0..j - 1]里面最小值的下标,而k选取a[j + 1..n - 1]最大值的下标。而这个东西我们可以用前缀、后缀的方法预处理出来。
比如我们可以算出b[i]表示 a[0..i]中最小值的下标,而c[i]表示a[i..n - 1]中最大值的下标。这个可以循环处理。

{{{
for (int i = 0; i < n; ++i) {
b[i] = ((i == 0) || (a[b[i - 1]] > a[i]))? i : b[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
c[i] = ((i == n - 1) || (a[c[i + 1]] < a[i]))? i : c[i + 1];
}

}}}

这样,选取的时候对i我们直接看一下b[i - 1]和c[i + 1]就可以了。

{{{

for (int i = 1; i + 1 < n; ++i) {
if ((a[b[i - 1]] < a[i]) && (a[c[i + 1]] > a[i])) {
return b[i - 1], i , c[i + 1]是一个解
}
}


}}}

优化优化
解法2 O(n)时间,O(1)空间的算法。
利用LIS的思想,因为我们实际上就是要找到一个长度为3的单调子序列,那么我们可以用O(nlogn)的LIS思想,但是由于长度只维护到3,所以没有必要2分,而且没有必要用数组保存长度为x的单调子序列的最后一项的最小值,用变量存就好了,但思路是不变的。
我们这么记录x表示目前为止长度为1的单增子序列最后一项的最小值在数组a中的下标,实际上x就是我们刚才那个b数组,而y表示目前为止长度为2的单增子序列最后一项的最小值在数组a中的下标。根据单调子序列的性质,我们有a[x] < a[y], 这个其实就是那个O(nlogn)算法思想的核心。我们先让x = 0,让y = -1,表示目前长度为1的单增自序列就是第一项,没有长度为2的单增子序列。同时我们需要维护一个z,表示长度为2的单增自序列的首项,也就是y之前那一项。我们从i = 1开始维护x、y、z的值。
y = -1时a[y]定义为无穷大。 我们看一下a[i] 和a[x] a[y]的关系。 (注意始终有a[x] <a[y])
(1) 如果a[i] > a[y],则我们找到了三元组(z, y, i)满足条件
(2) 如果a[i] == a[y], 则这一项没有意义,无法扩展子序列
(3) 如果a[x] < a[i] < a[y] (当然我们可以把情况2也放到这里), 那么我们可以把长度为2的单调子序列最后一项更新一下,所以更新y = i, z = x,实际上a[x], a[i]是个长度为2的单增子序列,且最后一项比a[y]小。
(4) 如果a[i] == a[x], 则这一项没有意义, 无法扩展子序列
(5) 如果a[i] < a[x] (当然我们可以把情况4也放到这里), 那么我们可以把长度为1的单调子序列最后一项更新一下(也就是目前最小值),所以更新x = i
这个时间复杂度显然是O(n),空间复杂度是O(1)。

{{{
int x = 0;
int y = -1;
int z = -1;
for (int i = 1; i < n; ++i) {
if ((y >= 0) && (a[i] > a[y])) {
return 找到三元组(z, y, i)满足要求
}
else if (a[i] > a[x]) {
y = i;
z = x;
}
else {
x = i;
}
}

}}}
YangL

YangL 回答了问题 • 2015-08-12 23:17 • 2 个回复 不感兴趣

#每日一面BAT#第22题 木杆蚂蚁

赞同来自:

如下图,考虑任意两只蚂蚁的情况:
** 插入的附件 **
则:
①如果两只蚂蚁是相向运动,如图 假定A向右 B向左 它们会在m处相遇。接着同时掉头向相反的方向移动,最终离开木杆。
在上述过程中,A B两只蚂蚁总共的路程分别为:
S... 显示全部 »
如下图,考虑任意两只蚂蚁的情况:
** 插入的附件 **
则:
①如果两只蚂蚁是相向运动,如图 假定A向右 B向左 它们会在m处相遇。接着同时掉头向相反的方向移动,最终离开木杆。
在上述过程中,A B两只蚂蚁总共的路程分别为:
SA = Am+ms SB=Bm+me
路程之和S = SA + SB =AB + SE = Ae + Bs 显然这是个常数
也就是说相向运动时 对蚂蚁离开木杆的时间没有影响。同时S = Ae + Bs也表明:
相向运动的蚂蚁相遇后掉头 等价于 两只蚂蚁相遇后不掉头仍然按照原先的运动方向至相应的终点。(对A来说是 e,对B来说是s)

因此,对时间有影响的运动是同向运动的蚂蚁。
②考虑同向运动的蚂蚁
最小时间离开木杆 <=> 每只蚂蚁朝离它最近的端点走。
最大时间离开木杆 <=> 每只蚂蚁朝离它最远的端点走。

对于多只蚂蚁的情况,按照②中的方法,比较所有蚂蚁的路程和,求对应情况下路程最大的蚂蚁所花时间即可。
cpcs

cpcs 回答了问题 • 2015-10-01 00:12 • 5 个回复 不感兴趣

抛个问题出来,大家想想

赞同来自:

方法二:
我们考虑区间(桶)和数的关系。
最开始 区间 [1..n] 有(n + 1)个数,所以至少一个"桶"有两个数。

假设我们有一个点mid, 我们把[1..n]分为两部分[1..mid]和[mid + 1..n]。由于整个区间上的数... 显示全部 »
方法二:
我们考虑区间(桶)和数的关系。
最开始 区间 [1..n] 有(n + 1)个数,所以至少一个"桶"有两个数。

假设我们有一个点mid, 我们把[1..n]分为两部分[1..mid]和[mid + 1..n]。由于整个区间上的数的个数比区间长度(桶的个数)多,至少有一部分满足里面数的个数比区间长度(桶的个数)多。换句话说
区间 [1..mid] 长度为mid, 数的个数为x
而区间[mid + 1..n] 长度为n - mid, 数的个数为y
因为n + 1 = (x + y) > n = mid + (n - mid)
所以至少有x > mid或者y > n - mid, 事实上因为只差了1,应该说有且仅有一个区间满足条件,但这无所谓。
满足这个条件的区间有重复的数——其实重复的数可以很多。

于是,问题变为二分这个mid,统计[1..mid]里数的个数,时间复杂度还是O(nlogn)。

代码:
{{{
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1; //index [0..n]
int left = 1, right = n - 1;
while (left <= right) {
int mid = (left + right) >> 1;
int x = 0;
for(int i = 0; i <= n; ++i) {
if (nums[i] <= mid) {
++x;
}
}
//[1..mid] x
//[mid + 1..n] n + 1 - x
if (mid < x) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return right + 1;
}
};
}}}

[百度]随机播放音乐(随机数相关)

面试klzhan 回复了问题 • 74 人关注 • 25 个回复 • 7171 次浏览 • 2015-08-30 17:29 • 来自相关主题

pc蛋蛋预测中奖95%软件群8887209-误会

回复

面试appoil 发起了问题 • 1 人关注 • 0 个回复 • 38 次浏览 • 5 天前 • 来自相关主题

『阿里面试题』组合排序问题

回复

面试 回复了问题 • 17 人关注 • 6 个回复 • 3387 次浏览 • 2017-08-14 10:46 • 来自相关主题

廿青春,共前行——2018网易互联网校招内推开启

回复

内推小易推推 回复了问题 • 2 人关注 • 1 个回复 • 291 次浏览 • 2017-07-29 11:58 • 来自相关主题

一起刷leetcode(78):Subsets

回复

leetcode/kaggleMrFat 回复了问题 • 6 人关注 • 3 个回复 • 1760 次浏览 • 2016-08-08 22:02 • 来自相关主题

C++面试知识点

回复

面试JoyceWYJ 发起了问题 • 4 人关注 • 0 个回复 • 823 次浏览 • 2016-07-08 12:47 • 来自相关主题

一起刷LeetCode(226): Invert Binary Tree

回复

leetcode/kaggleJoyceWYJ 回复了问题 • 2 人关注 • 2 个回复 • 317 次浏览 • 2016-06-29 18:44 • 来自相关主题

干货分享——机器学习与大数据的面试问题与答题思路

回复

面试wuyou123 回复了问题 • 12 人关注 • 2 个回复 • 1004 次浏览 • 2016-06-14 21:33 • 来自相关主题

阿里巴巴实习面经——天猫部

回复

面试JoyceWYJ 发起了问题 • 3 人关注 • 0 个回复 • 886 次浏览 • 2016-05-25 11:02 • 来自相关主题

[阿里]逆序打印整数,要求递归实现

回复

面试小付fu 回复了问题 • 33 人关注 • 24 个回复 • 3802 次浏览 • 2016-03-14 21:15 • 来自相关主题

#每日一面BAT#第24题 约数博弈

回复

面试hulala 回复了问题 • 7 人关注 • 2 个回复 • 1477 次浏览 • 2016-03-11 18:30 • 来自相关主题

抛个问题出来,大家想想

回复

面试July 回复了问题 • 7 人关注 • 5 个回复 • 1853 次浏览 • 2015-10-05 14:44 • 来自相关主题

[大众点评]N个未排序的整数,在线性时间内,求N个整数在数轴上相邻两个数之间的最大差值。

回复

面试邹博 回复了问题 • 5 人关注 • 3 个回复 • 1554 次浏览 • 2015-09-30 17:15 • 来自相关主题

[小米]首尾相连数组的最大子数组和

回复

面试zhangenwei 回复了问题 • 4 人关注 • 2 个回复 • 1337 次浏览 • 2015-09-12 19:01 • 来自相关主题

【腾讯面试】 如何对1亿个QQ号进行排序

回复

面试czmbit 回复了问题 • 42 人关注 • 15 个回复 • 6505 次浏览 • 2015-09-10 19:56 • 来自相关主题

【腾讯】新闻推荐中按照一定策略从排好序的新闻列表中选择新闻

回复

面试pnghwang 回复了问题 • 5 人关注 • 2 个回复 • 1004 次浏览 • 2015-08-31 19:57 • 来自相关主题

[百度]随机播放音乐(随机数相关)

回复

面试klzhan 回复了问题 • 74 人关注 • 25 个回复 • 7171 次浏览 • 2015-08-30 17:29 • 来自相关主题

腾讯面试题:字符串匹配。

回复

面试lidasong 回复了问题 • 29 人关注 • 10 个回复 • 5210 次浏览 • 2015-08-27 09:35 • 来自相关主题

#每日一面BAT#第10题:汽车最大补给

回复

算法zhouge 回复了问题 • 19 人关注 • 5 个回复 • 1682 次浏览 • 2015-08-26 19:39 • 来自相关主题

[阿里巴巴二面]两个字符串A、B,从A中剔除存在于B中的字符。

回复

面试sd1527907 回复了问题 • 37 人关注 • 16 个回复 • 4183 次浏览 • 2015-08-26 17:11 • 来自相关主题

【微软】设计魔方的数据结构

回复

面试solocode 回复了问题 • 9 人关注 • 2 个回复 • 1659 次浏览 • 2015-08-25 18:48 • 来自相关主题

#每日一面BAT#第23题 区间最大重叠

回复

面试cpcs 回复了问题 • 5 人关注 • 1 个回复 • 1694 次浏览 • 2015-08-22 22:36 • 来自相关主题

阿里面试题:强强对话的概率

回复

面试rcgn 回复了问题 • 33 人关注 • 21 个回复 • 4250 次浏览 • 2015-08-20 17:00 • 来自相关主题

2015年阿里研发工程师实习笔试附加题

回复

面试张小朋要奋斗 回复了问题 • 33 人关注 • 13 个回复 • 7050 次浏览 • 2015-08-19 11:42 • 来自相关主题

阿里云-多线程设计题

回复

面试Wen_nian 回复了问题 • 9 人关注 • 2 个回复 • 1550 次浏览 • 2015-08-16 15:14 • 来自相关主题

设计题-服务器流量统计器

回复

面试talentlei 发起了问题 • 4 人关注 • 0 个回复 • 964 次浏览 • 2015-08-13 16:20 • 来自相关主题

#每日一面BAT#第22题 木杆蚂蚁

回复

面试YangL 回复了问题 • 6 人关注 • 2 个回复 • 1320 次浏览 • 2015-08-13 08:46 • 来自相关主题

#每日一面BAT#第21题 下标三元组

回复

面试cpcs 回复了问题 • 7 人关注 • 1 个回复 • 1409 次浏览 • 2015-08-12 04:42 • 来自相关主题

#每日一面BAT#第11题 环形跑道

回复

面试YangL 回复了问题 • 8 人关注 • 3 个回复 • 1870 次浏览 • 2015-08-11 21:04 • 来自相关主题

#每日一面BAT#第20题 绳子覆盖点

回复

面试cpcs 回复了问题 • 5 人关注 • 1 个回复 • 850 次浏览 • 2015-08-11 13:23 • 来自相关主题

2015阿里巴巴校招电面一面题目分享~求细致完整的解答~

回复

面试YangL 回复了问题 • 16 人关注 • 4 个回复 • 2926 次浏览 • 2015-08-10 22:35 • 来自相关主题

#每日一面BAT#第19题 子序列的个数

回复

算法cpcs 回复了问题 • 6 人关注 • 1 个回复 • 1001 次浏览 • 2015-08-10 02:32 • 来自相关主题

#每日一面BAT#第18题 取石子游戏

回复

面试柳梦璃 回复了问题 • 9 人关注 • 3 个回复 • 970 次浏览 • 2015-08-08 22:47 • 来自相关主题

#每日一面BAT#第17题 RGB字符串

回复

面试天天 回复了问题 • 6 人关注 • 2 个回复 • 889 次浏览 • 2015-08-08 19:34 • 来自相关主题

#每日一面BAT#第1题:概率与集合元素个数

回复

算法Janvn 回复了问题 • 10 人关注 • 4 个回复 • 1525 次浏览 • 2015-08-07 18:56 • 来自相关主题

#每日一面BAT#第16题 最大指数

回复

面试EagleSky 回复了问题 • 5 人关注 • 1 个回复 • 952 次浏览 • 2015-08-07 10:18 • 来自相关主题

#每日一面BAT#第15题 a[x] == x

回复

面试cpcs 回复了问题 • 5 人关注 • 2 个回复 • 943 次浏览 • 2015-08-06 17:08 • 来自相关主题

用公平的硬币模拟 1/Pi概率?

回复

算法cpcs 回复了问题 • 5 人关注 • 2 个回复 • 1083 次浏览 • 2015-08-06 13:51 • 来自相关主题

#每日一面BAT#第14题 机器人指令序列

回复

面试cpcs 回复了问题 • 2 人关注 • 1 个回复 • 944 次浏览 • 2015-08-05 11:34 • 来自相关主题

#每日一面BAT#第3题:循环染色问题

回复

算法天天 回复了问题 • 11 人关注 • 4 个回复 • 1895 次浏览 • 2015-08-04 23:34 • 来自相关主题

#每日一面BAT#第13题 方程的正整数解

回复

面试cpcs 回复了问题 • 5 人关注 • 3 个回复 • 930 次浏览 • 2015-08-04 11:12 • 来自相关主题

2015百度校招一面题目分享~

回复

面试园园啊圈圈_oo 回复了问题 • 15 人关注 • 3 个回复 • 3020 次浏览 • 2015-08-04 10:41 • 来自相关主题

『腾讯面试题』类成员存储问题。

回复

面试天天 回复了问题 • 8 人关注 • 2 个回复 • 2425 次浏览 • 2015-08-03 23:56 • 来自相关主题

#每日一面BAT#第12题 文章与词

回复

面试cpcs 回复了问题 • 2 人关注 • 1 个回复 • 782 次浏览 • 2015-08-03 12:15 • 来自相关主题

[腾讯面试题]一个大小为N的数组,里面是N个整数,怎样去除重复。

回复

面试天天 回复了问题 • 41 人关注 • 14 个回复 • 4882 次浏览 • 2015-07-28 09:10 • 来自相关主题

一道关于数据库的面试题

回复

面试张_晓龙在人人 回复了问题 • 6 人关注 • 2 个回复 • 933 次浏览 • 2015-07-24 13:58 • 来自相关主题

[百度面试题]数组A中任意两个相邻元素大小相差1,在其中查找某个数。

回复

面试Miku 回复了问题 • 42 人关注 • 19 个回复 • 4477 次浏览 • 2015-07-20 17:57 • 来自相关主题

腾讯面试题:给40亿个不重复的unsigned int的数,没排序,然后再给一个数,如何快速间断这个数是否在那40亿个数中

回复

面试littletiger 回复了问题 • 14 人关注 • 5 个回复 • 4106 次浏览 • 2015-07-15 15:49 • 来自相关主题

#每日一面BAT#第9题:男女比例问题

回复

算法邹博 回复了问题 • 9 人关注 • 5 个回复 • 1419 次浏览 • 2015-07-14 20:23 • 来自相关主题

#每日一面BAT#第2题:三字符构成的字符串个数

回复

算法永不停息的狮子 回复了问题 • 20 人关注 • 6 个回复 • 2469 次浏览 • 2015-07-14 10:56 • 来自相关主题

google面试题汇总第31-40题

面试cpcs 发表了文章 • 3 个评论 • 2937 次浏览 • 2015-06-04 13:53 • 来自相关主题


1.给一个数列和一个目标数, 返回目标数出现的次数,数列已经排序

2.二树, 打印层次顺序的节点 (level order traversal)

3.给一个字符串只由一,零和星组成, 返还一组数, 把星替换成1和2

4.有...
查看更多
返回顶部