Carlo

3.7万

Carlo
2天前
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<double,vector<double>,greater<double>> q;
double ans = 1;
for(int i = 1;i < n;i ++){
q.push(ans * 2);
q.push(ans * 3);
q.push(ans * 5);
ans = q.top();
while(!q.empty() && ans == q.top()) q.pop();
}
return ans;
}
};


Carlo
11天前
class Solution {
public:
int trap(vector<int>& height) {
if(height.) return;
int n = height.size();
vector<int> left(n),right(n);
left[0] = height[0],right[n - 1] = height[n - 1];
for(int i = 1;i < n;i ++) left[i] = max(left[i - 1],height[i]);
for(int i = n - 2;i >= 0;i --)
right[i] = max(right[i + 1],height[i]);
int res = 0;
for(int i = 0;i < n;i ++)
res += min(left[i],right[i]) - height[i];
return res;
}
};


Carlo
11天前
class Solution {
public:
int longestCommonSubsequence(string s1, string s2) {
s1 = " " + s1,s2 = " " + s2;
vector<vector<int>> f(1010,vector<int>(1010,0));
for(int i = 1;i <= s1.size();i ++){
for(int j = 1;j <= s2.size();j ++)
{
f[i][j] = max(f[i - 1][j],f[i][j - 1]);
if(s1[i] == s2[j]) f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);
}
}
return f[s1.size() - 1][s2.size() - 1];
}
};


Carlo
12天前
class Solution {
public:
int clumsy(int N) {
int index = 0;
stack<int> stk;
stk.push(N);
N --;
while(N > 0){
if(index % 4 == 0){
stk.top() *= N;
}else if(index % 4 == 1){
stk.top() /= N;
}else if(index % 4 == 2){
stk.push(N);
}else{
stk.push(-N);
}
index ++;
N --;
}
int sum = 0;
while(!stk.empty()){
sum += stk.top();
stk.pop();
}
return sum;
}
};


Carlo
12天前
class Solution {
public:
unordered_map<int,int> cnt;
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
for(auto x : nums) cnt[x] ++;
dfs(-10);
return ans;
}

void dfs(int u){
if(u > 10) ans.push_back(path);
else {
// 0 1 2 ... cnt[u] + 1种选法
for(int i = 0;i < cnt[u] + 1;i ++){
dfs(u + 1);
path.push_back(u);
}
for(int i = 0;i < cnt[u] + 1;i ++){
path.pop_back();
}
}
}
};


Carlo
15天前
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for(int i = 0;i < 32;i ++){
res = res * 2 + (n >> i & 1);
}
return res;
}
};


Carlo
15天前
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = 0,n = matrix.size(),m = matrix[0].size();
for(int i = 0;i < n;i ++)
if(matrix[i][0] > target && (i - 1) >= 0)
{
row = i - 1;
break;
}else if(matrix[i][0] == target){
// row = i;
return true;
}else if(i == n - 1){
row = i;
}
for(int i = 0;i < m;i ++)
if(matrix[row][i] == target) return true;
return false;
}
};


Carlo
15天前

Carlo
16天前
class Solution {
public:
vector<int> p;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
unordered_map<string,vector<int>> hash;
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n = accounts.size();
for(int i = 0;i < n;i ++) p.push_back(i);
for(int i = 0;i < n;i ++)
for(int j = 1;j < accounts[i].size();j ++)
hash[accounts[i][j]].push_back(i);
for(auto& [k,v] : hash)
for(int i = 0;i < v.size();i ++)
p[find(v[i])] = find(v[0]);
vector<set<string>> res(n);
for(int i = 0;i < n;i ++)
for(int j = 1;j < accounts[i].size();j ++)
res[find(i)].insert(accounts[i][j]);
vector<vector<string>> ans;
for(int i = 0;i < n;i ++)
{
if(res[i].size()){
vector<string> t;
t.push_back(accounts[i][0]);
for(auto e:res[i]) t.push_back(e);
ans.push_back(t);
}
}
return ans;
}
};


Carlo
16天前
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for(int i = 0;i < 32;i ++){
res = res * 2 + (n >> i & 1);
}
return res;
}
};