1.字母轉(zhuǎn)換問(wèn)題

題目要求：

你得到一個(gè)可能混合大小寫(xiě)字母的字符串，你的任務(wù)是把該字符串轉(zhuǎn)為僅使用小寫(xiě)字母或者大寫(xiě)字母，為了盡可能少的改變：

如果字符串包含的大字母數(shù)小于等于小寫(xiě)字母數(shù)，則把字符串轉(zhuǎn)為小寫(xiě)。

如果大寫(xiě)的數(shù)目大于小寫(xiě)字母數(shù)，則把字符串轉(zhuǎn)為全大寫(xiě)。

比如：

solve('coDe')=="code" 
solve("CODe")=="CODE" 

這道題稍微簡(jiǎn)單一點(diǎn)，怎么解呢：

1).屌絲解法：

對(duì)字符串中的每個(gè)字符進(jìn)行判斷大寫(xiě)還是小寫(xiě)

大寫(xiě)則計(jì)數(shù)+1，小寫(xiě)也+1

比較兩種計(jì)數(shù)的大小，然后對(duì)字符串進(jìn)行大小寫(xiě)反轉(zhuǎn)

2).進(jìn)階解法

稍微把算法優(yōu)化一下，我們對(duì)小寫(xiě)的取-1，大寫(xiě)的取1，然后計(jì)算和。

大于0則全部大寫(xiě)，否則則全部小寫(xiě)

3).高手解法

這種解法絕對(duì)讓人拍案叫絕，值得思考。

2.數(shù)獨(dú)問(wèn)題

題目要求：

寫(xiě)一個(gè)函數(shù)檢驗(yàn)數(shù)獨(dú)是否完成：

• 如果完成，返回 “Finished!”
• 如果未完成，返回 “Try again!”

數(shù)獨(dú)規(guī)則

• 數(shù)獨(dú)為9行9列。
• 每一行和每一列均由 [1-9] 9個(gè)不重復(fù)數(shù)字組成。
• 將 9行x9列 的數(shù)獨(dú)分割為9個(gè)小區(qū)域，每個(gè)區(qū)域3行3列，且保證每個(gè)小區(qū)域數(shù)字也是從[1-9] 9 個(gè)不重復(fù)數(shù)組成。

屌絲解題思路：

board = [ 
[1, 3, 2, 5, 7, 9, 4, 6, 8], 
[4, 9, 8, 2, 6, 1, 3, 7, 5], 
[7, 5, 6, 3, 8, 4, 2, 1, 9], 
[6, 4, 3, 1, 5, 8, 7, 9, 2], 
[5, 2, 1, 7, 9, 3, 8, 4, 6], 
[9, 8, 7, 4, 2, 6, 5, 3, 1], 
[2, 1, 4, 9, 3, 5, 6, 8, 7], 
[3, 6, 5, 8, 1, 7, 9, 2, 4], 
[8, 7, 9, 6, 4, 2, 1, 3, 5] 
] 

1).可以將上邊列表看成一個(gè)矩陣圖形

首先要滿(mǎn)足的條件是行和列都必須由[1-9] 9個(gè)不重復(fù)的數(shù)組成。判斷行是否滿(mǎn)足條件：遍歷列表 board，然后對(duì)每個(gè)元素（行）進(jìn)行去重然后計(jì)算長(zhǎng)度，生成一個(gè)新列表

row_len=[len(set(row)) for row in board] 
# 結(jié)果為： 
[9, 9, 9, 9, 9, 9, 9, 9, 9] 
# 說(shuō)明每一行去重后仍有9個(gè)元素，說(shuō)明沒(méi)有重復(fù)元素 
# ***只需要判斷新生成的列表row_len 元素之和是否等于 81，就可以知道每一行是否有重復(fù)數(shù)字。 

2).判斷列是否滿(mǎn)足條件

將 board 行列轉(zhuǎn)換，然后像判斷行一樣進(jìn)行判斷

board2 = map(list,zip(*board)) 
# 結(jié)果： 
[[1, 4, 7, 6, 5, 9, 2, 3, 8], 
[3, 9, 5, 4, 2, 8, 1, 6, 7],  
[2, 8, 6, 3, 1, 7, 4, 5, 9],  
[5, 2, 3, 1, 7, 4, 9, 8, 6],  
[7, 6, 8, 5, 9, 2, 3, 1, 4],  
[9, 1, 4, 8, 3, 6, 5, 7, 2],  
[4, 3, 2, 7, 8, 5, 6, 9, 1],  
[6, 7, 1, 9, 4, 3, 8, 2, 3],  
[8, 5, 9, 2, 6, 1, 7, 4, 5]] 

3).***判斷行和列是否都滿(mǎn)足條件

def done_or_not(board): 
if sum([len(set(col)) for col in board2]) == 81 and sum([len(set(row)) for row in board]) ==81 : 
pass 
else: 
return 'Try again!' 

4).怎么分成9個(gè)小塊呢

使用numpy 將列表轉(zhuǎn)換為 array ，然后使用切片很方便的得到小區(qū)域，例如：

import numpy as np

board_array = np.array(board)
board_array[0:3,0:3] #取***行到第三行，第1列到第3列的，3x3小區(qū)塊
#結(jié)果：

import numpy as np 
 
