牛客網_アルゴリズム初級クラス_Lesson3_part2_犬の列回転印刷マトリックス_回転正方形行列_ジグザグ印刷マトリックス_行列が整列した行列の中で数を探す
57514 ワード
一、猫と犬の列
1、問題説明ペット、犬と猫の種類は以下の通りである:public class Pet{private String type;public Pet(String type){this.type=type;public String getPetType() { return this.type; } } public class Dog extends Pet { public Dog() { super(“dog”); } } public class Cat extends Pet { public Cat() { super(“cat”); } }
犬猫キューの構造を実現するには、addメソッドを呼び出してcatクラスまたはdogクラスのインスタンスをキューに入れることができる.ユーザはpollAllメソッドを呼び出し、キュー内のすべてのインスタンスをキューに入る順に順次ポップアップすることができる.ユーザはpollDogメソッドを呼び出し、キュー内のdogクラスのインスタンスをキューに入る順に順次ポップアップすることができる.ユーザはpollCatメソッドを呼び出し、キュー内のcatクラスのインスタンスをキューに入る順に順次ポップアップすることができる.ユーザーはisEmptyメソッドを呼び出し、キューにdogまたはcatのインスタンスがあるかどうかを確認できます.ユーザーはisDogEmptyメソッドを呼び出し、キューにdogクラスのインスタンスがあるかどうかを確認できます.ユーザーはisCatEmptyメソッドを呼び出し、キューにcatクラスのインスタンスがあるかどうかを確認できます.
2、考え方 dog操作に対してdogキューを直接操作するには である. cat操作に対してcatキューを直接操作するには である. pollAllが必要な場合は、グローバル変数を記録するためのcountを設定する必要があります.カウントツールと同様に、最小countに対応するpetは、最初に入るpet である.
ここで、DogCatQueueの属性はdogキューとcatキュー(いずれもキューオブジェクト)である.dogキュー、catキューの要素はpetEnterクラスのオブジェクトです.
3、python実現
4、まとめ注意継承中構造関数の使い方 各層の論理を体得し、分業は であることを明確にする.
二、回転輪印刷マトリックス
1、問題の説明
整数マトリクスmatrixを指定するには、回転輪で印刷します.
例えば、1 2 3 4 5 6 7 8 9 10 11 12 14 15 16印刷結果は、1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
【要件】余分な空間複雑度はO(1)である.
2、構想マクロはミクロの代わりに、分圏構造は解決する.領域の左上隅の行列を決定し、右下隅の行列を決定します(境界処理に注意:同行または同列の場合どう処理するか)丸の印刷マトリクスは、まず最外層 を印刷する.左上と右下の境界を内側に縮小し、印刷マトリクス を繰り返す.終了条件:左上の行が右下の行より大きいか、左上の列が右下の列より大きいか.
3、python実現
三、回転正方形行列
1、テーマの説明
整数正方形マトリクスmatrixを指定し、時計回りに90度回転するように調整します.【要件】余分な空間複雑度はO(1)である.
2、考え方は第二題と同じで、局部に陥らないでください.やはり境界処理、すなわちマクロに従ってミクロを解決しなければならない.四角交換 左上右シフト、右下左シフト、第1ステップ を繰り返す左上の行が右上より大きく、左上の列が右下より大きい場合、ループ が終了する.
3、python実現
四、ジグザグ印刷マトリックス
1、問題説明所与の行列matrixは、「之」字形の方式でこの行列を印刷する.例えば、1 2 3 4 5 6 7 8 9 10 11 12「之」字形印刷の結果は、1、2、5、9、6、3、4、7、10、11、8、12である.
【要件】余分な空間複雑度はO(1)である.
2、構想設計の2つの指針、A、Bと記す Aを右へ、Bを へ A一番右にぶつかると、Aは下へ行きます.B一番下に当たったら、Bは右へ 行きます.これで上下界A、Bが決まります.私たちはboolタイプ関数を設定して印刷方向を決定するだけで、下から上へ行くか、上から下へ行くかを決定することができます.
3、python実現
五、行列が並んでいる行列の中で数を探す
1、問題の説明
N*Mの整数行列matrixと整数Kが与えられ、matrixの各行と各列は順序付けされている.Kがmatrixにあるかどうかを判断する関数を実現します.たとえば、0 1 2 5 2 3 4 4 4 4 8 5 7 9 Kが7の場合、trueを返します.Kが6の場合はfalseを返します.【要件】時間的複雑度はO(N＋M)であり、余分な空間的複雑度はO(1)である.
2、考え方左下から歩く または右上から具体的に私が書いた前の文章を参照してください.剣指offerの問題と同じです.
3、python実現
1、問題説明ペット、犬と猫の種類は以下の通りである:public class Pet{private String type;public Pet(String type){this.type=type;public String getPetType() { return this.type; } } public class Dog extends Pet { public Dog() { super(“dog”); } } public class Cat extends Pet { public Cat() { super(“cat”); } }
犬猫キューの構造を実現するには、addメソッドを呼び出してcatクラスまたはdogクラスのインスタンスをキューに入れることができる.ユーザはpollAllメソッドを呼び出し、キュー内のすべてのインスタンスをキューに入る順に順次ポップアップすることができる.ユーザはpollDogメソッドを呼び出し、キュー内のdogクラスのインスタンスをキューに入る順に順次ポップアップすることができる.ユーザはpollCatメソッドを呼び出し、キュー内のcatクラスのインスタンスをキューに入る順に順次ポップアップすることができる.ユーザーはisEmptyメソッドを呼び出し、キューにdogまたはcatのインスタンスがあるかどうかを確認できます.ユーザーはisDogEmptyメソッドを呼び出し、キューにdogクラスのインスタンスがあるかどうかを確認できます.ユーザーはisCatEmptyメソッドを呼び出し、キューにcatクラスのインスタンスがあるかどうかを確認できます.
2、考え方
ここで、DogCatQueueの属性はdogキューとcatキュー(いずれもキューオブジェクト)である.dogキュー、catキューの要素はpetEnterクラスのオブジェクトです.
3、python実現
class ArrayQueue:
'''
：
，
'''
def __init__(self, initsize):
self.initsize = initsize
'''
'''
if self.initsize < 0:
print('The init size is less than 0')
self.arr = [0 for i in range(self.initsize)]
self.index = 0 #
self.start = 0 #
self.end = 0 #
def isEmpty(self):
'''
'''
return not self.index
def peek(self):
'''
'''
if self.index == 0:
return 0
return self.arr[self.start]
def push(self, num):
'''
：
'''
if self.index == self.initsize:
print("It's wrong!")
self.index += 1
self.arr[self.end] = num
self.end = 0 if (self.end == self.initsize - 1) else self.end + 1
def pop(self):
'''
:
'''
if self.index == 0:
print("It's wrong!")
self.index -= 1
tmp = self.start # stat ， ，
self.start = 0 if (self.start == self.initsize - 1) else self.start + 1
return self.arr[tmp]
class Pet:
'''
Pet ， -
'''
def __init__(self, typePet):
self.typePet = typePet
def getPetType(self):
return self.typePet
class Dog(Pet):
'''
Dog ， Pet， “ ”
'''
def __init__(self):
Pet.__init__(self, 'dog')
class Cat(Pet):
'''
Dog ， Pet， “ ”
'''
def __init__(self):
Pet.__init__(self, 'cat')
class PetEnter:
def __init__(self, count, pet=Pet):
'''
，
'''
self.pet = pet
self.count = count
def getPet(self):
'''
Pet
'''
return self.pet
def getCount(self):
'''
（ ， pollAll）
'''
return self.count
def getEnterPetType(self):
'''
（ ： ）
'''
return self.pet.getPetType()
class DogCatQueue:
'''
dog 、cat
'''
def __init__(self, initsize):
'''
'''
self.dogQ = ArrayQueue(initsize)
self.catQ = ArrayQueue(initsize)
self.count = 0
def add(self, pet=Pet):
'''
pet
'''
if pet.getPetType() == 'dog':
self.count += 1
self.dogQ.push(PetEnter(self.count, pet))
elif pet.getPetType() == 'cat':
self.count += 1
self.catQ.push(PetEnter(self.count, pet))
else:
print(' ')
def pollAll(self):
if (not self.dogQ.isEmpty()) and (not self.catQ.isEmpty()):
if self.dogQ.peek().getCount() < self.catQ.peek().getCount():
return self.dogQ.pop().getPet()
else:
return self.catQ.pop().getPet()
elif not self.dogQ.isEmpty():
return self.dogQ.pop().getPet()
elif not self.catQ.isEmpty():
return self.catQ.pop().getPet()
else:
print(' ！')
def pollDog(self):
if not self.dogQ.isEmpty():
return self.dogQ.pop().getPet()
else:
print(' ')
def pollCat(self):
if not self.catQ.isEmpty():
return self.catQ.pop().getPet()
else:
print(' ')
def isEmpty(self):
return self.dogQ.isEmpty() and self.catQ.isEmpty()
def isDogQueueEmpty(self):
return self.dogQ.isEmpty()
def isCatQueueEmpty(self):
return self.catQ.isEmpty()
test = DogCatQueue(6)
dog1 = Dog()
cat1 = Cat()
dog2 = Dog()
cat2 = Cat()
dog3 = Dog()
cat3 = Cat()
test.add(dog1)
test.add(cat1)
test.add(dog2)
test.add(cat2)
test.add(dog3)
test.add(cat3)
#
#while not test.isDogQueueEmpty():
# print(test.pollDog().getPetType())
while not test.isEmpty():
print(test.pollAll().getPetType())
4、まとめ
二、回転輪印刷マトリックス
1、問題の説明
整数マトリクスmatrixを指定するには、回転輪で印刷します.
例えば、1 2 3 4 5 6 7 8 9 10 11 12 14 15 16印刷結果は、1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
【要件】余分な空間複雑度はO(1)である.
2、構想マクロはミクロの代わりに、分圏構造は解決する.領域の左上隅の行列を決定し、右下隅の行列を決定します(境界処理に注意:同行または同列の場合どう処理するか)
3、python実現
def printMatrixSpiralOrder(matrix):
'''
：
'''
tR = 0 #
tC = 0 #
dR = len(matrix)-1 #
dC = len(matrix[0]) - 1 #
while tR <= dR and tC <= dC:
printEdge(matrix, tR, tC, dR, dC) #
tR += 1
tC += 1
dR -= 1
dC -= 1
def printEdge(matrix, tR, tC, dR, dC):
'''
（ ）
'''
if tR == dR:
for i in range(tC, dC+1):
print (matrix[tR][i], ' ')
elif tC == dC:
for i in range(tR, tC+1):
print (matrix[i][tC], ' ')
else:
curR = tR
curC = tC
while curC != dC:
print (matrix[curR][curC], ' ')
curC += 1
while curR != dR:
print (matrix[curR][curC], ' ')
curR += 1
while curC != tC:
print (matrix[curR][curC], ' ')
curC -= 1
while curR != tR:
print (matrix[curR][curC], ' ')
curR -= 1
matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
printMatrixSpiralOrder(matrix)
三、回転正方形行列
1、テーマの説明
整数正方形マトリクスmatrixを指定し、時計回りに90度回転するように調整します.【要件】余分な空間複雑度はO(1)である.
2、考え方は第二題と同じで、局部に陥らないでください.やはり境界処理、すなわちマクロに従ってミクロを解決しなければならない.
3、python実現
def RotateMatrix(matrix):
'''
（ ，）：
90° （ n*n）
，
'''
tR = 0
tC = 0
dR = len(matrix) - 1
dC = len(matrix[0]) - 1
while tR < dR and tC < dC:
rotateEdge(matrix, tR, tC, dR, dC)
tR += 1
tC += 1
dR -= 1
dC -= 1 #
def rotateEdge(matrix, tR, tC, dR, dC):
'''
'''
times = dC - tC
for i in range(tR, times): #
# times ， times + 1
tmp = matrix[tR][tC+i]
matrix[tR][tC+i] = matrix[dR-i][tC]
matrix[dR-i][tC] = matrix[dR][dC-i]
matrix[dR][dC-i] = matrix[tR+i][dC]
matrix[tR+i][dC] = tmp
def printMatrix(matrix):
'''
'''
for i in range(0, len(matrix)):
for j in range(0, len(matrix[0])):
print(matrix[i][j],' ')
print('
')
matrix = [[1, 2, 3], [ 4, 5, 6], [ 7, 8, 9]];
printMatrix(matrix)
print('======================================')
RotateMatrix(matrix)
printMatrix(matrix)
四、ジグザグ印刷マトリックス
1、問題説明所与の行列matrixは、「之」字形の方式でこの行列を印刷する.例えば、1 2 3 4 5 6 7 8 9 10 11 12「之」字形印刷の結果は、1、2、5、9、6、3、4、7、10、11、8、12である.
【要件】余分な空間複雑度はO(1)である.
2、構想設計の2つの指針、A、Bと記す
3、python実現
def printMatrixZigzag(matrix):
'''
： （ bug， ！！！！！）
“ ”
'''
aR = 0 #A
aC = 0 #A
bR = 0 #B
bC = 0 #B
endR = len(matrix) - 1
endC = len(matrix[0]) - 1 #
fromUp = False # （ ）
while aR != endR + 1:
'''
， A B
A
'''
printLevel(matrix, aR, aC, bR, bC, fromUp)
aR = aR if (aC < endC) else aR + 1
aC = aC+1 if (aC < endC) else aC
bC = bC if (bR < endR) else bC + 1
bR = bR+1 if (bR < endR) else bR # ！！！！ ！！！bR bC ！！！
# bR ， bR ， bC
# ： a b ， b
# a， b。 b，b ， a；
# aR = aR+1 if (aC == endC) else aR
# aC = aC if (aC == endC) else aC+1
#
# bC = bC+1 if (bR == endR) else bC
# bR = bR if (bR == endR) else bR+1
fromUp = (not fromUp)
def printLevel(matrix, aR, aC, bR, bC, fromUp):
'''
（ fromUp ）
'''
if fromUp: #
while aR != bR + 1:
print (matrix[aR][aC])
aR += 1
aC -= 1
else: #
while bR != aR - 1:
print(matrix[bR][bC])
bR -= 1
bC += 1
matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
printMatrixZigzag(matrix)
五、行列が並んでいる行列の中で数を探す
1、問題の説明
N*Mの整数行列matrixと整数Kが与えられ、matrixの各行と各列は順序付けされている.Kがmatrixにあるかどうかを判断する関数を実現します.たとえば、0 1 2 5 2 3 4 4 4 4 8 5 7 9 Kが7の場合、trueを返します.Kが6の場合はfalseを返します.【要件】時間的複雑度はO(N＋M)であり、余分な空間的複雑度はO(1)である.
2、考え方
3、python実現
class Solution(object):
'''
：
，
'''
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
i = 0
if matrix:
j = len(matrix[0]) - 1
else:
return False
while j >= 0 and i <= len(matrix)-1:
if matrix[i][j] > target:
j -= 1
elif matrix[i][j] < target:
i += 1
else:
return True
return False