全排列

整数表示

放棋子

<a href="http://www.gznb.xyz/posts/pythonTip-90-放棋子/">题解： http://www.gznb.xyz/posts/pythonTip-90-放棋子/</a>

按一般的人解决这个问题的思维来：比如下面这个ooxoxooxooxoxxxx我们自然会想，第一行有两个连通集，每个里面至多取一个，第二行只有一个连通集……所以我的思路就是 &nbsp;先做个f，判断AB两个点是不是联通然后按行，把每个连通集做出来，比如刚才的例子就是 {【0,0】，【0,1】}{【03】}{【1,1】【1,1】}{【2,0】【2,1】}{【2,3】}因为这个连通集里也可以不取，所以每个连通集里再加个空集，第一个元素就变成&nbsp;{【0,0】，【0,1】，【】}然后就从每个连通集里，依次开始取里面的元素构成点集，一边构，一边判断会不会纵向联通。最后，把所有构成点集的可能性里，空集最少的那个就是取点最多的那个。 import copy def f(a,b): &nbsp; &nbsp; if a==[] or b==[]: &nbsp; &nbsp; &nbsp; &nbsp; return 0 &nbsp; &nbsp; flag=0 &nbsp; &nbsp; if a[0]==b[0]: &nbsp; &nbsp; &nbsp; &nbsp; c,d=min(a[1],b[1]),max(a[1],b[1]) &nbsp; &nbsp; &nbsp; &nbsp; flag=1 &nbsp;#连接&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i in range(c+1,d): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if L[a[0]][i]=='X': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 0 &nbsp; &nbsp; if a[1]==b[1]: &nbsp; &nbsp; &nbsp; &nbsp; c,d=min(a[0],b[0]),max(a[0],b[0]) &nbsp; &nbsp; &nbsp; &nbsp; flag=1 &nbsp; &nbsp; &nbsp; &nbsp; for i in range(c+1,d): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if L[i][a[1]]=='X': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 0 &nbsp; &nbsp; return flag S=[] t=-1 for i in range(n): &nbsp; &nbsp; for j in range(n): &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if L[i][j]=='X': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue &nbsp; &nbsp; &nbsp; &nbsp; elif L[i][j]=='.' and t==-1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t=t+1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; S.append([[i,j]]) &nbsp; &nbsp; &nbsp; &nbsp; elif L[i][j]=='.' and f(S[t][-1],[i,j]): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; S[t].append([i,j]) &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t=t+1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; S.append([[i,j]]) for i in range(len(S)): &nbsp; &nbsp; S[i].append([]) K=[] for i in range(len(S)): &nbsp; &nbsp; K2=[] &nbsp; &nbsp; for j in S[i]: &nbsp; &nbsp; &nbsp; &nbsp; K1=copy.deepcopy(K) &nbsp; &nbsp; &nbsp; &nbsp; if i==0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; K1.append([j]) &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for m in range(len(K)): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for k in K[m]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if f(j,k): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; K1[m].append([]) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if not flag: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; K1[m].append(j) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; K2=K2+K1 &nbsp; &nbsp; K=copy.deepcopy(K2) a=n for i in range(len(K)): &nbsp; &nbsp; a=min(a,K[i].count([])) print len(S)-a

要注意，多维的list，复制不能简单用L=L1 或L=L1[:],一定要用 import COPY &nbsp; COPY.DEEPCOPY害得我调试代码一整天。

联通集 分组

一开始做的时候是直接使用贪心策略,从(0,0)位置开始到最后一个位置,如果可以放的话就直接放,但是这有一个问题,针对如下的LL=[&quot;....&quot;, &nbsp; &nbsp;&quot;.X..&quot;, &nbsp; &nbsp;&quot;....&quot;, &nbsp; &nbsp;&quot;....&quot;]答案应该是5才对,但是如果从(0,0)开始测试的话, 输出是4；因为第一行最好的位置是放置在(0,1)的位置,而不是(0,0)的位置,所以改进下,使用权重型的,给每个位置设置权重,权重的设置策略为每个位置初始为0,当前位置的周边四个位置,如果是X的话就加1,如果是.的话,就减1,然后遍历L的时候,从权重大的开始遍历判断可不可以放棋的策略是,按四个方向去测试,如果一直往这个方向,到边界也没有遇到已经放棋子的地方或是中途先遇到了X的话,就说明这个位置可以安放棋子了 代码如下<pre class="prettyprint lang-py linenums">def greedy(n, poss, L):
	steps = [(0,1),(0,-1),(1,0), (-1,0)]
	flags = [[False for i in range(n)] for j in range(n)]
	count = 0
	for pos in poss:
		i = pos[0]
		j = pos[1]
		temp = True
		if L[i][j] == '.':
			temp = True
			for step in steps: #按四个方向来遍历测试是否行得通
				new_i = i
				new_j = j
				while True:
					new_i += step[0]
					new_j += step[1]
					if isbound(new_i, new_j, n) or L[new_i][new_j] == 'X':
						break
					elif not isbound(new_i, new_j, n) and flags[new_i][new_j] == True:
						temp = False
						break
				if temp == False:
					break
			if temp == True:
				flags[i][j] = True
				count += 1
				#print 'pos', i, j
	#print flag
	return count

