A.
class Solution {
public:
int buyChoco(vector<int>& p, int money) {
sort(p.begin(),p.end());
int x=p[0]+p[1];
if(x>money) return money;
else return money-x;
}
};
B.
爆搜加一点点优化
typedef pair<int,int> PII;
class Solution {
public:
int minExtraChar(string s, vector<string>& d) {
int n=s.size();
int res=INT_MAX;
unordered_map<int,vector<int>> mp;
for(int i=0;i<n;i++)
{
for(auto&ss:d)
{
int m=ss.size();
if(i+m-1<n){
string t=s.substr(i,m);
if(t==ss){
mp[i].push_back(i+m);
}
}
}
}
function<void(int,int)> dfs=[&](int id,int cnt)
{
if(cnt>=res) return ;
if(id>=n)
{
res=min(res,cnt);
return ;
}
for(int i=0;i<mp[id].size();i++){
dfs(mp[id][i],cnt);
}
dfs(id+1,cnt+1);
};
dfs(0,0);
return res;
}
};
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
ans=51
n=len(s)
g=defaultdict(list)
for i in range(n):
for t in dictionary:
m=len(t)
if i+m-1<n and s[i:i+m]==t:
g[i].append(i+m)
def dfs(u:int,cnt:int):
nonlocal ans
if cnt>=ans:return
if u>=n:
ans=min(ans,cnt)
return
for i in g[u]:
dfs(i,cnt)
dfs(u+1,cnt+1)
dfs(0,0)
return ans
C.
贪心这题,但是范围很小比赛直接二进制枚举了
class Solution {
public:
long long maxStrength(vector<int>& nums) {
int n=nums.size();
long long res=0;
if(n==1) return nums[0];
for(int i=0;i<1<<n;i++)
{
long long mx=0;
for(int j=0;j<n;j++)
{
if(i>>j&1)
{
if(mx==0&&nums[j]!=0)
{
mx=nums[j];
}
else
mx=mx*nums[j];
}
}
res=max(res,mx);
}
return res;
}
};
D.并查集+分解质因数
为啥看出并查集,其实题目意思就是问能否通过gcd形成一个集合
so并查集
const int N=1e5+10;
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
unordered_map<int,int> mp;
int n=nums.size();
if(n==1) return true;
vector<int> p(n+1,0),siz(n+1,0);
int res=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,siz[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)
{
siz[b]+=siz[a];
p[a]=b;
res=max(res,siz[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)
{
siz[b]+=siz[a];
p[a]=b;
res=max(res,siz[b]);
}
}
else mp[nums[i]]=find(i);
}
}
return res==n;
}
};