最近的请求次数

题目内容

计算每个事件发生之时，往前算10000毫秒内有多少个事件发生，包含当事件；也即对于列表中的每个元素k，算出整个列表中有多少个元素介于k-10000和k（两端均含）之间。

输入样例

[0,10,100,1000,10000,20000,100000]

输出样例

[1,2,3,4,5,2,1]

---

代码

'''
最近的请求次数
'''

'''
类的实现
'''
class node:  # 这里不用加括号，具体参数都在init函数里，这也是和函数区别的一部分，函数的升级和高级有序集合
    def __init__(self, val, n):  # 传入参数的名字
        self.data = val
        self.next = None  # 类的某个元素的名字
        self.num = n  # 每个节点的默认节点都是指向空的
    def getData(self):
        return self.data
    
    def getnext(self):
        return self.next

    def getnum(self):
        return self.num

    def setData(self, newData):
        self.data = newData

    def setNext(self, newNext):
        self.next = newNext


class orderedList:  # 只存储表头的信息
    def __init__(self):
        self.head = None  # 注意这里是大写
    
    
    def size(self):
        count = 0
        p = self.head
        while p != None:
            count = count + 1
            p = p.getnext()
        return count
    
    def search(self, content, bos):
        p = self.head
        previous = None
        found = False  # 大写！！有了found这个较为特殊的变量时，代码更加易读清晰
        stop = False
        i = self.size() - 1
        while i >= bos and p != None:  # 保证从起始节点的下一个节点开始搜索，而不是从头开始
            previous = p
            p = p.getnext()
            i = i - 1
        while p != None and not found and not stop:  # 分类讨论
            if p.getData() == content:  # 如果相等，直接返回当前节点的序号
                return p.getnum()
            else:
                if p.getData() < content:  # 如果当前节点数据较小，那就返回之前节点的
                    stop = True  # 那么found肯定等于False， 这样写代码更加易读
                else:  # 大就继续移动
                    previous = p
                    p = p.getnext()
        if previous == None:
            return p.getnum()
        else:
            return previous.getnum()
        return found

     
def nor(mylist):  # num of request
    Mylist = orderedList()
    count = 0
    l1 = []
    l2 = []
    for each in mylist:
        newNode = node(each, count)
        newNode.setNext(Mylist.head)
        Mylist.head = newNode  # 这里老是容易搞混
        count = count + 1
    p = Mylist.head
    while p != None:
        temp = p.getData() - 10000
        n = Mylist.search(temp, p.getnum())
        dif = p.getnum() - n + 1
        l1.append(dif)
        p = p.getnext()
    length = len(l1)
    for i in range(length):
        l2.append(l1.pop())  # append方法需要参数 
    return l2

mylist = eval(input())
print(nor(mylist))  

备注

关键是搜索的时候讨论好各种情况