sep

hhh联盟

1.3万

AcWing2AK

WangJY
cyz3209
Gzm1317
Justice
LJ24PengHR

ZDC
xkf
Lurrick
ustc-lj

DPH

RyanMoriarty
M4LLKN0W
Kafuu_Chino

sep
5天前
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& g) {
vector<vector<int>> res;
unordered_map<int, vector<int>> hash;
for (int i = 0; i < g.size(); i ++ ) {
hash[g[i]].push_back(i);
if (hash[g[i]].size() == g[i]) {
res.push_back(hash[g[i]]);
hash[g[i]] = {};
}
}
return res;
}
};


sep
1个月前
class Solution {
public:
int maxProfit(vector<int>& p) {
int n = p.size();
vector<vector<int>> f(n + 1, vector<int>(3, INT_MIN));
f[0][1] = 0;
for (int i = 1; i <= n; i ++ ) {
f[i][0] = max(f[i - 1][0], f[i - 1][1] - p[i - 1]);
f[i][1] = max(f[i - 1][1], f[i - 1][2]);
f[i][2] = f[i - 1][0] + p[i - 1];
}
return max(f[n][1], f[n][2]);
}
};


sep
1个月前
const int N = 2510;
int son[N][26], idx, w[N];
class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {
memset(son, 0, sizeof son);
memset(w, 0, sizeof w);
idx = 0;
}

void insert(string key, int val) {
int p = 0;
for (auto c: key) {
int u = c - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
w[p] = val;
}

int sum(string prefix) {
int p = 0, res = 0;
for (auto c: prefix) {
int u = c - 'a';
if (son[p][u]) p = son[p][u];
else return 0;
}
return dfs(p);
}
int dfs(int p) {
int res = w[p];
for (int i = 0; i < 26; i ++ )
if (son[p][i])
res += dfs(son[p][i]);
return res;
}
};

/**
* Your MapSum object will be instantiated and called as such:
* MapSum* obj = new MapSum();
* obj->insert(key,val);
* int param_2 = obj->sum(prefix);
*/


sep
1个月前
class MagicDictionary {
public:
/** Initialize your data structure here. */
struct Node {
bool is_end;
Node* son[26];
Node() {
is_end = false;
memset(son, 0, sizeof son);
}
}*root;

void insert(string w) {
auto p = root;
for (int i = 0; i < w.size(); i ++ ) {
int idx = w[i] - 'a';
if (!p->son[idx]) p->son[idx] = new Node();
p = p->son[idx];
}
p->is_end = true;
}

MagicDictionary() {

}

void buildDict(vector<string> dictionary) {
root = new Node();
for (auto& w : dictionary) {
insert(w);
}
}

bool search(string w) {
return dfs(w, 0, 1, root);
}

bool dfs(string w, int u, int t, Node* p) {
if (u == w.size()) {
if (t == 0 && p->is_end) return true;
return false;
}
if (t < 0) return false;
int idx = w[u] - 'a';
for (int i = 0; i < 26; i ++ ) {
if (p->son[i]) {
if (dfs(w, u + 1, t - (i != idx), p->son[i]))
return true;
}
}
return false;
}
};

/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
*/


sep
1个月前
class Solution {
public:
vector<int> p;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
for (int i = 0; i < 2 * n; i ++ ) p.push_back(i);
for (auto e : edges) {
int a = e[0], b = e[1];
int pa = find(a), pb = find(b);
if (pa == pb) return {a, b};
else p[pa] = pb;
}
return edges[n - 1];
}
};


sep
1个月前
class Solution {
public:
vector<int> p;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool check(string& a, string& b) {
if (a == b) return true;
vector<int> q;
for (int k = 0; k < a.size(); k ++ ) {
if (a[k] != b[k]) {
q.push_back(k);
}
}
if (q.size() != 2) return false;
int x = q[0], y = q[1];
return a[x] == b[y] && a[y] == b[x];
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
for (int i = 0; i < n; i ++ ) {
p.push_back(i);
}
for (int i = 0; i < n; i ++ )
for (int j = i + 1; j < n; j ++ ) {
string a = strs[i], b = strs[j];
if (check(a, b)) {
p[find(i)] = find(j);
}
}
int ans = 0;
for (int i = 0; i < n; i ++ )
if (find(i) == i)
ans ++;
return ans;
}
};


sep
1个月前
const int N = 210;
int p[N];
class Solution {
public:
int n;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int findCircleNum(vector<vector<int>>& isConnected) {
n = isConnected.size();
for (int i = 1; i <= n; i ++ ) {
p[i] = i;
}
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ ) {
int a = i, b = j;
if (isConnected[i - 1][j - 1] == 1) {
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i ++ )
if (find(i) == i) ans ++;
return ans;
}
};


sep
1个月前
const int N = 2010;
class Solution {
public:
vector<int> g[N];
int d[N];
vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
memset(d, 0, sizeof d);
for (auto p : prerequisites) {
int a = p[0], b = p[1];
g[b].push_back(a);
d[a] ++;
}
queue<int> q;
for (int i = 0; i < n; i ++ )
if (!d[i])
q.push(i);

vector<int> res;
while (q.size()) {
auto t = q.front();
q.pop();
res.push_back(t);
for (auto v : g[t]) {
if (--d[v] == 0)
q.push(v);
}
}
if (res.size() != n) return {};
return res;
}
};


sep
1个月前
const int N = 210;
class Solution {
public:
int f[N][N];
int ans = 1, n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<vector<int>> g;
int longestIncreasingPath(vector<vector<int>>& matrix) {
memset(f, -1, sizeof f);
g = matrix;
n = matrix.size(), m = matrix[0].size();
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
ans = max(ans, dfs(i, j));
return ans;
}
int dfs(int x, int y) {
int& v = f[x][y];
if (v != -1) return v;
int res = 1;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y])
res = max(res, dfs(a, b) + 1);
}
return v = res;
}
};


sep
1个月前
class Solution {
public:
int n = 0;
double temp;
double g[30][30];
bool vis[30];
unordered_map<string, int> hash;
int getID(string a) {
if (!hash.count(a)) hash[a] = n ++;
return hash[a];
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
for (int i = 0; i < equations.size(); i ++ ) {
int a = getID(equations[i][0]), b = getID(equations[i][1]);
g[a][b] = values[i], g[b][a] = 1 / values[i];
}
vector<double> res;
for (auto& t : queries) {
string a = t[0], b = t[1];
if (!hash.count(a) || !hash.count(b)) res.push_back(-1);
else {
memset(vis, 0, sizeof vis);
if (dfs(getID(a), getID(b), 1)) res.push_back(temp);
else res.push_back(-1);
}
}
return res;
}
bool dfs(int u, int b, double m) {
if (u == b) {
temp = m;
return true;
}
vis[u] = true;
for (int i = 0; i < n; i ++ ) {
if (g[u][i] != 0 && !vis[i])
if (dfs(i, b, m * g[u][i]))
return true;
}
return false;
}
};