class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector<vector<int>> f(n + 2, vector<int>(n + 2));
// 区间DP模板
for(int len = 3; len <= n + 2; len++)
for(int l = 0; len + l - 1 <= n + 1; l++)
{
int r = l + len - 1;
int reslr = nums[l] * nums[r];
for(int k = l + 1; k < r; k++)
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + reslr * nums[k]);
}
return f[0][n + 1];
}
};
313 - 超级丑数
复习一下丑数系列：
263 - 丑数
只包含质因子2, 3, 5 的话 就把质因子2，3， 5 除干净 看看余数是不是1就可以了
class Solution {
public:
bool isUgly(int num) {
if(num < 1) return false;
while(num % 2 == 0) num /= 2;
while(num % 3 == 0) num /= 3;
while(num % 5 == 0) num /= 5;
return num == 1;
}
};
264 - 丑数II
丑数的定义是一样的 请找出第n个丑数
有点三路归并的意思, 用 i j k来表示丑数序列中因子2 3 5对应的指针 避免一个丑数同时有多个因子
int tree[N];
int lowbit(int x)
{
return x & (-x);
}
int add(int i, int x)
{
while(i <= n)
{
tree[i] += x;
i += lowbit(i);
}
}
int query(int i)
{
int sum = 0;
while(i > 0)
{
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
代码如下：
class Solution {
public:
static const int N = 100010;
int n;
int tree[N];
vector<int> q;
public:
int lowbit(int x)
{
return x & -x;
}
void add(int i, int x)
{
while(i <= n)
{
tree[i] += x;
i += lowbit(i);
}
}
int query(int i)
{
int sum = 0;
while(i > 0)
{
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
int find(int x)
{
return lower_bound(q.begin(), q.end(), x) - q.begin() + 1;
}
vector<int> countSmaller(vector<int>& nums) {
n = nums.size();
q = nums;
sort(q.begin(), q.end());
q.erase(unique(q.begin(), q.end()), q.end());
vector<int> res(n);
// 1. 插入树状数组
for(int i = n - 1; i >= 0; i--)
{
int idx = find(nums[i]);
res[i] = query(idx - 1);
add(idx, 1);
}
return res;
}
};
316 - 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置)
