统计
26
26
26 个字符中，每个字符数量
c
n
t
i
cnt_i
cnti ，以及指定的字符串中的
26
26
26 个字符每种数量
n
e
e
d
i
need_i
needi
对于
n
e
e
d
i
>
0
need_i>0
needi>0 的所有字符统计
min
{
⌊
c
n
t
i
n
e
e
d
i
⌋
}
min{lfloorfrac{cnt_i}{need_i}rfloor}
min{⌊needicnti⌋}
class Solution {
public:
int rearrangeCharacters(string s, string target) {
vector cnt(26, 0);
for(auto u : s) cnt[u - 'a'] += 1;
vector need(26, 0);
for(auto u : target) need[u - 'a'] += 1;
int res = 0x3f3f3f3f;
for(int i = 0; i < 26; ++i)
if(need[i] > 0)
res = min(res, cnt[i] / need[i]);
return res;
}
};
B.
细节挺多的小模拟，为了避免精度问题，直接采用了高精度解决
#define sz(x) (int)x.size()
class Solution {
public:
string get(string s, int d) {
vector A;
vector B;
for(int i = (int)s.size() - 1; i >= 0; --i) A.push_back(s[i] - '0');
while(d > 0) B.push_back(d % 10), d /= 10;
vector res(sz(A) + sz(B), 0);
for(int i = 0; i < sz(A); ++i)
for(int j = 0; j < sz(B); ++j)
res[i + j] += A[i] * B[j];
for(int i = 0; i < sz(A) + sz(B) - 1; ++i) {
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
while(sz(res) > 1 && res.back() == 0) res.pop_back();
reverse(res.begin(), res.end());
string ans = "";
for(auto u : res) ans += (u + '0');
if(ans.size() <= 2) {
while(ans.size() < 2) ans = "0" + ans;
ans = "0." + ans;
} else {
ans = ans.substr(0, sz(ans) - 2) + "." + ans[sz(ans) - 2] + ans.back();
}
return ans;
}
string discountPrices(string s, int d) {
string res = "";
int n = s.size();
for(int i = 0; i < n; ++i) {
if(s[i] == '$') {
int j = i + 1;
bool pure = true;
while(j < n && s[j] != ' ') {
if(!isdigit(s[j])) pure = false;
j += 1;
}
if(j - 1 == i) pure = false;
j -= 1;
if(!pure) {
for(int k = i; k <= j; ++k)
res += s[k];
} else {
if(d == 100) {
res += "$0.00";
} else if(d == 0) {
for(int k = i; k <= j; ++k)
res += s[k];
res += ".00";
} else {
res += "$" + get(s.substr(i + 1, j - i), 100 - d);
}
}
i = j;
} else {
res += s[i];
}
}
return res;
}
};
C.
难度很高的思维题
赛时想到的是链表模拟，但是细节实现的不是很好。
后来参考了这篇题解
单调栈解法
int del[2][100010];
int nxt[100010];
int g[2];
class Solution {
public:
int totalSteps(vector& nums) {
int n = nums.size();
g[0] = g[1] = 0;
for(int i = n - 1; i >= 0; --i) {
nxt[i] = i + 1;
if(i + 1 < n && nums[i] > nums[i + 1]) del[0][++g[0]] = i;
}
int u = 0;
int ans = 0;
while(g[u] > 0) {
ans += 1;
int v = u ^ 1;
g[v] = 0;
for(int i = 1; i <= g[u]; ++i) {
int x = del[u][i];
int temp = nxt[x];
nxt[x] = nxt[nxt[x]];
if(nxt[x] < n && nums[x] > nums[nxt[x]]) {
if(g[v] > 0 && del[v][g[v]] == temp) del[v][g[v]] = x;
else del[v][++g[v]] = x;
}
}
u = v;
}
return ans;
}
};
D.
0
−
1
B
F
S
0-1BFS
0−1BFS 问题，使用双端队列实现。
事实上暴力
B
F
S
BFS
BFS也没超时。
class Solution {
public:
int minimumObstacles(vector>& grid) {
int n = grid.size(), m = grid[0].size();
vector> dist(n, vector(m, 0x3f3f3f3f));
deque> q;
dist[0][0] = grid[0][0];
q.push_back({0, 0});
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
while(!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop_front();
for(int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > dist[x][y] + grid[nx][ny]) {
dist[nx][ny] = dist[x][y] + grid[nx][ny];
if(grid[nx][ny]) q.push_back({nx, ny});
else q.push_front({nx, ny});
}
}
}
return dist[n - 1][m - 1];
}
};
暴力 B F S BFS BFS
class Solution {
public:
struct Node {
int x, y, d;
};
int minimumObstacles(vector>& grid) {
int l = 0;
int r = 0;
int n = grid.size(), m = grid[0].size();
vector> dist(n, vector(m, 0x3f3f3f3f));
queue q;
q.push({0, 0, grid[0][0]});
dist[0][0] = grid[0][0];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(!q.empty()) {
Node t = q.front(); q.pop();
int x = t.x, y = t.y, d = t.d;
for(int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > dist[x][y] + grid[nx][ny]) {
dist[nx][ny] = dist[x][y] + grid[nx][ny];
q.push({nx, ny, dist[nx][ny]});
}
}
}
return dist[n - 1][m - 1];
}
};
