牛客网上的题总结下 python解法
1.二维数组的查找
描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
class Solution: # array 二维列表 def Find(self, target, array): # write code here row = 0 flag = False col = 0 while row < len(array) and array[0] !=[]: if target == array[row][col]: flag = True break elif target > array[row][col]: kk = len(array[0])-1-col for i in range(kk): if target > array[row][col+1]: col = col+1 elif target < array[row][col+1]: break else: flag = True break else: kk = col for i in range(kk): if target < array[row][col-1]: col = col-1 elif target > array[row][col-1]: break else: flag = True break row = row+1 return flag2.请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
# -*- coding:utf-8 -*- class Solution: # s 源字符串 def replaceSpace(self, s): # write code here res = '' for i in range(len(s)): if s[i] == ' ': res = res+'%20' else: res = res+s[i] return res3.输入一个链表,从尾到头打印链表每个节点的值。
# -*- 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 a =[] p = listNode #注意这里可能一开始为None,直接while判断即可 while p : a.append(p.val ) #这里直接用a.insert(0 ,p.val)会更方便 p = p.next b = a[:] for i in range(len(a)): b[i] = a[-1-i] return b4.牛牛从生物科研工作者那里获得一段字符串数据s,牛牛需要帮助科研工作者从中找出最长的DNA序列。DNA序列指的是序列中只包括'A','T','C','G'。牛牛觉得这个问题太简单了,就把问题交给你来解决。
例如: s = "ABCBOATER"中包含最长的DNA片段是"AT",所以最长的长度是2
输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),字符串中只包括大写字母('A'~'Z')。
输出一个整数,表示最长的DNA片段
输入:ABCBOATER
输出:2
def getMaxLen(strDna): outList = [] lists = ('A','T','C','G') maxLen = 0 while len(strDna) > 0: idx = len(strDna) for i in range( len(strDna) ): if strDna[i] in lists: idx = i break if idx == len(strDna): break cout = 1 while idx+1 < len(strDna) and ( strDna[idx+1] in lists): cout += 1 idx += 1 if cout > maxLen: maxLen = cout if idx+1 >= len(strDna): break strDna = strDna[(idx+1) : ] return maxLen strr = raw_input() print getMaxLen( strr )5.把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
# -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if len(rotateArray) == 0: return 0 for i in range( len(rotateArray)-1 ): if rotateArray[i+1] < rotateArray[i]: out = rotateArray[i+1] break return out6.用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型
# -*- coding:utf-8 -*- class Solution: stack1 = [] stack2 = [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if len(self.stack2) != 0: return self.stack2.pop() while len(self.stack1) != 0: self.stack2.append(self.stack1.pop()) return self.stack2.pop()7.大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
n<=39
# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): # write code here if n == 0: return 0 elif n == 1: return 1 else: lists = [0,1] while len(lists) <= n: lists.append( lists[-1]+lists[-2]) return lists[-1]8.
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
# -*- 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 or len(tin) == 0: return None elif len(pre) == 1: return TreeNode(pre[0]) else: tt = TreeNode(pre[0]) tt.left = self.reConstructBinaryTree( pre[1: tin.index(pre[0])+1] , tin[0:tin.index(pre[0])]) tt.right = self.reConstructBinaryTree( pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1 : ] ) return tt同样,如果依据 中序和后序重建二叉树,则可以以以下的方式判断
9.一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?
ans:第n级的跳法来自第n-1级跳1 和 第n-2级跳2,故依然可用斐波那契数列的方法f( n ) = f( n-1 ) + f(n-2)
# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, number): # write code here lists = [1,2] if number <= 0: return 0 elif number == 1: return 1 elif number == 2: return 2 else: while number > 2: lists.append(lists[-1]+lists[-2]) number = number - 1 return lists[-1]10.一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
ans: 第n级别的跳法其实来自前面全部 1,2,... ,n-1级的跳法 的和 加 1
# -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, number): # write code here lists = [1,2] if number <= 0: return 0 elif number == 1: return 1 elif number == 2: return 2 else: while number > 2: lists.append(sum(lists) +1) number = number - 1 return lists[-1]11.我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
ans: 思路跟第9 题 青蛙跳台阶一样
# -*- coding:utf-8 -*- class Solution: def rectCover(self, number): # write code here lists = [1,2] if number <= 0: return 0 elif number == 1: return 1 elif number == 2: return 2 else: while number > 2: lists.append(lists[-1]+lists[-2]) number = number - 1 return lists[-1]12.输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
ans: 如果是正数或者0的话很容易转换,如果为负数,若为-2^31,则显然2^31二进制码为100……0,反码为(1)11……1,(1)为正负表示,再加上1,就变成(1)00,……0;实际补 码的表示下-2^31 ~ 2^31-1 , 也即(1)00,……0 ~ (0)11,……1 ;如果为负数且绝对值为奇数,则显然反码为 (1)cc,……c0,加上1,则1的个数要增加1位 ;如果为偶数则不存在问题
# -*- coding:utf-8 -*- class Solution: def NumberOf1(self, n): # write code here count = 0 absn = abs(n) while absn > 0: if absn % 2 != 0: count += 1 absn = absn /2 if n < 0: if n == pow(-2 ,31): count = 1 else: if abs(n) % 2 == 0: count = 32 - count else: count = 32 - count +1 return count13.给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方
# -*- coding:utf-8 -*- class Solution: def Power(self, base, exponent): # write code here if base == 0 and exponent != 0 : return 0 elif base == 0 and exponent == 0 : return None elif exponent == 0: return 1 else: out = float(1) #python 只有float型 absExp = abs(exponent ) while absExp > 0 : out = out * base absExp = absExp -1 if exponent < 0: out = 1./out return out14.输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
# -*- coding:utf-8 -*- class Solution: def reOrderArray(self, array): # write code here res_ou = [] res_ji = [] for i in range( len(array) ): if array[i] %2 == 0: res_ou.append(array[i] ) else: res_ji.append( array[i] ) res_ji.extend(res_ou ) return res_ji15.输入一个链表,输出该链表中倒数第k个结点。
ans: 关键是要判断好 链表为空 , 题意中k值一定为正数,k值不能比链表长度大
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindKthToTail(self, head , k ): # write code here if head == None or k == 0: return None tail = head lens = 1 while tail.next != None: tail = tail.next lens = lens +1 if lens - k < 0: return None nodeK = head for i in range((lens - k )): nodeK = nodeK.next return nodeK16.输入一个链表,反转链表后,输出链表的所有元素。
ans: 循环的形式,从头到尾 相邻的两个节点进行反转
# -*- 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 res = [] p = listNode if p == None: return res q = p.next p.next = None while q != None: temp = q.next q.next = p p = q q = temp while p != None: res.append(p.val) p = p.next return res
17.输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
ans: 重新构造链表的重点在于 一个变量链表头,另一个变量同样引用这个链表头,然后使用改变量去增加链表的节点
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here if pHead1 == None: return pHead2 if pHead2 == None: return pHead1 new = ListNode(0) p1 = pHead1 p2 = pHead2 p3 = new while p1 != None and p2 != None: if p1.val <= p2.val: p3.next = p1 p1 = p1.next else: p3.next = p2 p2 = p2.next p3 = p3.next else: if p1 != None: p3.next = p1 else: p3.next = p2 return new.next
18.输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
ans: 这里需要用到2个递归调用,一个是同个节点开始判断是否一样,一个是循环分别到左节点和右节点 和 二叉树B做判断
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def checkNext(self , topRoot1 ,root2 ): if root2 == None: return True if topRoot1 == None: return False if topRoot1.val != root2.val: return False return self.checkNext( topRoot1.left , root2.left ) and self.checkNext(topRoot1.right,root2.right) def HasSubtree(self, pRoot1, pRoot2): # write code here res = False if pRoot1 != None and pRoot2 != None: if pRoot1.val == pRoot2.val: res = self.checkNext(pRoot1 , pRoot2 ) if not res: res = self.HasSubtree(pRoot1.left , pRoot2 ) if not res: res = self.HasSubtree(pRoot1.right , pRoot2 ) return res19.操作给定的二叉树,将其变换为源二叉树的镜像
ans:一定要用swap才能交换
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回镜像树的根节点 flag = True res = 0 def swap(self , root): temp=root.left root.left=root.right root.right=temp def Mirror(self, root): # write code here if root==None: return root else: self.swap(root) self.Mirror(root.left) self.Mirror(root.right) return root20.输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 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.
ans:外围分析法
# -*- coding:utf-8 -*- class Solution: # matrix类型为二维列表,需要返回列表 def getOuter(self ,mat, m_1 , m_2 , n_1 , n_2): out = [] for i in range((n_2-n_1)): out.append(mat[m_1][n_1+i ]) for j in range((m_2-m_1)): out.append(mat[m_1+j ][n_2 ]) for i in range((n_2-n_1)): out.append(mat[m_2 ][n_2-i ]) for j in range(( m_2-m_1 )): out.append(mat[m_2 - j ][ n_1 ]) return out def printMatrix(self, matrix): # write code here res = [] if len( matrix ) <= 1: return matrix[0] if len( matrix[0] ) <= 1: for i in range( len( matrix ) ): res.extend(matrix[i]) return res M = len( matrix ) N = len( matrix[0] ) m_1 = 0 m_2 = M-1 n_1 = 0 n_2 = N-1 while True: temp = self.getOuter(matrix, m_1 , m_2 , n_1 , n_2 ) res.extend(temp) m_1 += 1 m_2 -= 1 n_1 += 1 n_2 -= 1 if m_1 == m_2 and m_2 == n_1 and n_1 == n_2: res.append(matrix[m_1][n_1] ) break if m_1 == m_2 and n_1 != n_2: for i in range((n_2-n_1+1 )): res.append(matrix[m_1][n_1+i] ) break if m_1 > m_2 or n_1 > n_2: break return res21. 反转单向链表,反转方式为2 ->1 -> 5 -> 6 -> 7 变为 1 -> 2 -> 6 -> 5 -> 7
class ListNode: def __init__(self , x ): self.val = x self.next = None def solver( Li , n ): new = ListNode(0 ) newPtr = new while Li != None: v1 = Li.val if Li.next != None: v2 = Li.next.val newPtr.next = ListNode( v2 ) newPtr = newPtr.next newPtr.next = ListNode(v1 ) newPtr = newPtr.next Li = (Li.next).next else: newPtr.next = ListNode(v1) break return new.next if __name__=='__main__': data = [ 2 ,1 ,5 ,6 ,7 ]; inNode = ListNode( data[0] ) ptr = inNode for i in range(len(data) -1 ): ptr.next = ListNode( data[i+1] ) ptr = ptr.next outNode = solver( inNode , len(data) ) for i in range( len(data) ): print outNode.val , outNode = outNode.next
更多相关文章
- Python根据第一项从2d数组中删除元素
- linux中awk数组应用域替换
- 文本文件到字符串数组?
- 将现有数组中的所有元素传递给xargs
- Linux利用i节点删除乱码文件
- postgresql 数组 多了引号 空格处理
- MySQL Cluster在线添加数据节点
- PB怎么将动态的sql语句以及数组。传给datawindow。
- PostgreSQL: array 数组类型添加元素 数组的使用