board_array = np.array(board) 
board_array[0:3,0:3] #取***行到第三行，第1列到第3列的，3x3小區(qū)塊 
#結(jié)果： 
 
array([[1, 3, 2], 
 [4, 9, 8], 
 [7, 5, 6]]) 
 
那分成9個(gè)小區(qū)塊就是： 
board_array[0:3,0:3] 
board_array[0:3,3:6] 
board_array[0:3,6:9] 
board_array[3:6,0:3] 
board_array[3:6,3:6] 
board_array[3:6,6:9] 
board_array[6:9,0:3] 
board_array[6:9,3:6] 
board_array[6:9,6:9] 

可以看到每個(gè)小區(qū)塊也是一個(gè)二維列表，將二維列表轉(zhuǎn)成一維列表后進(jìn)行去重就可以知道這個(gè)小區(qū)塊有沒(méi)有重復(fù)出現(xiàn)的數(shù)字，進(jìn)而可以判斷是否符合數(shù)獨(dú)條件。

import numpy as np 
def done_or_not(board): 
 board2 = map(list,zip(*board)) 
 if sum([len(set(row)) for row in board2]) == 81 and sum([len(set(row)) for row in board]) ==81 : 
 board_array = np.array(board) 
 x = [0,3,6,9] 
 for y in range(0,len(x)-1): 
 for j in range(0,len(x)-1): 
 z = board_array[x[y]:x[y+1],x[j]:x[j+1]] 
 if len(set([num for row in z for num in row ])) != 9: 
 return 'Try again!' 
 return 'Finished!' 
 else: 
 return 'Try again!' 

2.看高手的解法

涉及到多維數(shù)組的處理，可以直接用numpy里面的vstack來(lái)處理，會(huì)簡(jiǎn)潔和方便

import numpy as np 
def done_or_not(aboard): #board[i][j] 
 board = np.array(aboard) 
 rows = [board[i,:] for i in range(9)] # 取行 
 cols = [board[:,j] for j in range(9)] #取列 
 sqrs = [board[i:i+3,j:j+3].flatten() for i in [0,3,6] for j in [0,3,6]] # 分區(qū) 
 for view in np.vstack((rows,cols,sqrs)): 
 if len(np.unique(view)) != 9: 
 return 'Try again!' 
 return 'Finished!' 

3.神一樣的解法

在上面用numpy的基礎(chǔ)上，進(jìn)一步巧妙的利用not all的用法

import numpy as np 
def done_or_not(board): 
rows = np.array(board) 
cols = np.transpose(rows) 
subs = [np.ndarray.flatten(rows[x:x+3, y:y+3]) for x in range(0,9,3) for y in range(0,9,3)] 
for test in [rows, cols, subs]: 
if not all(sorted(group) == range(1,10) for group in test): 
return 'Try again!' 
return 'Finished!' 

3.找出下一個(gè)大的數(shù)字

題目：

給定一個(gè)數(shù)字比如138，找出這個(gè)數(shù)字組合后下一個(gè)大的數(shù)字，比如138,183,318,813,831,很顯然下一個(gè)大一點(diǎn)的數(shù)字是183。

這道題怎么解呢：

1).屌絲解法：

我們用最簡(jiǎn)單的暴力破解，先把數(shù)字轉(zhuǎn)為字符列表，然后排列組合所有的情況，再把字符轉(zhuǎn)給數(shù)字，然后排序，取比原來(lái)數(shù)字大的那一個(gè)就行了。

• 首先我們利用itertool庫(kù)里面的牛逼閃閃的permutations，可以對(duì)一個(gè)列表進(jìn)行全排序
• 接著我們把排序好的字符里面，用迭代器合成為一個(gè)一個(gè)數(shù)字
• 把數(shù)字列表進(jìn)行從大到小的排序，找出比當(dāng)前數(shù)字大的數(shù)字，即index+1
• 如果沒(méi)有報(bào)錯(cuò)，則返回為-1

我們用assert測(cè)一下看看：

assert next_bigger(50)==-1 
 
assert next_bigger(13)==31 
 
assert next_bigger(217)==271 
 
assert next_bigger(16318)==16381 

完全正確，那么上面的解法有什么缺點(diǎn)嗎，確實(shí)就是耗時(shí)，比如我們現(xiàn)在一個(gè)15位的數(shù)字需要查詢(xún)，全排序顯然不是上策！我們接著看第二種：

2).優(yōu)化算法，進(jìn)階解法

既然全排序不行，那就要想一個(gè)算法來(lái)解決這個(gè)問(wèn)題，比如16318，顯然16381是比它大的，因?yàn)槲沂堑怪鴣?lái)的，個(gè)位數(shù)比十位數(shù)大，那么取反之后就可以得到一個(gè)比原來(lái)大的數(shù)字。所以我們的思路：

• 我們是反向操作：從n個(gè)位開(kāi)始依次和n+1(十位)，n+2(百位)，n+3(千位)，n+4(萬(wàn)位)...進(jìn)行比較
• 如果發(fā)現(xiàn)有大的數(shù)字，把n插入到n+1那里，同時(shí)把原來(lái)的n挪走，得到一個(gè)新的數(shù)字，放入我們的新列表
• 個(gè)位循環(huán)完畢，循環(huán)十位，依次重復(fù)上面的算法
• ***在新的列表中找出最小的那個(gè)數(shù)字就行了！

3).神一樣的解法