K******g
发帖数: 1870 | 1 今天面试被问到template class怎么处理Inheritance问题，我没有答上来，觉得
template class处理inheritance应该与普通的class没有什么区别。
放下电话后，在effective C++的item43里找到了，derived class cannot inherit
public functions from the base class, we need use this->, or using to use
public functions from the base class in the derived class.
但是，我写了个程序, derived class still can inherit public functions from
the base class.(用的是g++编译器）
请问C++的大牛们，到底哪个对啊？难道这种东西是compiler dependent的？
还有这个面试题应该怎么回答呢？多谢了 |
|
c****s
发帖数: 241 | 2 以前一直说要总结一下自己的面试题，总是忘了，现在补上。
面试我的是替bloomberg找人的consultant公司，这些题目主要是c，c++的知识题。下
面主要是我跟那个HR的聊天记录。有的答得不好，也可能有错误，仅供大家参考：
11:56 AM recruiter: // What happens?
int main()
{
return main();
}
11:58 AM // What prints?
void main()
{
static int var = 5;
printf("%d ",var--);
if(var) main();
}
11:59 AM // What prints?
void main()
{
char *p;
printf("%d %d ",sizeof(*p), sizeof(p));
}
12:00 PM // What prints?
#define a 10
void main()
{
#define a 50
printf("%d",a);
}
// What prints?
void main ()
{ |
|
b*******y
发帖数: 32 | 3 拿到一个bloomberg电面，赶紧准备了一些面试题贴在这里，算是临阵磨枪吧。
===C++===
$. Which one of the following statements accurately
expresses the disadvantages of making a function inline?
a) Inline functions always make the program bigger.
b) Inline functions always make the program slower.
c) Inline functions always make the program bigger and slower.
d) It is not possible to take the address of an inline function.
e) It increases compile-time dependencies.
$. Give scenarios in which even when specifying a func as
inline w |
|
m*****n
发帖数: 2152 | 4 这都是bloomberg面试题？会的不到60%，完蛋了。 |
|
i**********e
发帖数: 1145 | 5 Your argument doesn't sound convincing to me.
Assuming we are finding the 7th largest element, which is in the first
partition according to your example. To apply QuickSelect, you are assuming
you know the order of the elements in that partition... ie, how could you
tell for sure that the 7th largest element is not in [1,2] or [2,1]???
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 6 恩，听你这样说就挺有道理。
QuickSelect 的确不用排好序。
虽然我还是不很信服你这方法能 O(log M + log N) 运行，
但是你这方法的确开启了很好的思路。
我稍候再研究研究，并且顺便啃啃书，理解下 QuickSelect 这玩意。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 7 对了，听你的解说，似乎要 O(M) 来寻找一个 partition 的边界。
这样达不到你所说的 O( log M + log N ) 复杂度吧.(感觉上是 O(M*N)).
这样挺费时的吧，你能展开说说吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
w*****k
发帖数: 20 | 8 考古得到一个今年的google面试题(dawenxi88):已知一个长度为n的数组。假设一个子
集有k个数，则我们有k(k-1)/2个pair(x,y)。定义pair difference为|x-y|，子集的半
径为最小的pair difference。现在要求长度为k的半径最大的子集。原题在
http://www.mitbbs.com/article/JobHunting/31540541_3.html
大家讨论了很多，基本思路是DP。如果要求从A[i,j]中选k个数，则一定是从A[i,m]中
选p个数，A[i,m]中选k-p 个数，遍历所有的m和p，求一个最大值，就可以完成DP的一
步。这个命题看似正确，但是经不住推敲,因为这样组合起来不一定是半径最大的长度
为k的子集。假设
A[] = {0, 25, 49, 51, 75, 100 }
k= 4,p=2.
则{0, 25, 49}的半径最大子集是{0,49},{51, 75, 100 }的半径最大子集是{51,100 }
，但是{0, 25, 49, 51, 75, 100 }的最大半径子集显然不是{0, 49, 51, 100 |
|
i**********e
发帖数: 1145 | 9 paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
http://mitbbs.com/article_t/JobHunting/31731763.html
楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 10 paul 的方法是 O(N)吗？我怎么觉得像 O(MN）？这是因为每次为了计算字串长度，必须寻找 minimum，所以要遍历 M 次。有人可以解释一下吗？
我想到最直接的优化方法就是保持一个 min heap，能 O(1) 索取 minimum，但是代价就是 insert 和 delete 需要 O(lg M)。总复杂度为 O(N lg M)。
还有值得一提的是，以上的例子小串里没有重复的字母。万一小串是 "AABC" 怎么办呢？以上的方法都不能解决这个情况，只有 han6 的方法似乎比较对的，就是利用两个指针。但是解释得有点复杂，建议看 stormrage 的精简解法（在第9楼）。
http://mitbbs.com/article_t/JobHunting/31731763.html
楼上有人说如果 M 相对 N 很小，可以直接忽略，万一面试官不觉得是这么回事那就完蛋啦。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
s******d
发帖数: 538 | 11 phd面工业界经典面试题。为什么不找学术界的工作？总不能说research不强吧。是你
会怎么回答？ |
|
|
i**********e
发帖数: 1145 | 13 你这个答案不够优化，因为：
1）必须构造新的链表，需要额外空间。
2）必须把每一个元素给de-allocate，然后再allocate memory，需要额外的时间。
最优解是不需要变动元素的内存位置，变动的只是指针。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 15 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
经给定整数N （N是矩阵维数）, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time的solution.
这题O(N)的解相信大家都知道了，就是从左下角或者右上角开始搜索（很多人已经讨论过了），可以参考原帖：
http://www.mitbbs.com/article_t/JobHunting/31562567.html
我尝试了另一个解法，思路是利用binary search + divide and conquer。
给个例子：
假设我们所要找的是10。先看中间那列（请参考以下图片，灰色的那列），然后利用binary search的变种找到10是9与14之间。那么，我们可以将矩阵给分成两个（请参考图片，黄色与橙色部分），然后分别在那两个小矩阵以再进行同样的搜索。
我可以证明一个case，就是假设每次矩阵被分成两个同样大小的矩阵，那么复杂度就是:
T(n) = 2T(n/2) + c lg n
= O(N) <== 这里我省略了一些证明步骤。
注：... 阅读全帖 |
|
i**********e
发帖数: 1145 | 16 Thanks for your answer.
However, you have made an assumption that each divide is only eliminating
one row/column, which is not true.
Since we always choose the center column, each divide will eliminate half of
the columns (If the partition point is at the top most row/bottom most row)
. Therefore, we only need to perform at most log N divisions, but in your
case, it seems to be doing M+N divisions. How can that be possible?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
is |
|
i**********e
发帖数: 1145 | 17 Thanks again for your post.
Sorry I didn't make it clear in my question. If I am understand correctly,
you are trying to eliminate one row/column each time, therefore getting a lg
(N!) or N lg N solution.
I am asking for the worst case of the approach I mentioned in my first post.
This approach partitions the matrix to two sub-matrices each time, but the
problem is the two sub-matrices could be of different sizes.
There might be a case where each time it partitions the matrix to one sub-matrix
o... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 谢谢你们的尝试，我又尝试了一个方案，但还是不能证明worst case的upper bound是O
(N).
思路是这样的：
假设矩阵的大小是 NxM，那么总共有 NxM 个元素。每一次划分可以保证去除正好 NM/2
个元素。第二层的划分又可以保证去除 NM/4 个元素。那么最坏的情况我们可以保证
划分的层数绝对不会超过 lg (NM)。这也表示 recursion 的深度不会超过 lg (NM)。
第一层我们总共用了 lg N 的时间来去除 NM/2 个元素，剩下 NM/2 个元素来搜索。
第二层我们总共用了 lg(i1) + lg(N-i1) 的时间来去除 NM/4 个元素，剩下 NM/4 个
元素。（i1 是第二层选择的划分点）
Complexity:
1st level = lg (N), NM/2 items left
2nd level = lg(i1) + lg(N-i1), NM/4 items left
3rd level = lg(i2) + lg(i1-i2) + lg(i3) + lg(N-i1-i3), NM/8 items left... 阅读全帖 |
|
d***8
发帖数: 1552 | 19 能展开说说吗？
怎么存储链表里的data和next指针？
another list 是作什么用的？
多谢！
这是一道面试题。他让我周末作完发给他。 |
|
d****j
发帖数: 293 | 20 来自主题: JobHunting版 - 经典面试题 这个是正解！
Wiki里面的伪代码非常经典：
multiply(a[0..n−1], b[0..n−1]) // Arrays representing the binary
representations
x ← 0
for i from 0 to 2n−2
for j from max(0,i+1−n) to min(i,n−1)
k ← i − j
x ← x + (a[j] × b[k])
result[i] ← x mod 2
x ← floor(x/2)
return result[];
其中a, b [0,..n-1]表示从低位到高位的顺序，计算的顺序也是从低到高
改成10进制也很简单，x mod 2 改成 x%10, x/2-> x/10 即可。
注意，最后的进位上面代码里面没处理，需要处理一下。
自己练一下，还是很好玩的，特别是里面j的取值范围。
此外，如果a和b的数量级不一样，... 阅读全帖 |
|
w*********9
发帖数: 120 | 21 刚收到一份投行的笔试题，3题，给我3天时间做完，然后写一份答卷给他们。本人学工
科，没有什么商学背景，所以对其中一题有点问题，紧急求助！！！
问题：Please estimate the market size of salt （没有背景资料什么的，就这个问
题）。
我一看到这个题目，第一反应就是应该用“北京有几个理发店，北京一天卖出去多少个
煎饼”此类题目的思路作答，但是看了看前后的题目。前面一题是描述**行业的市场动
态，后一题是归纳**企业的核心进争力，似乎夹在中间的这题不应该属于脑筋急转弯类
型的，应该是要好好查资料查数据给出大概估计的，不知有没有有经验的同学点拨一下
？？
我的思路把salt分成食用盐和工业用盐两块，分别查资料统计。食用盐主要通过食用盐
主要品牌的销售量或者产量来估计（如何？），工业用盐比较费解，只考虑工业用NaCl
？什么工业用NaCl量比较大？这个要怎么查啊，不知道食用盐和工业用盐的制造商是不
是都是一样的~~，求助~~~~。然后这些销售量，产量的数据应该到什么地方查？我看网
上有行业报告available，但是都要钱~~~，闷心~
不知道我的思路有没有错... 阅读全帖 |
|
z*s
发帖数: 209 | 22 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
每人问45分钟。
一、
1、1~1000的数中有一个重复的数，把这个数找出来。
2、找出Binary Search Tree树的Median number。
这两道题的要求都是提出尽量多的算法，并给出复杂度。
3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
？他想要的答案大概是："Big O notation discards multiplicative constants on
the running time, and ignores efficiency for low input sizes, it does not
always reveal the fastest algorithm in practice or for practically-sized
data sets." http://en.wikipedia.org/wik... 阅读全帖 |
|
n****t
发帖数: 241 | 23 第二题怎么做？
这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
每人问45分钟。
一、
1、1~1000的数中有一个重复的数，把这个数找出来。
2、找出Binary Search Tree树的Median number。
这两道题的要求都是提出尽量多的算法，并给出复杂度。
3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
？他想要的答案大概是："Big O notation discards multiplicative constants on
the running time, and ignores efficiency for low input sizes, it does not
always reveal the fastest algorithm in practice or for practically-sized
data sets." http://en.wikipedi... 阅读全帖 |
|
n****t
发帖数: 241 | 24 我看到貌似正确的一个解法，加了很多限制条件。。。
面试题之二叉搜索树的中位数 收藏
这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
* No extra memory.
* Function should be reentrant (No static, global variables allowed.)
* Median for even no of nodes will be the average of 2 middle elements and
for odd no of terms will be middle element only.
* Algorithm should be efficient in terms of comple... 阅读全帖 |
|
i**********e
发帖数: 1145 | 25 我也尝试解一解这题，不知道是不是跟各位大侠的解法一样，欢迎讨论。
假设定义：
4A 为 连敲 4 次 A，
2D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V,将之前的 A X 2，
3D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V,将之前的 A X 3.
f(N) 为最优解.
n <= 7, 那么 f(n) = n.
n = 8, f(n) = 3A3D = 9.
n = 9, f(n) = 3A4D = 12.
n = 10, f(n) = 4A4D = 16.
n = 11, f(n) = 4A5D = 20.
n = 12, f(n) = 5A5D = 25.
n = 13, f(n) = 5A6D = 30.
n = 14, f(n) = 6A6D = 36.
思路很明显，就是要求 a*b = n-2, 并且 a 和 b 相乘为最大值。
注意了，
n = 15, f(n) = 6A7D = 42？
这是错的，因为当 n = 15,
f(n) = 3A4D4D = 48.
n = 16, f(n) = 4A4D4D = ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 26 谢谢你的总结。
可是我不明白，为什么以每节6击键(ACVVVV = 4D)为单位循环的效率最高？
给个例子，
当 n = 26,
f(n) = 5A5D5D5D (AAAAA ACVVVVV ACVVVVV ACVVVVV) = 625.
里面并没有 ACVVVV (4D) 的连接呀？
可能我理解错了？如果我的答案是错的，请指教。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
每节7击键(ACVVVVV)。
h(k) 有最大值。 |
|
i**********e
发帖数: 1145 | 27 n = 13, f(n) = 5A6D = 30. ( a = 5, b = 6, f(n) = a*b = 5*6 = 30 )
n = 14, f(n) = 6A6D = 36. ( a = 6, b = 6, f(n) = a*b = 6*6 = 36 )
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 29 这不一定。
if n = 19,
x=y=z= 19/4 = 4
4*4*4*7 = 448
But the max should be
4*5*5*5 = 500
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 30 不是大侠，贴一贴我的代码，代码如果不好看 请多多包涵
恐怕只能 handle 以上的 sample test case。
基本思路就是递归，如果有更复杂的情况可以再慢慢改进。
#include
#include
#include
using namespace std;
const int TAB_SPACE = 4;
void outputJSon(istream &in, int indentLevel) {
bool firstChar = true;
bool inBracket = false;
while (in) {
char c = in.get();
if (firstChar) {
cout << endl << setw(indentLevel) << c;
firstChar = false;
}
else {
cout << c;
}
if (c == '{') {
outputJSon(in... 阅读全帖 |
|
i**********e
发帖数: 1145 | 31 其实不递归 代码或许会更简单些
void outputJSon(istream &in) {
bool newLine = false;
bool inBracket = false;
int indentLevel = 0;
while (in) {
char c = in.get();
if (newLine) {
cout << endl << setw(indentLevel) << c;
newLine = false;
}
else {
cout << c;
}
if (c == '{') {
indentLevel += TAB_SPACE;
newLine = true;
} else if (!inBracket && c == ',') {
newLine = true;
} else if (c == '}') {
newLine = true;
} else if (c == '[') {
... 阅读全帖 |
|
l********h
发帖数: 130 | 32 最最经典和简单的一个java面试题，要求占用最少的内存和最好的算反。
我能想出至少3种方法，但是不知道那种最好。
Reverse words in a string. Example: AA BBB cccc -> cccc BBB AA
不允许用java.util
我知道的：
1）String.Split
2) Pattern
3）StringBuffer.reverse
请大牛问问有啥最好的算法并前占用最少的内存 |
|
i**********e
发帖数: 1145 | 33 The idea is simple but subtle. This trick is discussed in Programming Pearls.
Reverse the entire string.
Then reverse the characters for each individual word.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 34 最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
我想到一个利用堆的解法，可以达到 O(k log min(m, n)).
但看网上 google 要求的最优解法好... 阅读全帖 |
|
|
|
i**********e
发帖数: 1145 | 37 My solution using a heap and an array that maps indices from A to B.
const int MAX_M = 100;
const int MAX_N = 100;
typedef pair Pair;
int findKthLargestSum(int A[], int m, int B[], int n, int k) {
priority_queue Q;
int AToB[MAX_M] = {0}; // keep track of each col's indices that's
traversed.
// pushes all elements of the first row into heap
for (int i = 0; i < m; i++)
Q.push(Pair(A[i]+B[0], i));
// loop k-1 times to find the first k-1 elements
for (int i = 0; i < ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 38 To answer your question, No.
Counter example:
A = [9 8 7 6]
B = [9 7 2 1]
9 8 7 1
9 18 17 16 10
7 16 15 14 8
2 11 10 9 3
1 10 9 8 2
The 4th element (16) is not on any of A[4,1], a[3,2], a[2,3], a[1,4].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 39 LZ 谢谢分享。
我能想到的是用一个 table + double ended queue，O(n)，不知道还能不能更优化.
table 用来记录当前的字符访问过没.
每遇到一个不曾碰过的字符就 push 到 queue 的后边，然后纪录在 table 里.
如果字符被访问过了，就 update 一下 maximum length，然后一个一个从前头 pop，
直到 pop 出来的字符和此字符相等. 每次 pop 的时候也要更新 table.
总复杂度应该是 O(n)，因为每个字符最多被 push 和 pop 各一次.
解法有点类似于 google 的 sliding window 经典题.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
|
|
|
i**********e
发帖数: 1145 | 44 代码虽然对了，但是你这个不用 table 复杂度是很高的。
你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
度没法做到 O(N)。
简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
多，你可以比较一下）
虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 45 呵呵，
想说 O(N^2) 和 O(N) 的复杂度相差不大，有没有搞错？
不过这问题由于局限于26个不同的字母，所以可以保证过了26个字母就会有至少一个重
复的。
万一如果没有这样的局限，你的代码肯定会跑得更慢了。。只要一直没遇到重复的，你
的指针就一直要从头开始扫描.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 46 4. 很久以前写的大数 class. 基本思路很简单，就是小学的乘法 + carry.
BigInt BigInt::multiply(const BigInt &b) const
{
BigInt answer;
BigInt temp;
int carry = 0;
for (int i = 0; i < b.numDigits; i++)
{
temp.numDigits = this->numDigits + 1;
int down = b.digits[i];
for (int j = 0; j <= this->numDigits; j++)
{
int up = (j < this->numDigits) ? this->digits[j] : 0;
int tempDigit = up * down + carry;
temp.digits[j] = tempDigit % 10;
carry = tempDigit / 10;
}
temp.s... 阅读全帖 |
|
i**********e
发帖数: 1145 | 47 我的公式是：
i from 1 to n
j from i to n
max(i,j) = A[i], when i = j,
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1)), when i != j
max coins get by player 1 = max(1,n)
这公式跟你是一样的吧？(a(i)+sum(i+1,j) = sum(i,j))
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 48 如果硬币个数为偶数的话，就如 lilacc 和 ibread 所说的，只要比较奇数位置硬币之
和，还有偶数硬币之和就可以了。这是因为硬币个数为偶数时，先走的能够确保对手拿
所有奇数（或是偶数）位置的硬币。
打个比方，如果总共有10枚硬币。我先拿位置 1 的硬币，那对手就必须选择位置 2 或
者 10 的硬币。如果我先拿位置 10 的硬币，对手只能选择位置 1 或 9 的硬币。在硬
币个数为偶数时，这样的策略能保证对手拿的硬币位置全是偶数（或奇数），因此先拿
的绝对不会输。
如果硬币个数为奇数的话，那就要多算一步。假设对手也聪明，利用以上的策略，那就
可以准确预测对手下一步会拿那一枚硬币。这样就只需要算多一步。这时候，先拿的未
必会赢。
哦，明白了，dp 公式算的是 maximum possible amount，这里指的是对手拿硬币不一定根据以上的策略。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 49 你这 dp 公式跟我是一样的：
max(i,j) = max(sum(i,j)-max(i+1,j), sum(i,j)-max(i,j-1))，
然后 base case 为 max(i, j) = A[i], when i == j
可以用递归两行代码搞定，如果要提高效率的话用二维数组当缓冲，以免重复计算。
其实根本不需要这个公式来计算，直接计算硬币偶数位置的和，还有硬币奇数位置的和
，哪一个大就是答案了。（如果硬币个数是奇数的话，算多一步就知道答案了）。这是
因为对手也是聪明的，那他也会用同样的策略，所以对手的每一步都是可以预知的，所
以不需要 dp 公式来计算。
那如果把问题换为：
我先拿硬币，假设对手非常笨（尽量使得我拿到最多的硬币总值），那我最多能拿多少
呢？
这问题就要用 dp 来解了。
大家来探讨下思路吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 50 终于把这题研究明白了，而且找到自己错在哪里，希望以下的总结对各位有帮助.
的和，哪一个大就是答案了。
刚刚发现一个 counter example 证明以上的说法是错的.
举例：
{3,2,2,3,1,2}
这时候第一个拿硬币的人最多可以拿到 8 的总值。（不管对手采取什么策略）
第一步拿左 3，这时候对手可以选择拿左 2 或右 2.
-- 如果对手拿左 2，我就拿右 2，剩下 {2,3,1}. 最后的 3 我是吃定的了。总值
为 8.
-- 如果对手拿右 2，我就拿左 2，剩下 {2,3,1}. 最后的 3 我也是吃定了。总值
也为 8.
所以，不管对手采取什么策略，我都能保证我最多能拿 8（假设对手是聪明的）.
如果算偶数位置的总值（7）和奇数位置的总值（6），这样虽然获胜，但不能保证能拿
到最大的硬币总值。当硬币个数为偶数时，这策略能保证绝对不输（但有可能打平）
但是，当硬币个数为奇数的时候就不能用以上的策略。当我拿了第一枚硬币之后，硬币
个数就成为偶数了。对手并不一定会使用以上的策略。所以，要寻找你所能拿到最大的
硬币总值，必须使用 DP 来解。
公式为：(wh... 阅读全帖 |
|
