首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【剑指Offer】1-10题

【剑指Offer】1-10题

作者头像
致Great
发布2019-03-16 16:21:01
5990
发布2019-03-16 16:21:01
举报
文章被收录于专栏:程序生活程序生活

1 二维数组中的查找

1.1 题目描述

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

1.2 解题思路

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

1.3 解题代码

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows,cols=len(array),len(array[0])-1
        row=0
        while row<rows and cols>=0:
            if array[row][cols]==target:
                return True
            elif array[row][cols]>target:
                cols=cols-1
            else:
                row=row+1
        return False

2 替换空格

2.1 题目描述

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

2.2 解题思路

  • replace
  • 遍历字符串,然后遇到空格就替换成“%20”

2.3 解题代码

  • 思路1
# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        return s.replace(" ","%20")
  • 思路2
# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        news=""
        for c in s:
            if c==' ':
                news+="%20"
            else:
                news+=c
        return news

3 从尾到头打印链表

3.1 题目描述

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

3.2 解题思路

遍历列表,每次遍历一个节点,然后将当前节点的值添加到列表,然后更新节点为下一个节点,最后将列表反转。

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

4 重建二叉树

4.1 题目描述

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

4.2 解题思路

首先我们先回顾下前中后三种遍历顺序:

  • 前序遍历:根结点 ---> 左子树 ---> 右子树
  • 中序遍历:左子树---> 根结点 ---> 右子树
  • 后序遍历:左子树 ---> 右子树 ---> 根结点

然后发现前序的第一个节点肯定为根节点,在中序遍历中,在根节点左边的为左子树的中序遍历,在根节点右边的为右子树的中序遍历;那么在左子树的节点中,我们可以在前序遍历中找到左子树的根节点,右子树同理。

4.3 解题代码

# -*- 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])
        val=tin.index(pre[0])
        root.left=self.reConstructBinaryTree(pre[1:val+1],tin[:val])
        root.right=self.reConstructBinaryTree(pre[val+1:],tin[val+1:])
        return root
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019.03.14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1 二维数组中的查找
    • 1.1 题目描述
      • 1.2 解题思路
        • 1.3 解题代码
        • 2 替换空格
          • 2.1 题目描述
            • 2.2 解题思路
              • 2.3 解题代码
                • 3 从尾到头打印链表
                  • 3.1 题目描述
                    • 3.2 解题思路
                      • 3.3 解题代码
                        • 4 重建二叉树
                          • 4.1 题目描述
                            • 4.2 解题思路
                              • 4.3 解题代码
                              领券
                              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档