第 274 場周賽

Yake1965 2022-01-07 20:23:09 阅读数:363

5967. 檢查是否所有 A 都在 B 之前

Leetcode

class Solution:
def checkString(self, s: str) -> bool:
for i in range(1, len(s)):
if s[i] == 'a' and s[i - 1] == 'b': return False
return True
class Solution {

public boolean checkString(String s) {

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) == 'a' && s.charAt(i - 1) == 'b')
return false;
}
return true;
}
}

5968. 銀行中的激光束數量

Leetcode

class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
res = pre = 0
for s in bank:
c = s.count('1')
if not c: continue
res += pre * c
pre = c
return res
class Solution {

public int numberOfBeams(String[] bank) {

int res = 0, pre = 0;
for (String s: bank) {

int c = 0;
for (int i = 0; i < s.length(); i++){

if (s.charAt(i) == '1') c++;
}
if (c == 0) continue;
res += pre * c;
pre = c;
}
return res;
}
}

5969. 摧毀小行星

Leetcode

class Solution:
def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
asteroids.sort()
for i in asteroids:
if mass >= i: mass += i
else:return False
return True
class Solution {

public boolean asteroidsDestroyed(int mass, int[] asteroids) {

Arrays.sort(asteroids);
long y = mass; // 需要長整形
for (int x: asteroids){

if (y >= x) y += x;
else return false;
}
return true;
}
}

5970. 參加會議的最多員工數

Leetcode

class Solution:
def maximumInvitations(self, A: List[int]) -> int:
res = 0
pairs = []
d = defaultdict(list)
for i, a in enumerate(A):
if A[a] == i:
pairs.append(i)
else:
d[a].append(i)
# print(pairs, d)
@lru_cache(None)
def cal(x):
if d[x] == []:
return 1
mx = 0
for c in d[x]:
mx = max(mx, cal(c))
return mx + 1
for a in pairs:
# print(a, cal(a))
res += cal(a)
# print(res)
def check(i):
dd = {
}
cur = i
while True:
dd[cur] = len(dd)
cur = A[cur]
if cur in d:
for k in dd:
d[k] = -1
break
if cur in dd:
length = len(dd) - dd[cur]
for k, v in dd.items():
if v < len(dd) - length:
d[k] = -1
else:
d[k] = length
break
d = {
}
for i, a in enumerate(A):
if i in d:
continue
else:
check(i)
return max(res, max(d.values()))
class Solution {

public:
int maximumInvitations(vector<int>& p) {

int n = p.size(), ans = 0;
vector<int> v(n), d(n), dp(n, 1);
for (int i = 0; i < n; i += 1) if (not v[i]) {

vector<int> w;
int x = i;
while (not v[x]) {

w.push_back(x);
v[x] = 1;
x = p[x];
}
for (int j = 0; j < w.size(); j += 1) {

if (w[j] == x) {

ans = max((int)w.size() - j, ans);
}
}
}
queue<int> q;
for (int i = 0; i < n; i += 1) d[p[i]] += 1;
for (int i = 0; i < n; i += 1) if (d[i] == 0) {

q.push(i);
}
while (not q.empty()) {

int u = q.front();
q.pop();
dp[p[u]] = max(dp[p[u]], dp[u] + 1);
if (not (d[p[u]] -= 1)) q.push(p[u]);
}
int sum = 0;
for (int i = 0; i < n; i += 1) if (p[p[i]] == i and p[i] > i) sum += dp[i] + dp[p[i]];
return max(ans, sum);
}
};
版权声明:本文为[Yake1965]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072023092727.html