网站建设方案拓扑图,抚顺网站开发,手机版网站如何制作,免费制作照片的网站https://blog.csdn.net/tinkle181129/article/details/79326023# 二叉树的镜像 链表中环的入口结点 删除链表中重复的结点 从尾到头打印链表 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 把字符串转换成整数 平衡二叉树 和为S的连续正数序列 左… https://blog.csdn.net/tinkle181129/article/details/79326023# 二叉树的镜像 链表中环的入口结点 删除链表中重复的结点 从尾到头打印链表 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 把字符串转换成整数 平衡二叉树 和为S的连续正数序列 左旋转字符串 数字在排序数组中出现的次数 数组中只出现一次的数字 翻转单词顺序列 二叉树的深度 和为S的两个数字 顺时针打印矩阵 二叉树的下一个结点 对称的二叉树 把二叉树打印成多行 按之字形顺序打印二叉树 序列化二叉树 二叉搜索树的第k个结点 数据流中的中位数 重建二叉树 滑动窗口的最大值 用两个栈实现队列 旋转数组的最小数字 丑数 两个链表的第一个公共结点 第一个只出现一次的字符位置 数组中的逆序对 连续子数组的最大和 最小的K个数 数组中出现次数超过一半的数字 整数中1出现的次数从1到n整数中1出现的次数 把数组排成最小的数 数组中重复的数字 构建乘积数组 二维数组中的查找 扑克牌顺子 孩子们的游戏(圆圈中最后剩下的数) 正则表达式匹配 表示数值的字符串 字符流中第一个不重复的字符 替换空格 矩阵中的路径 机器人的运动范围 求123…n 不用加减乘除做加法 二叉搜索树与双向链表 复杂链表的复制 字符串的排列 二进制中1的个数 链表中倒数第k个结点 合并两个排序的链表 反转链表 树的子结构 数值的整数次方 调整数组顺序使奇数位于偶数前面 包含min函数的栈 二叉树中和为某一值的路径 从上往下打印二叉树 二叉搜索树的后序遍历序列 栈的压入、弹出序列(1) 二叉树的镜像Symmetric Tree牛客网链接Leetcode链接class Solution: # 返回镜像树的根节点 def Mirror(self, root): if root None: return self.Mirror(root.left) self.Mirror(root.right) root.left,root.right root.right,root.left 1 2 3 4 5 6 7 82链表中环的入口结点Leetcode 142. Linked List Cycle II寻找环的入口结点这题是Leetcode 141. Linked List Cycle的扩展。判断是否存在环用fast和slow两个指针从head开始一个走一步一个走两步如果最终到达同一个结点则说明存在环。class Solution(object): def hasCycle(self, head): :type head: ListNode :rtype: bool if head None or head.next None: return False slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15而寻找环的入口假设入口结点距离头结点a个单位fast和slow相遇在距离入口结点b个单位的位置环剩下的长度为c则有abcb 2*(ab) - a c因此在重合时候将fast置为head再一步一步地走当与slow重合时的结点即为入口结点class Solution: def EntryNodeOfLoop(self, pHead): # write code here if pHead None or pHead.next None: return None fast slow pHead while(fast and fast.next): slow slow.next fast fast.next.next if slow fast: fast pHead while(fast!slow): fast fast.next slow slow.next return fast return None 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 163 删除链表中重复的结点删除链表中重复的结点Leetcode. 82. Remove Duplicates from Sorted List II用flag来标记当前的结点是否为重复结点class Solution: def deleteDuplication(self, pHead): # write code here pos pHead ret ListNode(-1) tmp ret flag False while(pos and pos.next): if pos.val pos.next.val: flag True pos.next pos.next.next else: if flag: flag False else: tmp.next ListNode(pos.val) tmp tmp.next pos pos.next if pos and flagFalse: tmp.next ListNode(pos.val) return ret.next 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 214从头到尾打印链表从头到尾打印链表class Solution: # 返回从尾部到头部的列表值序列例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here ret [] head listNode while(head): ret.append(head.val) head head.next ret.reverse() return ret 1 2 3 4 5 6 7 8 9 10 115求斐波那契数列的第n项斐波那契数列# -*- coding:utf-8 -*-class Solution: def Fibonacci(self, n): if n 0: return 0 if n1 or n2: return 1 memories [1,1] for i in range(n-2): memories.append(memories[-1]memories[-2]) return memories[-1] 1 2 3 4 5 6 7 8 9 10 116跳台阶一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。dp[n]dp[n−1]dp[n−2]# -*- coding:utf-8 -*-class Solution: def jumpFloor(self, number): # write code here n 1 : 1 n 2 : 11 2 n 3 : dp[n-2]dp[n-1] if number 1 or number 2: return number dp [1,2] for i in range(number-2): dp.append(dp[-1]dp[-2]) return dp[-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 157变态跳台阶一只青蛙一次可以跳上1级台阶也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思考在dp[n] dp[n-1] dp[n-2] .. dp[1] 1(直接跳n)步骤即dp[n]∑n−1i1dp[i]1class Solution: def jumpFloorII(self, number): # write code here if number 1 or number 2: return number ret sum_ 3 for i in range(number-2): ret sum_1 sum_ret return ret 1 2 3 4 5 6 7 8 9 108矩形覆盖我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形总共有多少种方法思考 2*1 1 种 2*2 2种 2*3 3种 2*4 5种dp[n]dp[n−1]dp[n−2]# -*- coding:utf-8 -*-class Solution: def rectCover(self, number): # write code here if number2: return number dp [1,2] for i in range(number-2): dp.append(dp[-1]dp[-2]) return dp[-1] 1 2 3 4 5 6 7 8 9 10 119把字符串转换成整数把字符串转换成整数将一个字符串转换成一个整数要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0思考如果有正负号需要在数字之前出现其他字符或者字符串为空都非法返回0class Solution: def StrToInt(self, s): # write code here flag True pos 1 ret None if s: return 0 for i in s: if i or i-: if flag: pos -1 if i- else 1 flag False else: return 0 elif i0 and i9: flag False if ret None: ret int(i) else: ret ret*10int(i) else: return 0 return pos*ret if ret else 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2410平衡二叉树的判断思考BST的定义为|height(lefttree)−height(righttree)|1原问题拆分为计算树高度和判断高度差class Solution: def Treeheight(self,pRoot): if pRoot None: return 0 if pRoot.left None and pRoot.right None: return 1 lh self.Treeheight(pRoot.left) rh self.Treeheight(pRoot.right) return max(rh,lh)1 def IsBalanced_Solution(self, pRoot): # write code here if pRoot None: return True return abs(self.Treeheight(pRoot.left)-self.Treeheight(pRoot.right))1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1511和为S的连续正数序列输出所有和为S的连续正数序列。序列内按照从小至大的顺序序列间按照开始数字从小到大的顺序思考S%奇数0 或者S%偶数偶数2 就说明有这个连续序列但是注意是正数序列可能会出现越界情况class Solution: def FindContinuousSequence(self, tsum): # write code here k 2 ret [] for k in range(2,tsum): if k%21 and tsum%k0: tmp [] mid tsum/k if mid-k/20: for i in range(mid-k/2,midk/21): tmp.append(i) ret.append(tmp[:]) elif k%20 and (tsum%k)*2k: mid tsum/k tmp [] if mid-k/210: for i in range(mid-k/21,midk/21): tmp.append(i) ret.append(tmp[:]) ret.sort() return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2212左旋转字符串对于一个给定的字符序列S请你把其循环左移K位后的序列输出。思考需要先K K%len(S)# -*- coding:utf-8 -*-class Solution: def LeftRotateString(self, s, n): # write code here if s : return s n n%len(s) return s[n:]s[0:n] 1 2 3 4 5 6 7 813数字在排序数组中出现的次数数字在排序数组中出现的次数思考原来是可以用hash做的但是因为是排序数组所以可以用二分查找# -*- coding:utf-8 -*-class Solution: def GetNumberOfK(self, data, k): # write code here start 0 end len(data)-1 while(startend): mid (startend)/2 if data[mid]k: cnt 0 tmp mid while(tmp0 and data[tmp]k): cnt1 tmp-1 tmp mid1 while(tmplen(data) and data[tmp]k): cnt1 tmp1 return cnt elif data[mid]k: end mid-1 else: start mid1 return 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2414数组中只出现一次的数字一个整型数组里除了两个数字之外其他的数字都出现了两次。请写程序找出这两个只出现一次的数字思考用hash或者位运算首先利用0 ^ a a; a^a 0的性质两个不相等的元素在位级表示上必定会有一位存在不同将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果据异或的结果1所在的最低位把数字分成两半每一半里都还有一个出现一次的数据和其他成对出现的数据,问题就转化为了两个独立的子问题“数组中只有一个数出现一次其他数都出现了2次找出这个数字”。class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): # write code here ans,a1,a2,flag 0,0,0,1 for num in array: ans ans ^ num while(ans): if ans%2 0: ans ans 1 flag flag 1 else: break for num in array: if num flag: a1 a1 ^ num else: a2 a2 ^ num return a1,a2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915翻转单词顺序列# -*- coding:utf-8 -*-class Solution: def ReverseSentence(self, s): # write code here ret s.split( ) ret.reverse() return .join(ret) 1 2 3 4 5 6 716二叉树的深度# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right Noneclass Solution: def TreeDepth(self, pRoot): # write code here if pRoot None: return 0 if pRoot.left None and pRoot.rightNone: return 1 return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))1 1 2 3 4 5 6 7 8 9 10 11 12 13 1417和为S的两个数字输入一个递增排序的数组和一个数字S在数组中查找两个数是的他们的和正好是S如果有多对数字的和等于S输出两个数的乘积最小的。hash# -*- coding:utf-8 -*-class Solution: def FindNumbersWithSum(self, array, tsum): # write code here memorys {} ret [] for num in array: if tsum-num in memorys: if ret []: ret [tsum-num,num] elif ret and ret[0]*ret[1](tsum-num)*num: ret [tsum-num,num] else: memorys[num] 1 return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1518顺时针打印矩阵# -*- coding:utf-8 -*-class Solution: # matrix类型为二维列表需要返回列表 def printMatrix(self, matrix): # write code here mlen(matrix) ans[] if m0: return ans nlen(matrix[0]) #ans [[0 for i in range(n)] for j in range(n)] #print ans upper_i 0;lower_im-1;left_j0;right_jn-1 num1 i0;j0 right_pointer1 down_pointer0 while(numm*n): ans.append(matrix[i][j]) if right_pointer1: if jright_j: jj1 else: right_pointer0 down_pointer1 upper_i upper_i1 i i1 elif down_pointer 1: if ilower_i: i i1 else: right_pointer-1 down_pointer0 right_j right_j -1 j j-1 elif right_pointer -1: if j left_j: jj-1 else: right_pointer0 down_pointer-1 lower_i lower_i-1 i i-1 elif down_pointer -1: if i upper_i: ii-1 else: right_pointer1 down_pointer0 left_j left_j 1 j j1 numnum1 return ans 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5319* 二叉树的下一个结点二叉树的下一个结点给定一个二叉树和其中的一个结点请找出中序遍历顺序的下一个结点并且返回。注意树中的结点不仅包含左右子结点同时包含指向父结点的指针。思路中序遍历的顺序为LVR则有以下三种情况a. 如果该结点存在右子结点那么该结点的下一个结点是右子结点树上最左子结点b. 如果该结点不存在右子结点且它是它父结点的左子结点那么该结点的下一个结点是它的父结点c. 如果该结点既不存在右子结点且也不是它父结点的左子结点则需要一路向祖先结点搜索直到找到一个结点该结点是其父亲结点的左子结点。如果这样的结点存在那么该结点的父亲结点就是我们要找的下一个结点。class Solution: def GetNext(self, pNode): # write code here # left root right if pNode None: return None if pNode.right: tmp pNode.right while(tmp.left): tmp tmp.left return tmp p pNode.next while(p and p.rightpNode): pNode p p p.next return p 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1620对称的二叉树Leetcode 101. Symmetric Tree判断一棵树是不是左右对称的树class Solution: def Symmetrical(self,Lnode,Rnode): if Lnode None and Rnode None: return True if Lnode and Rnode: return Lnode.val Rnode.val and self.Symmetrical(Lnode.right,Rnode.left) and self.Symmetrical(Lnode.left,Rnode.right) else: return False def isSymmetrical(self, pRoot): # write code here if pRoot None: return True return self.Symmetrical(pRoot.left,pRoot.right) 1 2 3 4 5 6 7 8 9 10 11 12 1321把二叉树打印成多行从上到下按层打印二叉树同一层结点从左至右输出。每一层输出一行。class Solution: # 返回二维列表[[1,2],[4,5]] def Print(self, pRoot): # write code here if pRoot None: return [] stack [pRoot] ret [] while(stack): tmpstack [] tmp [] for node in stack: tmp.append(node.val) if node.left: tmpstack.append(node.left) if node.right: tmpstack.append(node.right) ret.append(tmp[:]) stack tmpstack[:] return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2122之字形打印二叉树class Solution: def Print(self, pRoot): # write code here if pRoot None: return [] stack [pRoot] step 1 ret [] while(stack): tmpstack [] tmp [] for node in stack: tmp[node.val] if node.left: tmpstack.append(node.left) if node.right: tmpstack.append(node.right) if step%20: tmp.reverse() ret.append(tmp) step 1 stack tmpstack[:] return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2323* 序列化和反序列化二叉树序列化和反序列化二叉树Serialize and Deserialize Binary Treeclass Solution: def Serialize(self, root): # write code here def doit(node): if node: vals.append(str(node.val)) doit(node.left) doit(node.right) else: vals.append(#) vals [] doit(root) return .join(vals) def Deserialize(self, s): # write code here def doit(): val next(vals) if val #: return None node TreeNode(int(val)) node.left doit() node.right doit() return node vals iter(s.split()) return doit() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2624 * 数据流中的中位数数据流中的中位数Find Median from Data Streamfrom heapq import *class MedianFinder: def __init__(self): self.heaps [], [] def addNum(self, num): small, large self.heaps heappush(small, -heappushpop(large, num)) if len(large) len(small): heappush(large, -heappop(small)) def findMedian(self): small, large self.heaps if len(large) len(small): return float(large[0]) return (large[0] - small[0]) / 2.0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1725* 二叉平衡树中的第k小数二叉搜索树中的第k大结点Leetcode 230. Kth Smallest Element in a BST思路BST的中序遍历就是一个有序数组需要注意到Leetcode中限制了k在[1,树结点个数]而牛客网没有所以需要考虑k的值有没有超出class Solution: # 返回对应节点TreeNode def KthNode(self, pRoot, k): # write code here stack [] node pRoot while node: stack.append(node) node node.left cnt 1 while(stack and cntk): node stack.pop() right node.right while right: stack.append(right) right right.left cnt1 if node and kcnt-1: return node return None 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2026重建二叉树Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal根据先序、中序来构建二叉树class Solution(object): def buildTree(self, pre, tin): :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode if pre[]: return None val pre[0] idx tin.index(val) ltin tin[0:idx] rtin tin[idx1:] lpre pre[1:1len(ltin)] rpre pre[1len(ltin):] root TreeNode(val) root.left self.buildTree(lpre,ltin) root.right self.buildTree(rpre,rtin) return root 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal根据中序和后序构建二叉树class Solution(object): def buildTree(self, inorder, postorder): :type inorder: List[int] :type postorder: List[int] :rtype: TreeNode if postorder []: return None val postorder[-1] idx inorder.index(val) lin inorder[0:idx] rin inorder[idx1:] lpos postorder[0:len(lin)] rpos postorder[len(lin):-1] root TreeNode(val) root.left self.buildTree(lin,lpos) root.right self.buildTree(rin,rpos) return root 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1927滑动窗口的最大值给定一个数组和滑动窗口的大小找出所有滑动窗口里数值的最大值。例如如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3那么一共存在6个滑动窗口他们的最大值分别为{4,4,6,6,6,5} 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个 {[2,3,4],2,6,2,5,1} {2,[3,4,2],6,2,5,1} {2,3,[4,2,6],2,5,1} {2,3,4,[2,6,2],5,1} {2,3,4,2,[6,2,5],1} {2,3,4,2,6,[2,5,1]}。思考假设当前窗口起始位置为start,结束位置为end我们要构造一个stack, 使得stack[0]为区间[start,end]的最大值。# -*- coding:utf-8 -*-class Solution: def maxInWindows(self, num, size): # write code here if size 0: return [] ret [] stack [] for pos in range(len(num)): while (stack and stack[-1][0] num[pos]): stack.pop() stack.append((num[pos], pos)) if possize-1: while(stack and stack[0][1]pos-size): stack.pop(0) ret.append(stack[0][0]) return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17(28) 用两个栈实现队列思考栈FILO队列FIFO# -*- coding:utf-8 -*-class Solution: def __init__(self): self.stack1 [] self.stack2 [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if len(self.stack2): return self.stack2.pop() while(self.stack1): self.stack2.append(self.stack1.pop()) return self.stack2.pop() 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16(29) 旋转数组的最小数字思考二分判断# -*- coding:utf-8 -*-class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if rotateArray []: return 0 _len len(rotateArray) left 0 right _len - 1 while left right: mid int((left right) 1) if rotateArray[mid]rotateArray[mid-1]: return rotateArray[mid] if rotateArray[mid] rotateArray[right]: # 说明在【midright】之间 left mid 1 else: # 说明在【leftmid】之间 right mid - 1 return rotateArray[mid] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2030丑数只包含因子2、3和5的数称作丑数Ugly Number求按从小到大的顺序的第N个丑数。思路heap# -*- coding:utf-8 -*-import heapqclass Solution: def GetUglyNumber_Solution(self, index): # write code here if index1: return 0 heaps [] heapq.heappush(heaps,1) lastnum None idx 1 while(idxindex): curnum heapq.heappop(heaps) while(curnumlastnum): curnum heapq.heappop(heaps) lastnum curnum idx1 heapq.heappush(heaps,curnum*2) heapq.heappush(heaps,curnum*3) heapq.heappush(heaps,curnum*5) return lastnum 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2131两个链表的第一个公共结点思考设链表pHead1的长度为a,到公共结点的长度为l1链表pHead2的长度为b,到公共结点的长度为l2有al2 bl1class Solution: def FindFirstCommonNode(self, pHead1, pHead2): # write code here if pHead1 None or pHead2 None: return None pa pHead1 pb pHead2 while(pa!pb): pa pHead2 if pa is None else pa.next pb pHead1 if pb is None else pb.next return pa 1 2 3 4 5 6 7 8 9 10 11(32) 第一个只出现一次的字符思考hash加队列# -*- coding:utf-8 -*-class Solution: def FirstNotRepeatingChar(self, s): # write code here queue [] memories dict() for idx,char in enumerate(s): if char not in memories: queue.append(idx) memories[char]0 memories[char]1 while(queue and memories[s[queue[0]]]1): queue.pop(0) return queue[0] if queue else -1 1 2 3 4 5 6 7 8 9 10 11 12 13 1433 数组中的逆序对在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007思考这边的python会超时但是思路是对的时间复杂度O(nlogn),空间复杂度O(n)。先将数组逆转构建一个新的数组L将num二分插入到L中所插入的位置i代表有i个数字比当前这个数字小import bisectclass Solution: def InversePairs(self, data): data.reverse() L [] ret 0 for d in data: pos bisect.bisect_left(L,d) L.insert(pos,d) ret pos ret ret % 1000000007 return ret % 1000000007 1 2 3 4 5 6 7 8 9 10 11 12C解法来源于好朋友的博客/*** 运行时间191ms* 占用内存4336k*/class Solution {private: long long cnt;public: int InversePairs(vectorint data) { cnt 0; vectorint TmpArray(data.size()); Msort(data,TmpArray,0,data.size()-1); return cnt % 1000000007; }private: void Msort(vectorint data,vectorint TmpArray,int left, int right) { int center; if(left right) { center (left right)/2; Msort(data,TmpArray,left,center); Msort(data,TmpArray,center1,right); // 任意时刻只需要一个临时数组TmpArray活动 Merge(data,TmpArray,left,center1,right); } } void Merge(vectorint data,vectorint TmpArray,int Lpos,int Rpos,int RightEnd) { // 合并算法 int i,LeftEnd,NumElements,TmpPos; LeftEnd Rpos - 1; TmpPos RightEnd; NumElements RightEnd - Lpos 1; /* 主循环*/ while(LeftEnd Lpos RightEnd Rpos) { if(data[LeftEnd] data[RightEnd]) { TmpArray[TmpPos--] data[LeftEnd--]; /*计算逆序对数*/ cnt RightEnd - Rpos 1; } else //data[LeftEnd] data[RightEnd] TmpArray[TmpPos--] data[RightEnd--]; } while(LeftEnd Lpos) // 拷贝左半剩余部分 TmpArray[TmpPos--] data[LeftEnd--]; while(RightEnd Rpos) // 拷贝右半剩余部分 TmpArray[TmpPos--] data[RightEnd--]; /* 拷贝回原数组*/ for(int i 0;i NumElements;i,Lpos) data[Lpos] TmpArray[Lpos]; }}; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57(34) 连续子数组的最大和思考贪心class Solution: def FindGreatestSumOfSubArray(self, array): # write code here if len(array)1: return array[0] cur pos array[0] for i in range(1,len(array)): pos max(posarray[i],array[i]) cur max(cur,pos) return cur 1 2 3 4 5 6 7 8 9 10(35) 最小的K个数import heapqclass Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here heaps [] ret [] for num in tinput: heapq.heappush(heaps,num) if klen(heaps): return [] for i in range(k): ret.append(heapq.heappop(heaps)) return ret 1 2 3 4 5 6 7 8 9 10 11 12 1336数组中出现次数超过一半的数字思考摩尔投票法# -*- coding:utf-8 -*-class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here if numbers []: return 0 val,cnt None,0 for num in numbers: if cnt0: val,cnt num,1 elif val num: cnt1 else: cnt-1 return val if numbers.count(val)*2len(numbers) else 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1537* 从1到n整数中1出现的次数思考可以从n的每个位上入手pos来记录位ans来记录当前1的个数last来记录前面的数这样讲好复杂举个例子好了xxxxYzzzz 假设9位在Y上1的个数由xxxx,zzzz和Y来决定首先至少有xxxx0000个其次看Y如果Y大于1那么会多了10000个如果Y等于1那么会多了zzzz1个# -*- coding:utf-8 -*-class Solution: def NumberOf1Between1AndN_Solution(self, n): # write code here if n1: return 0 if n1: return 1 last,ans,pos 0,0,1 while(n): num n%10 n n/10 ans pos*n if num1: anspos elif num1: ans(last1) last lastnum*pos pos*10 return ans 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1838把数组排成最小的数输入一个正整数数组把数组里所有数字拼接起来排成一个数打印能拼接出的所有数字中最小的一个。例如输入数组{332321}则打印出这三个数字能排成的最小数字为321323。思考总的思路是先将整型字符串化然后重新定义排序规则我的做法是将n扩展成长度为n(maxlen-len(n))*n[0]的字符串看别人的解答又觉得巧妙# -*- coding:utf-8 -*-import heapqclass Solution: def PrintMinNumber(self, numbers): # write code here heaps [] maxlen 0 for num in numbers: maxlenlen(str(num)) for num in numbers: n str(num) heapq.heappush(heaps,(int(n(maxlen-len(n))*n[0]),num)) ret while(heaps): retstr(heapq.heappop(heaps)[1]) return int(ret) if len(ret) else 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16链接https://www.nowcoder.com/questionTerminal/8fecd3f8ba334add803bf2a06af1b993来源牛客网# -*- coding:utf-8 -*-class Solution: def PrintMinNumber(self, numbers): # write code here if not numbers:return numbers list(map(str,numbers)) numbers.sort(cmplambda x,y:cmp(xy,yx)) return 0 if numbers[0]0 else .join(numbers) 1 2 3 4 5 6 7 8 9 10 1139数组中重复的数字思考哈希然而依旧是一题Python不通过的题目# -*- coding:utf-8 -*-class Solution: # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0] # 函数返回True/False def duplicate(self, numbers, duplication): # write code here dup dict() for num in numbers: if num not in dup: dup[num] True else: duplication[0]num return True 1 2 3 4 5 6 7 8 9 10 11 12 1340* 构造乘积数组B[i]A[0]A[1]…A[i-1]*A[i1]…*A[n-1]思考分为下三角和上三角DP计算B下三角B[i]A[0]A[1]A[2]..A[i−1]B[i−1]A[i−1]上三角从最后往前tmpA[−1]A[−2]A[−3]...class Solution: def multiply(self, A): # write code here size len(A) B [1]*size for i in range(1,size): B[i] B[i-1]*A[i-1] tmp 1 for i in range(size-2,-1,-1): tmp tmp*A[i1] B[i] B[i]*tmp return B 1 2 3 4 5 6 7 8 9 10 11 1241二维数组中的查找在一个二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。思考从0,n-1出开始小了往下大了往左# -*- coding:utf-8 -*-class Solution: # array 二维列表 def Find(self, target, array): # write code here if len(array)0 or len(array[0])0: return False i 0 j len(array[0])-1 while(ilen(array) and j0): if array[i][j]target: return True elif array[i][j]target: j-1 else: i1 return False 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1742* 扑克牌顺子LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。class Solution: def IsContinuous(self, numbers): # write code here if not numbers: return 0 numbers.sort() zeros numbers.count(0) for i, v in enumerate(numbers[:-1]): if v!0: if numbers[i1]v: return False zeros - (numbers[i1]-numbers[i]-1) if zeros0: return False return True 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1543孩子们的游戏# -*- coding:utf-8 -*-class Solution: def LastRemaining_Solution(self, n, m): # write code here if n1: return -1 final,start -1,0 cnt [i for i in range(n)] while cnt: k (startm-1)%n final cnt.pop(k) n-1 start k return final 1 2 3 4 5 6 7 8 9 10 11 12 1344正则表达式匹配请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符而’‘表示它前面的字符可以出现任意次包含0次。 在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串”aaa”与模式”a.a”和”ab*ac*a”匹配但是与”aa.a”和”ab*a”均不匹配思考第一种情况当p ” 时 return s”当len(p)1时 要满足len(s)1 AND (p[0]s[0] OR p[0] ‘.’)当len(p)1时要讨论p[1] 是不是为’’ 因为如果p[1]’’ 时候 可能会是p[2:] 和 s 匹配情况但当p[1]!’*’ 时候 意味着 必须要关注是否 p[0]s[0] 或者 p[0]’.’那么这两个可以合并为IF len(p) 0 or p[1]!’*’返回 len(s) AND match(p[1:],s[1:]) AND (p[0]s[0] OR p[0] ‘.’)然后最复杂的一种情况p[1] ‘*’p ‘b*bbacd’ s ‘bbbbbacd’很明显的是如果p[0]!s[0] 且 p[0]!’.’ 那么 看p[2:] 和 s 的匹配情况如果p[0] s[0] 或者 p[0] ‘.’ 可以判断p[2:] 和 s[1:] … p[2:] 和 s[2:] … p[2:] 和 s[3:] … 搞个循环 就可以# -*- coding:utf-8 -*-class Solution: # s, pattern都是字符串 def __init__(self): self.dic {} def match(self, s, p): # write code here if (s,p) in self.dic: return self.dic[(s,p)] if p : return s if len(p)1 or p[1]!*: self.dic[(s[1:],p[1:])] self.match(s[1:],p[1:]) return len(s)0 and (p[0]. or p[0]s[0]) and self.dic[(s[1:],p[1:])] while(len(s) and (p[0]. or p[0]s[0])): self.dic[(s,p[2:])] self.match(s,p[2:]) if self.match(s[:],p[2:]): return True s s[1:] self.dic[(s,p[2:])] self.match(s,p[2:]) return self.dic[(s,p[2:])] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2145判断一个字符串是否表示数值就是各种逻辑# -*- coding:utf-8 -*-class Solution: # s字符串 def isNumeric(self, s): # write code here INVALID0; SPACE1; SIGN2; DIGIT3; DOT4; EXPONENT5; #0invalid,1space,2sign,3digit,4dot,5exponent,6num_inputs transitionTable[[-1, 0, 3, 1, 2, -1], #0 no input or just spaces [-1, 8, -1, 1, 4, 5], #1 input is digits [-1, -1, -1, 4, -1, -1], #2 no digits in front just Dot [-1, -1, -1, 1, 2, -1], #3 sign [-1, 8, -1, 4, -1, 5], #4 digits and dot in front [-1, -1, 6, 7, -1, -1], #5 input e or E [-1, -1, -1, 7, -1, -1], #6 after e input sign [-1, 8, -1, 7, -1, -1], #7 after e input digits [-1, 8, -1, -1, -1, -1]] #8 after valid input input space state0; i0 while ilen(s): inputtype INVALID if s[i] : inputtypeSPACE elif s[i]- or s[i]: inputtypeSIGN elif s[i] in 0123456789: inputtypeDIGIT elif s[i].: inputtypeDOT elif s[i]e or s[i]E: inputtypeEXPONENT statetransitionTable[state][inputtype] if state-1: return False else: i1 return state 1 or state 4 or state 7 or state 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2946字符流中第一个不重复的字符思考用个队列和hash# -*- coding:utf-8 -*-class Solution: # 返回对应char def __init__(self): self.memory dict() self.queue [] def FirstAppearingOnce(self): # write code here while len(self.queue) and self.memory[self.queue[0]]1: self.queue.pop(0) return self.queue[0] if len(self.queue) else # def Insert(self, char): # write code here if char not in self.memory: self.memory[char]0 self.memory[char]1 if self.memory[char]1: self.queue.append(char) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2047替换空格# -*- coding:utf-8 -*-import reclass Solution: # s 源字符串 def replaceSpace(self, s): # write code here return re.sub( ,%20,s) 1 2 3 4 5 6 748矩阵中的路径思考dfs加记忆化搜索# -*- coding:utf-8 -*-class Solution: def hasPath(self, matrix, rows, cols, path): def dfs(memories,r,c,s): if s: return True dx [-1,1,0,0] dy [0,0,-1,1] for k in range(4): x dx[k] r y dy[k] c if x 0 and x rows and y 0 and y cols and memories[x][y] and matrix[x*colsy]s[0]: memories[x][y]False if dfs(memories[:], x, y,s[1:]): return True memories[x][y]True return False if path : return True memories [[True for c in range(cols)] for r in range(rows)] for r in range(rows): for c in range(cols): if matrix[r*colsc] path[0]: memories[r][c] False if dfs(memories[:],r,c,path[1:]): return True memories[r][c] True return False 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2949机器人的运动范围地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动每一次只能向左右上下四个方向移动一格但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如当k为18时机器人能够进入方格35,37因为3537 18。但是它不能进入方格35,38因为3538 19。请问该机器人能够达到多少个格子思考dfs记忆化搜索# -*- coding:utf-8 -*-class Solution: def movingCount(self, threshold, rows, cols): # write code here memories set() def dfs(i,j): def judge(i,j): return sum(map(int, list(str(i)))) sum(map(int, list(str(j)))) threshold if not judge(i,j) or (i,j) in memories: return memories.add((i,j)) if i ! rows - 1: dfs(i 1, j) if j ! cols - 1: dfs(i, j 1) dfs(0,0) return len(memories) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1750求123..n思考递归# -*- coding:utf-8 -*-class Solution: def Sum_Solution(self, n): # write code here if n 1: return 1 return nself.Sum_Solution(n-1) 1 2 3 4 5 651* 不用加减乘除做加法思考不计进位的和为 a^b进位就是 abab a^b (ab)1;这题python依旧有坑 public class Solution { public int Add(int a,int b) { int unit a ^ b; int carry_bit a b; while(carry_bit ! 0) { int temp_a unit; int temp_b carry_bit 1; unit temp_a ^ temp_b; carry_bit temp_a temp_b; } return unit; }} 1 2 3 4 5 6 7 8 9 10 11 12 1352二叉搜索树与双向链表思考左子树上最右结点 - root - 右子树上的最左结点class Solution: def Convert(self, pRootOfTree): # write code here if pRootOfTree None: return pRootOfTree if pRootOfTree.left None and pRootOfTree.right None: return pRootOfTree left self.Convert(pRootOfTree.left) p left if left: while(p.right): p p.right p.right pRootOfTree pRootOfTree.left p right self.Convert(pRootOfTree.right) if right: pRootOfTree.right right right.left pRootOfTree return left if left else pRootOfTree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1953复杂链表的复制输入一个复杂链表每个节点中有节点值以及两个指针一个指向下一个节点另一个特殊指针指向任意一个节点返回结果为复制后复杂链表的head。注意输出结果中请不要返回参数中的节点引用否则判题程序会直接返回空思考hashclass Solution: # 返回 RandomListNode def Clone(self, head): :type head: RandomListNode :rtype: RandomListNode if head None: return head node_dict {} node_dict[head] RandomListNode(head.label) tmp head while(head): random head.random nexthd head.next if random !None: if random not in node_dict: node_dict[random] RandomListNode(random.label) node_dict[head].random node_dict[random] if nexthd !None: if nexthd not in node_dict: node_dict[nexthd] RandomListNode(nexthd.label) node_dict[head].next node_dict[nexthd] head head.next return node_dict[tmp] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2654字符串的排列思考dfs# -*- coding:utf-8 -*-class Solution: def Permutation(self, ss): def dfs(s): if len(s) : return [] if len(s)1: return [s] if len(s)2: return list(set([s[0]s[1],s[1]s[0]])) ans set([]) left s[0] right dfs(s[1:]) for word in right: for i in range(len(word)1): ans.add(word[:i]leftword[i:]) return list(ans) if ss : return [] return sorted(dfs(ss)) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2055二进制中1的个数思考python没有无符号移动需要处理下# -*- coding:utf-8 -*-class Solution: def NumberOf1(self, n): # write code here ans 0 if n0: n n 0xffffffff while n: ans n 1 n 1 return ans 1 2 3 4 5 6 7 8 9 10 1156链表中倒数第k个结点思考两个指针p,q p先走k步class Solution: def FindKthToTail(self, head, k): # write code here p1 p2 head for i in range(k): if p1None: return None p1 p1.next while(p1): p2 p2.next p1 p1.next return p2 1 2 3 4 5 6 7 8 9 10 11 1257合并两个排序的链表class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here ret ListNode(0) tmp ret p1 pHead1 p2 pHead2 while(p1 and p2): if p1.valp2.val: tmp.next ListNode(p1.val) p1 p1.next else: tmp.next ListNode(p2.val) p2 p2.next tmp tmp.next if p1: tmp.next p1 if p2: tmp.next p2 return ret.next 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2158翻转链表class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here head None while(pHead): tmp ListNode(pHead.val) tmp.next head head tmp pHead pHead.next return head 1 2 3 4 5 6 7 8 9 10 11class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here if pHeadNone or pHead.next None: return pHead p self.ReverseList(pHead.next) pHead.next.next pHead pHead.next None return p 1 2 3 4 5 6 7 8 9 1059判断树B是否是树A的子结构class Solution: def HasSubtree(self, pRoot1, pRoot2): def subtree(pRoot1,pRoot2): if pRoot2 None and pRoot1 None: return True if pRoot2 None: return False if pRoot1 None: return False if pRoot2.val pRoot1.val: if pRoot2.left None and pRoot2.right None: return True if subtree(pRoot1.left,pRoot2.left) and subtree(pRoot1.right,pRoot2.right): return True return subtree(pRoot1.left,pRoot2) or subtree(pRoot1.right,pRoot2) if pRoot1 None and pRoot2 None: return False return subtree(pRoot1,pRoot2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1960* 数值的n次方思考109可以分解为10(1001,2)用二分class Solution: def Power(self, base, exponent): # write code here if exponent0: return 1 ans exp pos 1 if exponent0: pos,exponent -1,-exponent while(exponent): if exponent % 2: ans ans*(base**(exp)) exponent exponent1 exp exp*2 return ans if pos1 else 1.0/ans 1 2 3 4 5 6 7 8 9 10 11 12 13 1461调整数组顺序使奇数位于偶数前面# -*- coding:utf-8 -*-class Solution: def reOrderArray(self, array): size len(array) pos size-1 cnt 0 while(cntsize): if array[pos]%21: tmp array[pos] for i in range(pos-1,-1,-1): array[i1] array[i] array[0] tmp else: pos -1 cnt 1 return array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1662包含min函数的栈定义栈的数据结构请在该类型中实现一个能够得到栈最小元素的min函数。# -*- coding:utf-8 -*-class Solution: def __init__(self): initialize your data structure here. self.stack [] self.minstack [] def push(self, x): :type x: int :rtype: void self.stack.append(x) if len(self.minstack)0 or self.minstack[-1][0]x: self.minstack.append((x,1)) elif self.minstack[-1][0] x: self.minstack[-1] (x,self.minstack[-1][1]1) def pop(self): :rtype: void ans self.stack[-1] self.stack self.stack[0:len(self.stack)-1] if ans self.minstack[-1][0]: if self.minstack[-1][1] 1: self.minstack.remove(self.minstack[-1]) else: self.minstack[-1] (ans,self.minstack[-1][1]-1) def top(self): :rtype: int return self.stack[-1] def min(self): :rtype: int return self.minstack[-1][0] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4663二叉树中和为某一值的路径输入一颗二叉树和一个整数打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思考dfsclass Solution: # 返回二维列表内部每个列表表示找到的路径 def FindPath(self, root, expectNumber): # write code here ret [] def dfs(root,sum_,tmp): if root: if root.leftNone and root.right None: if root.val sum_: tmp.append(root.val) ret.append(tmp[:]) else: tmp.append(root.val) dfs(root.left,sum_-root.val,tmp[:]) dfs(root.right,sum_-root.val,tmp[:]) dfs(root,expectNumber,[]) return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1764从上往下打印二叉树思考bfsclass Solution: # 返回从上到下每个节点值列表例[1,2,3] def PrintFromTopToBottom(self, root): # write code here ret [] if root None: return ret bfs [root] while(bfs): tbfs [] for node in bfs: ret.append(node.val) if node.left: tbfs.append(node.left) if node.right: tbfs.append(node.right) bfs tbfs[:] return ret 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1865* 二叉搜索树的后序遍历序列输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思考后序遍历意味着num[-1]为root那么根据这个值和二叉搜索树的性质可以把数组划分成两个部分left 和 right 再递归判断# -*- coding:utf-8 -*-class Solution: def VerifySquenceOfBST(self, sequence): # write code here if len(sequence)0: return False root sequence[-1] i 0 for node in sequence[:-1]: if node root: break i 1 for node in sequence[i:-1]: if node root: return False left True if i 1: left self.VerifySquenceOfBST(sequence[:i]) right True if i len(sequence) - 2 and left: right self.VerifySquenceOfBST(sequence[i1:-1]) return left and right 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2566栈的压入、弹出序列# -*- coding:utf-8 -*-class Solution: def IsPopOrder(self, pushV, popV): # write code here stack [] while(popV): if pushV and pushV[0]popV[0]: pushV.pop(0) popV.pop(0) elif stack and stack[-1]popV[0]: stack.pop() popV.pop(0) elif pushV: stack.append(pushV.pop(0)) else: return False return True --------------------- 作者ep_mashiro 来源CSDN 原文https://blog.csdn.net/tinkle181129/article/details/79326023 版权声明本文为博主原创文章转载请附上博文链接转载于:https://www.cnblogs.com/fengff/p/10452817.html
