流行的算法？

天策魂之音

明年就毕业

现在要准备求职了

请问下各位大大

在游戏行业里面 作为一个应届生

应该去熟悉哪些算法和数据结构？

常见的排序算法？笔试似乎常见。。可是STL就有而且比我写的要好为什么还考-。-

对我来说A*算法就有点复杂了

如果要求职 是否还要去学习比A*更复杂的算法呢？

多谢各位大大了 [em3]

PS：对于应届生，或者实习生

游戏公司注重的是？

qwertyqqq

我也想知道，大大说说吧，我大三了，还一年多也毕业了

ldhhp

打好基本功吧，不要去测试的时候，连基本的函数和语法格式都忘记了。

tanjiplay

基本功最重要
基本功好了，那些所谓的算法在用的时候查查资料就可以了~~~

天策魂之音

谢谢ls大大

我也觉得基本功很重要

不过笔试的时候常出算法题阿

之前出了一题我到现在还没想出来

大概是把1-100000存在一个数组中，然后任意取两个数出来，再把剩下的99998个数乱序放回数组A中，问只允许遍历数组一次，允许使用5个局部变量，不允许使用数组变量，如何找出这两个数是什么？

有个大概的想法是从A[0]开始，假设A[0]是88,就访问A[88]，一直下去直到A[X]下面没有数，那么令A[Y]=X的Y就是被拿出来的一个数，但是我不知道接下来应该找到下一次的开始的起点了，从A[1]开始显然是不可行的，因为A[1]可能在上一次就被访问过了，从A[1]开始只能是又陷入了上一次的过程之中；又有可能出现A[0]=7;A[7]=0;的情况，这样也无法确认下一次访问应该从哪里开始。。。

各位大大有没有更好的思路？

missh

遍历一遍该数组
求一次和为A, 求一次积为B
然后1+2+...10000-A=x+y
    1*2*...10000/B=x*y
    解之

天策魂之音

missh: Re:流行的算法？

遍历一遍该数组
求一次和为A, 求一次积为B
然后1+2+...10000-A=x+y
    1*2*...10000/B=x*y
    解之

笔试遇到的这题。。要的就是这答案。。？

100000的阶乘是个超大整数阿，我一开始就认为这个方案不可行-。-

您确定？

demonbee

哪位大哥稍微讲清楚点

vinix

把1-100000存在一个数组中，然后任意取两个数出来，再把剩下的99998个数乱序放回数组A中，问只允许遍历数组一次，允许使用5个局部变量，不允许使用数组变量，如何找出这两个数是什么？

异或满足交换律和结合律，并且1^0 = 1，1^1 = 0，0^0 = 0。对于正整数X来说，有两个很重要的性质，X^X = 0，X^0 = X。不过这个性质有什么用吗？请看下面。

有很多个ID，其中只有一个ID出现了1次，其他正常的ID都出现了2次，问如何找到这个次数为1的ID。
有了上面的提示，可以想到把所有的ID进行异或运算，我们可以用x(i) 来表示那个出现一次的ID，由于出现2次的ID异或后为0，所以最后只剩下x(i)为所求的次数为1的ID。x(i) = List[0]^List[1]^…^List。

如果上面的题改成有两个ID出现了1次，那么怎么找出这两个ID呢？

我们假设这两个ID为A和B，当我们把所有的ID异或后，结果为A^B。正常来说A不等于B，所以A^B不为0，也就是这个异或值的二进制中某一位为1。显然，A和B中有且仅有一个数的这一位上也为1。
于是，我们把所有的ID分成两类，一类在这位上为1，另一类这位上为0。那么对于这两类ID，每一类分别含有A和B中的一个。那么再分别计算这两类ID的异或和，即可得到A和B的值。

上面的数组为1-100000，正好符合上面ID的性质。具体解法就不说了，上面解释的应该很清楚了。