Posts

Kick Start 2019 Round A Training (7pts, 13pts) 一共有N个人，从中选P个人，计算这P个人中 skill rating 的最大值与其他人的 skill rating 的差值之和。 $$ \sum_{i}^{j} max(rating) - rating[i] $$ Solution: Sort + Prefix Sum 先对数组排序，然后在长度为N的有序数组中遍历长为P的所有连续子数组，计算子数组中的最大值与其他值的差值之和。 $$ \sum_{i}^{j - 1} rating[j] - rating[i] $$ 如果直接遍历长为P的子数组会浪费很多时间，可以将上面的公式简化为如下。 $$ \sum_{i}^{j - 1} rating[j] - rating[i] = rating[j] * (j - 1 - i) - \sum_{i}^{j - 1} rating[i] $$ 为了避免重复计算 $$ \sum_{i}^{j - 1} rating[i] $$，可以用一个长为N+1的数组将原始数组的前缀和保存下来，这样每次直接计算 prefix[j] - prefix[i] 就能得到 $$ \sum_{i}^{j - 1} rating[i] $$ 了，时间复杂度是O(N)。 ...

Methods to Prevent Overfitting in Deep Learning Overfitting Overfitting refers to that when a model fits the training data well but cannot predict the test data correctly, we may say that the model lacks the ability of generalization. It is important to figure out how it happens, and how we can prevent overfitting from the very beginning. Detect Overfitting The simplest way to detect overfitting is to split the dataset into two parts: the training set for training the model, and the test set for testing the accuracy of the model on a dataset that it has never seen before. Of course, we will also partition part of the training set to be the validation set for fine-tuning hyper-parameters. Note that it is necessary to shuffle all the data before splitting. ...

C++智能指针（3）：shared_ptr 分析 UniquePointer对象只能绑定单个指针，要实现指针的自动管理和销毁需要引入计数器 private: int *counter; T *pointer; D *deleter; 计数器的主要作用是标识当前指针被几个智能指针对象所引用，在析构当前对象时，使其计数器自减1。如果计数器等于0，则表示已经没有其他的对象在使用当前指针，此时则可以销毁指针，计数器和删除器。 template<typename T, typename D> void SharedPointer<T, D>::release() { if (pointer) { std::cout << "SharedPointer " << this << " counter remains " << *counter << std::endl; if (--(*counter) == 0) { std::cout << "SharedPointer " << this << " destructor called." << std::endl; (*deleter)(pointer); (*deleter)(counter); (*deleter)(deleter); pointer = nullptr; counter = nullptr; deleter = nullptr; } } } reset函数将指针设为other的指针 template<typename T, typename D> void SharedPointer<T, D>::reset(const SharedPointer<T, D> &other) { pointer = other.pointer; counter = other.counter; deleter = other.deleter; if (pointer) ++(*counter); } 析构函数可以直接调用release函数 ...

C++智能指针（2）：unique_ptr 分析 在使用 AutoPointer 的时候会发生所有权转移和内存泄漏的问题，所以我们可以对 AutoPointer 类稍加修改，修复这两个问题。 所有权转移 为了规避可能发生所有权转移的情况，我们可以直接禁止它使用拷贝构造函数和赋值操作符。 UniquePointer(UniquePointer<T> &other) = delete; UniquePointer<T> &operator=(const UniquePointer<T> &other) = delete; 但很多时候我们都需要使用到传递指针的操作，如果只是使用 deleted 函数禁止拷贝构造函数和赋值操作符，那么这个智能指针存在的意义就不大了，我们可以通过 move 语义来实现移动构造函数和移动赋值操作符，从而在使用 UniquePointer 的时候可以在特定情况下进行所有权转移。 UniquePointer(UniquePointer<T> &&other) noexcept; UniquePointer &operator=(UniquePointer &&other) noexcept; 内存泄漏 为了防止发生内存泄漏，我们可以在UniquePointer的私有成员中增加一个删除器，并根据当前指针对象的类型指定删除器，从而防止发生内存泄漏。 class Deleter { template<typename T> void operator()(T *p) { if (p) delete p; } }; template<typename T, typename D> class UniquePointer { ... private: T *pointer; Deleter deleter; }; 实现 根据unique_ptr的源码，能够大致实现UniquePointer类 template<typename T, typename D> class UniquePointer { public: explicit UniquePointer(T *t, const D &d); ~UniquePointer(); T &operator*(); T *operator->(); T *release(); void reset(T *p); UniquePointer(UniquePointer &&other) noexcept; UniquePointer &operator=(UniquePointer &&other) noexcept; UniquePointer(const UniquePointer &other) = delete; UniquePointer &operator=(const UniquePointer &other) = delete; private: T *pointer; D deleter; }; template<typename T, typename D> UniquePointer<T, D>::UniquePointer(T *t, const D &d) { std::cout << "UniquePointer " << this << " constructor called." << std::endl; this->pointer = t; this->deleter = d; } template<typename T, typename D> UniquePointer<T, D>::~UniquePointer() { std::cout << "UniquePointer " << this << " destructor called." << std::endl; deleter(this->pointer); } template<typename T, typename D> T &UniquePointer<T, D>::operator*() { return *this->pointer; } template<typename T, typename D> T *UniquePointer<T, D>::operator->() { return this->pointer; } template<typename T, typename D> T *UniquePointer<T, D>::release() { T *new_pointer = this->pointer; this->pointer = nullptr; return new_pointer; } template<typename T, typename D> void UniquePointer<T, D>::reset(T *p) { if (this->pointer != p) { deleter(this->pointer); this->pointer = p; } } template<typename T, typename D> UniquePointer<T, D>::UniquePointer(UniquePointer<T, D> &&other) noexcept { std::cout << "UniquePointer " << this << " move constructor called." << std::endl; this->pointer = other.release(); deleter(std::move(other.deleter)); } template<typename T, typename D> UniquePointer<T, D> &UniquePointer<T, D>::operator=(UniquePointer<T, D> &&other) noexcept { std::cout << "UniquePointer " << this << " assignment operator called." << std::endl; if (this->pointer != other.pointer) { reset(other.release()); deleter = std::move(other.deleter); } return *this; } 测试 尝试使用移动构造函数 ...

