31-35

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