17天前
class Solution {
public:
int minCost(string s, vector<int>& cost) {
stack<int> ss;

int cnt = 0;

for(int i = 0; i < s.size(); )
{
int sums = 0;
if(ss.size() && s[ss.top()] == s[i])
{
while(ss.size() && s[ss.top()] == s[i])
{
if(cost[ss.top()] < cost[i])
{
cnt += cost[ss.top()];
ss.pop();
ss.push(i);
}
else
{
cnt += cost[i];
}
i++;
}
}
else
{
ss.push(i);
i++;
}

}
return cnt;
}
};


17天前
class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {

long long cnt = 0;

unordered_map<long long, int> m1;
for(int i = 0; i < nums1.size(); i++)
{
long long n = 1ll*(1ll*nums1[i] * 1ll*nums1[i]);
m1[n]++;
}

for(int j = 0; j < nums2.size(); j++)
{
for(int k = j + 1; k < nums2.size(); k++)
{
if(m1.count(1ll*nums2[j] * nums2[k]))
{
cnt += m1[1ll*nums2[j]* nums2[k]];
//cout << cnt << endl;
}
}
}

unordered_map<long long, int> m2;
for(int i = 0; i < nums2.size(); i++)
{
long long n = 1ll* (1ll*nums2[i] * 1ll*nums2[i]);
m2[n]++;
}

for(int j = 0; j < nums1.size(); j++)
{
for(int k = j + 1; k < nums1.size(); k++)
{
if(m2.count(1ll*nums1[j] * nums1[k]))
{
cnt += m2[1ll*nums1[j]* nums1[k]];
//cout << cnt << endl;
}
}
}

return cnt;
}
};


2个月前

class Solution {
public:
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
vector[HTML_REMOVED] simplifiedFractions(int n) {
vector[HTML_REMOVED] vs;
for(int i = 1; i <= n; i)
{
for(int j = 1; j < i; j
)
{
if(gcd(i,j) == 1)
{
string s1 = to_string(j);
s1 += ‘/’;
s1 += to_string(i);
vs.push_back(s1);
}
}
}
return vs;

}


};

2个月前

class Solution {
public:
int maxPower(string s) {
int max_ = 1;
for(int i = 0; i < s.size(); i)
{
char ch = s[i];
int count = 0;
while(i < s.size()&& s[i] == ch)
{
i
;
count++;
}
if(count > 0)
{
max_ = max(max_,count);
i -= 1;
}
}
return max_;
}
};

2个月前

/
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode
left;
* TreeNode
right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}
* };
/
class Solution {
public:
int count = 0;
void _good(TreeNode
root, int max_)
{
if(root == nullptr)
return;
if(max_ <= root->val)
count++;
max_ = max(max_,root->val);
good(root->left, max);
good(root->right,max);
}
int goodNodes(TreeNode* root) {
if(root == nullptr)
return 0;
_good(root,root->val);

    return count;
}


};

2个月前

class Solution {
public:
map[HTML_REMOVED] m;
void dfs(string str, int k, int index)
{
if(str.size() == k)
{
m[str] = true;
return ;
}
str += ‘0’;
dfs(str,k,index + 1);

    str.pop_back();
str += '1';
dfs(str,k,index + 1);
}
bool hasAllCodes(string s, int k) {
//map<string,bool> m;

dfs("",k,0);

unordered_set<string> ms;
for(int i = 0; i + k <= s.size(); i++)
{
ms.insert(s.substr(i,k));
}

return ms.size() == 1 << k;
}


};

2个月前

class Solution {
public:
vector[HTML_REMOVED] checkIfPrerequisite(int n, vector[HTML_REMOVED]>& prerequisites, vector[HTML_REMOVED]>& queries) {

    vector<bool> vb(queries.size());
vector<vector<bool>> g(n,vector<bool>(n,false));
for(int i = 0; i <prerequisites.size() ; i++)
{
g[prerequisites[i][0]][prerequisites[i][1]] = true;
}

// Floyed 算法
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
for(int k = 0 ; k < n; k++)
{
if(g[k][i] && g[i][j])
g[k][j] = true;
}
}
}

for(int i = 0; i < queries.size(); i++)
{
vb[i] = g[queries[i][0]][queries[i][1]] ;
}
return vb;
}


};

2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


class Solution {
public:
bool canBeEqual(vector[HTML_REMOVED]& target, vector[HTML_REMOVED]& arr) {
map[HTML_REMOVED] m;
for(int i = 0 ; i < target.size(); i)
{
m[target[i]]
;
}
for(int i = 0; i < arr.size(); i++)
{
if(m[arr[i]] == 0)
return false;
m[arr[i]]–;
}
return true;
}
};

2个月前

class Solution {
public:
bool canBeEqual(vector[HTML_REMOVED]& target, vector[HTML_REMOVED]& arr) {
map[HTML_REMOVED] m;
for(int i = 0 ; i < target.size(); i)
{
m[target[i]]
;
}
for(int i = 0; i < arr.size(); i++)
{
if(m[arr[i]] == 0)
return false;
m[arr[i]]–;
}
return true;
}
};

2个月前

class Solution {
public:

// 7.18 二刷  开数组 max_ - min_的形式 会 内存溢出
// 所以还是map的方法 。。。
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
map<int,int> m;
for(auto e : arr)
{
m[e]++;
}
vector<int> v;
for(auto e: m)
{
v.push_back(e.second);
}
sort(v.begin(),v.end());
int sum = 0;
int ans = 0;
for(int i = 0; i < v.size(); i++)
{
if(sum + v[i] <= k)
{
sum += v[i];
ans++;
}
else
{
break;
}
}
return v.size() - ans;
}


};