剑指offer刷题总结：
第1题：二维数组的查找
题目说明：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
程序：
1.循环遍历每一个整数，判断是否等于给定的整数，如果相等则输出存在，否则不存在。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for i in range(len(array)):#数组行数
            for j in range(len(array[0])):#数组列数
                if target == array[i][j]:
                    return 'true'
        return 'false'
while True:
    try:
        S=Solution()
        # 字符串转为list
        L=list(eval(raw_input()))
        array=L[1]
        target=L[0]
        print(S.Find(target, array))
    except:
        break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

eval()详解
2.从左下角开始查找，已知右边的元素比该元素大，上边的元素比该元素小，所以，target如果等于该元素输出存在，如果小于该元素行数-1，如果大于该元素列数+1，如果出了边界，则说明二维数组中不存在target。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols= len(array[0]) - 1
        i = rows
        j = 0
        while j<=cols and i>=0:
            if target<array[i][j]:
                i -= 1
            elif target>array[i][j]:
                j += 1
            else:
                return 'true'
        return 'false'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

知识点：
创建数组：

import numpy as np
a = np.zeros((3,3))#np.zeros([3,3])  创建全0矩阵
b = np.ones((3,3))#np.ones([3,3])  创建全1矩阵
c = np.full((2,2), 7)#创建二维数组，数组元素全部为7
d = np.eye(2)#创建二维对角数组
e = np.random.random((2,2))#创建二维随机数组
1
2
3
4
5
6

第2题：替换空格
题目说明：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
程序：
1.字符串替换方法：s.replace(old, new)。

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = s.replace(' ', '%20')
        return s
1
2
3
4
5
6
7

2.遍历替换。

class Solution:
	def replaceSpace(self, s):
		s = list(s)
		for i in range(len(s)):
			if ' ' == s[i]:
				s[i] = '%20'
		return ''.join(s)
1
2
3
4
5
6
7

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s_new = ''
        for i in s:
            if i == ' ':
                i = '%20'
            s_new = s_new + i
        return s_new
1
2
3
4
5
6
7
8
9
10
11

知识点：
**字符串(string)**常用方法总结：
1.查找
(1)find()及index()：检测某个子串是否包含在主串中，如果存在，返回子串位置下标；如果不存在，返回-1(index()输出异常)。
语法：字符串.find(子串, 开始位置下标, 结束位置下标)/字符串.index(子串, 开始位置下标, 结束位置下标)
rfind()和find()功能相同，但查找方向从右侧开始，rindex()同理。
(2)count()：返回某个子串在主串中出现的次数。
语法：字符串.count(子串, 开始位置下标, 结束位置下标)
2.修改
(1)replace()：替换
语法：字符串.replace(旧子串, 新子串, 替换次数)
(2)split()：按照指定字符分割字符串，返回的是列表，如果分割字符是原有字符的子串，分割后该子串丢失。
语法：字符串.split(分割字符，分割数目)
(3)join()：用一个字符或子串合并字符串，即将多个字符串合并成一个新的字符串。
语法：字符/子串.join(字符序列)例子

mylist = ["aa","bb","cc"]#可以处理列表、元组、字符串、字典(字典以key值连接，特点：无序性)
print("...".join(mylist))
# 输出aa...bb...cc
1
2
3

(4)
capitalize()：将字符串第一个字符转化成大写；
title()：将字符串每个单词首字母转化成大写；
lower()：将字符串中大写转小写；
upper()：将字符串中小写转大写。
lstrip()：删除字符串左侧空白字符；
rstrip()：删除字符串右侧空白字符；
strip()：删除字符串两侧空白字符。
3.判断
(1)startswith()：检查字符串是否以指定子串开头，是则返回True，否则返回False。如果设置开始和结束位置下标，则是在指定范围内检查。
语法：字符串.startswith(子串, 开始位置下标, 结束位置下标)
(2)endswith()：检查字符串是否以指定子串结尾，是则返回True，否则返回False。如果设置开始和结束位置下标，则是在指定范围内检查。
语法：字符串.endswith(子串, 开始位置下标, 结束位置下标)
第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
        list = []
        while listNode:
            list.append(listNode.val)
            listNode = listNode.next
        return list[::-1]#切片操作：从后向前输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第4题：重建二叉树
题目说明：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
程序：
前序遍历的第一个值为根结点，对应中序遍历点的下标为记为i，在中序遍历中，该点左侧为根的左子树，该点右侧为根的右子树。本题使用递归思想，分别取前序遍历[1: i+1]和中序遍历[: i]对应左子树继续上一过程，取前序遍历[i+1: ]和中序遍历[i+1: ]对应右子树继续上一过程，最终重建二叉树。

# -*- 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])
        else:
            res = TreeNode(pre[0])
            res.left = self.reConstructBinaryTree(pre[1: tin.index(pre[0]) + 1], tin[: tin.index(pre[0])])
            res.right = self.reConstructBinaryTree(pre[tin.index(pre[0]) + 1: ], tin[tin.index(pre[0]) + 1: ])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

知识点：
1.二叉树遍历
2.**列表(list)**常用方法总结：
列表可以一次存储多个变量，且可以为不同数据类型数据。
(1)index()：返回指定数据所在位置的下标。
语法：列表.index(数据, 开始位置下标, 结束位置下标)
(2)count()：统计指定数据在当前列表中出现的次数。
语法：列表.(数据, 开始位置下标, 结束位置下标)
(3)len()：访问列表长度，即列表中数据的个数。
(4)reverse()：逆置
(5)sort()：排序，默认升序，条件为reverse=True时：降序。
(6)copy()：复制
练习题：
题目说明：8位老师，3个办公室，将8位老师随机分配到3个办公室。
程序：
8位老师–列表；
3个办公室–列表嵌套;
分配老师到办公室–随机分配，就是把老师名字写入到办公室列表;
验证是否分配成功–打印办公室详细信息。

import random 
teachers = ['小王', '小李', '小包', '小雪', '小钱', '小花', '小唐', '小陆']
offices = [[], [], []]
for name in teachers:
	num = random.randint(0, 2)
	offices[num].append(name)
i = 1
for office in offices:
	print('第{}个办公室的人数是：{}，老师分别是：'.format(i, len(office)))
	for name in office:
		print(name)
1
2
3
4
5
6
7
8
9
10
11

知识点：
格式化：
(1)print('hello,%s and %s') % ('boys', 'girls')
(2)字典形式：print('hello,%(first) and %(second)' % {'first': 'boys', 'second': 'girls'})
(3)format形式：print('hello,{first} and {second}'.format(first = 'boys', second = 'girls'))

参考博客：
剑指offer题解
字符串常用方法