Citadel白嫖OA自己写&整理的答案，求加米

就那几道题，希望大家给我加一下米。有不对的地方还请指出

#1-4去年的
#1.A longest subarray that sums to less than or equal to a given value k
# only non-negative numbers
def solution1(nums: List[int], k: int) -> int:
    l, r, ans, n = 0, 0, 0, len(nums)
    window = 0
    while r < n:
        window += nums[r]
        r += 1
        while l < n and window > k:
            window -= nums[l]
            l += 1
        ans = max(ans, r - l)
    return ans
print('1------------------')
print(solution1([1,2,4,2,7,2,1,5,6,12,7,2,1,3,2,3,4,5,6,3,2,4,6,5], 18))
print(solution1([9, 1, 2, 3, 4, 5], 7))
print('1. follow up')

# can handle negative numbers
#(a) the current window sum exceeds k and (b) the remainder of the array cannot possibly decrease the value any more
def solution1_follow_up(nums: List[int], k: int) -> int:
    l, r, ans, n = 0, 0, 0, len(nums)
    window, rn, negs = 0, 0, [0] * n
    for i in range(n - 1, -1, -1):
        negs[i] = rn
        rn = min(0, rn + nums[i])
    while r < n:
        window += nums[r]
        while l < n and window + negs[r] > k:
            window -= nums[l]
            l += 1
        r += 1
        ans = max(ans, r - l)
    return ans
print(solution1_follow_up([1,2,4,2,7,2,1,5,6,12,7,2,1,3,2,3,4,5,6,3,2,4,6,5], 18))
print(solution1_follow_up([9, 1, 2, 3, 4, 5], 7))
print(solution1_follow_up([1, 2, 1, 0, 1, -8, -9, 0], 4))
print(solution1_follow_up([5, -10, 7, -20, 57], -22))
print(solution1_follow_up([-5, 8, -14, 2, 4, 12], 5))
print(solution1_follow_up([1, 2, 1, 0, 1, -8, -9, 0], 4))


#2 Find the number of K-subarray i.e: sum of a subarray % k == 0
#subarraysDivByK 974
def subarraysDivByK(nums: List[int], k: int) -> int:
    n = len(nums)
    preSum, mp, ans = 0, {0:1}, 0
    for i in range(n):
        preSum += nums[i]
        mod = preSum % k
        ans += mp.get(mod, 0)
        mp[mod] = mp.ge

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

        self.count(node.right)

#8 Knight Moves
class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        if x == 0 and y == 0:
            return 0
        x = abs(x) #关于（0,0）对称
        y = abs(y)
        Q = deque()
        Q.append((0, 0))
        visited = set()
        visited.add((0, 0))
        step = 0
        while Q:
            cur_len = len(Q)
            step += 1
            for _ in range(cur_len):
                (x0, y0) = Q.popleft()
                for dx, dy in ((-2,1), (-2,-1), (-1,2), (-1,-2), (1,2), (1,-2), (2,1), (2,-1)):
                    nx = x0 + dx
                    ny = y0 + dy
                    if (nx, ny) not in visited:
                        if -1 <= nx <= x + 2 and -1 <= ny <= y + 1:
                            if nx == x and ny == y:
                                return step
                            else:
                                Q.append((nx, ny))
                                visited.add((nx, ny))

#9 first lady of software
def FindNumberOfWays(n_processes, n_interval):
    if n_processes == 1:
        return 1 if n_interval == 1 else 0
    return n_processes * pow(n_processes - 1, n_interval - 1) % (10**9 + 7)

什么大善人😭给你加多多的米