12. 数值的整数次方
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
return base ** exponent
13. 调整数组顺序使奇数位于偶数之前
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
a, b = [], []
for i in array:
if i % 2 == 1:
a.append(i)
else:
b.append(i)
return a+b
大佬的一行代码……
return sorted(array,key=lambda c:c%2,reverse=True)
#也可以写成下面这样
return sorted(a,key=lambda c:c%2!=1)
14. 链表中倒数第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
l=[]
while head!=None:
l.append(head)
head=head.next
if k>len(l) or k<1:
return
return l[-k]
好一点的就是用双指针，当第一个指针指向第K个节点的时候，第二个指针指向头结点，然后两个指针同时向后移动，当第一个节点指空的时候，第二个节点指向的就是倒数第K个元素
#本地运行测试
def FindKthToTail(head, k):
# write code here
cnt = 0
tail = head
node = head
while node:
node = node.next
if cnt >= k:
tail = tail.next
cnt += 1
return tail.val
15. 反转链表
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
bHead = None
while pHead:
cur = [pHead, pHead.next]
temp = bHead
pHead.next = bHead
bHead = cur[0]
pHead = cur[1]
return bHead
16. 合并连个排序的链表
很明显就是归并排序的归并部分
# -*- 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
result = pHead = ListNode(None)
while pHead1 and pHead2:
if pHead1.val<pHead2.val:
pHead.next, pHead1 = pHead1, pHead1.next
else:
pHead.next, pHead2 = pHead2, pHead2.next
pHead = pHead.next
pHead.next = pHead1 or pHead2
return result.next
17. 树的子结构
遍历 A树的各个节点与B树比较
需要注意如果A=B，B树的叶子节点为空时，A树可能不为空
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
return (self._is_eq(pRoot1, pRoot2) or
self.HasSubtree(pRoot1.left, pRoot2) or
self.HasSubtree(pRoot1.right, pRoot2))
def _is_eq(self, root1, root2):
if not root2:
return True
if not root1 or root1.val != root2.val:
return False
return (self._is_eq(root1.left, root2.left) and
self._is_eq(root1.right, root2.right))
18. 二叉树的镜像
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root:
root.left,root.right=root.right,root.left
self.Mirror(root.left)
self.Mirror(root.right)
19. 顺时针打印矩阵
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
while matrix:
res += matrix.pop(0)
if matrix and matrix[0]:
for row in matrix:
res.append(row.pop())
if matrix:
res += matrix.pop()[::-1]
if matrix and matrix[0]:
for row in matrix[::-1]:
res.append(row.pop(0))
return res
20. 包含min函数的栈
# -*- coding:utf-8 -*-
class Solution:
stack = []
MIN = []
def push(self, node):
# write code here
self.stack.append(node)
if len(self.stack)==1:
self.MIN.append(node)
elif self.MIN[-1]>node:
self.MIN.append(node)
def pop(self):
# write code here
if self.top() == self.MIN[-1]:
self.MIN.pop()
self.stack.pop()
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.MIN[-1]
21. 栈的压入、弹出序列
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
res = []
while True:
if res and popV[0] == res[-1]:
popV.pop(0)
res.pop()
elif pushV:
res.append(pushV.pop(0))
else:
break
if res:
return False
return True
22. 从上到下打印二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
l=[]
if not root:
return []
q=[root]
while len(q):
t=q.pop(0)
l.append(t.val)
if t.left:
q.append(t.left)
if t.right:
q.append(t.right)
return l
