剑指office 牛客刷题

牛客网剑指office刷题记录

# 1. 二维数组中的查找

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

思路：右上或左下，这两个数只有左下或上右，两边的数不是比他大就是比他小，所以从这里循环，速度比较快，另外在最开始，判断数组array[0]是否为空，判断是否比【0，0】和【len(array)-1，len(array[0])-1】小或者大，如果是，那一定不存在

循环条件：如果选择右上，则行数不大于总行数，并且列大于等于0

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表 [[1,2,3],[2,3,4],[3,4,5]]
    def Find(self, target, array):
        # write code here
        if not array[0]:
            return False
        row = len(array)  # 行数
        low = len(array[0])  # 列数
        if  target < array[0][0] or target > array[row-1][low-1]:
            return False
        i = 0
        j = low -1
        while i<row and j >= 0:
            if target > array[i][j]:
                i += 1
            elif target < array[i][j]:
                j -= 1
            else:
                return True
        return False

# 2. 替换空格

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

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = list(s)
        for i in range(len(s)):
            if s[i]==' ':
                s[i] = "%20"
        return ''.join(s)

# 3. 从尾到头打印列表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

# -*- 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 here
        arr = []
        while listNode:
            arr.insert(0, listNode.val)
            listNode = listNode.next
        return arr

# 4. 前序中序重建二叉树

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

思想，前序第一个是root，中序找到root左边是左，右边是右，前序取左子树，中序取左子树，前序子树的第一位依旧分割了中序子树的左右部分，所以递归构建，右子树同理

# -*- 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
        if len(pre) == 1:
            return TreeNode(pre[0])
        root = TreeNode(pre[0])
        pos = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])
        root.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])
        return root

# 5. 两个栈实现队列

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

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr = []
        self.lis = []
    def push(self, node):
        # write code here
        self.arr.append(node)
        print(self.arr)
    def pop(self):
        self.lis = self.arr[::-1]
        s = self.lis.pop()
        self.arr = self.lis[::-1]
        return s

# 6. 旋转数组的最小值

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

'''
这一题也不好解，在算法上，考虑数字没有重复的情况的话，使用二分法，有两个指针，第一个指针指向front，第二个指针指向rear，
midIndex是中间数字，只要是旋转数组，那么首位一定大于中间位，所以如果首位大于中间位的话，那么就把指针从首位移到中间
位，前面数字向后移动，不断迭代，当首位和最后位只差1时，最后维就是最小值。此时最坏时间复杂度是O(logn),但是要考虑数字
重复的话，情况只可能是首位和末尾和中间重这种[1,0,1,1]只能取其中最小值，逐一排列，对于首位和中间位重的，比如[1,1,0],
把首位移动到后面去，可以处理，或者中间位和末尾重，比如[1,0,0]，也是能处理，其他情况不存在，因为前提要求是旋转数组
'''

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

        front, rear = 0, len(rotateArray) - 1
        midIndex = 0
        while rotateArray[front] >= rotateArray[rear]:
            if rear - front == 1:
                midIndex = rear
                break
            midIndex = (front + rear) // 2
            if rotateArray[front] == rotateArray[midIndex] and rotateArray[front] == rotateArray[rear]:
                return self.minOrder(rotateArray, front, rear)

            if rotateArray[front] <= rotateArray[midIndex]:
                front = midIndex
            elif rotateArray[rear] >= rotateArray[midIndex]:
                rear = midIndex
        return rotateArray[midIndex]

    def minOrder(self, array, front, end):
        result = array[0]
        for i in array[front:end + 1]:
            if i < result:
                result = i
        return result

# 7. 斐波那契数列

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr1 = 0
        self.arr2 = 1
    def Fibonacci(self, n):
        # write code here
        first = {1:1,2:1}
        if n in first.keys():
            return first[n]
        num = 0
        while n-1>0:
            num = self.arr1 + self.arr2
            self.arr1 = self.arr2
            self.arr2 = num
            n -= 1
        return num

# 8. 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

可找规律，链接：https://www.nowcoder.com/questionTerminal/8c82a5b80378478f9484d87d1c5f12a4?f=discussion

比较倾向于找规律的解法，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5，可以总结出f(n) = f(n-1) + f(n-2)的规律，但是为什么会出现这样的规律呢？假设现在6个台阶，我们可以从第5跳一步到6，这样的话有多少种方案跳到5就有多少种方案跳到6，另外我们也可以从4跳两步跳到6，跳到4有多少种方案的话，就有多少种方案跳到6，其他的不能从3跳到6什么的啦，所以最后就是f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。

class Solution:
    def jumpFloor(self, number):
        # write code here
        a = 1
        b = 1
        for i in range(number):
            a,b = b,a+b
        return a

# 9. 变态跳台阶

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

就变成了阶乘问题

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <= 0:
            return 0
        else:
            return pow(2,number-1)