【刷题】剑指Offer 66 题 PYTHON版

雨点打透心脏的1/2处 2022-06-12 05:09 177阅读 0赞

目的：挤出时间夯实基础，准备秋招。记录刷题的思路以及反思不足。  
目标： 三周内内初步刷完，工作日平均2题/day，周末5~6题/day

Begin 2017-7-16

### 1.题目描述 ###

**在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。**

分析题目：  
1.有序数组的查找 –可用二分查找，但只能用于一维数组  
2.二维都有序 –多个一维数组增加循环化为两个一维数组看待，可看做两个有序数组的合并问题，由于两个一维序列都递增，把第二个序列的数插到前一个序列。  
2.但是似乎我只用到了一个维度递增这一个信息。

So最终我的思路：  
将二维数组归并成一维数组，再用二分查找。

My code:

class Solution:
        # array 二维列表
        def Merge(self,array):
            if len(array)>len(array[0]):
                array = map(list, zip(*array))
            if len(array)==1:
                return array[0]
            else:
                numr = 1
                vect0 = array[0]
                while not(numr==len(array)):
                    vect0 = self.Insert(vect0,array[numr])
                    numr+=1
            return vect0
    
        def Insert(self,a,b):
            len_a = len(a)
            len_b = len(b)
    
            for i in range(len_b):
                si = 1
                while (a[0-si]>b[i]):
                    si+=1
                if a[0-si]==b[i]:
                    continue
                else:
                    a.insert(len_a-si+1,b[i])
                    len_a+=1
            return a
    
        def BiSearch(self,vectora,target):
            st = 0
            ed = len(vectora)-1
            while (st<=ed):
                md = (st+ed)//2
                if target==vectora[md]:
                    return 1
                else:
                    if target>vectora[md]:
                        st = md+1
                    else:
                        ed = md-1
            return 0
    
        def Find(self, target, array):
            # write code here
            w_exist = 0
            if target>array[-1][-1] or target<array[0][0]:
                return w_exist
            else:
                #归并成一维数组
                vectora = self.Merge(array)
                #二分查找
                w_exist = self.BiSearch(vectora,target)
                return w_exist

算法复杂度计算：  
归并序列的总的复杂度为 O(MN)  
二分查找总的复杂度为 O(log(MN))  
由上可知我的思路算法复杂度太高，甚至不如直接比较。  
**解法一：**  
不用有序信息，直接暴力比较，比我的方法简单很多并且复杂度也要低！！！

class Solution:
        # array 二维列表
        def Find(self, target, array):
            # write code here
            for a in array:
                for b in a:
                    if target==b:
                        return True
            return False

**解法二：**  
利用二维递增数组的特点，对于二维数组右上角的数，若某一个数比它大，则它不在该行当中，若某数比它小，则一定不在该行之中。经过排除缩小范围，最终只留下一个数，判断是否存在。

class Solution:
        # array 二维列表                  
        def Find(self, target, array):
            # write code here
            while(len(array) and len(array[0])):
    
                if target==array[0][-1]:
                    return 1
                elif (target<array[0][-1]):
                    [b.remove(b[-1]) for b in array]
                else:
                    array.remove(array[0])
    
            return 0

### 2.题目描述 ###

**请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。**

*Python利用自带函数做法：*

# -*- coding:utf-8 -*-
    class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            # write code here
            return s.replace(' ','%20')

不用函数做法：

# -*- coding:utf-8 -*-
    class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            # write code here
            len_s = len(s)
            re = ''
            for ss in s:
                if ss==' ':
                    re+='%20'
                else:
                    re+=ss
            return re

没GET到这道题的考察点，大概是C++中用指针做有一些难度吧！

2017-07-17

### 3.题目描述 ###

输入一个链表，从尾到头打印链表每个节点的值。

分析：  
1. 用一个数组保存每个节点的值  
2. 再倒序输出  
在 python 里似乎很容易，如下代码，本题主要考查对链表的性质的理解。

class Solution:
        # 返回从尾部到头部的列表值序列，例如[1,2,3]
        def printListFromTailToHead(self, listNode):
            # write code here
            a = []
            while(listNode):
                a.append(listNode.val)
                listNode = listNode.next
            return a[::-1]

### 4. 题目描述 ###

**输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。**

分析：1. 对策：利用递归的方法，重建每一个节点。  
2. 利用前序遍历第一个数可得到根节点的数值，在中序遍历中找到对应的位置从而划分出左右子树。

class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            # write code here
            if len(tin)==0:
                return
            else:
                rootval = pre[0]
                for i in range(len(tin)):
                    if rootval == tin[i]:
                        sub_left = tin[:i]
                        pre_left = pre[1:1+i]
                        sub_right = tin[i+1:]
                        pre_right = pre[1+i:]
                        root = TreeNode(rootval)
                        root.left = self.reConstructBinaryTree(pre_left,sub_left)
                        root.right = self.reConstructBinaryTree(pre_right,sub_right)
                return root

2017-07-18

### 5.题目描述 ###

**用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。**

2017-07-19

### 7. ###

### 8.题目描述 ###

**一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。**  
利用递归分析，化成for循环。

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloor(self, number):
            # write code here
            if number==0:
                return NULL
            elif number==1:
                return 1
            elif number==2:
                return 2
            else:
                num_jump = ['']*number
                num_jump[0] = 1
                num_jump[1] = 2
                for ni in range(2,number):
                    num_jump[ni] = num_jump[ni-1]+num_jump[ni-2]
                return num_jump[-1]