5003

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

## bfs

class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
unordered_set<string> S;
for (auto str : bank) S.insert(str);
unordered_map<string, int> dist;
dist[start] = 0;

char gene[4] = {'A', 'C', 'G', 'T'};
queue<string> q;
q.push(start);
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = 0; i < t.size(); i ++) {
string a = t;
for (int j = 0; j < 4; j ++) {
a[i] = gene[j];
if (S.count(a) && dist.count(a) == 0) {
dist[a] = dist[t] + 1;
if (a == end) return dist[a];
q.push(a);
}
}
}
}
return -1;
}
};

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

## 双指针

class Solution {
public:
int countSegments(string s) {
int res = 0;
for (int i = 0; i < s.size(); i ++) {
if (s[i] == ' ') continue;
int j = i + 1;
while (j < s.size() && s[j] != ' ') j ++;
res ++;
i = j;
}
return res;
}
};

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

## 贪心选区间

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& q) {
if (q.empty()) return 0;
sort(q.begin(), q.end(), [](vector<int> a, vector<int> b){
return a[1] < b[1];
});

int res = 1, right = q[0][1];
for (int i = 1; i < q.size(); i ++)
if (q[i][0] >= right) {
res ++, right = q[i][1];
}
return q.size() - res;
}
};

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

## 各个击破

class Solution {
public:
string originalDigits(string s) {
vector<char> letter = {'z', 'g', 'h', 'w', 'r', 'f', 'x', 's', 'o', 'i'};
vector<char> number = {'0', '8', '3', '2', '4', '5', '6', '7', '1', '9'};
vector<string> word = {"zero", "eight", "three", "two", "four", "five", "six", "seven", "one", "nine"};

unordered_map<char, int> cnt;
for (auto c : s) cnt[c] ++;

string res;
for (int i = 0; i < 10; i ++) {
int t = cnt[letter[i]];
for (int j = 0; j < t; j ++) res += number[i];
for (auto c : word[i]) {
cnt[c] -= t;
}
}
sort(res.begin(), res.end());
return res;
}
};

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

## 每个点到所有边界的路径中最大值的最小值, 小根堆

class Solution {
public:
struct Cell{
int h, x, y;
bool operator< (const Cell& t) const{
return h > t.h;
}
};

int trapRainWater(vector<vector<int>>& h) { //小根堆
if (h.empty() || h[0].empty()) return 0;
int n = h.size(), m = h[0].size();
priority_queue<Cell> q;
vector<vector<bool>> st(n, vector<bool>(m));
for (int i = 0; i < n; i ++) {
q.push({h[i][0], i, 0});
q.push({h[i][m - 1], i, m - 1});
st[i][0] = st[i][m - 1] = true;
}
for (int i = 0; i < m; i ++) {
q.push({h[0][i], 0, i});
q.push({h[n - 1][i], n - 1, i});
st[0][i] = st[n - 1][i] = true;
}

int res = 0;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while (q.size()) {
auto t = q.top();
q.pop();
res += t.h - h[t.x][t.y];

for (int i = 0; i < 4; i ++) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) {
q.push({max(h[a][b], t.h), a, b});
st[a][b] = true;
}
}
}
return res;
}
};

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

## bfs

class Solution {
public:

string findLexSmallestString(string s, int a, int b) {
unordered_set<string> S;
S.insert(s);
string minv = s;
queue<string> q;
q.push(s);

while (q.size()) {
auto t = q.front();
q.pop();
// cout << t << endl;
if (t < minv) minv = t;
auto t1 = t, t2 = t;
for (int i = 1; i < t.size(); i += 2) t1[i] = (t[i] - '0' + a) % 10 + '0';
if (!S.count(t1)) q.push(t1), S.insert(t1);
t2 = t.substr(t.size() - b) + t.substr(0, t.size() - b);
if (!S.count(t2)) q.push(t2), S.insert(t2);
}
return minv;

}
};

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

## 枚举

class Solution {
public:

vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
vector<int> res(n - 1);
vector<vector<int>> di(n + 1, vector<int>(n + 1, 1e8));
for (auto &e : edges) {
auto a = e[0], b = e[1];
di[a][b] = di[b][a] = 1;
}
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
di[i][j] = min(di[i][j], di[i][k] + di[k][j]);

for (int p = 0; p < 1 << n; p ++) {
vector<int> s;
for (int i = 0; i < n; i ++)
if ((p >> i) & 1) s.push_back(i + 1);
if (s.size() < 2) continue;

int cnt = 0;
for (int i = 0; i < s.size(); i ++)
for (int j = i + 1; j < s.size(); j ++) {
if (link[s[i]][s[j]] == 1) cnt ++;
}
if (cnt < s.size() - 1) continue;
int dist = 0;
for (int i = 0; i < s.size(); i ++)
for (int j = i + 1; j < s.size(); j ++)
dist = max(dist, di[s[i]][s[j]]);
res[dist - 1] ++;

}
return res;
}
};

4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
int n, m;
vector<vector<int>> w, st;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
w = matrix;
if (w.empty() || w[0].empty()) return {};
n = w.size(), m = w[0].size();
st.resize(n, vector<int>(m));

for (int i = 0; i < n; i ++) dfs(i, 0, 1), dfs(i, m - 1, 2);
for (int i = 0; i < m; i ++) dfs(0, i, 1), dfs(n - 1, i, 2);

vector<vector<int>> res;
for (int i = 0; i < n; i ++)
for (int j = 0;j < m; j ++) {
if (st[i][j] == 3) res.push_back({i, j});
}
return res;
}

void dfs(int x, int y, int t) {
if (st[x][y] & t) return;
st[x][y] |= t;
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 && w[a][b] >= w[x][y]) {
dfs(a, b, t);
}
}
}
};

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

## 分类讨论,y总牛逼

class Solution {
public:
int a = 0, b = 0, c = 0, n = s.size(), k = 0;
for (int i = 0; i < n; i ++) {
if (s[i] >= 'a' && s[i] <= 'z') a = 1;
if (s[i] >= 'A' && s[i] <= 'Z') b = 1;
if (s[i] >= '0' && s[i] <= '9') c = 1;
}
k = a + b + c;

if (n < 6) return max(6 - n, 3 - k);
int d[3] = {0}, p = 0, del = n - 20, res = del;
for (int i = 0; i < n;) {
int j = i;
while (j < n && s[j] == s[i]) j ++;
int t = j - i;
p += t / 3;
if (t >= 3) d[t % 3] ++;
i = j;
}
if (n <= 20) return max(p, 3 - k);
if (d[0] && del) {
int t = min(d[0], del);
del -= t;
p -= t;
}
if (d[1] && del) {
int t = min(d[1] * 2, del);
del -= t;
p -= t / 2;
}
if (p && del) {
int t = min(p * 3, del);
p -= t / 3;
}
return res + max(p, 3 - k);
}
};

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

## 统计左上角的个数

class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int res = 0, n = board.size(), m = board[0].size();
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++) {
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
if (board[i][j] == 'X') res ++;
}
return res;
}
};