python 数据结构与算法

剑指office 牛客刷题

刷题记录

systemime
2020-03-26
8 min

牛客网剑指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)

# 10.

上次编辑于: 2021/5/24 下午1:55:49