剑指offer刷题......

作者: 进击的STE | 来源:发表于2018-07-13 22:57 被阅读0次

学习

1.二维数组中的查找

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

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array ):
        # write code here
        if array == None or array == []:
            return False

        rows = len(array) - 1
        columns = len(array[0])

        col = 0
        while rows >= 0 and col < columns :
            if array[rows][col] == target:
                return True
            if array[rows][col] > target:
                rows -= 1
            if array[rows][col] < target:
                col += 1
        return False
两个方向在变化，固定一个方向，进行大小比较。

2.替换空格

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

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

3.从尾到头打印链表

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

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code her
        #借助列表进行打印

        temp_list = []

        if listNode == None:
            return temp_list

        while listNode != None:
            temp_list.append(listNode.val)
            listNode = listNode.next

        return temp_list[::-1]

        #链表反转
        '''
        temp_list = None
        relist = []
        while listNode != None:
            tmpphead = listNode
            listNode = listNode.next
            tmpphead.next = temp_list
            temp_list = tmpphead
        while temp_list != None:
            relist.append(temp_list.val)
            temp_list = temp_list.next
        return relist
'''

4.重建二叉树

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

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        root = TreeNode(pre[0])
        for i in range(len(tin)):
            if tin[i] == root.val:
                break
        root.left = self.reConstructBinaryTree(pre[1:i + 1], tin[:i])
        root.right = self.reConstructBinaryTree(pre[i + 1:], tin[i + 1:])
        return root

5.用两个栈实现队列

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

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):#构造两个栈用来当做进和出
        self.stack1=[]#进
        self.stack2=[]#出

    def push(self, node):
        # write code here
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        self.stack2.append(node)
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        return self.stack2
    def pop(self):
        # return xx
        return self.stack2.pop()

6.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0

        for i in range(len(rotateArray) - 1):
            if rotateArray[i] > rotateArray[i + 1]:
                rotateArray = rotateArray[i + 1:] + rotateArray[:i + 1]
                break
        return rotateArray[0]

#二分法查找
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        low = 0
        high = len(rotateArray) - 1

        while low < high:
            mid = low + (high - low) / 2
            if rotateArray[mid] > rotateArray[high]:
                low = mid + 1
            elif rotateArray[mid] == rotateArray[high]:
                high = high - 1
            else:
                high = mid
        return rotateArray[low]

7. 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0:return 0
        if n <= 2:
            return 1
        num1 = 1
        num2 = 1

        while n > 2:
            num1, num2 = num2, num1 + num2
            n -= 1
        return num2

8.跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解析：前提只有一次 1阶或者2阶的跳法。 a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1); b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2) c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 0:
            return 0
        sum_number = [1, 2]
        if number < 3:
            return sum_number[number - 1]
        for i in range(2, number):
            sum_number.append(sum_number[i - 1] + sum_number[i - 2])
        return sum_number[number - 1]

9.变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解析：关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

说明：
1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的跳法数。
2）n = 1时，只有1种跳法，f(1)=1;

n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），f(2) = f(2-1) + f(2-2)
n = 3时，会有三种跳得方式，1阶、2阶、3阶，那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论： f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
由以上已经是一种结论，但是为了简单，我们可以继续简化： f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1) 可以得出： f(n) = 2*f(n-1)

#一般解法
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 0:
            return 0
        sum_number = [1, 2]
        if number < 3:
            return sum_number[number - 1]
        for i in range(2, number):
            sum_number.append(sum(sum_number) + 1)
        return sum_number[number - 1]
#递归解法
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number==1 or number==0:
            return number
        return 2*self.jumpFloorII(number-1)

10.矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
2n的大矩形，和n个21的小矩形
其中target2为大矩阵的大小
有以下几种情形：
1.️target <= 0 大矩形为<= 20,直接return 1；
2.️target = 1大矩形为21，只有一种摆放方法，return1 ；
3.️target = 2 大矩形为22，有两种摆放方法，return2；
4.️target = n 分为两步考虑：
第一次摆放一块 21 的小矩阵，则摆放方法总共为f(target - 1)
|| | | | |....
|| | | | |....
第一次摆放一块12的小矩阵，则摆放方法总共为f(target-2)
因为，摆放了一块12的小矩阵（用表示），对应下方的12（用××表示）摆放方法就确定了，所以为f(targte-2)
||*| | | |....
|-|-| | | |....

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number< 3:
            return number
        sum1 = 1
        sum2 = 2
        while number >= 3:
            sum1, sum2 = sum2, sum1 + sum2
            number -= 1
        return sum2

11.链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
'''
   整体思路:
   1.采用两个指针一前一后去遍历；
   2.第一个指针先遍历k步，然后第二个指针开始遍历；
   3.等第一个指针遍历到空指针时，此时第二个指针正好位于倒数第k个结点。
   注意：1.可能输入的链表为空，或者k小于1，此时判断输出结点也为None；
   2.输入的k值大于整个链表的长度，因此需要进行必要的判断。
'''
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head == None or k < 1:#判断输入的有效性
            return None

        pre_head = head #第一个指针
        while k > 0 and pre_head != None:#k不为0并且指针不为空
            pre_head  = pre_head.next
            k -= 1
        if k > 0:#此条件出现的是因为已经遍历完链表，但是k值仍不为0，k大于链表长度。
            return None
        while pre_head != None:
            head = head.next
            pre_head = pre_head.next
        return head

12.反转链表

输入一个链表，反转链表后，输出新链表的表头
思路： 1.采用头插法，创建一条新的链表； 2.采用Python中的list，进行反转 3.。。。。。

#头插法：1.创建一个头指针为None的表头；2.原有链表每取出一次表头就将该表头.next指向创建的None
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None or pHead.next == None:
            return pHead

        new_pHead = None
        while pHead != None:
            temp_pHead = pHead
            pHead = pHead.next
            temp_pHead.next = new_pHead
            new_pHead = temp_pHead
        return new_pHead

13.合并两个有序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        if pHead1.val < pHead2.val:
            pHeadtemp = pHead1
            pHeadtemp.next = self.Merge(pHead1.next,pHead2)
        else:
            pHeadtemp = pHead2
            pHeadtemp.next = self.Merge(pHead1,pHead2.next)
        return pHeadtemp

14.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack=[]
        self.minstack=[]
    def push(self, node):
        # write code here
        Min=self.min()
        self.stack.append(node)
        if not Min or node<Min:
            self.minstack.append(node)
        else:
            self.minstack.append(Min)
    def pop(self):
        # write code here
        if self.stack:
            self.minstack.pop()
            return self.stack.pop()
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]
    def min(self):
        # write code here
        if self.minstack:
            return self.minstack[-1]

15.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        #如果序列为空或者不等，返回False
        if not pushV  or len(pushV) != len(popV):
            return False

        #借助辅助list
        stack = []
        #将压入序列依次压入stack中，并比较当前栈顶元素是否与pop队列的第一个元素相等，并依次进行比较
        for index in pushV:
            stack.append(index)
            while stack and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
        #如果压入序列遍历结束后，stack不为空则返回False
        if stack:
            return False
        return True