1 最小的K个数：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

分析：可以

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k): #最大堆效率最高
       # write code her
        tinput.sort()
        if k > len(tinput) or not tinput:
            return []
        return tinput[0:k]

先排序，再切片，似乎很简单。注意的是  1 排序要会手写   2 注意对异常值的处理 

但是时间复杂度还可以再优化，而且改变了原始数组的值。因此想到用容器来装最小的值，这就需要用最大堆实现。

python中有最小堆：heapq，因此考虑利用。

maxnum = []
        if k > len(tinput) or not tinput or k <= 0:
            return []
        for ele in tinput:
            ele = - ele
            if len(maxnum) <  k:
                heapq.heappush(maxnum, ele)
            else:
                heapq.heappushpop(maxnum,ele)
        res = map(lambda x: -x , maxnum)   #不能直接return .sort()
        res.sort()
        return res

要注意的有，对异常值的处理，要进行取负才能利用最小堆实现最大堆的功能，map的用法，lambdad的用法，sort不能直接return否则会报错。参考链接：https://www.cnblogs.com/cotyb/p/5205123.html

2 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：排序，找出出现次数最多的数字的次数，与K一半进行比较，从而确定结果

class Solution: #类似的，还有利用dict的解法
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        if len(numbers) == 1:
            return numbers[0]
        numbers.sort()
        res = []
        tmpmax = tmp = 1
        for i in range(len(numbers)):
            if numbers[i] in res:
                tmp = tmp + 1
                if tmp >= tmpmax:
                    tmpmax = tmp
                    nummax = numbers[i]
                else:
                    pass
            else:
                tmp = 1 
                res.append(numbers[i])
        if tmpmax > len(numbers)/2:
            return nummax
        else:
            return 0

想到可以用dict来统计每个数字出现的频率：

链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
来源：牛客网

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        dict = {}
        for no in numbers:
            if not dict.has_key(no):
                dict[no] = 1
            else:
                dict[no] = dict[no] + 1
            if dict[no] > len(numbers)/2:
                return no
        return 0

注意dict的用法

3 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

本地调试成功，牛客网运行失败的程序：


res = list(itertools.permutations(ss, len(ss)))
ressort = []
for i in res:
    ressort.append("".join(i))
    ressort.sort()
for j in ressort:
    print(j)

4 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:            #检测空
            return
        self.res = []                  #定义结果数组
        self.mid(pRootOfTree)          # 中序遍历数组
        for i,v in enumerate(self.res[:-1]): #调成双向链表的形式
            v.right = self.res[ i + 1 ]
            self.res[i+1].left = v
        return self.res[0]
            
    def mid(self,root):
        if not root:
            return
        self.mid(root.left)
        self.res.append(root)
        self.mid(root.right)

中序遍历，建立链表，牢记树的遍历的性质与写法

补充：

python中双引号单引号，三引号的用法； 

方法与函数的区别：

  1. 与类和实例无绑定关系的function都属于函数（function）
  2. 与类和实例有绑定关系的function都属于方法（method）
  3. python 自带排列组合函数 itertools，如import itertools print(list(itertools.permutations([1,2,3], 3))) 参考网址：https://blog.csdn.net/Deeven123/article/details/82970560
  4. 字符串与列表相互转换的方法 Join与split   参考链接：https://blog.csdn.net/roytao2/article/details/53433373
  5. 数组去重： https://www.cnblogs.com/zknublx/p/6042295.html
  6. xrange() 函数用法与 range 完全相同，所不同的是生成的不是一个数组，而是一个生成器。
  7. 一个不错的算法作者：https://blog.csdn.net/fuxuemingzhu
  8.  

    map() 会根据提供的函数对指定序列做映射。

    第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表

    map(function, iterable, ...)
  9. 用本地调试会方便很多，牛客网的编程界面无力吐槽。。