好久没来更新了，从上次更新到现在忙了很多事情，而且忙了半天也不知道自己忙了些啥，很丧。做的为数不多的比较扎实的事情就是仿照着GitHub上的开源项目写了一个WebServer，目前已经完成了一个可以传输静态页面的Demo，还需要优化以及添加一些别的功能。先记录一下，免得以后忘了。

基本框架

程序采用的是“半同步半反应堆式”的线程池，也就是：

• 主线程负责监听文件描述符上发生的事件，并针对事件进行IO。

• 子线程负责处理逻辑，解析收到的HTTP报文，准备好要发送的数据，并通知主线程可以进行IO了。

具体实现时，程序分为了若干个模块：线程同步模块、日志模块、MySQL连接池模块、HTTP处理模块、mmap模块、线程池模块、epoll监听模块。

线程同步

是整个项目最简单的一部分，也是上手完成的第一个部分，就是把Linux底层提供的一些线程同步机制进行了封装，使用的时候会更加方便一些。把init()和destroy()分别写进了构造函数和析构函数，随取随用，让代码更加简洁，应该也属于所谓的RAII机制。

RAII机制：资源获取就是初始化（Resource Acquisition Is Initialization），这是一种管理资源的方式，C++保证任何情况下，已构造的对象最终都会销毁，即它的析构函数一定会被调用。所以只要把资源的获取和释放分别封装进一个类的构造函数和析构函数，就可以保证资源不会发生“泄露”。

声明：

互斥量

1
2
3
4
5
6
7
8
9
10
11

class locker
{
private:
    pthread_mutex_t mutex;
public:
    locker();
    ~locker();
    bool lock();
    bool unlock();
    pthread_mutex_t* get();
};

条件变量

1
2
3
4
5
6
7
8
9
10
11

class cond
{
private:
    pthread_cond_t m_cond;
public:
    cond();
    ~cond();
    bool wait(pthread_mutex_t *mutex);
    bool signal();
    bool broadcast();
};

信号量

1
2
3
4
5
6
7
8
9
10
11

class sem
{
private:
    sem_t m_sem;
public:
    sem();
    sem(int num);
    ~sem();
    bool wait();
    bool post();
};

条件变量与信号量的区别：个人理解中，信号量sem本质上是一个计数的功能，post就是让信号量加一，wait就是让信号量减一，post和wait调用先后问题不大；而条件变量cond则必须先wait再signal或broadcast，否则就会发生丢失信号的现象，特定情况下甚至会造成死锁。另外，信号量可以在进程之间共享，而条件变量只能在进程内部、线程之间共享。

日志

日志系统实现了同步写日志和异步写日志两种模式。同步写日志就是调用了写日志函数之后就等着写完了才退出函数，异步写日志则是在日志系统中维护了一个“生产者-消费者”模型，写日志的函数只负责生产任务，而真正的写入工作则由异步线程完成。为了实现这个“生产者-消费者”模型，我编写了一个阻塞队列，就是把STL中带有的队列模板进行进一步封装，让它的每一个操作都是线程安全的。这样生产者只管push，消费者只管pop就行了。

回到日志系统本身。日志类是在单例模式下编写的。所谓的单例模式，就是把这个类的构造函数和析构函数都私有化，只有类自己能调用，程序的其它部分不能创建新的对象；然后在这个类里静态地内置一个自己，保证整个程序只有这一个对象，并可通过类的静态方法来获取这个唯一对象。

代码摘录：

1
2
3
4
5
6
7
8
9
10
11

class Log{
private:
    Log();
    ~Log();
public:
    static Log *get_instance()
    {
        static Log instance;
        return &instance;
    }
}

MySQL连接池

由于建立和释放MySQL连接是非常消耗资源的，所以用到了临时建立连接太低效了，我们可以维护一个连接池，在初始化时建立一些连接，程序在需要时就可以直接从池里获得一个连接，用完还回来就行。同样采用单例的编写模式。连接池模块有两个类，一个是连接池本体，一个是RAII的接口，接口初始化时从池里获取连接，析构时自动归还。

