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);
    }
};

概述

哈希化是一种常见的数据存储方式，可以把一堆数据存到一起，并在O(1)复杂度下检索其中的任意一项。而对于字符串来说，普通的unordered_set<string>在哈希的时候会对整个字符串进行遍历，今天做到的这道题会因此TLE。

在需要对某个字符串的子字符串进行哈希时，可以对整个字符串进行一个预处理，使后续的哈希从伪O(1)实O(n)降低为真正的O(1)。

原理

字符串哈希将整个字符串看作一个base进制的数，这个base一般会取一个足够大的质数，例如1331、13331等。为方便理解，我们先取base为10，并取字符串s = "123456"。

如果我想得到s[1:2]的哈希值（即23)，我们可以先取得s[0:2]的哈希值(记为h[2])，即123，再减去多余的100即可。那这个100怎么来的呢？只需要将s[0]的值乘以若干次方（此处为2次）的base就可以了。根据这个原理，我们就可以得到一个通用的公式：h[l:r] = h[r] - h[l-1] * p[r - l + 1]，其中h[l:r]表示字符串s下标从1开始数第l为和第r位之间的子串的哈希值，h[idx]表示字符串s前idx位的哈希值，p数组是次方数组，其内容为{1,base,base²,base³,...}。

由此，我们可以做到一次预处理，无数次O(1)哈希其子字符串，节省大量时间。

例题

LeetCode 1044. 最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

1
2

输入：s = "banana"
输出："ana"

示例 2：

1
2

输入：s = "abcd"
输出：""

题解

刚看到这道题的时候就傻眼了，除了暴力想不到什么可行的办法。一看评论区，"温馨提示, 今天这个打卡题出自136场周赛第四题, 当时国服只有6个人做出来，所以不会做很正常哦"，原来大家都不会做，那我就放心了呀！

不过其实知道怎么做之后，这题还是没那么难的。虽然本题暴力验证每一个长度的子字符串存不存在重复非常的蠢，但是有了字符串哈希的技巧，验证其中某一个长度的子字符串存不存在重复却可以在O(n)的时间复杂度下完成。而且出现重复的可能性是单调递减的， 即待验证的子字符串长度越长，子字符串出现重复的可能性越小。所以我们可以对答案空间进行二分搜索，免去了大量的无用功。虽然不是第一次见这种技巧了，但有时就差这么tingle一下，想不到可以这么解。

还有一个技巧就是使用unsigned long long来储存哈希值，这样超过了2^64的时候就会自动取模，省的再做大数处理。（回忆起了周赛做了一个小时大数处理没做出来的恐惧[ac01]）

代码：

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
43

class Solution {
private:
    vector<unsigned long long> h;
    vector<unsigned long long> p;
    unsigned long long getHash(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
public:
    string longestDupSubstring(string s) {
        int n = s.length();
        int l = 0; int r = n - 1;
        const int base = 1331;
        h.resize(n + 1);
        p.resize(n + 1);
        p[0] = 1;
        h[0] = 0;
        for (int i = 1; i < n + 1; i++) {
            h[i] = h[i - 1] * base + s[i - 1] - 'a' + 1;
            p[i] = p[i - 1] * base;
        }
        string res;
        while (l <= r) {
            int len = (l + r) >> 1;
            unordered_set<unsigned long long> set;
            bool find = false;
            for (int i = 0; i < n - len + 1; i++) {
                unsigned long long hash = getHash(i + 1, i + len);
                if (set.count(hash)) {
                    find = true;
                    if (len > res.length()) res = s.substr(i, len);
                    break;
                }
                set.insert(hash);
            }
            if (find) l = len + 1;
            else {
                if (l == r) break;
                else r = len;
            }
        }
        return res;
    }
};

有的没的

没事听点歌（不才 - 夜航星)