Cookie和Session 为了获取我们自己的提交记录，我们首先要进行登录的操作。但我们都知道HTTP是一种无状态的协议，它的每个请求都是独立的。无论是GET还是POST请求，都包含了处理当前这一条请求的所有信息，但它并不会涉及到状态的变化。因此，为了在无状态的HTTP协议上维护一个持久的状态，引入了Cookie和Session的概念，两者都是为了辨识用户相关信息而储存在内存或硬盘上的加密数据。 Cookie是由客户端浏览器维护的。客户端浏览器会在需要时把Cookie保存在内存中，当其再次向该域名相关的网站发出request时，浏览器会把url和Cookie一起作为request的一部分发送给服务器。服务器通过解析该Cookie来确认用户的状态，并对Cookie的内容作出相应的修改。一般来说，如果不设置过期时间，非持久Cookie会保存在内存中，浏览器关闭后就被删除了。 Session是由服务器维护的。当客户端第一次向服务器发出request后，服务器会为该客户端创建一个Session。当该客户端再次访问服务器时，服务器会根据该Session来获取相关信息。一般来说，服务器会为Seesion设置一个失效时间，当距离接收到客户端上一次发送request的时间超过这个失效时间后，服务器会主动删除Session。 两种方法都可以用来维护登录的状态。为了简便起见，本项目目前使用Session作为维护登录状态的方法。 获取数据 分析 首先我们进入登录页面，打开开发者工具，勾选Preserve log。为了知道在登录时浏览器向服务器提交了哪些数据，我们可以先输入一个错误的用户名和密码，便于抓包。 通过分析"login/“这条request，我们可以知道我们所需要的一些关键信息，例如headers中的user-agent和referer，表单数据（form data）中的csrfmiddlewaretoken，login和password。显然，user-agent和referer我们可以直接复制下来，login和password是我们填写的用户名和密码。还有一个很陌生的csrfmiddlewaretoken。这是CSRF的中间件token，CSRF是Cross-Site Request Forgery，相关知识可以查询跨站请求伪造的维基百科。那么现在我们就要分析这个token是从何而来。 获取csrfmiddlewaretoken 我们将刚才获取到的csrfmiddlewaretoken复制下来，在开发者工具中使用搜索功能，可以发现这个csrfmiddlewaretoken出现在了登录之前的一些request对应的response中。例如在刚才打开登录页面，发送GET请求时，response的headers的set-cookie中出现了"csrftoken=…“，而这里csrftoken的值与我们需要在登录表单中提交的值完全相同。因此，我们可以通过获取刚才的response中的Cookies来获取csrfmiddlewaretoken的值。 首先我们通过发送GET请求来分析一下Cookies的构成 login_url = "https://leetcode.com/accounts/login/" session = requests.session() result = session.get(login_url) print(result) print(type(result.cookies)) for cookie in result.cookies: print(type(cookie)) print(cookie) 得到的结果是 <Response [200]> 状态码200，表示请求成功 <class 'requests.cookies.RequestsCookieJar'> cookies的类型是CookieJar <class 'http.cookiejar.Cookie'> 第一条cookie的类型是Cookie <Cookie__cfduid=d3e02d4309b848f9369e21671fabbce571548041181 for .leetcode.com/> 第一条cookie的信息 <class 'http.cookiejar.Cookie'> 第二条cookie的类型是Cookie <Cookie csrftoken=13mQWE9tYN6g2IrlKY8oMLRc4VhVNoet4j328YdDapW2WC2nf93y5iCuzorovTDl for leetcode.com/> 第二条cookie的信息，也就是我们所需要的csrftoken 这样一来我们便获取到了在提交表单信息时所需要的csrfmiddlewaretoken，之后我们便可以开始着手写登录的相关代码了。顺便一提，在使用Django进行后端开发的时候自动生成的csrf token的键也叫csrfmiddlewaretoken，不知道LeetCode是不是用Django作为后端开发框架的。 实现 首先我们需要在爬虫开始运行之前获取登录信息，将Session作为类的成员变量保存下来，方便在获取submissions时使用。同时我们需要在与爬虫文件相同的目录下新建config.json，将自己的用户名和密码保存在该json文件里，这样就能顺利登陆了。 def start_requests(self): self.Login() # 登录 questionset_url = "https://leetcode.com/api/problems/all/" yield scrapy.Request(url=questionset_url, callback=self.ParseQuestionSet) def Login(self): login_url = "https://leetcode.com/accounts/login/" login_headers = { "user_agent": "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/71.0.3578.98 Safari/537.36'", "referer": "https://leetcode.com/accounts/login/", # "content-type": "multipart/form-data; boundary=----WebKitFormBoundary70YlQBtroATwu9Jx" } self.session = requests.session() result = self.session.get(login_url) file = open('./config.json', 'r') info = json.load(file) data = {"login": info["username"], "password": inf["password"], "csrfmiddlewaretoken": self.session.cookies['csrftoken']} self.session.post(login_url, data=data,headers=login_headers) print("login info: " + str(result)) 注意如果在headers中填写了content-type的值，可能会产生一些奇怪的错误信息，并且后续不能正确地获取自己的submissions，只需要user_agent和refere的信息即可。 ...