34. 第一个只出现一次的字符
python3.6可运行
在python3.5及以下版本中字典是乱序的
def FirstNotRepeatingChar(self, s):
res = {}
for i, v in enumerate(s):
res[v] = (res.get(v, (0, i))[0] + 1, i)
for v in res.values():
if v[0] == 1:
return v[1]
else:
return -1
修改后
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if not s:
return -1
res = {}
for i, v in enumerate(s):
if v not in res:
res[v] = i
else:
res[v] = -1
min_index=[]
for k,v in res.items():
if v != -1:
min_index.append(v)
return min(min_index)
35.数组中的逆序对
直观的遍历数组每一项，再与其后面的数作比较
但是很明显时间复杂度为O(n^2)提交直接报超时了
def InversePairs(self, data):
# write code here
n = 0
length = len(data)
for i in range(length):
for j in range(i+1,length):
if data[i] > data[j]:
n += 1
return n%1000000007
改进后的方法，首先拷贝一份源数组，对拷贝数组排序，然后从最小数开始查看其在源数组的索引位置，可以看出索引左边的数与当前最小数都成逆序对，索引数就是逆序对数，记录下来。然后删除当前最小数，重复查看即可
时间复杂度为n(logn)
牛客网关于这道题使用python通不过……
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
sortData = sorted(data)
count = 0
for i in sortData:
pos = data.index(i)
count += pos
data.pop(pos)
return count
def quick_sort(self, data):
if len(data) < 2:
return data
left = self.quick_sort([i for i in data[1:] if i <= data[0]])
right = self.quick_sort([j for j in data[1:] if j > data[0]])
return left + [data[0]] + right
36. 两个链表的第一个公共结点
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, head1, head2):
# write code here
list1 = []
list2 = []
node1 = head1
node2 = head2
while node1:
list1.append(node1.val)
node1 = node1.next
while node2:
if node2.val in list1:
return node2
else:
node2 = node2.next
37. 统计一个数字在排序数组中出现的次数
用list.count()很简单
不过看见有序数组还是用二分查找吧
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
def BiSearch(data, k):
L = len(data)
if L == 0:
return 0
if L == 1 and data[0] == k:
return 1
mid = L >> 1
if data[mid] == k:
return 1 + BiSearch(data[:mid],k) + BiSearch(data[mid+1:],k)
elif data[mid] < k:
return BiSearch(data[mid+1:],k)
elif data[mid] > k:
return BiSearch(data[:mid],k)
return BiSearch(data,k)
38.二叉树的深度
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot == None:
return 0
nLeft = self.TreeDepth(pRoot.left)
nRight = self.TreeDepth(pRoot.right)
return (nLeft+1 if nLeft > nRight else nRight +1)
39. 平衡二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
if not pRoot:
return True
l = r = 0
lRoot = pRoot.left
rRoot = pRoot.right
while lRoot:
l+=1
lRoot=lRoot.left
while rRoot:
r+=1
rRoot=rRoot.right
if l==r:
return True
40. 数组只出现一次的数字
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
#tmp = set()
tmp = []
for a in array:
if a in tmp:
tmp.remove(a)
else:
tmp.append(a)
return tmp
41. 和为S的连续正数序列
双指针
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
l_num = [i for i in range(1, tsum + 1)]
start = 0
end = 2
res = []
while end - start >= 2 and end < tsum:
a = sum(l_num[start:end])
if a < tsum:
end += 1
elif a > tsum:
start += 1
else:
res.append(l_num[start:end])
start += 1
return res
42. 和为S的两个数
还是用双指针，因为是递增数列，所以指针从两边取
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
start = 0
end = len(array)-1
while end - start >=2:
if array[start]+array[end] > tsum:
end -= 1
elif array[start]+array[end] < tsum:
start += 1
else:
return [array[start],array[end]]
return[]
43. 左旋转字符串
# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
# write code here
return s[n:]+s[:n]
可以用切片做，更科学的是使用多次翻转
# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
if not s: return s
s = list(s)
self.reverse(s, 0, n - 1)
self.reverse(s, n, len(s) - 1)
self.reverse(s, 0, len(s) - 1)
return ''.join(s)
def reverse(self, s, start, end):
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
44. 翻转单词顺序列
# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
if not s.strip():
return s
res = " ".join(reversed(s.split()))
return res