连接池本体声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class connection_pool
{
private:
    connection_pool();
    ~connection_pool();
    string user;
    string passwd;
    string DatabaseName;
    bool close_log; /* If true, the connection pool won't write logs. */
    int max_conn;
    locker m_locker;
    list<MYSQL*> connList;
    sem m_sem; /* sem > 0 means there is free connections. */
public:
    static connection_pool* get_instance()
    {
        static connection_pool instance;
        return &instance;
    }

    void init(string user, string password, string name, int maxconn, bool close_log = true);
    
    MYSQL* getConnection(); /* Get a free connection from pool. */
    bool releaseConnection(MYSQL *conn); /* Return a connection into the pool. */
    void destroyPool();
};

HTTP处理

这个模块暂时只实现了传输静态页面，图片、文件的传输还有待研究。类里有一个process()函数，用于处理输入、获得待写输出。process()函数由线程池异步调用，处理好再通知主线程进行一个数据的写。

声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class http{
public: /*private*/
    char state_line[64];
    char headers[256];
public:
    http();
    http(char pack[], int fd);
    ~http();
    void process();
    int clntfd;

public:
    char package[1024];
    struct iovec iov[3]; /* iov[0]: state_line; iov[1]: headers; iov[2]: resource to be got */
};

这里用到了iovec，就是分布式IO，可以把需要IO的部分（用起始地址和偏移量表示）存进一个向量里，然后调用readv()或writev()一次性读写多个缓冲区，相当优雅。

mmap

对底层的mmap API进行了封装。mmap还没用明白，所以暂时还没用进程序里，不过理论上可以大幅度提高程序的IO性能。

mmap是一种内存映射文件的方式。普通的文件读写，需要先open()，把文件在读取进操作系统内核的内存里，然后再read()和write()，将内核的内存拷贝进用户态的内存里，造成了效率的浪费；而使用mmap，则可以让内核和用户共享一块内存，省去了第二步的拷贝，更加高效。

声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class mmap_file
{
private:
    int fd;
    void *start; /* The start of mmap. */
    struct stat st;
public:
    mmap_file();
    mmap_file(string path);
    ~mmap_file();
    void openFile(string path);
    void* getStart();
    int getSize();
};

输入一个文件路径，获取这个文件mmap后的起始内存和偏移量。不过好像iovec不能直接用，还没来得及研究和调试。

线程池模块

复用了日志模块的阻塞队列，将已经完成了读操作的http对象加入到工作队列中，由线程池维护的若干个线程竞争获取任务，然后在子线程中异步地完成处理，并注册对应文件描述符上的写事件，通知主线程进行一个写。同样采用单例模式编写。

声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class threadpool
{
private:
    threadpool();
    ~threadpool();
    static void* worker(void* arg); /* Call process() in an infinite loop. */

private:
    pthread_t* m_threads;
    block_queue<http*> workq;
    int m_thread_number;
    sem m_sem;
    locker m_locker;
public:
    bool append(http* request);
    void init(int thread_number, int max_requests);
    static threadpool* get_instance(){
        static threadpool instance;
        return &instance;
    }
};

EPOLL 监听

EPOLL是一种IO多路复用的模型，类似的模型还有SELECT和POLL，但他俩都不如EPOLL好使。在我写的项目里就以单例模式维护了一个EPOLL的监听池，封装了一些API，方便程序直接调用。

IO多路复用

简单地理解就是在一个线程同时监听一大堆文件描述符是否有可写事件和可读事件发生，这样程序可以同时处理来自多个事件流中的事件。

SELECT、POLL和EPOLL的区别

最早被写出来的IO多路复用模型是SELECT，实现思路也非常耿直：就是维护一个数组，调用wait()的时候就去遍历一遍这个数组，看看每个文件描述符是否有事件发生，如果有的话就拎出来告诉调用者。因为用的是数组，所以监听的文件描述符数量有上限，大概是1024个。

而POLL所作出的改进是用链表代替了普通的数组，突破了1024个的上限。但由于还是采用遍历的方式来判断是否有事件发生，依然是线性的复杂度。

然后EPOLL就闪亮登场了。EPOLL底层维护了一棵红黑树和一个链表，红黑树用于保存文件描述符，链表用于保存已经发生了事件的文件描述符。与前两代模型不同，EPOLL不是主动地去遍历，而是给每个文件描述符设置一个“回调函数”，当有事件发生时就自动调用，把文件描述符存进链表中，这样就可以不用遍历了，调用wait()时只需要返回那个链表就行，时间复杂度是常量级的。

有的没的

