11 、1的个数
~-9的计算步骤：
转二进制：1 1001
计算补码：1 0111
按位取反：0 1000
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
if n >= 0:
while n:
count += (n & 1)
n = (n >> 1)
else:
n = ~n
while n:
count += (n & 1)
n = (n >> 1)
count = 32 - count
return count
class Solution:
def NumberOf1(self, num):
# write code here
count = 0
if num < 0:
return 32 - self.NumberOf1(~num)
while num:
num = num & (num-1)
count += 1
return count
12、power(x, y)
class Solution:
def Power(self, base, exponent):
# write code here
if exponent == 0:
return 1
if exponent < 0:
temp = self.Power(base, -exponent)
return 1.0 / temp
temp = self.Power(base, exponent / 2)
if temp % 2:
return temp * temp * base
else:
return temp * temp
13、奇数位于偶数前面
基础
class Solution:
def reOrderArray(self, array):
# write code here
even, odd = [], []
for item in array:
if item % 2:
odd.append(item)
else:
even.append(item)
return odd + even
深入：
冒泡排序：
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
for i in range(0, len(array)):
for j in range(len(array)-1, i, -1):
if array[j-1] % 2 == 0 and array[j] % 2 == 1:
array[j], array[j-1] = array[j-1], array[j]
return array
14、链表倒数第k个值
class Solution:
def FindKthToTail(self, head, k):
# write code here
if head == None:
return None
dummy = ListNode(-1)
dummy.next = head
fast, slow = dummy, dummy
for _ in xrange(k):
fast = fast.next
if fast is None:
return None
while fast:
fast, slow = fast.next, slow.next
return slow
15、反转链表
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead is None or pHead.next is None:
return pHead
p, q = pHead, pHead.next
p.next = None
while q:
temp = q.next
q.next = p
p, q = q, temp
return p
16、合并两个排序链表
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
dummy = ListNode(-1)
head = dummy
while pHead1 or pHead2:
if pHead1 is None:
dummy.next = ListNode(pHead2.val)
pHead2, dummy = pHead2.next, dummy.next
continue
if pHead2 is None:
dummy.next = ListNode(pHead1.val)
pHead1, dummy = pHead1.next, dummy.next
continue
if pHead1.val < pHead2.val:
dummy.next = ListNode(pHead1.val)
pHead1, dummy = pHead1.next, dummy.next
else:
dummy.next = ListNode(pHead2.val)
pHead2, dummy = pHead2.next, dummy.next
return head.next
17、判断B树是不是A的子树
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if pRoot2 is None or pRoot1 is None:
return False
if pRoot2.val == pRoot1.val:
if self.issubtree(pRoot1,pRoot2):
return True
return self.HasSubtree(pRoot1.left, pRoot2) or \
self.HasSubtree(pRoot1.right, pRoot2)
def issubtree(self, root1, root2):
if root2 is None:
return True
if root1 is None and root2 is not None:
return False
if root1.val == root2.val:
return self.issubtree(root1.left, root2.left) and \
self.issubtree(root1.right, root2.right)
18、二叉树的镜像
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root is None:
return None
mirroot = TreeNode(root.val)
self.helper(root, mirroot)
return mirroot
def helper(self, root1, root2):
if root1.right:
root2.left = TreeNode(root1.right.val)
self.helper(root1.right, root2.left)
if root1.left:
root2.right = TreeNode(root1.left.val)
self.helper(root1.left, root2.right)
上面的方法一直不通过，题意是要在树本身的基础上进行修改。
class Solution1:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root is None:
return None
root.left, root.right = root.right, root.left
if root.right:
self.Mirror(root.right)
if root.left:
self.Mirror(root.left)
19、顺时针打印数组
20、包含min函数的栈
class Solution:
def __init__(self):
self.stack = []
self.stack2 = []
self.minim = float("inf")
def push(self, node):
# write code here
self.stack.append(node)
if node < self.minim:
self.minim = node
self.stack2.append(self.minim)
def pop(self):
# write code here
temp = self.stack.pop()
self.stack2.pop()
self.minim = self.stack2[len(self.stack2) - 1]
return temp
def top(self):
# write code here
return self.stack[len(self.stack)-1]
def min(self):
# write code here
return self.minim
21 栈的压入弹出序列
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
stack = []
i = 0
for item in pushV:
stack.append(item)
while stack and stack[-1] == popV[i]:
stack.pop()
i += 1
return stack == []
很容易绕到自己的小思维中，可以设置一个辅助栈，模拟入栈出栈过程。
22 从上往下打印二叉树
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
if root is None:
return []
current = [root]
res = []
while current:
nextlevel = []
for node in current:
res.append(node.val)
if node.left:
nextlevel.append(node.left)
if node.right:
nextlevel.append(node.right)
current = nextlevel
return res
23 是否是二叉搜索树的后序遍历
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if len(sequence) == 0:
return False
return self.helper(sequence)
def helper(self,sequence):
if len(sequence) == 0:
return True
point = sequence[-1]
i = 0
while sequence[i] < point:
i += 1
less, more = sequence[:i], sequence[i:-1]
if any(item < point for item in more):
return False
else:
return self.helper(less) and self.helper(more)
能独立写出来也是比较高兴，后序遍历的特点是最后一个元素是根节点，而二叉搜索树的特点是对于每一棵子树，左节点小于根节点，右节点大于根节点。因此，对一个序列，取出根节点（最后一个元素），则比根节点小的必定是左子树。然后递归遍历每一个子树。需要注意的是右子树序列是sequence[i:-1]，需要去掉根节点。
24 二叉搜索树中和为某一值得路径
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if root is None:
return []
self.res = []
self.helper(root, [], expectNumber)
return self.res
def helper(self, root, subres, number):
if number == root.val and root.left is None and root.right is None:
subres.append(root.val)
self.res.append(subres[:])
subres.pop()
return
if number < 0:
return
if root.left:
subres.append(root.val)
self.helper(root.left, subres, number-root.val)
subres.pop()
if root.right:
subres.append(root.val)
self.helper(root.right, subres, number - root.val)
subres.pop()
这个题用的回溯解，复杂度和内存肯定比较高，较好的解法是
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root: return []
if root.left is None and root.right is None:
if sum == root.val:
return [[root.val]]
else:
return []
a = self.pathSum(root.left, sum - root.val) + \
self.pathSum(root.right, sum - root.val)
return [[root.val] + i for i in a]
但这种解法比较难想。具体对比分析在 总结中。
25 复杂链表的复制
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
lookup = {}
current, dummy = pHead, RandomListNode(-1)
cHead = dummy
# 复制链表，只复制next
while current:
node = RandomListNode(current.label)
lookup[current] = node
cHead.next = node
cHead, current = node, current.next
# 复制random指针
cHead, current = dummy.next, pHead
while current:
# cHead.random = lookup[current.random]
cHead.random = lookup.get(current.random）
cHead, current = cHead.next, current.next
return dummy.next
上面cHead.random = lookup[current.random]是容易出现键值错误的，而get方法就可以实现安全操作，当不存在或为None会返回空。
可以进一步简化：
class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
dic = collections.defaultdict(lambda: RandomListNode(0))
dic[None] = None
n = head
while n:
dic[n].label = n.label
dic[n].next = dic[n.next]
dic[n].random = dic[n.random]
n = n.next
return dic[head]
26 二叉搜索树与双向链表
将一棵二叉搜索树转换为双向链表，自然而然想到的是中序遍历（递归），中序遍历比较简单，需要注意的是如何保存好第一个元素以供返回以及保存好上一个元素。
class Solution:
flag = 0
first = None
pre = None
def Convert(self, pRootOfTree):
# write code here
if pRootOfTree:
root = pRootOfTree
self.Convert(pRootOfTree.left)
if not self.flag:
self.first = root
self.pre = self.first
self.flag = 1
else:
self.pre.right = root
root.left = self.pre
self.pre = root
self.Convert(root.right)
return self.first
27、字符串的全排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if ss == '':
return []
self.res = set()
self.helper(list(ss), 0, len(ss))
return sorted(self.res)
def helper(self, s, start, end):
if start > end:
return
if start == end:
self.res.add(''.join(s))
else:
for i in range(start, end):
s[start], s[i] = s[i], s[start]
self.helper(s, start + 1, end)
s[start], s[i] = s[i], s[start]
import itertools
class Solution2:
def Permutation(self, ss):
# write code here
result = []
if not ss:
return []
else:
res = itertools.permutations(ss)
for i in res:
if "".join(i) not in result:
result.append("".join(i))
return result
28 、超过一半的数字
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
lookup = {}
length = len(numbers) / 2
for item in numbers:
if lookup.get(item):
lookup[item] += 1
if lookup[item] > length:
return item
else:
lookup[item] = 1
return 0
简化：
import collections
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
tmp = collections.Counter(numbers)
x = len(numbers)/2
for k, v in tmp.items():
if v > x:
return k
return 0
上面的空间复杂度是o(n)，也可以有o（1）的方案，维持两个变量，
https://blog.csdn.net/derrantcm/article/details/46736859
29、最小的k个数
这个题需要结合排序算法进一步总结。涉及到堆排序等知识。
http://www.cnblogs.com/felixfang/articles/3533890.html
30、连续子数组的最大和
动态规划求解，但只需要保存两个参数，一个是前一个元素位置的最大值，另一个是全局的最大值。
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
maxsum, pre_max = float('-inf'), 0
for item in array:
if pre_max <= 0:
pre_max = item
else:
pre_max += item
maxsum = max(pre_max, maxsum)
return maxsum
31、整数中1出现的次数
参考思路：https://blog.csdn.net/yi_afly/article/details/52012593
对一个数，如 523，首先判断个位上1出现的次数，52 + 1 = 53次，十位上是 5 * 10 + 10 = 60，（注意如果是 513，则是5 * 10 + 3 + 1 = 54)，百位上则是 100，如果是 123则是 23 + 1 = 24。总结下来，逐位判断，还要注意当前位是否是1。
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
res = 0
base = 1
temp = n
while n:
weight = n % 10
n /= 10
res += n * base
if weight > 1:
res += base
elif weight == 1:
res += temp % base + 1
base *= 10
return res
32、把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
一开始肯定就是想到全排列，然后逐个寻找，全排列需要好好理解。回溯算法的理解。
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if numbers == []:
return ''
numbers = map(str, numbers)
self.minnum = '9'
self.helper(numbers, 0)
return int(self.minnum)
def helper(self, numbers, index):
if index == len(numbers):
temp = ''.join(numbers)
if temp < self.minnum:
self.minnum = temp
return
for i in range(index, len(numbers)):
numbers[index], numbers[i] = numbers[i], numbers[index]
self.helper(numbers, index + 1)
numbers[index], numbers[i] = numbers[i], numbers[index]
上面的方法肯定不是最优，因为全部搜索了一遍。
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ""
lmb = lambda n1, n2:int(str(n1)+str(n2))-int(str(n2)+str(n1))
array = sorted(numbers, cmp=lmb)
return ''.join([str(i) for i in array])
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ""
num=map(str,numbers)
num.sort(lambda x,y:cmp(x+y,y+x))
return ''.join(num)
33、丑数
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index == 0:
return 0
res = [1 for _ in range(index)]
k2 = k3 = k5 = 0
for i in range(1, index):
res[i] = min(res[k2] * 2, res[k3] * 3, res[k5] * 5)
if res[i] == res[k2] * 2:
k2 += 1
if res[i] == res[k3] * 3:
k3 += 1
if res[i] == res[k5] * 5:
k5 += 1
return res[-1]
一开始写时不是三个if，容易写成if elif else结构，这种写法是错误的，因为会出现两个6， 23 = 32 = 6，为了避免这种情况，需要用三个if。
34、第一个出现一次的字符
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
count = [0 for _ in range(256)]
for char in s:
count[ord(char)] += 1
for i, char in enumerate(s):
if count[ord(char)] == 1:
return i
return -1
方法比较朴素，还没看别人的求解思路。上面的方法也是书中推荐的方法。
35、数组中逆序对
class Solution:
def InversePairs(self, data):
# write code here
self.count = 0
self.merge_sorted(data)
return self.count
def merge_sorted(self,nums):
if len(nums) == 1:
return nums
mid = len(nums) / 2
left = self.merge_sorted(nums[:mid])
right = self.merge_sorted(nums[mid:])
return self.sort(left, right)
def sort(self, left, right):
global count
m, n = len(left), len(right)
array = []
i, j = 0, 0
while i < m and j < n:
if left[i] <= right[j]:
array.append(left[i])
i += 1
else:
array.append(right[j])
j += 1
self.count += len(left) - i
array.extend(left[i:])
array.extend(right[j:])
return array
leetcode 315
36 两个链表的第一个公共节点
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
length1, length2 = 0, 0
p1, p2 = pHead1, pHead2
while p1:
length1 += 1
p1 = p1.next
while p2:
length2 += 1
p2 = p2.next
if length1 > length2:
while length2 < length1:
pHead1 = pHead1.next
length1 -= 1
else:
while length1 < length2:
pHead2 = pHead2.next
length2 -= 1
while pHead1 is not pHead2:
pHead1, pHead2 = pHead1.next, pHead2.next
return pHead1
主要思路是先统计数组长度，因为如果有公共节点，则公共节点之后的元素是相同的，如下图
image.png
上面链表长度是5，下面链表长度是4，则如果长度相同，即上面从2开始遍历，下面从4开始遍历，则就会同节奏找到公共节点6.
37、数字在排序数组中出现的次数
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if data == []:
return 0
first = self.getfirst(data,k)
last = self.getlast(data, k)
if first == -1 and last == -1:
return 0
if first == -1 or last == -1:
return 1
else:
return last - first + 1
def getfirst(self,data,k):
start, end = 0, len(data) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if data[mid] < k:
start = mid + 1
else:
end = mid
if data[start] == k:
return start
if data[end] == k:
return end
return -1
def getlast(self,data, k):
start, end = 0, len(data) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if data[mid] > k:
end = mid - 1
else:
start = mid
if data[end] == k:
return end
if data[start] == k:
return start
return -1
s = Solution()
print s.GetNumberOfK([1,2,3,5,5,5,7], 5)
40、数组中只出现一次的元素
一个数组，除了两个元素以外，其他元素都出现两次，求这两个元素。
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
sum = 0
for item in array:
sum ^= item
bitset = 1
while (sum & bitset) == 0:
bitset = (bitset << 1)
array1, array2 = [], []
for item in array:
if (item & bitset) == 0:
array1.append(item)
else:
array2.append(item)
num1, num2 = 0, 0
for a in array1:
num1 ^= a
for b in array2:
num2 ^= b
return num1, num2
如果说求只出现一次的单个元素，很好求，直接所有元素相异或，但是有两个不同，自然而然会想到如何分成两个不同数组，每个数组中包含一个不同，其他的都出现两次。
41、和为s的连续正整数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
这道题也算比较重要，两个指针的应用，不是很难，但是很多细节需要理清楚。
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
res = []
plow, phigh = 1, 2
while plow < phigh:
sum = (plow + phigh) * (phigh - plow + 1) >> 1
if sum < tsum:
phigh += 1
elif sum > tsum:
plow += 1
else:
temp = [item for item in range(plow,phigh+1)]
res.append(temp)
plow += 1
return res
42、和为s的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
start, end = 0, len(array) - 1
min_produce = float('inf')
num1, num2 = 0, 0
while start < end:
if array[start] + array[end] > tsum:
end -= 1
elif array[start] + array[end] < tsum:
start += 1
else:
if array[start] * array[end] < min_produce:
min_produce = array[start] * array[end]
num1, num2 = array[start], array[end]
end, start = end - 1, start + 1
return [] if num1 == num2 else [num1, num2]
43、左旋转字符串
class Solution:
def LeftRotateString(self, s, n):
# write code here
if s == '':
return ''
length = len(s)
n %= length
return s[n:] + s[:n]
48、不用加减乘除做加法
class Solution:
def Add(self, num1, num2):
# write code here
sum = num1 ^ num2
carry = (num1 & num2) << 1
while carry:
carry, sum = ((sum & carry) << 1), sum ^ carry
return sum
上面的方法超时了，但是思路没有问题，首先用异或，表示两数相加，不考虑进位。两数相与再左移一位，表示进位；上面两步的结果再相加，表示加上进位，但是可能还有进位，因此需要循环，直到进位为0，表示完成。
49、字符串转换为整数
class Solution:
def StrToInt(self, s):
# write code here
if s == '':
return 0
i, flag = 0, 1
while s[i] == ' ':
i += 1
if s[i] == '-':
flag = -1
i += 1
elif s[i] == '+':
i += 1
res = 0
for j in range(i,len(s)):
if s[j] not in '0123456789':
return 0
else:
res = res * 10 + ord(s[j]) - ord('0')
return flag * res
这道题leetcode上也有，算是比较熟悉了，要注意的地方有，1、去空格；2、注意正负号；3、考虑异常，主要有两个，一是输入为空，二是输入只有’-‘，所以用 if elif。
50、数组中重复的值
class Solution1:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
lookup = {}
for item in numbers:
if lookup.get(item):
duplication[0] = item
return True
else:
lookup[item] = 1
return False
51、构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
image.png
这道题比较关键的一点在于 不要重复计算，如果每行都从左到右计算，中间很多过程都是浪费的。
可以分为两个部分，分别为上三角和下三角计算。
class Solution:
def multiply(self, A):
# write code here
if len(A) < 2:
return A
length = len(A)
B = [1 for _ in range(length)]
tempB = [1 for _ in range(length)]
for i in xrange(1, length):
B[i] = B[i-1] * A[i-1]
for j in xrange(length-2, -1, -1):
tempB[j] = tempB[j+1] * A[j+1]
for i in xrange(length):
B[i] *= tempB[i]
return B
52、正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# write code here
if s is None:
return
return self.isMatch(s, 0, pattern, 0)
def isMatch(self, s, sp, pattern, pp):
if sp == len(s) and pp == len(pattern):
return True
if pp >= len(pattern):
return False
if pp < len(pattern) - 1 and pattern[pp+1] == '*':
if (sp < len(s) and s[sp] == pattern[pp]) or pattern[pp] == '.':
return self.isMatch(s, sp, pattern, pp+2) or \
self.isMatch(s, sp+1, pattern, pp+2) or \
self.isMatch(s, sp+1, pattern, pp)
else:
return self.isMatch(s, sp, pattern, pp + 2)
if sp >= len(s):
return False
if s[sp] == pattern[pp] or pattern[pp] == '.':
return self.isMatch(s, sp + 1, pattern, pp + 1)
return False
s = Solution()
print s.match('bcbbabab', '.*a*a')
上面大部分没有问题，但是会出现递归深度超出的限制，如上面的测试用例。
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# write code here
if len(s) == 0 and len(pattern) == 0:
return True
if len(s) > 0 and len(pattern) == 0:
return False
if len(pattern) > 1 and pattern[1] == '*':
if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
else:
return self.match(s, pattern[2:])
if len(s) > 0 and (pattern[0] == '.' or pattern[0] == s[0]):
return self.match(s[1:], pattern[1:])
return False
上面两个解法思路差不多，为什么性能相差这么多。
53、表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
class Solution1:
# s字符串
def isNumeric(self, s):
# write code here
self.flag1, self.flag2 = 0, 0
start = 0
if s[0] in '+-':
start += 1
while start < len(s):
if s[start] in '+-' and s[start-1] in 'eE':
start += 1
if s[start] in '1234567890':
start += 1
elif s[start] in 'eE':
if self.flag1 == 1:
return False
else:
self.flag1 = 1
start += 1
elif s[start] == '.' and start > 0 and s[start-1] in '+-1234567890':
if self.flag2 == 1 or self.flag1 == 1:
return False
else:
self.flag2 = 1
start += 1
else:
return False
if s[-1] in 'eE.+-':
return False
return True
调用内置函数：
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
try :
p = float(s)
return True
except:
return False
54、删除链表中重复的节点
class Solution1:
def deleteDuplication(self, pHead):
# write code here
if pHead is None or pHead.next is None:
return pHead
dummy = ListNode(-1)
dummy.next = pHead
pre, head = dummy, dummy
while pHead and pHead.next:
if pHead.val != pHead.next.val:
pHead = pHead.next
pre = pre.next
else:
while pHead and pHead.next and pHead.val == pHead.next.val:
pHead = pHead.next
pHead = pHead.next
pre.next = pHead
return dummy.next
这个题要注意的是重复的元素都删除，不用保留一个。
55、二叉树的下一个节点
寻找二叉树的下一个节点。
class Solution:
def GetNext(self, pNode):
# write code here
if pNode is None:
return None
if pNode.right:
temp = pNode.right
while temp.left:
temp = temp.left
return temp
temp = pNode
while temp.next and temp != temp.next.left:
temp = temp.next
return temp.next
class Solution1:
def GetNext(self, pNode):
# write code here
if pNode is None:
return None
if pNode.right:
temp = pNode.right
while temp.left:
temp = temp.left
return temp
temp = pNode
while temp.next:
if temp is temp.next.left:
return temp.next
temp = temp.next
return temp.next
56、对称二叉树
class Solution:
def isSymmetrical(self, pRoot):
# write code here
if pRoot is None:
return True
return self.helper(pRoot.left, pRoot.right)
def helper(self, root1, root2):
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
return root1.val == root2.val and self.helper(root1.left, root2.right) and \
self.helper(root1.right, root2.left)
57、之字形打印二叉树
class Solution:
def Print(self, pRoot):
# write code here
if pRoot is None:
return []
current = [pRoot]
flag = 1
res = []
while current:
nextlevel, subres = [], []
for node in current:
subres.append(node.val)
if node.left:
nextlevel.append(node.left)
if node.right:
nextlevel.append(node.right)
current = nextlevel
res.append(subres if flag else subres[::-1])
flag = 1 if flag == 0 else 0
return res
58、二叉树打印多行
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if pRoot is None:
return []
current = [pRoot]
res = []
while current:
nextlevel, subres = [], []
for node in current:
subres.append(node.val)
if node.left:
nextlevel.append(node.left)
if node.right:
nextlevel.append(node.right)
current = nextlevel
res.append(subres)
return res
59、序列化和反序列化二叉树
class Solution:
def Serialize(self, root):
# write code here
self.pre = []
self.inorder = []
self.preFunc(root)
self.inorderFunc(root)
return (self.pre, self.inorder)
def preFunc(self,root):
if root:
self.pre.append(root.val)
self.preFunc(root.left)
self.preFunc(root.right)
def inorderFunc(self, root):
if root:
self.inorderFunc(root.left)
self.inorder.append(root.val)
self.inorderFunc(root.right)
def Deserialize(self, s):
# write code here
preorder, inorder = s[0], s[1]
return self.buildTree(preorder, inorder)
def buildTree(self,preorder, inorder):
if inorder:
index = inorder.index(preorder[0])
del preorder[0]
node = TreeNode(inorder[index])
node.left = self.buildTree(preorder, inorder[:index])
node.right = self.buildTree(preorder, inorder[index+1:])
return node
最先想到的是最简单的由中序和前序遍历构造二叉树，其实还可以用自己特有的方式。
60、二叉搜索树的第k个节点
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if k <= 0:
return
self.pre = []
self.preorder(pRoot)
if k > len(self.pre):
return
return self.pre[k-1]
def preorder(self, root):
if root:
self.preorder(root.left)
self.pre.append(root)
self.preorder(root.right)
上面是最基本的方法，先中序遍历，然后取第k个元素。但其实有很多操作都是无用。
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if k <= 0:
return
self.count, self.node = k, None
self.preorder(pRoot)
return self.node
def preorder(self, root):
if root and self.count:
self.preorder(root.left)
self.count -= 1
if self.count == 0:
self.node = root
self.preorder(root.right)
上面的方法则不用全部遍历，但最终运行时间和空间消耗都不如第一种方法。可能大数据集适用。
61、数据流中的中位数
class Solution:
sort_list = []
length = 0
def Insert(self, num):
self.sort_list.append(num)
self.sort_list.sort()
self.length += 1
def GetMedian(self,data):
# write code here
if self.length % 2:
return self.sort_list[self.length//2]
else:
return self.sort_list[self.length//2] * 0.5 + self.sort_list[self.length//2-1] * 0.5
s = Solution()
for item in [3, 4, 5, 72, 6, 2]:
s.Insert1(item)
print s.sort_list
备注：
如何往一个有序的列表中插入数值。
def Insert1(self, num):
# write code here
start, end = 0, self.length - 1
while start < end:
mid = start + (end - start) >> 1
if self.sort_list[mid] > num:
end = mid
else:
start = mid + 1
self.sort_list.insert(start, num)
self.length += 1
网友评论