题目1
给定一个有序数组arr，代表坐落在X轴上的点
给定一个正数K，代表绳子的长度
返回绳子最多压中几个点?
即使绳子边缘处盖住点也算盖住
输入：
第一行 arr的size，k
第二行 arr
输出：
最多覆盖的点
思路
滑动窗口，窗口不回退模型。窗口左边界L，右边界R，初始值都是0，R每次往右移动到最右的位置，统计一次压中的点数，然后L往右移动一次，R继续，直到L越界。
代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, k;
cin >> n;
cin >> k;
vector<int> vec(n);
for (int i = 0; i < n; i++)
{
cin >> vec[i];
}
int l = 0;
int r = 0;
int Max = 0;
for (; l < vec.size(); l++)
{
while (r < vec.size() && vec[r] - vec[r] <= k)
{
r++;
}
Max = max(Max, r - l); //由于while的特点，r最后会位于能移动到的最右位置+1的位置，所以少统计一个
}
cout << Max << endl;
return 0;
}
题目2
一个数组中只有两种字符'G'和'B'
想让所有的G都放在左侧，所有的B都放在右侧
但是只能在相邻字符之间进行交换操作
返回至少需要交换几次
思路
贪心。策略是第i次出现的G只用移动到数组下标为i-1的位置。比如第一次出现的G只用移动到0位置。
代码
int main()
{
string str;
cin >> str;
int L = 0;
int i = 0;
int ans = 0;
for (; i < str.size(); i++)
{
if (str[i] == 'G')
{
ans += i - L;
L++;
}
}
cout << ans << endl;
return 0;
}
题目3(leetcode494)
给定一个数组arr，你可以在每个数字之前决定 + 或者 - ，但是必须所有数字都参与
再给定一个数target，请问最后数组中所有数字按照给定的+和-算出target的方法数是多少?
思路
- 暴力递归尝试。
- 优化后思路：
1.不管给定的arr中有没有负数，方法数结果都跟全部都取绝对值时相同。原因是因为负数加上 - 后就变成了负数，与正数加上 + 一样，无非就是原来是 - 现在变成了 + 。所以一开始把所有数字都处理成正数
2.因为所有的数字都要用上，假设arr所有数字的绝对值的和为sum，则sum必须大于target，否则不可能算出target，且sum的奇偶性与target一样。
3.假设加上符号后所有正数集合的和为P，负数集合的和为N，一定有P - N = sum，P + N = target，第一个式子两边同时加上P + N，得到2P = sum + P + N = sum + target，P = (sum + target) / 2 。sum和target的值都是已知的，所以只要从arr中任取数字拼凑出P(此时arr中的数已经被全部处理为正数了，拼凑是指只做相加操作，所以满足P是所有正数的集合这个要求)，剩下的都拼成负数即可获得target，这种优化思路下，把问题转换成了经典背包问题。而且dp数字的规模也减小了，原来的dp列规模是-sum到sum，现在是0~sum(因为target最大取sum)，减小了一半
4.空间压缩技巧
代码
暴力递归
int process(vector<int> arr, int index, int rest)
{
if (index == arr.size())
{
return rest == 0 ? 1 : 0;
}
return process(arr, index + 1, rest - (arr[index] - '0')) + process(arr, index + 1, rest + (arr[index] - '0'));
}
int main()
{
int n, tar;
cin >> n;
cin >> tar;
vector<int> arr(n);
cout << process(arr, 0, tar) << endl;
return 0;
}
优化后动态规划(没有做空间压缩)
int subset(vector<int> nums, int s)
{
vector<vector<int>> dp(nums.size() + 1, vector<int>(s + 1));
dp[nums.size()][0] = 1;
for (int i = nums.size() - 1; i >= 0; i--)
{
for (int j = 0; j < dp[0].size(); j++)
{
if (j - nums[i] >= 0)
{
dp[i][j] = dp[i + 1][j - nums[i]] + dp[i + 1][j];
}
}
}
return dp[0][s];
}
int main()
{
int n, tar;
cin >> n;
cin >> tar;
vector<int> arr(n);
int sum = 0;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
arr[i] = abs(arr[i]);
sum += arr[i];
}
if (sum < abs(tar) || ((sum & 1) ^ (tar & 1)) != 0)
{
cout << 0 << endl;
}
else
{
cout << subset(arr, (tar + sum) / 2) << endl;
}
return 0;
}
题目4
现有司机N*2人，调度中心会将所有司机平分给A、B两个区域(注意是平分)
第i个司机去A可得收入为income[i][0],
第i个司机去B可得收入为income[i][1],
返回所有调度方案中能使所有司机总收入最高的方案，是多少钱
思路
暴力递归，详细看代码
暴力递归代码
int process(vector<vector<int>> &income, int index, int rest) //index：当前来到的司机的位置，rest：A区域还剩多少个司机可以分配
{
if (index = income.size())
{ //越界了返回0元
return 0;
}
if (income.size() - index == rest) //剩下的只能选A区域
{
return income[index][0] + process(income, index + 1, rest - 1);
}
if (rest == 0) //剩下的只能选B区域
{
return income[index][1] + process(income, index + 1, rest);
}
//A区域和B区域都可以选，选钱最多的
int p1 = income[index][0] + process(income, index + 1, rest - 1);
int p2 = income[index][1] + process(income, index + 1, rest);
return max(p1, p2);
}
int main()
{
int N;
cin >> N; //N一定是2的倍数
vector<vector<int>> income(N, vector<int>(2));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 2; j++)
{
cin >> income[i][j];
}
}
cout << process(income, 0, N / 2) << endl;
return 0;
}
题目5
给哈希表添加一个setAll操作，setAll(int n)的功能是将哈希表内所有value都改成n，要求setAll操作的时间复杂度是O(1)，可以使用stl的哈希模板实现
思路
假设要求实现的哈希表叫hashmap，hashmap的内部有一个哈希表，一个当前时间(初始值为0，每存入一个key，时间++)，一个setAll时间(初始值为0，当进行setAll时更新成当前时间)，一个setAll值(setAll操作时更新为setAll传入的参数)。在hashmap的内部储存value时储存pair形式，pair的第一个值为用户存入的value，第二个值为存入时间，当进行setAll操作时，更新setAll值、setAll时间，当用户想要拿到他存入的key对应的value时，判断存入时间是否小于setAll时间，如果是，则返回setAll值给他，如果不是则返回用户自己存入的value。
题目6
求一个字符串中，最长无重复子串的长度
思路
动态规划，准备一个辅助字符数组(或哈希表)，储存从前往后遍历字符串时当前字符出现的上一个位置。dp[i]的含义是以i位置的字符结尾，最长无重复子串的长度。dp[i]有两个瓶颈，一个是i位置字符上一次出现的位置，在辅助字符数组(或哈希表)中有记录，另一个是dp[i-1]的值，取两个瓶颈离自己最近的即可更新dp[i]，提前准备一个max变量，边更新dp边比较最大值，最后返回max。
代码
int main()
{
string str;
cin >> str;
unordered_map<char, int> map;
vector<int> dp(str.size());
dp[0] = 1;
map[str[0]] = 0;
int max = 1;
for (int i = 1; i < dp.size(); i++)
{
if (map.count(str[i]) == 0)
{
dp[i] = dp[i - 1] + 1;
}
else
{
dp[i] = min(i - map[str[i]], dp[i - 1] + 1);
}
map[str[i]] = i;
max = max > dp[i] ? max : dp[i];
}
cout << max << endl;
return 0;
}
题目6
给定一个数组arr，代表每个人的能力值。再给定一个非负数k
如果两个人能力差值正好为k，那么可以凑在一起比赛
一局比赛只有两个人
返回最多可以同时有多少场比赛
思路
窗口。先从小到大排序，准备一个bool类型的数组，大小与arr一样，初始值全为false，i位置上如果为true则代表i已经分配过比赛了，不能再次分配了。窗口两个边界分别为L和R，初始值都是0。首先判断L所处的位置是否已经被分配过比赛，如果是，L右移进下一次循环。如果不是，则判断L与R是否是同一位置，如果是，R向右移动进下一次循环，如果不是，先判断R位置的能力值减去L位置的能力值是否等于K，如果是，R位置false置为true，L与R同时右移进下一次循环，如果小于k，R右移，大于K，L右移。直到L或R越界
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n;
cin >> k;
vector<int> c(n);
for (int i = 0; i < n; i++)
{
cin >> c[i];
}
sort(c.begin(), c.end());
int L = 0;
int R = 0;
vector<bool> used(n);
int ans = 0;
while (L < n && R < n)
{
if (used[L])
{
L++;
}
else if (L == R)
{
R++;
}
else
{
int dis = c[R] - c[L];
if (dis == k)
{
ans++;
used[R] = true;
L++;
R++;
}
else if (dis < k)
{
R++;
}
else
{
L++;
}
}
}
cout << ans << endl;
return 0;
}
题目7
给定一个正数数组arr，代表若干人的体重
再给定一个正数limit，表示所有船共同拥有的载重量
每艘船最多坐两人，且不能超过载重
想让所有的人同时过河，并且用最好的分配方法让船尽量少
返回最少的船数