网抑云（五月天、孙燕姿 - 温柔 #MaydayBlue20th）

Tags

题面

LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。

实现 RandomizedCollection 类:

• RandomizedCollection()初始化空的 RandomizedCollection 对象。
• bool insert(int val) 将一个 val 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 true ，否则返回 false 。
• bool remove(int val) 如果存在，从集合中移除一个 val 项。如果该项存在，则返回 true ，否则返回 false 。注意，如果 val 在集合中出现多次，我们只删除其中一个。
• int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。

您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。

注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

输入
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
输出
[null, true, false, true, 2, true, 1]

解释
RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
collection.insert(1);// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(2);// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.getRandom();// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.remove(1);// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.getRandom();// getRandom 应有相同概率返回 1 和 2 。

题解

是我最喜欢的数据结构运用题。这里有一个小技巧，就是一般vector是不允许O(1)时间复杂度的随机删除的，但是本题中我们不在乎用到的vector里元素的顺序是怎么样的，那么我们就可以把需要删除的元素和末位元素进行一个位置互换，然后我们就能直接在O(1)时间复杂度下pop_back()了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class RandomizedCollection {
private:
    unordered_map<int, unordered_set<int>> map;
    vector<int> nums;
public:
    RandomizedCollection() {

    }

    bool insert(int val) {
        map[val].insert(nums.size());
        nums.push_back(val);
        if (map[val].size() == 1) return true;
        else return false;
    }

    bool remove(int val) {
        if (map[val].size() > 0) {
            int torm = *map[val].begin();
            map[val].erase(torm);
            map[nums.back()].insert(torm);
            map[nums.back()].erase(nums.size() - 1);
            swap(nums[torm], nums[nums.size() - 1]);
            nums.pop_back();
            return true;
        }
        else return false;
    }

    int getRandom() {
        int rndidx = rand() % nums.size();
        return nums[rndidx];
    }
};

线程同步

互斥量：pthread_mutex系列

• int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr);

初始化一个互斥量，即第一个参数指向的mutex。一个互斥量必须初始化了之后才能用。

• int pthread_mutex_destroy(pthread_mutex_t *mutex);

顾名思义，就是删除一个互斥量，释放它的内存。

• int pthread_mutex_lock(pthread_mutex_t *mutex);
• int pthread_mutex_unlock(pthread_mutex_t *mutex);

给互斥量上锁和解锁。如果需要上锁的互斥量已经被别的线程锁住了，那调用pthread_mutex_lock()的线程就会一直被阻塞直到那个互斥量被解锁，然后这个线程再获得锁。上面三个函数都是成功返回0，否则返回错误编号。如果不希望线程被阻塞，那可以用下面这个函数：

• int pthread_mutex_trylock(pthread_mutex_t *mutex);

这个函数会尝试对互斥量加锁，如果锁没被锁上，它就锁上这个锁；如果锁已经被锁住了，那么这个函数就会返回EBUSY。这个函数在避免死锁这件事上有很大帮助（如果不能取得全部的一系列锁，不是干等着而是把已经取得的锁都释放掉，避免跟另一个线程死锁）。

• int pthread_mutex_timedlock(pthread_mutex_t *restrict mutex, const struct timespec *restrict tsptr);

在某个时间前阻塞等待获得锁，超过这个时间就返回错误码ETIMEDOUT。

读写锁：pthread_rwlock系列

读写锁与互斥量类似，但是它支持更高的并行性。它有三种状态：读模式下加锁、写模式下加锁和不加锁。当读写锁是写加锁时，无法被别的线程读、写加锁；当读写锁是读加锁时，所有试图以读模式对它进行加锁的线程都可以得到访问权，但是任何希望以写模式对此锁进行加锁的线程都会阻塞。读写锁非常适合对数据结构读的次数远大于写的情况。

• int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock, const pthread_rwlockattr_t *restrict attr);
• int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);

这两个函数分别用于初始化一个读写锁和销毁一个读写锁以释放它的内存。如果成功，返回0；否则，返回错误编号。

• int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
• int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
• int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);

这三个函数分别对一个读写锁进行读加锁、写加锁和解锁操作。如果成功，返回0；否则，返回错误编号。

• int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
• int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock);
• int pthread_rwlock_timedrdlock(pthread_rwlock_t *restrict rwlock, const struct timespec *restrict tsptr);
• int pthread_rwlock_timedwrlock(pthread_rwlock_t *restrict rwlock, const struct timespec *restrict tsptr);

