第一题

给搜索二叉树的前序遍历结果，重构搜索二叉树，返回根结点。
思路：递归维护两个值，一个是可插入的最大值和可插入的最小值。
1、当前插入的值满足小于可插入的最大值和大于可插入的最小值，就插入，然后递归其左右子树
2、当前插入的值不满足上述条件，返回None，回溯父节点
3、当前插入次数等于总结点数，返回None，结束

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def reConstructBST(self , preSlice):if not preSlice:return Noneself.index = 0return self.dfs(preSlice, 99999999, -9999999)def dfs(self, preSlice, up, down):if self.index == len(preSlice):return Noneif preSlice[self.index] > up or preSlice[self.index] < down:return Noneroot = TreeNode(preSlice[self.index])self.index += 1root.left = self.dfs(preSlice, root.val, down)root.right = self.dfs(preSlice, up, root.val)return root

第二题

第二题是先顺时针90度翻转W * H的矩阵，然后螺旋打印，
螺旋打印如下：
翻转矩阵比较简单，代码如下：

def rotate_90(matrix):if not matrix:return []h = len(matrix)l = len(matrix[0])new_res = []for j in range(l):new_res.append([])for i in range(h):i = h - i - 1new_res[j].append(matrix[i][j])return new_res

螺旋打印，笔试写的有点复杂，但是思路很简单，从0，0开始，定义一个方向flag和当前搜索的坐标，flag初始化是向下搜索，当数组越界后，flag转向右搜索，数组越界后，flag转向上搜索，越界后转向左搜索，越界后向下搜索。在搜索的同时把搜索过的位置值改None，碰到None的时候也一样修改搜索的flag。
整体代码如下：

class Solution:def antiSpiralOrder(self , matrix ):# write code hereif not matrix:return []h = len(matrix)l = len(matrix[0])new_res = []for j in range(l):new_res.append([])for i in range(h):i = h - i - 1new_res[j].append(matrix[i][j])total = h * lres = []flag = "d"x,y = 0,0while total > 0:res.append(new_res[y][x])new_res[y][x] = -1total -= 1if flag == 'd':y += 1if y >= l:flag = 'r'y -= 1x += 1continueif new_res[y][x] == -1:flag = 'r'y -= 1x += 1elif flag == 'r':x += 1if x >= h:flag = 'u'x -= 1y -= 1continueif new_res[y][x] == -1:flag = 'u'x -= 1y -= 1elif flag == 'u':y -= 1if y < 0:flag = 'l'y += 1x -= 1continueif new_res[y][x] == -1:flag = 'l'y += 1x -= 1elif flag == 'l':x -= 1if x < 0:flag = 'd'x += 1y += 1continueif new_res[y][x] == -1:flag = 'd'x += 1y += 1return res

第三题

输出数组的最长等比子序列长度，和leetcode1027最长等差子序列长度异曲同工。
动态规划即可：

import collections
class Solution:def longestGeometricSeqLength(self , nums ):mem = [collections.defaultdict(int) for _ in nums]res = 1for i in range(len(nums)):for j in range(i + 1, len(nums)):v = nums[j] * 1.0 / nums[i]mem[j][v] = max(mem[i][v] + 1, mem[j][v])res = max(res, mem[j][v])return res + 1s  = Solution()
print(s.longestGeometricSeqLength([75,72,27,25,5,9,12,1,3,1]))