11-15题

11、和为S的连续正数序列
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
最笨的办法直接从头遍历，但是肯定还有更好的方法，上网查了一下，不得不说，数学真的很重要啊。
（链接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
来源：牛客网）
满足条件的n分两种情况：
n为奇数时，序列中间的数正好是序列的平均值，所以条件为：(n & 1) == 1 && sum % n == 0；
n为偶数时，序列中间两个数的平均值是序列的平均值，而这个平均值的小数部分为0.5，所以条件为：(sum % n) * 2 == n.
看了思路自己用代码实现：

class Solution:
    from math import sqrt
    def FindContinuousSequence(self, tsum):
        temp = []
        for n in range(2, int(sqrt(2*tsum))):
            if n % 2 == 1:
                if tsum % n == 0:
                    left = int(tsum/n) - int((n-1)/2)
                    right = int(tsum/n) + int((n-1)/2)
                    if left >= 1:
                        temp.append(list(range(left, right+1)))
            if n % 2 == 0:
                if int(0.5*n) == int(tsum%n):
                    left = int(tsum//n) - int(n/2) + 1
                    right = int(tsum//n) + int(n/2)
                    if left >= 1:
                        temp.append(list(range(left, right+1)))
        rst = sorted(temp, key=lambda x:x[0], reverse=False)
        return rst

12、左旋转字符串
对于一个给定的字符序列S，请你把其循环左移K位后的序列输出
这题比较简单，使用列表切片就可以了

class Solution:
    def LeftRotateString(self, s, n):
        if s == '':
            return s
        temp = int(n%len(s))
        return s[temp:] + s[:temp]

13、数字在排序数组中出现的次数
直接可以用python列表的count方法，或者用字典做，但是是个排序数组，可以联想到用二分查找

class Solution:
    def GetNumberOfK(self, data, k):
        left = 0
        right = len(data)
        while k != data[(left+right)//2]:
            if k > data[(left+right)//2]:
                left = (left+right)//2
            else:
                right = (left+right)//2
            if left==right and k!=data[(left+right)//2]:
                return 0
        temp = (left+right)//2
        rst = 0
        for i in range(temp, -1, -1):
            if data[i] == k:
                rst += 1
            else:
                break
        for i in range(temp+1, len(data)):
            if data[i] == k:
                rst += 1
            else:
                break
        return rst

14、数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
可以直接用字典或者用count函数。之前在leetcode中有一题类似，不过只有一个出现一次的数字。那么可以去重后求和的两倍减去原数组的和，但有两个数字的话就不行了

class Solution:
    def FindNumsAppearOnce(self, array):
        dic = {}
        for i in array:
            dic[i] = dic.get(i, 0) + 1

        rst = []
        for i in array:
            if dic[i] == 1:
                rst.append(i)

        return rst

15、翻转单词顺序列

class Solution:
    def ReverseSentence(self, s):
        temp = s.split(' ')
        rst = temp[::-1]
        return ' '.join(rst)