小米笔试编程题AC分享

两道题侥幸AC了

1. 集合合并

• 问题：给定若干集合，将其中交集不为空的集合合并，输出合并后集合个数以及最大集合中元素个数

• 思路：并查集

• 代码：

import collections
class Uf(object):
    def __init__(self, n):
        self.id = [i for i in range(n)]
        self.count = n
    def find(self, p):
        while p != self.id[p]:
            p = self.id[p]
        return p
    def union(self,p,q):
        p_id = self.find(p)
        q_id = self.find(q)
        if p_id != q_id:
            for i in range(len(self.id)):
                if self.id[i] == q_id:
                    self.id[i] = p_id
            self.count -= 1
    def connectd(self,p,q):
        return self.find(p) == self.find(q)
    def count():
        return self.count

n = input()
a = []

for _ in xrange(n):
    tmp = set(map(int, raw_input().split()))
    a.append(tmp)

d = collections.defaultdict(list)
for i in xrange(n):
    for val in a[i]:
        d[val].append(i)

uf = Uf(n)
for key,items in d.items():
    father = items[0]
    for it in items:
        uf.union(father,it)

count = uf.count
res = collections.defaultdict(set)

for i in xrange(n):
    p = uf.find(i)
    res[p] |= a[i]

max_res = 0
for k in res:
    max_res = max(max_res, len(res[k]))

print count
print max_res

2. 如何添加运算符

• 问题：给定1~n，在其中插入加减或空格，空格代表连接两个相邻数字，求表达式和为m的个数；

• 分析：问题规模不大n<=7，m<=100，直接dfs暴力求解，这里用到了eval()，也可以自己实现转化为后缀表达式求值的函数；

• 代码：

n,m = map(int, raw_input().split())

res = [0]

def dfs(i,s):
    if i == n:
        if m == eval(s):
            res[0] += 1
    else:
        dfs(i+1,s+'+'+str(i+1))
        dfs(i+1,s+'-'+str(i+1))
        dfs(i+1,s+str(i+1))

dfs(1,'1')
print res[0]