*Forming a Magic Square（规制魔方）
Problem Description
魔方矩阵的行列之和均为15，且元素从[1,9]各出现一次
设计算矩阵行列之和，得出两个代表行列和的数组 ，并结合元素排序得到的数组进行判断
查询其他解答发现使用的是枚举出所有的 3 阶魔方解集，依次遍历求得代价，感觉不太巧妙
Function Description
Complete the formingMagicSquare function in the editor below. It should return an integer that represents the minimal total cost of converting the input square to a magic square.
formingMagicSquare has the following parameter(s):
- s: a array of integers
Solution
def formingMagicSquare(s):
row = []
for line in s:
row.append(sum(line))
column = s[0]
for i in range(1, len(s)):
for j in range(len(s)):
column[j] = column[j] + s[i][j]
The Time in Words（时间文字）
Problem Description
有些过于简单的题目，不知道为什么分类到Medium
Function Description
Complete the timeInWords function in the editor below. It should return a time string as described.
timeInWords has the following parameter(s):
- h: an integer representing hour of the day
- m: an integer representing minutes after the hour
Solution
def timeInWords(h, m):
_known = {
0:'zero',
1:'one',
2: 'two',
3: 'three',
4: 'four',
5: 'five',
6: 'six',
7: 'seven',
8: 'eight',
9: 'nine',
10: 'ten',
11: 'eleven',
12: 'twelve',
13: 'thirteen',
14: 'fourteen',
15: 'quarter',
16: 'sixteen',
17: 'seventeen',
18: 'eighteen',
19: 'nineteen',
20: 'twenty',
21: 'twenty one',
22: 'twenty two',
23: 'twenty three',
24: 'twenty four',
25: 'twenty five',
26: 'twenty six',
27: 'twenty seven',
28: 'twenty eight',
29: 'twenty nine',
30: 'half'}
if 0<=m<=30:
mKey = _known.get(m)
hKey = _known.get(h)
if m == 1:
return mKey + " minute" + " past " + hKey
if m == 15 or m == 30:
return mKey + " past " + hKey
elif m == 0:
return hKey+" o' clock"
else :
return mKey + " minutes" + " past " + hKey
elif m>30:
mKey = _known.get(60-m)
hKey = _known.get(h+1)
if m == 45:
return mKey + " to " + hKey
else :
return mKey + " minutes" + " to " + hKey
3D Surface Area（三维表面积）
Problem Description
求体位为单位1组成的三维积木的表面积，分别求六个面的面积（各个方向行列的高低差）然后汇总
Solution
def surfaceArea(A):
r = len(A)
c = len(A[0])
# 上下表面积
surface = 2*r*c
for line in A:
surface-=line.count(0)
# 前后左右面积
up = sum(A[0])
down = sum(A[-1])
left=right=0
for i in range(r):
left += A[i][0]
right += A[i][-1]
for i in range(r-1):
for j in range(c):
if A[i][j]<A[i+1][j]:
up+=A[i+1][j]-A[i][j]
elif A[i][j]>A[i+1][j]:
down+=A[i][j]-A[i+1][j]
for i in range(r):
for j in range(c-1):
if A[i][j]<A[i][j+1]:
left+=A[i][j+1]-A[i][j]
elif A[i][j]>A[i][j+1]:
right+=A[i][j]-A[i][j+1]
s = surface + up + down + left + right
return s
*Queen's Attack II（皇后攻势II）
Problem Description
求皇后的进攻区域面积，可以先确定无障碍情况下的攻击区域，然后加上障碍将区域刷新
*仍然有10个cases无法通过，暂不清楚原因
Solution
def queensAttack(n, k, r_q, c_q, obstacles):
# 将皇后的位置改为0-base
r_q -= 1
c_q -= 1
# 初始化棋盘矩阵
matrix =[]
for i in range(n):
line = []
for j in range(n):
line.append(0)
matrix.append(line)
# 先确定无障碍的攻击区域
for i in range(n):
for j in range(n):
if i==r_q or j==c_q or abs(r_q-i) == abs(c_q-j):
matrix[i][j] = 1
# 修改攻击区域
for item in obstacles:
x = item[0]-1
y = item[1]-1
if x == r_q:
if y<c_q:
for i in range(y):
matrix[x][i]=0
else:
for i in range(y):
matrix[x][n-i]=0
elif y == c_q:
if x<r_q:
for i in range(x):
matrix[i][y]=0
else:
for i in range(x):
matrix[n-i][y]=0
elif abs(r_q-x) == abs(c_q-y):
pass
matrix[r_q][c_q] = 0
# 统计攻击区域面积
count = 0
for line in matrix:
count += sum(line)
return count
后发现这样做冗余操作太多，需要额外在内存中建立Matrix，不如省略棋盘建模
New Solution
def queensAttack(n, k, r_q, c_q, obstacles):
# 统计无障碍攻击区域面积
count = 2*(n-1)
count += n - abs(r_q-c_q)-1
count += n - abs(r_q+c_q-n-1)-1
# 修改攻击区域
for item in obstacles:
x = item[0]
y = item[1]
if x == r_q:
if y<c_q:
count -= y
else:
count -= n-y
elif y == c_q:
if x<r_q:
count -= x
else:
count -= n-x
if abs(r_q-x) == abs(c_q-y):
if x<r_q:
if y<c_q:
count -= min(x,y)
else:
count -= min(x,n-y)
else:
if y<c_q:
count -= min(n-x,y)
else:
count -= min(n-x,n-y)
return count
*Non-Divisible Subset（不可除子集）
Problem Description
如果满足A%K+B%K=K，则A+B之和可以被K整除
8/17 test cases failed，基本上是"Your code did not execute within the time limits"，算法有待优化
Solution
def nonDivisibleSubset(k, s):
# Write your code here
mod = []
for i in s:
mod.append(i%k)
mod.sort()
# if mod[0]==0:
# for i in range(len(mod[0])):
# if mod[i]==0:
# mod.remove(0)
# mod.append(0)
# mod.sort()
pairs = []
count = len(mod)
for num in mod:
dist = k - num
if mod.count(dist)!=0 and pairs.count([min(num,dist), max(num,dist)])==0:
pairs.append([min(num,dist), max(num,dist)])
if mod.count(num)<mod.count(dist):
count -= mod.count(num)
else:
count -= mod.count(dist)
return count
