- 博客(62)
- 收藏
- 关注
RSS订阅原创 剑指offer python版 44.数字序列中某一位的数字
"""数字以01234567891011121314...的格式序列化到第一个字符序列中。在这个序列中，第五位（从0开始计数）是5，第13位是1，第19位是4。请写一个函数，求任意第n位对应的数字。""""""如求序列的1001位：0-9序列的前10位是0-9这10个只有一位的数字。显然1001>10，因此我们在后面的序列中找地1001-10=991位数字10-99 90X2 = 180接下来的180位数字是90个10-99的两位数。同样地，991>180，因此我
2020-06-19 11:29:42
221
原创 剑指offer python版 43.1-n整数中1出现的次数
"""输入一个整数n，求这1-n这n个整数的十进制表示中1 出现的次数。例如，输入12，1-12这些整数中包含1的数字有1、10、11、12，1一共出现了五次"""class Solution: def NumberOf1Between1AndN(self, n): number = 0 for i in range(1, n+1): number += self.NumberOf1(i) return number
2020-06-19 11:29:01
208
原创 剑指offer python版 42.连续子数组的最大和
"""输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。"""class Solution: def FindGreatestSumOfSubArray(self, data): if data == []: return cur_sum = 0 res = data[0] for i in range(len(data)
2020-06-19 11:28:05
191
原创 剑指offer python版 41.数据流中的中位数
"""如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值""""""构建一个最大堆和一个最小堆，分别存储比中位数小的数和大的数。当目前两堆总数为偶数的时候，把数字存入最大堆，然后重排最大堆，如果最大堆的堆顶数字大于最小堆堆顶数字，则把两个堆顶数字交换，重排两堆，此时两堆数字总数为奇数，直接输出最大堆堆顶数字即为中位数；如果当前两堆总数为技术的时候，把数字存入最
2020-06-19 11:27:15
163
原创 剑指offer python版 40.最小的K个数
"""输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4."""class Solution: # O(n)的算法，只有当我们可以修改输入的数组时可用 # 基于Partition的方法 def GetLeastNumbers_Solution(self, tinput, k): if tinput == None or len(tinput) < k or len(tinput) <
2020-06-19 11:26:16
157
原创 剑指offer python版 39.数组中出现次数超过一半的数字
"""数组中有一个数字的出现次数超过数组长度的一半，请找出这个数字例如输入一个长度为9的数组[1,2,3,2,2,2,4,5,2]。由于数字2在数组中出现了5次，超过数组长度的一半。因此输出2，不存在则输出0。"""class Solution: def Partition(self, numbers, length, start, end): if numbers == None or length <= 0 or start < 0 or end >=
2020-06-19 11:25:29
156
原创 剑指offer python版 38.字符串的排列
"""输入一个字符串，打印出该字符串中字符的所有排列。如输入abc，则打印出abc、acb、bac、cab、cba"""class Solution: def Permutation(self, s): if s == None: return [] if len(s) == 1: return list(s) else: result = []
2020-06-19 11:24:50
170
原创 剑指offer python版 37.序列化二叉树
"""实现两个函数，分别用来序列化和反序列化二叉树"""class TreeNonde: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: flag = -1 def Serialize(self, root): if not root: return '#'
2020-06-19 11:24:09
91
原创 剑指offer python版 36.二叉搜索树与双向链表
"""输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表要求不能创建任何新的节点，只能调整树中节点指针的指向"""class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def Convert(self, pRootOfTree): if pRootOfTree
2020-06-19 11:23:39
129
原创 剑指offer python版 35.复杂链表的复制
"""输入一个复杂链表（每个节点有节点值以及两个指针）一个指向下一个节点，另一个特殊指针指向任意一个节点返回结果为复制后复杂链表的head"""class RandomListNode: def __init__(self, x): self.label = x self.next = None self.random = Noneclass Solution: def Clone(self, pHead): if
2020-06-16 10:26:45
174
原创 剑指offer python版 34.二叉树中和为某一值的路径
"""输入一棵二叉树和整数，打印出二叉树中节点值的和为输入整数的所有路径"""class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def FindPath(self, root, sum): if root == None: return []
2020-06-16 10:26:11
132
原创 剑指offer python版 33.二叉搜索树的后序遍历
"""输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。假设输入数组的任意两个数字都互不相同二叉搜索树对于每一个非叶子节点, 均有结点左子节点<当前节点<结点右子节点"""class Solution: def VerifySquenceOfBST(self, sequence): if sequence == []: return False root = sequence[-1] leng
2020-06-16 10:25:33
83
原创 剑指offer python版 32.从上到下打印二叉树
"""从上往下打印出二叉树的每个节点，同层节点从左至右打印。广度优先遍历"""class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: # 返回从上到下每个节点值列表 def PrintFromTopToBottom(self, root): queue = []
2020-06-16 10:24:59
110
原创 剑指offer python版 31.栈的压入、弹出序列
"""输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。"""class Solution: # 方法1 def IsPopOrder(self, pushV, popV): if pushV == [] or popV == []: return False stack = [] for i in pushV: stack
2020-06-16 10:24:27
127
原创 剑指offer python版 30.包含min函数的栈
"""定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push、pop的时间复杂度都是O（1）"""class Solution: def __init__(self): self.stack = [] self.minStack = [] def push(self, node): self.stack.append(node) if self.minStack == [
2020-06-16 10:23:57
190
1
原创 剑指offer python版 29.顺时针打印矩阵
'''输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：[[ 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.'''class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix):
2020-06-16 10:23:26
182
原创 剑指offer python版 28.对称的二叉树
"""实现一个函数，判断一颗二叉树是不是对称的。如果一个二叉树和它的镜像一样，那么它是对称的。"""class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def isSymmetrical(self, pRoot): return self.isSymmetrical1
2020-06-16 10:22:50
120
原创 剑指offer python版 27.二叉树的镜像
"""输入一棵二叉树，该函数输出它的镜像。"""class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: # 递归实现 def MirrorRecursively(self, pNode): if pNode == None: return
2020-06-16 10:22:17
126
原创 剑指offer python版 26.树的子结构
class ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def Merge(self, pHead1, pHead2): if pHead1 is None: return pHead2 if pHead2 is None: return pHead1
2020-06-15 11:29:26
139
原创 剑指offer python版 25.合并排序的两个链表
class ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def Merge(self, pHead1, pHead2): if pHead1 is None: return pHead2 if pHead2 is None: return pHead1
2020-06-15 11:28:54
128
原创 剑指offer python版 24.反转链表
"""定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点"""class ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def ReverseList(self, pHead): pReverseHead = None pNode = pHead pPrev = None
2020-06-15 11:26:56
146
原创 剑指offer python版 23.链表中环的入口节点
"""一个链表中包含环，请找出该链表的环的入口节点"""class ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def EntryNodeOfLoop(self, pHead): if pHead is None or pHead.next is None: return None fa
2020-06-15 11:26:24
102
原创 剑指offer python版 22.链表中倒数第k个节点
"""输入一个整数数组，实现一个函数来调整该数组中的数字的顺序，使得所有奇数位于数组的前半部分，所有的偶数位于数组的后半部分。"""class Solution: # 一个类似于快排的方法, 只是简单的满足了奇数在前,偶数在后, 奇数的顺序发生了改变 def reOrderArray(self, array): if len(array) < 1: return elif len(array) == 1:
2020-06-15 11:25:09
110
原创 剑指offer python版 21.调整数组顺序使奇数位于偶数前面
"""输入一个整数数组，实现一个函数来调整该数组中的数字的顺序，使得所有奇数位于数组的前半部分，所有的偶数位于数组的后半部分。"""class Solution: # 一个类似于快排的方法, 只是简单的满足了奇数在前,偶数在后, 奇数的顺序发生了改变 def reOrderArray(self, array): if len(array) < 1: return elif len(array) == 1:
2020-06-15 11:24:32
220
原创 剑指offer python版 20.表示数值的字符串
"""请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串“+100”、“5e2”、“-123”、“3.123”、“-1E-16”都表示数值，但"12e"、"1a3.14"、"1.1.2"、"+5"、"12e+5.4"都不是"""class Solution: def isNumeric(self, s): if s is None or len(s) == 0: return False hasE, isDec
2020-06-11 13:59:20
235
原创 剑指offer python版 19.正则表达式匹配
"""请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"aba"均不匹配"""class Solution: # s, pattern都是字符串 def match(self, s, pattern): if len(s) == 0 and le
2020-06-11 13:58:34
118
原创 剑指offer python版 18.删除链表的节点
'''给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点'''class ListNode: def __init__(self, x=None): self.val = x self.next = None def __del__(self): self.val = None self.next = Noneclass Solution: def DeleteNode(self, p
2020-06-11 13:57:47
146
原创 剑指offer python版 17.打印从1到最大的n位数
"""输入数字n, 按顺序打印从1最大的n位十进制数比如输入3, 则打印出1、2、3、到最大的3位数即999"""class Solution: def Print1ToMaxOfNDigits(self, n): if n <= 0: return number = ['0'] * n while not self.Increment(number): self.PrintNumber
2020-06-11 13:56:59
73
原创 剑指offer python版 16.数值的整数次方
class Solution: def Power(self, base, exponent): g_InvalidInput = False if (abs(base) < 1e-6) and exponent < 0: g_InvalidInput = True return 0. absExponent = exponent if exponent < 0:
2020-06-11 13:56:00
113
原创 剑指offer python版 15.二进制中1的个数
class Solution: def NumberOf1(self, n): count = 0 flag = 1 while(flag): if n & flag: count += 1 flag = flag << 1 return count def NumberOf1_1(self, n): coun
2020-06-11 13:55:21
145
原创 剑指offer python版 14.剪绳子
class Solution: """ 使用动态规划算法 """ def cutLine(self, n): if n < 2: return 0 if n == 2: return 1 if n == 3: return 2 MaxLine = [0, 1, 2, 3] for i in range(4, n+1)
2020-06-11 13:54:21
108
原创 剑指offer python版 13.机器人的运动范围
'''地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？'''class Solution: def movingCount(self, threshold, rows, cols):
2020-06-11 13:53:48
150
原创 剑指offer python版 12.矩阵中的路径
'''请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 [[a b c e], [s f c s], [a d e e]] 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。'''class Solu
2020-06-10 18:21:41
151
原创 剑指offer python版 11.旋转数组的最小数字
'''把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。'''class Solution: def minNumberInRotateArray1(self, rotateArray): if len(rotateArray) == 0:
2020-06-10 18:21:07
106
原创 剑指offer python版 10.斐波那契数列
'''用两个队列来实现一个栈，完成栈的Push和Pop操作。 栈中的元素为int类型。'''class Solution: def __init__(self): self.queue1 = [] self.queue2 = [] def push(self, x): if self.queue2 == []: self.queue1.append(x) else: se
2020-06-10 18:20:35
151
原创 剑指offer python版 9.2用两个队列实现栈
'''用两个队列来实现一个栈，完成栈的Push和Pop操作。 栈中的元素为int类型。'''class Solution: def __init__(self): self.queue1 = [] self.queue2 = [] def push(self, x): if self.queue2 == []: self.queue1.append(x) else: se
2020-06-10 17:25:53
82
原创 剑指offer python版 9.1用两个栈实现队列
'''用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。'''class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): self.stack1.append(node) def pop(self): if len(self.stack1) == 0 a
2020-06-10 17:25:23
61
原创 剑指offer python版 8.二叉树的下一个节点
'''给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。'''class TreeLinkNode: def __init__(self, x): self.val = x self.left = None self.right = None self.next = Noneclass Solution: def GetNext(.
2020-06-10 17:24:47
54
原创 剑指offer python版 7.重建二叉树
'''输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。'''class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solu
2020-06-10 17:24:15
74
原创 剑指offer python版 6.从尾到头打印链表
"""输入一个链表，从尾到头打印每个节点的值"""class ListNode: def __init__(self, x=None): self.val = x self.next = Noneclass Solution: def printListFromTailToHead1(self, listNode): """ 通过列表insert方式把链表顺序的元素插入列表头 :param listNo
2020-06-10 17:23:18
77
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人