具体题目名字记不太清了,大概如下

第一题

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

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def reConstructBST(self , preSlice):
        if not preSlice:
            return None
        self.index = 0
        return self.dfs(preSlice, 99999999, -9999999)

    def dfs(self, preSlice, up, down):
        if self.index == len(preSlice):
            return None

        if preSlice[self.index] > up or preSlice[self.index] < down:
            return None
        root = TreeNode(preSlice[self.index])
        self.index += 1
        root.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 - 1
	        new_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 here
        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 - 1
                new_res[j].append(matrix[i][j])
        total = h * l
        res = []
        flag = "d"
        x,y = 0,0
        while total > 0:
            res.append(new_res[y][x])
            new_res[y][x] = -1
            total -= 1
            if flag == 'd':
                y += 1
                if y >= l:
                    flag = 'r'
                    y -= 1
                    x += 1
                    continue
                if new_res[y][x] == -1:
                    flag = 'r'
                    y -= 1
                    x += 1
            elif flag == 'r':
                x += 1
                if x >= h:
                    flag = 'u'
                    x -= 1
                    y -= 1
                    continue
                if new_res[y][x] == -1:
                    flag = 'u'
                    x -= 1
                    y -= 1
            elif flag == 'u':
                y -= 1
                if y < 0:
                    flag = 'l'
                    y += 1
                    x -= 1
                    continue
                if new_res[y][x] == -1:
                    flag = 'l'
                    y += 1
                    x -= 1
            elif flag == 'l':
                x -= 1
                if x < 0:
                    flag = 'd'
                    x += 1
                    y += 1
                    continue
                if new_res[y][x] == -1:
                    flag = 'd'
                    x += 1
                    y += 1
        return res

第三题

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

import collections
class Solution:
    def longestGeometricSeqLength(self , nums ):
        mem = [collections.defaultdict(int) for _ in nums]
        res = 1
        for 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 + 1

s  = Solution()
print(s.longestGeometricSeqLength([75,72,27,25,5,9,12,1,3,1]))