就是读写锁版的trylock()和timedlock()。

条件变量：pthread_cond系列

• int pthread_cond_init(pthread_cond_t *restrict cond, const pthread_condattr_t *restrict attr);
• int pthread_cond_destroy(pthread_cond_t *cond);

这两个函数分别用于初始化和销毁一个条件变量。如果成功，返回0；否则，返回错误编号。

• int pthread_cond_wait(pthread_cond_t *restreict cond, pthread_mutex_t *restrict mutex);
• int pthread_cond_timedwait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex, const struct timespec *restrict tsptr);

这两个函数用于等待条件变量变为真。而第二个函数则是带有超时的版本。这两个函数都需要自带一个锁上的互斥量，这是为了保证检查条件变量到线程进入休眠等待条件改变这两个操作之间的操作是原子的。因为发信号的接收信号的进程往往会有一些公共的资源（比如生产者-消费者模型，会有一段任务队列是公用的），为了保证这些线程在访问这些公共资源的时候是原子性的，所以需要上锁。那么就有可能发生这样的情况：

消费者获得锁，然后去读取任务队列，发现是空的，所以要等待生产者生产出任务，然后发送信号；

而生产者在向任务队列中写入任务前也需要获得锁，这就造成了一个死锁现象。

为了避免这种情况，消费者在进入睡眠等待之前，要释放锁，让生产者去获得锁并生产出任务；生产者生产出任务并唤醒消费者后，消费者要再次获得锁并读取任务队列。

那么一来二去的，人们就发现还不如直接把这些上锁解锁的操作直接集成进pthread_cond_wait()里来的方便，于是这个函数就多了一个互斥量的参数了。

就这么干说有点抽象，可以看看这篇文章，写的相当详细，赞。

• int pthread_cond_signal(pthread_cond_t *cond);
• int pthread_cond_broadcast(pthread_cond_t *cond);

这两个函数用于向某个信号量发出条件满足的信号，第一个函数至少能唤醒一个等待该条件的线程，而第二个能唤醒所有等待该条件的所有线程。如果成功，返回0；否则，返回错误编号。

还有一个要注意的点是我们要用while而不是if来判断条件，因为如果有多个消费者存在的话，可能某个消费者被唤醒后还没来得及获得锁，任务就已经被其它消费者处理完了。

屏障：pthread_barrier系列

屏障是用户协调多个线程并行工作的同步机制。屏障允许每个线程等待，直到所有合作的线程都达到某一点，然后从该点继续执行。pthread_join()就是一种屏障，允许一个线程等待，直到另一个线程退出。但是屏障对象的概念更广，它们允许任意数量的线程等待，直到所有的线程完成处理工作，而线程不需要退出，所有线程达到屏障后可以接着工作。

• int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned int count);
• int pthread_barrier_destroy(pthread_barrier_t *barrier);

这两个函数分别用于屏障的初始化和销毁，如果成功，返回0；否则，返回错误编号。在初始化函数中，第三个参数count可以指定允许所有线程继续运行前，必须到达屏障的线程数目。

• int pthread_barrier_wait(pthread_barrier_t *barrier);

这个函数表示线程已经完成工作，正在等待其他线程赶上来。如果成功，返回0或者PTHREAD_BARRIER_SERIAL_THREAD；否则，返回错误编号。只有第一个成功返回wait()会返回PTHREAD_BARRIER_SERIAL_THREAD，其余都返回0。这样特殊一点的线程就可以作为主线程工作在其他所有线程已完成的工作上。

一旦到达屏障计数值，而且线程处于非阻塞状态，屏障就可以被重用。如果需要改变计数值，就需要destroy()后重新init()。

线程创建与退出

创建线程：pthread_create()

• 定义：int pthread_create(pthread_t *restrict tidp, const pthread_attr_t *restrict attr, void*(*start_rtn)(void*), void *restrict arg);

好长一段定义，咱们一个参数一个参数看。

• pthread_t *restrict tidp：成功创建线程后会把新建线程的ID存在这个指针指向的地址空间里。
• const pthread_attr_t *restrict attr：用于定制不同的线程属性。attr=attribute
• void*(*start_rtn)(void*)：看不太懂啥意思，反正用来指定新线程运行的函数，传函数名就行。
• void *restrict arg：用来指定函数的参数。如果有多个参数，需要用结构体打包传进去。

