- 博客(43)
- 收藏
- 关注
RSS订阅原创 主方法（master公式）
最近经常碰到主方法的使用，今天再这里做一个记录。有些算法在处理一个较大规模的问题时，往往会把问题拆分成几个子问题，对其中的一个或多个问题递归地处理，并在分治之前或之后进行一些预处理、汇总处理。这时候我们可以得到关于这个算法复杂度的一个递推方程，求解此方程便能得到算法的复杂度。主方法Master是用来利用分治策略来解决问题经常使用的时间复杂度的分析方法，众所周知，分治策略中使用递归来求...
2019-07-23 14:22:40
5200
1
原创 《剑指offer》之二叉搜索树与双向链表（python实现）
题目描述:输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路：二叉搜索树的中序遍历序列就是排序的数列；然后将当前节点的右子树设为下一个节点,下一个节点的左子树设为该节点，即可。（先中序遍历生成有序数列arr，之后进行左右节点设置）python代码实现如下：# -*- coding:utf-8 -*-# ...
2019-07-22 23:12:36
319
原创 《剑指offer》之深度链表的复制（python实现）
题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）思路：（参考牛客网评论） 1. 把复制的结点链接在原始链表的每一对应结点后面 2.把复制的结点的random指针指向被复制结点的...
2019-07-21 09:20:42
169
原创 《剑指offer》之数组中出现次数超过一半的数字（python实现）
问题描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。思路分析：我们首先使用sort对数组进行排序，如果数组拥有出现次数超过一半的数字，那么排序后的数组第（一半+1）个数字肯定是这个数字的。[1,2,2,2,2,4,5,...
2019-07-16 15:09:20
204
原创 《剑指offer》之二叉树中和为某一值的路径（python实现）
问题描述：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)思路分析：使用两个数列a，b；b用来存储二叉树路径，a来符合要求的路径；python代码实现如下：# -*- coding:utf-8 -*-# class ...
2019-07-16 14:32:31
135
原创 《剑指offer》之二叉搜索树的后续遍历序列（python实现）
问题描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路：后序遍历最后一位是根节点，二叉搜索树左子树所有节点小于根节点，右子树大于根节点；根据这个信息依次找出左右子树，递归判断是否符合后序遍历。步骤：1）我们找到根节点（最后一位）2）遍历数列，找到第一个大于等于根节点的元素i（i...
2019-07-14 21:54:31
120
原创 《剑指offer》之从上往下打印二叉树（python实现）
问题描述：从上往下打印出二叉树的每个节点，同层节点从左至右打印。思路分析：从题意看这就是二叉树的层次遍历，宽度优先搜索问题。借助两个数组，一个用来存储节点（这是一个队列），另外一个用来存储节点值（result）。从根节点开始遍历节点，把每一层的节点都放进这个队列中；开始遍历这个队列，将队列的值以及放进result数组中最后返回。总结一下：1）将根节点加入队列2）队列不为空...
2019-07-14 17:45:01
168
原创 《剑指offer》之栈的压入、弹出序列（python实现）
题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）思路分析：借用一个辅助的栈，遍历压栈表的顺序；先将第一个值放...
2019-07-09 21:22:46
77
原创 《剑指offer》之用两个栈实现队列（python实现）
问题描述： 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。分析思路：栈是先进后出；队列是先进先出；push操作没有影响，压入相应值就可以；区别在pop操作，两个栈来实现，就好像两个杯子进行倒水，将一杯水导入另一杯的时候，先前那杯水的杯子底部的水就到了另一个杯子的顶部；python代码实现如下：# -*- codin...
2019-07-08 16:44:03
133
原创 《剑指offer》之包含min函数的栈（python实现）
问题描述： 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。思路分析：构建一个辅助栈helper来辅助解决问题；向栈stack压入元素的时候，如果辅助栈没有元素或者压入的值小于辅助栈顶的值，就将其同时压入栈stack和辅助栈helper；如果压入的值大于或者等于辅助栈顶，则辅助栈再次压入辅助栈栈顶的指，这样可...
2019-07-07 23:08:45
190
原创 《剑指offer》之顺时针打印矩阵（python实现）
问题描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.思路分析：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
2019-07-06 23:34:32
207
原创 《剑指offer》之二叉树的镜像（python实现）
问题描述： 操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 ...
2019-07-06 22:40:20
91
原创 《剑指offer》之树的子结构（python实现）
问题描述： 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）思路分析：（思路整体上参考了牛客网评论区的答案）对于两棵二叉树来说，要判断B是不是A的子结构----首先第一步在树A中查找与B根节点的值一样的节点；第二步就是判断树A中以R为根节点的子树是不是和树B具有相同的结构；如果节点R的值和树的根节点不相同，则以R为根节...
2019-07-06 21:20:31
179
原创 《剑指offer》之合并两个排序的链表（python实现）
问题描述： 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。思路分析：不断对两个链表当前头指针所指向的元素值进行比较，小的接入合并链表尾部，头指针后移一位，该元素的next域改为空，直到有一个链表遍历完，再将有剩余的链表合并到链表尾部即可完成。python语言代码实现如下：# -*- coding:utf-8...
2019-07-04 15:20:10
134
原创 《剑指offer》之反转链表（python实现）
问题描述： 输入一个链表，反转链表后，输出新链表的表头。思路分析：这是典型的链表反转问题，之前学习在看一本python语言的图解数据结构，其中链表一张中讲解了链表的反转。python实现代码如下：# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# s...
2019-07-04 13:22:32
228
原创 《剑指offer》之链表中倒数第k个结点（python实现）
问题描述：输入一个链表，输出该链表中倒数第k个结点。思路分析：我们使用两个指针来进行处理，两个指针间隔为k-1，同时在链表上移动，这样第一个指针到达列表末尾的时候第二个指针刚好指向倒数第k个节点。（注意本题要求返回的是结点而不是返回结点值，博主在做的时候就看错题以为返回的是结点值，花费了很多时间）代码如下：# -*- coding:utf-8 -*-# class Li...
2019-07-02 17:24:58
190
原创 《剑指offer》之调整数组顺序使奇数位于偶数前面（python实现）
问题描述： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。思路： 顺序循环列表将列表元素依次进行奇偶判断，如果是奇数加到前边奇数列表中，如果是偶数增加到后边偶数列表中。# -*- coding:utf-8 -*-class Solut...
2019-07-02 16:40:29
155
原创 《剑指offer》之数值的次方运算（python实现）
问题描述： 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。分析：此题很简单就是简单的python求次方运算（a的b次方），差不多可以三种小方法解决：1）a**b2）pow(a,b)3) import math math.pow(a,b)代码如下:# -*- coding:utf-8 ...
2019-07-02 14:25:58
556
原创 《剑指offer》之二进制中1的个数（python实现）
问题描述: 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。思路分析：首先我们知道正数的原码、反码、补码是一样的；负数的补码是原码符号位不变其余位取反加1得到的；根据补码原理我们将其分为求0、求正数、求负数的补码中1的个数；求出补码之后我们再使用.count("1")来进行数1的个数；正数直接使用bin()进行求解补码；python中负数的补...
2019-07-02 14:07:02
157
原创 《剑指offer》之矩形覆盖问题（python实现）
问题描述： 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？思路分析：我们任然使用找规律的方法进行解决问题。n=1时，总共有1种方法，f(1)=1;n=2时，总共有2种方法，f(2)=2;n=3时，总共有3种方法，f(3)=3;n=4时，总共有5种方法，f(4)=5;.........
2019-07-02 11:07:51
182
原创 《剑指offer》之变态跳台阶（python实现）
问题描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路分析：一：我们仍然使用上一题跳台阶的思路进行找规律找出求解方法。我们使用F(n)表示跳n阶台阶总共的跳法总数。F(1)=1F(2)=2F(3)=4F(4)=8......我们发现了一个规律：F(n)=2*F(n-1)我们便可以使用...
2019-07-02 09:51:10
494
原创 《剑指offer》之跳台阶（python实现）
问题描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 分析：这是在考察循环与递归的内容； 一种方法是我们可以使用找规律的方法找出n阶台阶的跳法，1阶1种可以表示成f（1）=1，2阶2种f（2）=2，3阶3种f（3）=3，4阶5种f（4）=5.....
2019-07-01 22:58:34
312
原创 《剑指offer》之斐波那契数列（python实现）
问题描述： 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39思路分析： 斐波那契数列：从第三项开始，每一项是前两项的和，第一项和第二项是0和1。 我们先生成数列，之后返回第n项即可实现。如下是博主实现所使用的代码（生成整个列表，再返回第n项）：# -*- ...
2019-06-30 22:07:59
275
原创 《剑指offer》之旋转数组的最小数字（python实现）
问题描述： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。思路整体可以以下几种方法解决，博主在刷题的时候使用了第一种比较的方法，之后在网上看到...
2019-06-29 10:01:37
77
原创 《剑指offer》之重建二叉树（python实现）
问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。参考网上其他小伙伴的解答方案用以下代码解题，两种方式略有差别。（感慨大牛思路666，自己 写了几十行代码没搞定，还是参考了网上代码思路。）...
2019-06-28 21:23:54
198
原创 《剑指offer》之从尾到头输出链表（python实现）
问题描述’：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。在牛客网刷题的时候使用了如下两种简便的方法：方法一：这种方法使用了list的特性，向list添加元素可以直接使用+[value]。value是向列表添加的元素。# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):...
2019-06-28 16:59:48
222
原创 《剑指offer》之替换空格（python实现）
问题描述： 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。思路： 之间使用python的join函数通过字符连接生成新的字符串返回。Python join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串。join()方法...
2019-06-28 14:02:54
176
原创 《剑指offer》之二维数组中的查找（python实现）
（最近开始刷一些算法题，简要做个记录）问题描述： 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路： 由问题描述可以得到，从二位数组左下角来看，右边的数大于左下角值（从左到右依次递增），上边的数小于左下角的值...
2019-06-28 13:40:50
174
原创 格式输出10000以内第M到第N个素数
def isPrime(): X = [] Max = 10000 for i in range(2,Max): for j in range(2,i): if i % j == 0: break else: X.append(i) return ...
2019-06-27 09:45:44
381
原创 python实现输出任意两个数之间的所有素数
输入在一行中给出M和N，其间以空格分隔输出从M到N之间的所有素数，每10个数字占1行，其间以空格分隔，行末不可以有多余空格M,N = map(int,input().split(' '))X = []for i in range(M,N+1): for j in range(2,i): if i % j == 0: break ...
2019-06-25 16:56:17
19951
7
原创 聊天机器人Chatterbot学习测试使用（一）
#!/usr/bin/python# -*- coding: utf-8 -*-from chatterbot import ChatBotfrom chatterbot.trainers import ChatterBotCorpusTrainermy_bot = ChatBot("Training demo")trainer = ChatterBotCorpusTrainer(m...
2019-06-17 16:55:35
576
原创 Jupyter Notebook基础入门使用技巧
Jupyter Notebook是以网页的形式打开，可以在网页页面中直接编写代码和运行代码，代码的运行结果也会直接在代码块下显示。如在编程过程中需要编写说明文档，可在同一个页面中直接编写，便于作及时的说明和解释。启动Jupyter Notebook在文件所在目录使用终端使用如下命令：jupyter notebook常用快捷键命令如下： 执行当前cell，并自动跳到下一个ce...
2019-06-13 16:23:16
313
转载 python常用OS模块详解
学习过程中经常会使用到一些os模块的一些函数，通过网络查找罗列以下常用os模块函数，方便使用。/内容均查找自网络常见函数使用方法：#OS模块#os模块就是对操作系统进行操作，使用该模块必须先导入模块：import os#getcwd() 获取当前工作目录(当前工作目录默认都是当前文件所在的文件夹)result = os.getcwd()print(result)#chd...
2019-05-20 14:54:05
217
原创 python常见数据类型转换（字符串-整数-浮点数）
int(str) 函数将符合整数规范的字符串转换成 int 型num = "123"print(type(num))num1 = int(num)print("num1: %d" % num1)print(type(num1))'''结果<class 'str'>num1: 123<class 'int'>''' float(str) 函数将...
2019-03-25 10:08:25
8172
原创 经典排序算法-选择排序-python实现
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。算法描述：（n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果） 1.初始状态：无序区为R[1..n]...
2019-03-22 10:09:36
96
原创 经典排序算法-冒泡排序-python实现
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。算法描述： 1.比较相邻的元素。如果第一个比第二个大，就交换它们两个； 2.对每一对相邻元素作同样的工作，...
2019-03-22 10:06:11
204
原创 经典排序算法-归并排序-python实现
归并排序:：利用归并的思想实现的排序方法，该算法采用经典的分治策略。分治法：将问题分成一些小的问题然后递归求解，而治则是将分的阶段得到的各答案拼接在一起，即分而治之。算法思想步骤：（先将需排序的数组递归分解进行排序，后合并有序数组）1.递归分解，基本思路是将数组分解成left和right2.如果这两个数组内部数据是有序的，那么就可以用合并数组的方法将这两个数组合并排序3.如何让...
2019-03-22 09:51:34
143
原创 经典排序算法-快速排序-python实现
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序采用分治算法，算法步骤如下：1.两个指针left，right分别指向列表的第一个元素和最后一个元素，然后取一个参考值，默认为第一个列表的第一个元素（也可以取最后一个），称为Key2.然后right指向的值先和参考值Key进行比...
2019-03-21 13:28:03
223
2
原创 经典排序算法-希尔排序-python实现
希尔排序（shell sort）又称为缩小增量排序，是1959年D·L·Shell提出来的。是插入排序的改进版基本思想是：设待排序元素序列有n个元素，首先取一个整数jump（小于n）作为间隔将全部元素分为jump个子序列，所有距离为jump的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔jump，重复上述子序列划分和排序工作。直到最后取jump=1，将所有元素...
2019-03-20 15:26:08
127
原创 经典排序算法-插入排序-python实现
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。算法描述一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：从第一个元素开始，该元素可以认为已经被排序； 取出下一个元素，在已经排序的元素序列中从后向前扫描； 如果该元素（已排序）大于新元素，...
2019-03-19 15:20:34
296
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人