淘先锋技术网

首页 1 2 3 4 5 6 7

2.3 寻找发帖“水王”

题意:给N个数,其中某个数出现的次数超过一半,找出这个数。

这道题目书中给出的解题思路是,在所有ID中,每次删除两个不同的ID,剩下的就是要求的ID。

这个思想比较简单,但作者给出的代码策略很值得学习。代码维护一个具有相同元素的容器,由于元素相同,我们只需要用两个变量分别记录容器中元素的ID和个数。对于一个新需要考察的ID,若容器为空,则把这个元素加入容器,若不为空,则对比容器中ID和当前ID是否相等,相等则容器元素个数加1,不等则减1。

对于扩展问题中,3个水王的情况,我们可以维护三个容器,思想还是一样的。首先考虑是否可以合并到容器中去,若合并不了,则说明这是一个和已有容器中ID都不一样的元素,此时,若已经有3个不为空的容器,则可以都消去1,若容器不足3个,则为此元素新建一个容器。

def find(IDs):
    c = {}
    for ID in IDs:
        try:
            c[ID] += 1
        except:
            if len(c) == 3:
                for k in c:
                    c[k] -= 1
                    if c[k] == 0:
                        del c[k]
            else:
                c[ID] = 1
    return c

if __name__ == "__main__":
    IDs = [11, 22, 11, 22, 33, 33, 44]
    print find(IDs)

 

2.4 1的数目

题意:写一个函数f(N),返回1到N之间出现的“1”的个数。

解法一是一个暴力搜索算法,遍历1到N,并找出每个数字的每个位上面是否存在1,这个方法的缺点很明显,效率差。

解法二实际上是一个找规律的方法,这个规律虽然不难找,但不是很简明。

这种找规律的过程,锻炼一下思维还是不错的。

转载于:https://www.cnblogs.com/xcoder/archive/2012/11/01/2750173.html