成功返回0，否则返回错误编号。

restrict是C99标准引入的关键字，用于限定和约束指针，表示这个指针是访问对应地址空间的唯一方式。它可以帮助编译器更好地优化代码，生成更有效率的汇编代码。

线程终止：pthread_exit() & pthread_join() & pthread_cancel()

• pthread_exit()的定义：void pthread_exit(void *rval_ptr);

这个函数只有一个参数，用于指定线程退出时的退出码。调用这个函数之后，线程就会退出。和主线程的exit()差不多道理，但是线程里调用exit()会终止整个进程。

• pthread_join()的定义：int pthread_join(pthread_t thread, void **rval_ptr);

第一个参数用来指定一个线程，第二个参数用于接收该线程的退出码。这个函数被调用后会一直被阻塞，直到前面指定的线程退出、返回或被取消了。

成功返回0，否则返回错误编号。

• pthread_cancel()的定义：int pthread_cancel(pthread_t tid);

指定一个线程，强行把它取消了。成功返回0，否则返回错误编号。

一个未被pthread_detach(pthread_t tid)过的线程执行结束后会保存终止状态，知道这个线程被另一个线程join。

线程清理：pthread_cleanup_push() & pthread_cleanup_pop()

• pthread_cleanup_push()的定义：void pthread_cleanup_push(void (*rtn)(void *), void *arg);

第一个参数用于指定清理函数，填函数名；第二个参数前面那个函数执行需要的参数。当线程执行以下动作时会调用清理函数：

1. 调用pthread_exit时；
2. 响应取消请求时；
3. 用非零execute参数调用pthread_cleanup_pop()时。

• pthread_cleanup_pop()的定义：void pthread_cleanup_pop(int execute);

如果将execute参数设置为0，则清理函数不会被调用。无论被发生什么情况，pthread_cleanup_pop()都会删除上次pthread_cleanup_push()调用建立的清理处理程序。可以把push和pop想象成在一个储存“清理函数”的栈上操作。

有的没的

网抑云（告五人 - 爱人错过）

今天是一个特别的日子，可以网抑云。

Tags

题面

LeetCode 995. K 连续位的最小翻转次数

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

子数组 是数组的 连续 部分。

示例 1：

1
2
3

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

1
2
3

输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

1
2
3
4
5
6

输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

题解

差分数组

当我隐约感觉某道题或许可以用差分做的时候，那道题往往用不了差分；当我想破脑袋都想不到可以用差分做时，差分就来了。

策略就是当遇到0时进行翻转，否则不翻转。一开始根据这个策略做，暴力模拟，经典超时。后来看了题解才会做。我们可以用差分数组来维护某个位置被翻转的次数，结合这个位置的初始状态，就可以快速得到这个位置目前的状态。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> diff(n + 1, 0);
        int res = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += diff[i];
            if ((nums[i] + cnt) % 2 == 0) {
                if (i + k > n) return -1;
                res++;
                cnt++;
                diff[i + k]--;
            }
        }
        return res;
    }
};

滑动窗口

当然，差分数组也不是必要的，可以维护一个滑动窗口来将空间复杂度降为O(1)。

思路就是用一个队列维护对当前仍有影响的取了反的位置，这样队列的长度就反映了当前位置反转的次数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        queue<int> q;
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (!q.empty() && q.front() + k == i) q.pop();
            if (q.size() % 2 == nums[i]) {
                if (i + k > n) return -1;
                q.push(i);
                res++;
            }
        }
        return res;
    }
};

有的没的

曙光

从十一开始就没有闲下来过。国庆过完紧跟着信息政策的pre，然后是毛概，还有计网的实验报告，还有信息检索。后面还要计网写Web Server，还（算是）接过了98勋章系统的活（虽然还啥都不会，得从零开始学）。不过还好都熬过来了，这个周末忙完大概就可以稍微闲一阵子了。微博好友圈里看到的同学们都好用功，怎么每天都能学到凌晨才回寝室的，为什么会有这么多事情要做，合着她们学校不把同学当人似的。或许只是单纯是她们比较有追求，不是我这种咸鱼能理解的。

gtmdzyh

