python-剑指offer1-5

1、数组

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

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if any(array):
            m,n = len(array), len(array[0])
            min = array[0][0]
            max = array[m-1][n-1]
            if target < min or target > max:
                return False
            else:
                raw = 0
                column = n-1
                Flag = False
                while raw <= m-1 and column >=0:
                    curnum = array[raw][column]
                    if target == curnum:
                        Flag = True
                        return Flag
                    elif target > curnum:
                        raw += 1
                    else:
                        column -= 1
            return Flag
        else:
            return False

解题思路:按行开始遍历,假设target大于第一行的最后一个数,那么我们就在第二行查找;如果target小于一行的最后一个数,那么我们检查下倒数第二列是否等于target。

踩过的坑:len([[]])是等于1,因此判断二维数组是否为空要用any;初始时,要判断target是否在数组的范围内;要先用flag标记是否找到,找到了标记flag为True并结束循环。

2、字符串

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

def replaceSpace(s):
    # ind = s.replace(" ","%20")
    s2 = []
    s = list(s)
    for str1 in s:
        if str1 == " ":
            s2.append("%20")
        else:
            s2.append(str1)
    print("".join(s2))

解题思路:将字符串转换为列表,遍历列表,是字母就加入,是空格就加入%20,最后用join转换为字符串。

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
        res = []
        while listNode:
            res.append(listNode.val)
            listNode = listNode.next
        return res[::-1]

解题思路:链表的建立,考一个node = node.next,然后就是如何调用所定义的链表以及列表的翻转。

或者我们也可以先翻转链表:

# -*- 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
        pre=None
        cur=listNode
        while cur:
            t=cur.next
            cur.next=pre
            pre=cur
            cur=t
        res=[]
        while pre:
            res.append(pre.val)
            pre=pre.next
        return res

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

解题思路:首先是树的建立,然后是先由先序遍历确定根节点,然后在中序遍历中找到根节点的位置,然后先序遍历中剩余的一半部分为左子树的先序遍历,一般为右子树的先序遍历,中序遍历中一半为左子树的中序遍历,一半为右子树的中序遍历,进行递归即可。

5、栈

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

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s1=[]
        self.s2=[]
    def push(self, node):
        # write code here
        self.s1.append(node)
            
    def pop(self):
        # return xx
        if len(self.s2)>0:
            return self.s2.pop()
        else:
            if len(self.s1)>0:
                while len(self.s1)>0:
                    self.s2.append(self.s1.pop())
                return self.s2.pop()

解题思路:主要是pop()时需要注意,先要判断s2中是否为空,当s2中为空时才能将s1中的元素从后往前依次加入到s2中。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【python实现卷积神经网络】批量归一化层实现

    代码来源:https://github.com/eriklindernoren/ML-From-Scratch

    绝命生
  • 动态分组卷积-Dynamic Group Convolution for Accelerating Convolutional Neural Networks

    github:https://github.com/zhuogege1943/dgc/

    绝命生
  • 【论文笔记】张航和李沐等提出:ResNeSt: Split-Attention Networks(ResNet改进版本)

    github地址:https://github.com/zhanghang1989/ResNeSt

    绝命生
  • Python学习之魔法方法

    Python中会看到前后都加双下划线的函数名,例如 __init__(self),这类写法在Python中具有特殊的含义。如果对象使用了这类方法中的某一个,那么...

    py3study
  • python写的监控mysql主从的ap

    [global] user = cmVwbsdfsdfA== passwd = SGMxNzVBcEdEZ0ZRTGsfdfV6aA== time = 1...

    py3study
  • 强化学习FrozenLake求解

    大概情景是湖面结冰不结实、黑色圆圈表示踩到就会跌落、白色圆圈表示目标、红色小圆圈代表agent

    万木逢春
  • PaddlePaddle版Flappy-Bird—使用DQN算法实现游戏智能

    刚刚举行的 WAVE SUMMIT 2019 深度学习开发者峰会上,PaddlePaddle 发布了 PARL 1.1 版本,这一版新增了 IMPALA、A3C...

    用户1386409
  • python codis集群客户端(二) - 基于zookeeper对实例创建与摘除

     在这一篇中我们实现了不通过zk来编写codis集群proxys的api, 如果codis集群暴露zk给你的话,那么就方便了,探活和故障摘除与恢复codis集群...

    用户1225216
  • Python3实现飞机大战游戏

    本文实例为大家分享了Python3实现飞机大战游戏的具体代码,供大家参考,具体内容如下

    砸漏
  • python第四十二课——__str__(self)函数

    4.__str__(self): 作用: 创建完对象,直接打印对象名/引用名我们得到的是对象的内存信息(十六进制的地址信息), 这串数据我们程序员并不关心...

    hankleo

扫码关注云+社区

领取腾讯云代金券