本文共 4963 字，大约阅读时间需要 16 分钟。

jz1.二维数组中的查找

题目描述

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

思路分析：

1.由于二维数组array行与列都是有序的，我们可以引用二分查找思想

2.我们可以从四个角出发找寻指定值。比如我们从左下角第一个元素开始查找，其右边元素是比这个元素大，上边的元素比这个元素小。左下角第一个元素的行坐标i为(行数-1)，列坐标j为0

伪代码：

3.若j<=列数-1 以及 i>=0:

• 若指定值比这个元素array[i][j]小，则就往上找，同时i减少1。
• 若指定值比这个元素array[i][j]大，则就往右找，同时j增加1。
• 否则，指定值在数组内

4.指定值没有在数组内

【python 代码实现】

def Find(self, target, array):        # write code here        rows = len(array)-1 # 行数-1        cols=len(array[0])-1 # 列数-1        i = rows #左下角第一个元素的行坐标        j=0 #左下角第一个元素的列坐标        # 左下角第一个坐标为[行数-1][0]=[i][j],开始查找，循环条件为数组内的长度        while j<=cols and i>=0:            if target
   
    array[i][j]: # 若指定值比这个元素大，则就往右找                j+=1            else:                print('在数组内，找到该值!')                return True        return False
   

【java 代码实现】

public class Solution {       public boolean Find(int target, int [][] array) {           int rows=array.length;//行数        int colums=array[0].length;//列数        int i=rows-1;        int j=0;        while (i>=0&&j
   
    target){                   i--;            }else{                   return true;            }        }        return false;    }}
   

jz2.替换空格

题目描述

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

思路分析：

1.新建一个空列表，一边访问一边添加；

2.遍历字符串，遇到空格，就转换； 3.将列表再转化为字符串。

【python代码实现】：

# -*- coding:utf-8 -*-class Solution:    # s 源字符串    def replaceSpace(self, s):        # write code here        A=[ ]        for a in list(s):            if a==' ':                a='%20'            A.append(a)        result=''.join(A)#将列表转换为字符串的方法        return result

【Java代码实现】

public class Solution {       public String replaceSpace(StringBuffer str) {            return str.toString().replace(" ", "%20");    }}

题解2：

class Solution:    # s 源字符串    def replaceSpace(self, s):        # write code here        a = ''        for i in s:            if i == ' ':                a += '%20'            else:                a += i        return a

字符串转换成列表

• list函数即可

例子：

str = 'abcde'list = list(str)list

结果：

['a', 'b', 'c', 'd', 'e']

列表转换成字符串

方法一：直接取出字符串进行拼接

list1 = ['hello','world']ret = list1[0] + list1[1]print(ret)

结果

helloworld

方法二：join( ）-常用方法

list1 = ['hello','world']# 引号中的内容为，连接各个字符串的字符a="".join(list1)print(a)

结果：

helloworld

python之字符串的遍历

方法一：for in

str = "hello world" for a in str:    print(a)

方法二：range() 把字符串长度传进去就行

str1="hello wprld"for index in range(len(str1)):    print(str1[index])

方法三：iter()

str1 = "hello world"for a in iter(str1):    print(a)

jz3.从尾到头打印链表

题目描述

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

思路分析：

题目要求：倒序输出链表

遍历链表，在遍历的同时倒序输出：每一次遍历都将其值插入到列表的首位置，这样就完成了倒叙的过程。

【python 代码实现】

class Solution:    # 返回从尾部到头部的列表值序列，例如[1,2,3]    def printListFromTailToHead(self, listNode):        # write code here        list1 = []        head = listNode        while head:#  当head不为空时            list1.insert(0,head.val)            head = head.next        return list1

jz4.重建二叉树

题目描述

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

思路分析：

1.前序遍历：根–>左–>右

2.中序遍历：左–>根–>右 3.前序遍历序列的第一个元素1是二叉树的根结点 4.二叉树的根结点1在中序遍历的位置将中序遍历划分为左子树与右子树两部分，这样4，7，2是1的左子树，3，5，8，6是1的右子树 5.删除前序遍历的元素1，并递归使用函数

从上面的图解来看，是一个递归的过程，注意，前序序列在使用root结点，是需要将其删除的，然后再使用前序序列，同时中序序列是分左子树与右子树的。

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # 返回构造的TreeNode根节点    def reConstructBinaryTree(self, pre, tin):        # write code here        if not pre or not tin:            return None        root = TreeNode(pre.pop(0))#根结点，pop方法移除并返回被移除的元素，被pop删除的元素是没办法恢复的        index = tin.index(root.val)#返回根结点在中序遍历序列中的索引        root.left = self.reConstructBinaryTree(pre,tin[:index])#创建左子树        root.right = self.reConstructBinaryTree(pre,tin[index+1:])#创建右子树        return root

jz5.用两个栈实现队列

题目描述

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

思路分析：

1.栈是先进后出，队列是先进先出

2.

• 当我们向模拟的队列插入数 1，2，3时，假设插入的是 stack1，此时的栈情况为：

栈 stack1：{1,2,3}

栈 stack2：{}

• 当需要弹出一个数，根据队列的"先进先出"原则，1先进入，则 1 应该先弹出。但是此时 1在 stack1 的最下面，所以我们需要将 stack1 中全部元素逐个弹出压入 stack2，从而1，2，3倒序，现在可以正确的从 stack2 中弹出 1，此时的栈情况为：
  栈 stack1：{}
  栈 stack2：{3，2}
• 继续弹出一个数，3比 2先进入"队列"，b 弹出，注意此时 b 在 stack2 的栈顶，可直接弹出，此时的栈情况为：
  栈 stack1：{}
  栈 stack2：{3}
• 此时向模拟队列插入一个数 4，还是插入 stack1，此时的栈情况为：
  栈 stack1：{4}
  栈 stack2：{3}
  弹出一个数，3比 4 先进入，3 弹出，因为 3在 stack2 的栈顶，可直接弹出，此时的栈情况为：
  栈 stack1：{4}
  栈 stack2：{}

根据上述描述可得出结论：

push操作就直接往stack1中push， pop操作需要分类一下：如果stack2为空，那么需要将stack1中的数据转移到stack2中，然后在对stack2进行pop，如果stack2不为空，直接pop就ok。

python实现之

# -*- coding:utf-8 -*-class Solution:    def __init__(self):        self.stack1=[ ]        self.stack2=[ ]    def push(self, node):        return self.stack1.append(node)    def pop(self):        if self.stack2==[ ]:#如果stack2为空，将stack1的元素转移到stack2            while self.stack1:                self.stack2.append(self.stack1.pop())            return self.stack2.pop()        return self.stack2.pop()