31、两个链表的第一个公共节点
之前在leetcode上刷到过，刷的时候不会做，后来参考了别人的写法，把其中一个链表的尾节点指向另一个链表的头节点，这样就转化成了求一个环形链表的入环节点。但是后来看了下最快的办法，真的是又快又简洁，在这里贴上代码：
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p1, p2 = headA, headB
while(p1 != p2):
p1 = headB if p1 == None else p1.next
p2 = headA if p2 == None else p2.next
return p1
32、第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写。
能想到的只有遍历两遍，第一遍用字典计数，第二遍找第一个只出现一次的字符。
class Solution:
def FirstNotRepeatingChar(self, s):
dic = {}
for i in s:
print(i)
dic[i] = dic.get(i, 0) + 1
for i in s:
if dic[i] == 1:
return i
else:
return -1
33、数据中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
我想到的是递归求逆序对的个数，递归的时候可以像求斐波那契数列一样用动态规划优化一下。但是想想其实跟直接遍历的时间复杂度是一样的。看了下别人的答案，用了归并排序之类的，关于排序算法之前没仔细看过，只知道冒泡、选择、插入算法。刷完剑指offer再去详细了解一下，先马住。贴上自己写的递归版答案
class Solution:
def InversePairs(self, data):
# write code here
memory = [0]
def getnumsofpairs(data):
for i in range(1, len(data)):
count = 0
for j in range(i):
if data[j] > data[i]:
count += 1
memory.append(memory[i-1]+count)
return memory[-1]
return getnumsofpairs(data)%1000000007
34、连续子数组最大和
这题也在leetcode中刷过
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
all_max = nums[0]
cur = 0
for i in nums:
cur = max(cur+i, i)
all_max = max(all_max, cur)
return all_max
35、最小的k个数
最笨的办法就是写个排序。思考了一下如何优化，可以用一个列表先储存前k个数，然后对剩下的数开始遍历，如果小于列表的最大值，那么列表的最大值替换为k。看了下别人的答案，思路是一样的，但是是用最大堆来储存k个数，我还不知道堆是什么😔，之前了解了一点排序算法，有个最大堆排序没仔细看，待会去看一下。先把列表的答案贴上。
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
temp = tinput[:k]
for i in tinput[k:]:
if i < max(temp):
temp[temp.index(max(temp))] = i
return temp
