以下哪种情况使用链表比数组更合适？

函数removeElements删除单链表中所有结点值等于val的结点，并返回新的头结点，则横线处填写（ ）。

函数hasCycle采用Floyd快慢指针法判断一个单链表中是否存在环，即用两个指针在链表上前进：slow每次走1步，fast每次走2步，若存在环，fast终会

函数isPerfectNumber判断一个正整数是否为完全数（该数是否等于它的真因子之和），则横线上应填写（ ）。

以下代码计算两个正整数的最大公约数(GCD)，横线上应填写（ ）。

函数sieve实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（ ）。

函数linearSieve实现线性筛法(欧拉筛)，横线处应填入（）。

vector<int> linearSieve(int n) {
vector<bool> is_prime(n+1, true);
vector<int> primes;
for(int i = 2; i <= n; i++) {
if(is_prime[i]) primes.push_back(i);
for(int p : primes) {
if(p * i > n) break;
is_prime[p * i] = false;
if(________) break;
}
}
return primes;
}

关于埃氏筛和线性筛的比较，下列说法错误的是（ ）。

唯一分解定理描述的是( )。

给定一个n×n的矩阵matrix，矩阵的每一行和每一列都按升序排列。函数countLE返回矩阵中第k小的元素，则两处横线上应分别填写（ ）。

// 统计矩阵中 <= x 的元素个数：从左下角开始
int countLE(const vector<vector<int>>& matrix, int x) {
int n = (int)matrix.size();
int i = n - 1, j = 0, cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= x) {
cnt += i + 1;
++j;
}
else {
--i;
}
}
return cnt;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = (int)matrix.size();
int lo = matrix[0][0];
int hi = matrix[n - 1][n - 1];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (countLE(matrix, mid) >= k) {
________________ // 在此处填入代码
} else {
________________ // 在此处填入代码
}
}
return lo;
}

下述C++代码实现了快速排序算法，下面说法错误的是（ ）。

下述C++代码实现了归并排序算法，则横线上应填写（ ）。

假设你是一家电影院的排片经理，只有一个放映厅。你有一个电影列表 movies ，其中 movies[i] =[start_i, end_i] 表示第 i 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影，则横线上应分别填写的代码为（ ）。
int maxMovies(vector<vector<int>>& movies) {
if (movies.empty()) return 0;
sort(movies.begin(), movies.end(), [](const vector<int>& a, const vector<int>& b) {
return ______; // 在此处填入代码
});
int count = 1;
int lastEnd = movies[0][1];
for (int i = 1; i < movies.size(); i++) {
if (movies[i][0] >= lastEnd) {
count++;
______ = movies[i][1]; // 在此处填入代码
}
}
return count;
}

给定一个整数数组nums，下面代码找到一个具有最大和的连续子数组，并返回该最大和。则下面说法错误的是（ ）。

给定一个由非负整数组成的数组digits，表示一个非负整数的各位数字，其中最高位在数组首位。下面代码对该整数执行+1操作，并返回结果数组，则横线上应填写（

基于下面定义的函数，通过判断isDivisibleBy9(n) == isDigitSumDivisibleBy9(n)代码可验算如果一个数能被9整除，则它的各位数字之和能被9整除。

bool isDivisibleBy9(int n) {
return n % 9 == 0;
}
bool isDigitSumDivisibleBy9(int n) {
int sum = 0;
string numStr = to_string(n);
for (char c : numStr) {
sum += (c - '0');
}
return sum % 9 == 0;
}

假设函数gcd()能正确求两个正整数的最大公约数，则下面的findMusicalPattern(4, 6)函数返回2。

下面递归实现的斐波那契数列的时间复杂度为O(n)。

链表通过更改指针实现高效的结点插入与删除，但结点访问效率低、占用内存较多，且对缓存利用不友好。

二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找，且仅适用于数组或基于数组实现的数据结构。

线性筛关键是"每个合数只会被最小质因子筛到一次"，因此为O(n)。

快速排序和归并排序都是稳定的排序算法。

下面代码采用分治算法求解标准3柱汉诺塔问题，时间复杂度为O(2^n)。

void move(vector<int> &src, vector<int> &tar) {
int pan = src.back();
src.pop_back();
tar.push_back(pan);
}
void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) {
if (n == 1) {
move(src, tar);
return;
}
dfs(n - 1, src, tar, buf);
move(src, tar);
dfs(n - 1, buf, src, tar);
}
void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
int n = A.size();
dfs(n, A, B, C);
}

所有递归算法都可以转换为迭代算法。

贪心算法总能得到全局最优解。

数字选取

给定正整数N，现在有1, 2, ..., N共计N个整数。你需要从这N个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为1）。请你最大化所选取整数的数量。
例如，当N=6时，可以选择1, 2, 3, 5共计4个整数。可以验证不存在数量更多的选取整数的方案。

一行，一个正整数N，表示给定的正整数。

一行，一个正整数，表示所选取整数的最大数量。

【样例输入】

6
【样例输出】

4
对于50%的测试点，保证N<=1000。
对于所有测试点，保证N<=10^5。

有趣的数字和

如果一个正整数的二进制表示包含奇数个1，那么小A就会认为这个正整数是有趣的。
例如，3的二进制表示为11，包含1的个数为2个，所以3不是有趣的。但是5包含2个1，所以5也不是有趣的。
给定正整数L和R，请你统计满足L<=x<=R的有趣的整数x之和。

一行，两个正整数L, R，表示给定的正整数。

一行，一个正整数，表示L到R之间有趣的整数之和。

【样例输入】

3 8
【样例输出】

19
对于30%的测试点，保证L,R<=1000。
对于另外30%的测试点，保证L=1并且R=2^k-1，其中k是大于0的正整数。
对于所有测试点，保证1<=L<=R<=10^9。