通过一个for循环实现五子棋输赢判定
看过好些人写的判定方法,发现基本都是使用三层for来遍历实现的虽然时间复杂度不是N^3但是如下算法时间复杂度仅仅是N
经过分析,时间复杂度的原因来自(x + i, y) in smallPointList
->O(N)但是for i in range(-4, 5)
的时间复杂度为O(1)但是可以看到的是,我们使用的空间复杂度也是O(1)已经是最低,如果要将时间复杂度降低的话,我们需要提高空间复杂度,可以考虑将smallPointList存为一个矩阵(15x15),每个矩阵的值是一个二维数组,此时虽然空间复杂度提高了一点,但是仍然不是O(N),因此在如果计算量很高的的情况下可以适当提高空间复杂度
总结如下代码时间复杂度为O(N)空间复杂度为O(1)
只要我们将判定点是否在list这段代码对应的list(x + i, y) in smallPointList
改为一个二维数组数据里面存point就可以实现时间复杂度O(1),空间复杂度O(1),占用内存略微提高
def haveFive():
# 刚下完棋的x点坐标
x = 10
y = 4
# 当前需要判定的所有白子或者是黑子的坐标集合
smallPointList = [(10, 4), (11, 3), (9, 4), (11, 4), (8, 4), (7, 4), (12, 4), (6, 0)]
# - | / \ 四个方向
count = [1, 1, 1, 1]
for i in range(-4, 5):
continueCount = 0
# 表示超出边界
# -
if x + i < 0 or x + i > 14 or i == 0:
continueCount += 1
# |
if y + i < 0 or y + i > 14 or i == 0:
continueCount += 1
# /
if x + i < 0 or x + i > 14 or y - i < 0 or y - i > 14 or i == 0:
continueCount += 1
# \
if x + i < 0 or x + i > 14 or y + i < 0 or y + i > 14 or i == 0:
continueCount += 1
if continueCount == 4:
# continueCount == 1
continue
# 没有超出边界
else:
# -
if (x + i, y) in smallPointList:
count[0] = count[0] + 1
if count[0] == 5:
print("true - ")
return True
else:
count[0] = 1
# |
if (x, y + i) in smallPointList:
count[1] = count[1] + 1
if count[1] == 5:
print("true | ")
return True
else:
count[1] = 1
# /
if (x + i, y - i) in smallPointList:
count[2] = count[2] + 1
if count[2] == 5:
print("true / ")
return True
else:
count[2] = 1
# \
if (x + i, y + i) in smallPointList:
count[3] = count[3] + 1
if count[3] == 5:
print("true \\ ")
return True
else:
count[3] = 1
return False
标签:count,gobang,smallPointList,return,continueCount,复杂度,五子棋,输赢,14
From: https://www.cnblogs.com/sqmw/p/16990887.html