章燕华查老师2.2分属于是给高了，嘴碎屁事多也就算了，饭点拖课是真的不能忍，等结课了一定要给她刷1分。这门课爷反正摆了，爱给几分给几分，还能把爷挂了不成。不过话说回来，刷低分也没啥用，专业必修课也没得选。晦气晦气。

没事听点歌（陈粒 - 走马）

Tags

题面

LeetCode 483. 最小好进制

以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。

如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

示例 1：

1
2
3

输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

1
2
3

输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

1
2
3

输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

题解

又是一道经典的“不看题解不会做，一看题解恍然大悟”的题。由于数据的范围是[3,1e18]，在64位以内，我们可以从大到小（位数越多，进制越小）枚举全是1的二进制位数，然后再二分k进制的所有可能性，就可以快速找到最小的好进制。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
private:
    unsigned long long str2ull(string& s) {
        unsigned long long res = 0;
        for (char c : s) {
            res *= 10;
            res += c - '0';
        }
        return res;
    }
public:
    string smallestGoodBase(string n) {
        unsigned long long num = str2ull(n);
        for (int i = 64; i >= 2; i--) {
            unsigned long long l = 2;
            unsigned long long r = num;
            while (l < r) {
                unsigned long long mid = l + ((r - l) >> 1);
                unsigned long long temp = 0;
                for (int j = 0; j < i; j++) {
                    if ((log(temp) + log(mid)) / log(2) >= 64) {
                        temp = num + 1;
                        break;
                    }
                    else temp = temp * mid + 1;
                }
                if (temp > num) r = mid;
                else if (temp < num) l = mid + 1;
                else return to_string(mid);
            }
        }
        return "";
    }
};

里面涉及了一个新学的小技巧：如果一个unsigned long long已经溢出过了，那么必然是不符合答案的，应该直接退出计算然后继续二分下一个答案。那么怎么判断temp和mid相乘后是否溢出过呢？只要这两个数分别对2取对数（即二进制的最高位在哪一位），只要取完对数相加后大于或等于64，就意味着已经溢出并自动取模过了。

有的没的

没事听点歌（RADWIMPS - グランドエスケープ （《天气之子》插曲））

整点二次元！

Tags

题面

LeetCode 332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

1
2

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2:

1
2
3

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

题解

显然这道题最基本的结构是图。因为要查找字典序最小的行程组合，我们只需要排序后贪心地进行深度优先搜索就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
private:
    vector<string> res;
    unordered_map<string, vector<string>> map;
    bool found = false;
    int cnt = 0;
    void dfs(string cur) {
        if (found) return;
        res.push_back(cur);
        if (cnt == 0) {
            found = true;
            return;
        }

        for (int i = map[cur].size() - 1; i >= 0; i--) {
            if (map[cur][i] == "") continue;
            string next = map[cur][i];
            map[cur][i] = "";
            cnt--;
            dfs(next);
            if (found) return;
            cnt++;
            res.pop_back();
            map[cur][i] = next;
        }

    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (vector<string> s : tickets) {
            map[s[0]].push_back(s[1]);
            cnt++;
        }
        for (auto& i : map) {
            sort(i.second.begin(), i.second.end());
            reverse(i.second.begin(), i.second.end());
        }
        dfs("JFK");
        return res;

    }
};

但是我的办法是删删改改后的蠢办法，只能勉强通过。用上优先队列可以更优雅地实现快速找到字典序最小的下一个节点。还需要用上欧拉回路的一个性质，就是入度和出度相差为1的节点必定是最后一个节点。用上这个性质就可以写出更简洁的代码了。

有的没的

国庆总结

今年度过了一个充实的国庆假期。

30号在玉泉上了课之后去了青芝坞的花先生厨房吃午饭。店里的环境很棒，牛河炒的中规中矩，炒豆角里的炸蛋碎碎简直是神来之笔，咸蛋黄炸蘑菇的咸蛋黄存在感很强，红烧肉吃的满嘴流油超级满足。

1号和2号在寝室连扣了两天代码，写了计网的TCP套接字编程的作业。项目在https://github.com/Cyclohexatriene/Lab7 ，昨天加了最后一块碎片正式完工，但是实验报告还没来得及写。非常有成就感！

3号写了信息检索的爬虫作业，IP被豆瓣封了若干次，最后换了手机两张卡的热点才爬完全部结果。第一次自己写爬虫代码，觉得还是学到不少东西的。