def isbound(i,j,n): #判断是不是边界
	if i &lt; 0 or i &gt;= n or j &lt; 0 or j &gt;= n:
		return True
	else:
		return False

def gen_weight_L(L, n): #按策略生成权重型的位置
	poss = []
	steps = [(0,1),(1,0),(-1,0),(0,-1)]
	for i in range(n):
		for j in range(n):
			count = 0
			for step in steps:
				new_i = i + step[0] 
				new_j = j + step[1]
				if new_i &gt;= 0 and new_i &lt; n and new_j &gt;= 0 and new_j &lt; n:
					if L[new_i][new_j] == 'X':
						count += 1
					else:
						count -= 1
			poss.append((i,j,count))
	size = len(poss)
	for i in range(1, size):
		for j in range(0, size - i):
			if poss[j][2] &lt; poss[j+1][2]:
				temp = poss[j]
				poss[j] = poss[j+1]
				poss[j+1] = temp
	return poss



poss = gen_weight_L(L, n)
#print poss
count = greedy(n, poss, L)
print count
</pre>

带权重的贪心策略

思路: &nbsp;给每个可放棋子的位置计算权值。&nbsp;一个位置四周的障碍物/墙越多，权值越大。&nbsp;如果两个位置的四周的障碍物/墙数相等， 再比较这两个位置放下棋子后影响到的位置数， 影响的越少，权值越大。算出权值后， 依次取权值最大的位置，放下棋子，直至无处可放，即得到最大可放下的棋子数。 steps = [[0,1],[1,0],[0,-1],[-1,0]]; def getMaxNum(L,n): 	weights = [[] &nbsp;for x in xrange(0,5)]; 	weights1 = [[] for x in xrange(0,5)]; 	marks = [[ x for x in y] for y in L]; 	for i in xrange(0, n): 		for j in xrange(0,n): 			if L[i][j] != &quot;.&quot;: 				continue; 			weight = 0; 			for step in steps: 				if (0 &lt;= i + step[0] &lt; n) and (0 &lt;= j + step[1] &lt; n): 					if L[i+step[0]][j+step[1]] == 'X': 						weight += 1; 				else: 					weight += 1; 			weight1 = 2*n; 			x = i - 1; 			while &nbsp;0 &lt;= x and L[x][j] != 'X': 				weight1 -= 1; 				x -= 1; 			x = i + 1; 			while &nbsp; x &lt; n and L[x][j] != 'X': 				weight1 -= 1; 				x += 1; 			y = j - 1; 			while &nbsp;0 &lt;= y and marks[i][y] != 'X': 				weight1 -= 1; 				y-=1; 			y = j + 1; 			while &nbsp;y &lt; n and marks[i][y] != 'X': 				weight1 -= 1; 				y+=1; 			y = j + 1; 			k = 0; 			while k &lt; len(weights[weight]) and weights1[weight][k] &gt; weight1: 				k += 1; 			weights[weight].insert(k,(i,j)); 			weights1[weight].insert(k,weight1); 	count = 0; #	print weights; 	for k in xrange(4, -1, -1): 		for (i, j) in weights[k]: 			if marks[i][j] == &quot;0&quot;: 				continue; 			marks[i][j] = 1; 			count += 1; 			x = i - 1; 			while &nbsp;0 &lt;= x and marks[x][j] != 'X': 				marks[x][j] = &quot;0&quot;; 				x -= 1; 			x = i + 1; 			while &nbsp; x &lt; n and marks[x][j] != 'X': 				marks[x][j] = &quot;0&quot;; 				x += 1; 			y = j - 1; 			while &nbsp;0 &lt;= y and marks[i][y] != 'X': 				marks[i][y] = &quot;0&quot;; 				y -= 1; 			y = j + 1; 			while &nbsp;y &lt; n and marks[i][y] != 'X': 				marks[i][y] = &quot;0&quot;; 				y += 1; #	print marks 	return count; print getMaxNum(L,n);

