coorch

coorch
2天前

resNet解决了什么问题？

coorch
3天前

coorch
8天前

# 一面

## 算法部分

### 第二题

acwing1612. 最大正方形

TCP和UDP

# 二面

## 其他问题

resNet解决了什么问题？

coorch
15天前
class Solution:
def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
# 通过将dfs的思路转化为dp，类似记忆化搜索
n = len(locations)
dp = [[0] * n for _ in range(fuel + 1)]
# dp[i][j]表示从j地出发，到finish，拥有汽油为i时的方案数
for i in range(fuel+1):
for j in range(n):
# j就是finish，呆在原地就是一条路
if j == finish:
dp[i][j] = 1
# 类似于dfs，
# 因为每个城市可以经过多次，所以只要还有油，就可以继续去除了j之外的任意位置
# 下一次去k地，汽油还剩i-abs(locations[k] - locations[j])，
for k in range(n):
if k != j:
dis = abs(locations[k] - locations[j])
if i - dis >= 0:
dp[i][j] += dp[i-dis][k]

return dp[fuel][start] % (10**9+7)


coorch
15天前
class Solution:
def minCost(self, s: str, cost: List[int]) -> int:
n = len(s)
res = 0
for i in range(1, n):
if s[i] == s[i-1]:
res += min(cost[i], cost[i-1])
cost[i] = max(cost[i], cost[i-1])
return res


coorch
15天前
class Solution:
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
nums1.sort()
nums2.sort()
ans = 0

m, n = len(nums1), len(nums2)
dict1 = {}

for j in range(n-1):
for k in range(j+1, n):
temp = nums2[j] * nums2[k]
if temp not in dict1:
dict1[temp] = 0
dict1[temp] += 1
for i in range(m):
if nums1[i] * nums1[i] in dict1:
ans += dict1[nums1[i] * nums1[i]]

dict1 = {}
for j in range(m-1):
for k in range(j+1, m):
temp = nums1[j] * nums1[k]
if temp not in dict1:
dict1[temp] = 0
dict1[temp] += 1
for i in range(n):
if nums2[i] * nums2[i] in dict1:
ans += dict1[nums2[i] * nums2[i]]

return ans


coorch
15天前
class Solution:
def modifyString(self, s: str) -> str:
n = len(s)
var = "abcdefghijklmnopqrstuvwxyz"
ans = []

for i in range(n):
if s[i] == '?':
used = set()
if i > 0 and ans[-1] != '?':
if i < n-1 and s[i+1] != '?':
for c in var:
if c not in used:
ans.append(c)
break
else:
ans.append(s[i])

return ''.join(ans)


coorch
17天前
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
# 也就是要找到最长的非递减序列
# 并且因为删除的是连续子数组，所以这个非递减序列一定是以第一个元素开头或以最后一个元素结尾的

# 分别找到左右两侧的非递减序列

# 从第0个元素开始的非递减：arr[:l+1]
l = 0
n = len(arr)
for i in range(1, n):
if arr[i] >= arr[i-1]:
l += 1
else:
break

# 以第n-1个元素结尾的非递减：arr[r:]
r = n-1
for i in range(n-2, -1, -1):
if arr[i] <= arr[i+1]:
r -= 1
else:
break

if l >= r:
return 0

# 右序列都选arr[r:]，左序列取不大于右序列最后一个元素的部分
r_l = n-r
for i in range(l+1):
# 从第0位开始，只要不大于arr[r],这部分就可以合并到右序列中
if arr[i] <= arr[r]:
r_l += 1
else:
break

# 左序列都选，右序列取不小于左序列最后一个元素的部分
l_r = l+1
for i in range(n-1, r-1, -1):
if arr[i] >= arr[l]:
l_r += 1

return n - max(l_r, r_l)



coorch
17天前
class Solution:
def numWays(self, s: str) -> int:
one_count = 0
n = len(s)

for c in s:
if c == '1':
one_count += 1

if one_count == 0:
return int((n-1) * (n-2) // 2 % (1e9 + 7))

if one_count % 3 != 0:
return 0

fir = one_count // 3
sec = 2 * fir
one_count = 0
for i in range(n):
if s[i] == '1':
one_count += 1
if one_count == fir:
f1 = i
if one_count == fir + 1:
f2 = i
if one_count == sec:
s1 = i
if one_count == sec + 1:
s2 = i

return int((f2 - f1) * (s2 - s1)  % (1e9 + 7))


coorch
17天前
class Solution:
def diagonalSum(self, mat: List[List[int]]) -> int:
n = len(mat)
ans = 0
for i in range(n):
ans += mat[i][i]
if n-1-i != i:
ans += mat[i][n-1-i]

return ans