LeetCode weekly contest 236

发表于 分类于 阅读英文版
三道题统计乘积符号、求约瑟夫环赢家，并用自底向上的动态规划计算最少侧跳；第四题未展开。

YoungForest · https://youngforest.github.io/2021/04/11/LeetCode-weekly-contest-236/

文章目录 · 4 节
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
1513 / 12115 YoungForest 12 0:45:18 0:02:57 0:08:59 0:40:18 1 null
正负砝码决定天平方向，圆环座位逐轮退出，三车道小车侧跳避障，最后一座工作台仍留空

1822. Sign of the Product of an Array

签到题。多少负数，是否有0。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def arraySign(self, nums: List[int]) -> int:
        x = 1
        for i in nums:
            x *= i
        if x > 0:
            return 1
        elif x == 0:
            return 0
        else:
            return -1

时间复杂度: O(N),
空间复杂度: O(1).

1823. Find the Winner of the Circular Game

经典的约瑟夫环问题。随便Google了一个: 约瑟夫环——公式法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int cir(int n,int m)
    {
        int p=0;
        for(int i=2;i<=n;i++)
        {
            p=(p+m)%i;
        }
        return p+1;
    }
public:
    int findTheWinner(int n, int k) {
        return cir(n, k);
    }
};

时间复杂度: O(N),
空间复杂度: O(1).

1824. Minimum Sideway Jumps

动态规划。

dp[i][j] 表示从i的位置，第j个lane 到末尾需要的最小side jumps.
需要注意的是 本题N <= 5 * 10^5，Python TOP-BOTTOM的DP会爆栈。
因此比赛时Runtime Error一次，加了
sys.setrecursionlimit(110000)仍然不行，遂改成了Bottom-Up 的DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        n = len(obstacles) - 1
        dp = [[float('inf')] * 4 for i in range(n + 1)]
        dp[n][1] = dp[n][2] = dp[n][3] = 0
        for i in range(n - 1, -1, -1):
            for j in (1, 2, 3):
                if obstacles[i+1] != j:
                    dp[i][j] = min(dp[i][j], dp[i+1][j])
                for nj in (1, 2, 3):
                    if j == nj: continue
                    if obstacles[i] != nj and obstacles[i+1] != nj:
                        dp[i][j] = min(dp[i][j], dp[i+1][nj] + 1)
        return dp[0][2]

时间复杂度: O(N),
空间复杂度: O(1).

1825. Finding MK Average