ch8

Jack-Lee-Hiter · Jack-Lee-Hiter · commit 19bfa124d3ee · 2016-07-16T11:40:23.000+08:00
面试题65和66
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/Target Offer/滑动窗口的最大值.py b/Target Offer/滑动窗口的最大值.py
@@ -0,0 +1,36 @@
+'''
+给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
+例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，
+他们的最大值分别为{4,4,6,6,6,5}；
+针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：
+{[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
+'''
+
+# -*- coding:utf-8 -*-
+class Solution:
+    def maxInWindows(self, num, size):
+        if num == None or len(num) <= 0 or size <= 0:
+            return []
+        deque = []
+        if len(num) >= size:
+            index = []
+            for i in range(size):
+                while len(index) > 0 and num[i] > num[index[-1]]:
+                    index.pop()
+                index.append(i)
+
+            for i in range(size, len(num)):
+                deque.append(num[index[0]])
+                while len(index) > 0 and num[i] >= num[index[-1]]:
+                    index.pop()
+                if len(index) > 0 and index[0] <= i - size:
+                    index.pop(0)
+                index.append(i)
+
+            deque.append(num[index[0]])
+        return deque
+
+test = [2, 3, 4, 2, 6, 2, 5, 1]
+s = Solution()
+print(s.maxInWindows(test, 3))
+
diff --git a/Target Offer/矩阵中的路径.py b/Target Offer/矩阵中的路径.py
@@ -0,0 +1,48 @@
+'''
+请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
+路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
+如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
+例如 [[a b c e], [s f c s], [a d e e]] 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
+因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
+'''
+
+# -*- coding:utf-8 -*-
+class Solution:
+    def hasPath(self, matrix, rows, cols, path):
+        if matrix == None or rows < 1 or cols < 1 or path == None:
+            return False
+        visited = [0] * (rows * cols)
+
+        pathLength = 0
+        for row in range(rows):
+            for col in range(cols):
+                if self.hasPathCore(matrix, rows, cols, row, col, path, pathLength, visited):
+                    return True
+        return False
+
+    def hasPathCore(self, matrix, rows, cols, row, col, path, pathLength, visited):
+        if len(path) == pathLength:
+            return True
+
+        hasPath = False
+        if row >= 0 and row < rows and col >= 0 and col < cols and matrix[row * cols + col] == path[pathLength] and not \
+        visited[row * cols + col]:
+
+            pathLength += 1
+            visited[row * cols + col] = True
+
+            hasPath = self.hasPathCore(matrix, rows, cols, row, col - 1, path, pathLength, visited) or \
+                      self.hasPathCore(matrix, rows, cols, row - 1, col, path, pathLength, visited) or \
+                      self.hasPathCore(matrix, rows, cols, row, col + 1, path, pathLength, visited) or \
+                      self.hasPathCore(matrix, rows, cols, row + 1, col, path, pathLength, visited)
+
+            if not hasPath:
+                pathLength -= 1
+                visited[row * cols + col] = False
+
+        return hasPath
+
+s = Solution()
+ifTrue = s.hasPath("ABCESFCSADEE", 3, 4, "ABCCED")
+ifTrue2 = s.hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS", 5, 8, "SGGFIECVAASABCEHJIGQEM")
+print(ifTrue2)
