剑指Offer——完美+今日头条笔试题+知识点总结

情景回顾

时间:2016.9.28 16：00-18：00 19：00-21：00
地点:山东省网络环境智能计算技术重点实验室
事件:完美世界笔试今日头条笔试

今日头条的两道编程题均涉及到大数据量的处理。按照一般方法解题只能够通过30%-40%。而大数据量的处理也正是自己的软肋。

涉及到的知识点如下，仅供参考。

线程中sleep与wait的区别

1、这两个方法来自不同的类分别是Thread和Object，在java.lang.Thread类中，提供了sleep()，而java.lang.Object类中提供了wait()，notify()和notifyAll()方法来操作线程。
2、最主要是sleep方法没有释放锁，而wait方法释放了锁，使得其他线程可以使用同步控制块或者方法。
3、wait，notify和notifyAll只能在同步控制方法或者同步控制块里面使用，而sleep可以在任何地方使用（使用范围）
　　synchronized(x){ 　　x.notify() 　　//或者wait() 　　}
4、sleep必须捕获异常，而wait，notify和notifyAll不需要捕获异常。

ConcurrentHashMap

HashMap不是线程安全的,ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。

在ConcurrentHashMap中，线程对映射表做读操作时，一般情况下不需要加锁就可以完成，对容器做结构性修改的操作才需要加锁。

补充知识一点资讯面试题

单链表反转

完美世界编程题

1.球掉落问题

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

有一幢N（N > 0）层的楼，当从高于某一楼层往下扔玻璃球时，玻璃球会被摔坏，反之，玻璃球保持完好。现在用m（m > 0）颗完全一样的玻璃球，每次从某一楼层往下扔一颗球，来找到这个刚好能使玻璃球摔坏的临界楼层。规定扔碎的玻璃球不可用于下一次试验，求一定能确定这个临界楼层的最少试验次数。主函数已经完成，请完成calcThrowNumber(int,int)函数。

include <stdio.h>int calcThrowNumber(int numOfFloors, int numOfBalls){//implement your code here}int main(){int numOfFloors, numOfBalls;while(scanf("%d%d", &numOfFloors, &numOfBalls) != EOF) {printf("%d\n", calcThrowNumber(numOfFloors, numOfBalls));}}

输入

输入数据为一行，包括两个整数N和m（0 < N <= 10000，0 < m <= 10000）

输出

对于每组测试实例，要求输出最少试验次数。

样例输入

100 3

样例输出

2.即时战略游戏编队

时间限制：C/C++语言 2000MS；其他语言 4000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

你正在玩一个RST（即时战略）游戏。此时你已经有很多队士兵，每一队里的士兵战队力相同。该游戏士兵种类以战斗力区分，既战斗力一样的士兵算作一种。你想重新调整编队，将现有的队列合并成战斗力相同的两队，请想出有多少种编队方法吧。

比如：你现在有两队士兵，第一队有4个士兵，每个士兵战斗力都是1，第二队有2个士兵，每个士兵战斗力都是2. 这时你有三种编队方法，可以将这些士兵合并成战斗力相同的两个队伍：

方法一：队伍1有4个战斗力为1的士兵，队伍2有2个战斗力为2的士兵，两队的战斗力都是4

方法二：队伍1有2个战斗力为2的士兵，队伍2有4个战斗力为1的士兵，两队的战斗力都是4

方法三：队伍1有2个战斗力为1的士兵和1个战斗力为2的士兵，队伍2有2个战斗力为1的士兵和1个战斗力为2的士兵，两队的战斗力都是4

输入

两个int型数组，长度均为n（0

今日头条编程题

1.String Shifting

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

我们规定对一个字符串的shift操作如下：

shift(“ABCD”, 0) = “ABCD”

shift(“ABCD”, 1) = “BCDA”

shift(“ABCD”, 2) = “CDAB”

换言之, 我们把最左侧的N个字符剪切下来, 按序附加到了右侧。

给定一个长度为n的字符串，我们规定最多可以进行n次向左的循环shift操作。如果shift(string, x) = string (0 <= x < n), 我们称其为一次匹配(match)。求在shift过程中出现匹配的次数。

输入

输入仅包括一个给定的字符串，只包含大小写字符。

输出

输出仅包括一行，即所求的匹配次数。

样例输入

byebyebye

样例输出

Hint

数据范围

对于40%的数据，字符串长度不超过100；

对于100%的数据，字符串长度不超过10^6。

2.找数字

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

给定整数n和m，将1到n的这n个整数按字典序排列之后，求其中的第m个数字。

对于n = 11，m = 4，按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9，因此第4个数字为2。

输入

输入仅包含两个整数n和m。

输出

输出仅包括一行，即所求排列中的第m个数字。

样例输入

11 4

样例输出

Hint

数据范围

对于20%的数据，1 <= m <= n <= 5；

对于80%的数据，1 <= m <= n <= 10^7；

对于100%的数据，1 <= m <= n <= 10^18。

剑指Offer——完美+今日头条笔试题+知识点总结

剑指Offer——完美+今日头条笔试题+知识点总结

情景回顾

线程中sleep与wait的区别

ConcurrentHashMap