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实现
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 13 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('\n') 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、思路 设计两个指针，记为A、B
A往右走，B往下走A若碰到最右边，则A往下走；B若碰到最下面，则B往右走这样上下界A、B就定好了。我们只需要设置一个bool类型函数来决定打印方向，是从下往上还是从上往下即可。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 7 4 4 4 8 5 7 7 9 如果K为7，返回true； 如果K为6，返 回false。 【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。
2、思路
左下开始走或者右上开始走 具体地参照我写的前面一篇文章，与剑指offer的那道题一样。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