购买两块巧克力
传送门
暴力枚举下
C++ 代码
class Solution {
public:
int buyChoco(vector<int>& prices, int money) {
sort(prices.begin(), prices.end());
int cnt = prices[0] + prices[1];
if (cnt > money) return money;
else return money - cnt;
}
};
字符串中的额外字符
传送门
设f[i]表示0 到i - 1字符的字符最少个数
我们会发现只要存在dictionary 中的单词,我们就可以推出f[i] = min(f[s], f[i])
, s是上一个状态
否则 f[i] = f[i - 1] + 1
C++ 代码
class Solution {
public:
int minExtraChar(string s, vector<string>& dictionary) {
int n = s.size();
vector<int> f(n + 1, 0);
unordered_set<string> st;
for (auto d : dictionary) st.insert(d);
for (int i = 1; i <= n; i ++ )
{
f[i] = f[i - 1] + 1;
for (int j = 1; j <= i; j ++ )
{
string tmp = s.substr(j - 1, i - j + 1);
if (st.count(tmp)) f[i] = min(f[i], f[j - 1]);
}
}
return f[n];
}
};
一个小组的最大实力值
传送门
设f[i][0]代表前i项的最大,f[i][1]代表前i项最小
f[i][0] = max({f[i - 1][0], f[i][0] * nums[i - 1], f[i][1] * nums[i - 1], nums[i]);
f[i][1] = min({f[i - 1][1], f[i][0] * nums[i - 1], f[i][1] * nums[i - 1], nums[i]);
C++ 代码
class Solution {
public:
long long maxStrength(vector<int>& nums) {
int n = nums.size();
long long f[n + 1][2];
f[1][0] = nums[0]; //最大
f[1][1] = nums[0]; //最小
for (int i = 2; i <= n; i ++ )
{
f[i][0] = max(f[i - 1][0],
max(f[i - 1][0] * nums[i - 1],
max(f[i - 1][1] * nums[i - 1], 1LL * nums[i - 1])));
f[i][1] = min(f[i - 1][1],
min(f[i - 1][0] * nums[i - 1],
min(f[i - 1][1] * nums[i - 1], 1LL * nums[i - 1])));
}
return f[n][0];
}
};
最大公约数遍历
传送门
质因数分解 + 并查集
C++ 代码
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
unordered_map<int,int> mp;
int n = nums.size(), res = 0;
if (n == 1) return true;
vector<int> p(n + 1, 0), f(n + 1, 0);
function<int (int)> find = [&](int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
};
for (int i = 0; i < n; i ++ ) p[i] = i, f[i] = 1;
for (int i = 0; i < n; i ++ )
{
for (int j = 2; j <= nums[i] / j; j ++ )
{
if (nums[i] % j == 0)
{
if (mp.count(j))
{
int a = find(i), b = find(mp[j]);
if (a != b)
{
f[b] += f[a];
p[a] = b;
if (res < f[b]) res = f[b];
}
}
else mp[j] = find(i);
while (nums[i] % j == 0) nums[i] /= j;
}
}
if (nums[i] > 1)
{
if (mp.count(nums[i]))
{
int a = find(i), b = find(mp[nums[i]]);
if (a != b)
{
f[b] += f[a];
p[a] = b;
if (res < f[b]) res = f[b];
}
}
else mp[nums[i]] = find(i);
}
}
return res == n;
}
};