wyf

2.1万

Rezarc
KONNG

Michael.

wyf
2个月前
class Solution {
public:
int peakIndexInMountainArray(vector<int>& A) {
int n = A.size();
for (int i = 1; i < n - 1; i++)
if (A[i - 1] < A[i] && A[i] > A[i + 1])
return i;
return -1;
}
};


wyf
2个月前
class Solution {
public:
vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
int n = quiet.size();
vector<vector<int>> edges(n);
vector<int> deg(n, 0);

for (auto &e : richer) {
edges[e[0]].push_back(e[1]);
deg[e[1]]++;
}

queue<int> q;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = i;
if (deg[i] == 0)
q.push(i);
}

while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &v : edges[u]) {
deg[v]--;
if (quiet[ans[v]] > quiet[ans[u]])
ans[v] = ans[u];
if (deg[v] == 0)
q.push(v);
}
}
return ans;
}
};


wyf
2个月前
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
*   public:
*     int guess(string word);
* };
*/
class Solution {
public:
int get(vector<int>& g, vector<bool>& st, int u) {
int res = 0;
for (int i = 0; i < g.size(); i ++ )
if (g[i] == u && st[i])
res ++ ;
return res;
}

void findSecretWord(vector<string>& wordlist, Master& master) {
int n = wordlist.size();
vector<vector<int>> f(n, vector<int>(n));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
for (int k = 0; k < 6; k ++ )
if (wordlist[i][k] == wordlist[j][k])
f[i][j] ++ ;

vector<bool> st(n, true);
for (int i = 0; i < 10; i ++ ) {
int k = -1, t = INT_MAX;
for (int j = 0; j < n; j ++ ) {
if (!st[j]) continue;
int s = 0;
for (int u = 0; u <= 6; u ++ )
s = max(s, get(f[j], st, u));
if (t > s) {
k = j;
t = s;
}
}
int res = master.guess(wordlist[k]);
if (res == 6) break;
st[k] = false;
for (int j = 0; j < n; j ++ )
if (f[k][j] != res)
st[j] = false;
}
}
};


wyf
2个月前
class Solution {
public:
double new21Game(int N, int K, int W) {
if (K == 0) return 1.0;

vector<double> f(N + 1, 0), s(N + 1, 0);
f[0] = s[0] = 1;

for (int i = 1; i <= N; i++) {
int l = max(0, i - W), r = min(K - 1, i - 1);

if (l <= r) {
if (l == 0) f[i] = s[r] / W;
else f[i] = (s[r] - s[l - 1]) / W;
}

s[i] = s[i - 1] + f[i];
}

return s[N] - s[K - 1];
}
};


wyf
2个月前
typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

class Solution {
public:
const int MOD = 1e9 + 7;
vector<vector<int>> rects;

int calc(int a, int b) {
vector<PII> q;
for (auto& r: rects)
if (a >= r[0] && b <= r[2])
q.push_back({r[1], r[3]});
sort(q.begin(), q.end());

int res = 0, st = -1, ed = -1;
for (auto& t: q)
if (t.x > ed) {
res = (res + ed - st) % MOD;
st = t.x, ed = t.y;
} else {
ed = max(ed, t.y);
}
res = (res + ed - st) % MOD;
return res * (LL)(b - a) % MOD;
}

int rectangleArea(vector<vector<int>>& rectangles) {
rects = rectangles;
vector<int> xs;
for (auto& r: rects) {
xs.push_back(r[0]);
xs.push_back(r[2]);
}
sort(xs.begin(), xs.end());
int res = 0;
for (int i = 1; i < xs.size(); i ++ )
res = (res + calc(xs[i - 1], xs[i])) % MOD;
return res;
}
};


wyf
2个月前
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int res = 0;
for (int i = 0; i < seats.size(); i ++ ) {
if (seats[i]) continue;
int j = i + 1;
while (j < seats.size() && !seats[j]) j ++ ;
if (!i) res = max(res, j - i);
if (j == seats.size()) res = max(res, j - i);
res = max(res, (j - i + 1) / 2);
i = j;
}
return res;
}
};


wyf
2个月前
class Solution {
public:
#define LL long long
string shiftingLetters(string S, vector<int>& shifts) {
int n = S.length();
LL tot = 0;
for (int i = n - 1; i >= 0; i--) {
tot += shifts[i];
S[i] = (S[i] - 'a' + tot) % 26 + 'a';
}
return S;
}
};


wyf
2个月前
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<int>> map(n, vector<int>(n, n * n));
vector<vector<int>> f(1 << n, vector<int>(n, n * n));

for (int i = 0; i < n; i++)
for (auto j : graph[i])
map[i][j] = map[j][i] = 1;

for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

for (int i = 0; i < n; i++)
f[1 << i][i] = 0;

for (int S = 0; S < (1 << n); S++)
for (int i = 0; i < n; i++)
if (S & 1 << i)
for (int j = 0; j < n; j++)
if (! (S & (1 << j)))
f[S | (1 << j)][j] = min(f[S | (1 << j)][j], f[S][i] + map[i][j]);

int ans = n * n;
for (int i = 0; i < n; i++)
ans = min(ans, f[(1 << n) - 1][i]);
return ans;
}
};


wyf
2个月前
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
int n = hand.size();
if (n % W != 0)
return false;
multiset<int> s(hand.begin(), hand.end());
multiset<int>::iterator it;
for (int i = 0; i < n / W; i++) {
int st = *s.begin();
for (int j = st; j < st + W; j++) {
it = s.find(j);
if (it == s.end())
return false;
s.erase(it);
}
}
return true;
}
};


wyf
2个月前
class Solution {
public:
int longestMountain(vector<int>& A) {
int n = A.size(), ans = 0;
int last = 0;
bool up = false, down = false;
for (int i = 1; i < n; i++) {
if (A[i] == A[i - 1]) {
last = i;
up = down = false;
}
else if (A[i] > A[i - 1]) { // up
if (down) {
down = false;
last = i - 1;
}
up = true;
}
else {  // down
if (!up) {
last = i;
down = false;
}
else {
down = true;
}
}
if (up && down)
ans = max(ans, i - last + 1);
}
return ans;
}
};