4号和胖喜鹊同学去了灵隐寺玩，下山后沿着西湖从北山街逛到了湖滨银泰，被西湖的风吹得有点迷糊。淋了点小雨，走得很累，但是玩得很开心！

5号和6号写了暑假小学期的报告，个人报告糊弄了不到1500字交上去了，写得非常求是了可以说是。还玩了《守望先锋》（归来），雾子太好看了，新老婆。后来发现日语声优还和徐伦是同一个人，双厨狂喜。

7号本来打算参加一下LeetCode的秋季赛，但是好多同学来问了爬虫的问题，不得不说，爬虫真是太玄学了。竞赛后来做了一道题就摆了，有好多必须回的消息，干扰太大了，没法专心思考。而且咕了太久的刷题了，脑子有点转不动（所以今天也摇了一道水Hard做做，嘿嘿）。

刚才发现博客里好多图片显示不出来。或者说，只有首页的图片能显示。目测是相对路径的问题，回头再研究下。修好了捏。

Tags

题面

LeetCode 664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

• 打印机每次只能打印由 同一个字符 组成的序列。
• 每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

1
2
3

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：

1
2
3

输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

题解

动态规划好多题真是不看题解不会做，一看题解就秒懂，这题就是其中之一（还有不少是看了题解也做不来的）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) dp[i][j] = dp[i][j - 1];
                else {
                    int mini = INT_MAX;
                    for (int k = i; k < j; k++) 
                        mini = min(mini, dp[i][k] + dp[k + 1][j]);
                    dp[i][j] = mini;
                }
            }
        }
        return dp[0][n - 1];
    }
};

Tags

题面

LeetCode 1611. 使整数变为 0 的最少操作次数

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

示例 1：

1
2
3
4
5

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 2：

1
2
3
4
5
6
7

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

题解

冥思苦想了半天，尝试了两三种方法，还是写不出来，一下午就耗这了。看了题解，勉强做出来。

(以下摘自**LeetCode @自在飞花 **前辈的题解)

设 cal(xxxxx) 表示将二进制为 xxxxx 的数字变为 0 的最小操作次数。

如果 xxxxx 形如 11xxx，则只能通过 11xxx -> 11000 -> 1000 -> 0 (只列出了转换序列中的关键步骤) 这样的顺序来改变。

即 cal(11xxx)=cal(xxx)+1+cal(1000)。解释一下：

• cal(xxx) 表示将 11xxx 变为 11000 的操作数
• 1 表示将 11000 变为 1000 的操作数
• cal(1000) 表示将 1000 变为 0 的操作数

如果 xxxxx 形如 10xxx，则只能通过 10xxx -> 11000 -> 1000 -> 0 (只列出了转换序列中的关键步骤) 这样的顺序来改变。

即 cal(10xxx)=cal(1000)−cal(xxx)+cal(11000)。解释一下：

• cal(1000) - cal(xxx) 表示将 xxx 变为 1000 的操作数。因为任意一点到达 S 点有且只有一条路径，所有从 xxx 到 1000 的值为 cal(1000) - cal(xxx)。
• cal(11000) 表示将 11000 变为 0 的操作数。

而我之所以没做出来就是因为想不到把cal(xxx)减掉的思路。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
private:
    int highbit(int x) {
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        return x - (x >> 1);
    }
    unordered_map<int, int> map;
    unordered_map<int, int> memory;
    int steps(int n) {
        int m = n;
        if (map.count(n)) return map[n];
        if (!memory.count(n)) {
            int high = highbit(n);
            while (n > 0) {
                if (n & high) {
                    if (n & (high >> 1)) {
                        memory[n] = steps(n ^ high ^ (high >> 1)) + 1 + map[high >> 1];
                        n = n ^ high ^ (high >> 1);
                    }
                    else {
                        memory[n] = map[high >> 1] - steps(n ^ high) + steps(high + (high >> 1));
                        n = n ^ high;
                    }
                }
                high >>= 1;
            }
        }
        return memory[m];
    }
public:
    int minimumOneBitOperations(int n) {
        map[1] = 1;
        for (int i = 1; i < 31; i++) map[1 << i] = 2 * map[1 << (i - 1)] + 1;
        memory[0] = 0;
        memory[1] = 1;
        return steps(n);
    }
};