上面代码还是有点问题。修改如下。 def getMaxNum(L, n): 	weights = [[] &nbsp;for x in xrange(0,2* n &nbsp;)]; 	marks = [[ x for x in y] for y in L]; 	for i in xrange(0, n): 		for j in xrange(0,n): 			if L[i][j] != &quot;.&quot;: 				continue; 			weight = 2*n - 1; 			x = i - 1; 			while &nbsp;0 &lt;= x and L[x][j] != 'X': 				weight -= 1; 				x -= 1; 			x = i + 1; 			while &nbsp; x &lt; n and L[x][j] != 'X': 				weight -= 1; 				x += 1; 			y = j - 1; 			while &nbsp;0 &lt;= y and marks[i][y] != 'X': 				weight -= 1; 				y-=1; 			y = j + 1; 			while &nbsp;y &lt; n and marks[i][y] != 'X': 				weight -= 1; 				y+=1; 			weights[weight].append((i,j)); 	count = 0; #	print weights; 	for k in xrange(2*n - 1, -1, -1): 		for (i, j) in weights[k]: 			if marks[i][j] == &quot;0&quot;: 				continue; 			marks[i][j] = 1; 			count += 1; 			x = i - 1; 			while &nbsp;0 &lt;= x and marks[x][j] != 'X': 				marks[x][j] = &quot;0&quot;; 				x -= 1; 			x = i + 1; 			while &nbsp; x &lt; n and marks[x][j] != 'X': 				marks[x][j] = &quot;0&quot;; 				x += 1; 			y = j - 1; 			while &nbsp;0 &lt;= y and marks[i][y] != 'X': 				marks[i][y] = &quot;0&quot;; 				y -= 1; 			y = j + 1; 			while &nbsp;y &lt; n and marks[i][y] != 'X': 				marks[i][y] = &quot;0&quot;; 				y += 1; #	print marks 	return count; print getMaxNum(L, n);

仔细想想的话，计算权值只需要计算每个位置放下棋子后影响的位置数， 影响越少权值越大，即可。更新代码。还有优化空间。 def getMaxNum(L, n): 	weights = [[] &nbsp;for x in xrange(0,2* n - 1 )]; 	marks = [[ x for x in y] for y in L]; 	for i in xrange(0, n): 		for j in xrange(0,n): 			if L[i][j] != &quot;.&quot;: 				continue; 			weight = 2*n - 2; 			x = i - 1; 			while &nbsp;0 &lt;= x and L[x][j] != 'X': 				weight -= 1; 				x -= 1; 			x = i + 1; 			while &nbsp; x &lt; n and L[x][j] != 'X': 				weight -= 1; 				x += 1; 			y = j - 1; 			while &nbsp;0 &lt;= y and marks[i][y] != 'X': 				weight -= 1; 				y-=1; 			y = j + 1; 			while &nbsp;y &lt; n and marks[i][y] != 'X': 				weight -= 1; 				y+=1; 			weights[weight].append((i,j)); 	count = 0; #	print weights; 	for k in xrange(2*n - 2, -1, -1): 		for (i, j) in weights[k]: 			if marks[i][j] == &quot;0&quot;: 				continue; 			marks[i][j] = 1; 			count += 1; 			x = i - 1; 			while &nbsp;0 &lt;= x and marks[x][j] != 'X': 				marks[x][j] = &quot;0&quot;; 				x -= 1; 			x = i + 1; 			while &nbsp; x &lt; n and marks[x][j] != 'X': 				marks[x][j] = &quot;0&quot;; 				x += 1; 			y = j - 1; 			while &nbsp;0 &lt;= y and marks[i][y] != 'X': 				marks[i][y] = &quot;0&quot;; 				y -= 1; 			y = j + 1; 			while &nbsp;y &lt; n and marks[i][y] != 'X': 				marks[i][y] = &quot;0&quot;; 				y += 1; #	print marks 	return count;

抛砖

各种判定有点多，看上去很乱def rc(ll,r,L,n):     fb=[]     l0=list(range(n))     lx=[] for i in range(n-1,-1,-1): if L[r][i]==&#x27;X&#x27;:             lx.append(i) del l0[i] continue for l in ll: if l[1]!=i: continue else:                 sl=[] for c in range(l[0]+1,r):                     sl.append(L[c][i]) if &#x27;X&#x27; not in sl: del l0[i] break if len(l0)==0: return [] if len(lx)==0:         ln=l0 for l in ln:             fb.append(ll+[[r,l]]) return fb else:         lln=[list(range(lx[0]))]         lx.append(n) for i in range(len(lx)-1):             sl=list(range(lx[i]+1,lx[i+1])) if len(sl)&gt;0:                 lln.append(sl) for i in range(len(lln)-1,-1,-1):             lln[i]=list(set(lln[i])&amp;set(l0)) if len(lln[i])==0: del lln[i]         ln=[[]] for i in range(len(lln)): for ii in range(len(ln)):                 l=ln[ii] for j in range(len(lln[i])):                     ln.append(l+[lln[i][j]]) del ln[0] for l in ln:             lz=[] for l1 in l:                 lz+=[[r,l1]]             fb.append(ll+lz) return fb def solve_it():     wl=[[]] for row in range(n): for wi in range(len(wl)):             w=wl[wi]             wl+=(rc(w,row,L,n)) for wi in range(len(wl)):         wl[wi]=len(wl[wi]) return max(wl) #your answer print(solve_it())  # 答案需要输出

第90题：放棋子

神の安♂排

大小写转换

完美数

木棒问题