LeetCode BitWeek 139

3285. 找到稳定山的下标

1
2
3
4
5
6
7
class Solution:
    def stableMountains(self, height: List[int], threshold: int) -> List[int]:
        stable = []
        for i, x in enumerate(height):
            if i > 0 and height[i - 1] > threshold:
                stable.append(i)
        return stable

3286. 穿越网格图的安全路径

经典 BFS + dp，设 dp[x][y][h] 表示到达 (x, y) 时剩余 h 血量是否被走过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int n = static_cast<int>(grid.size());
        int m = static_cast<int>(grid[0].size());

        const static std::vector<int> dx {1, 0, -1, 0};
        const static std::vector<int> dy {0, 1, 0, -1};

        std::vector<std::vector<std::vector<bool>>> visited(n, std::vector<std::vector<bool>>(m, std::vector<bool>(health + 1)));

        std::queue<std::array<int, 3>> q;
        q.push({0, 0, health - grid[0][0]});
        visited[0][0][health] = true;

        while (!q.empty()) {
        	auto [x, y, h] = q.front();
        	q.pop();
        	if (h <= 0) {
        		continue;
        	}
        	if (x == n - 1 and y == m - 1) {
        		return true;
        	}

        	for (int i = 0; i < 4; i += 1) {
        		int nx = x + dx[i];
        		int ny = y + dy[i];
        		if (nx < 0 or nx >= n or ny < 0 or ny >= m or h - grid[nx][ny] <= 0 or visited[nx][ny][h - grid[nx][ny]]) {
        			continue;
        		}
        		q.push({nx, ny, h - grid[nx][ny]});
                visited[nx][ny][h - grid[nx][ny]] = true;
        	}
        }

        return false;
    }
};

3287. 求出数组中最大序列值

  • 前后缀分解 + dp
  • 设 prefix_or[i][j][mask] 表示 1-i 个数中选 j 个数，使得这 j 个数的或值为 mask。
  • 设 suffix_or[i][j][mask] 表示 i-n 个数中选 j 个数，使得这 j 个数的或值为 mask。
  • if (prefix_or[i][k][mask1] && suffix_or[i + 1][k][mask2]) ans = std::max(ans, mask1 ^ mask2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int STATE = 1 << 7;
bool prefix_or[402][201][STATE];
bool suffix_or[402][201][STATE];

class Solution {
public:
    int maxValue(vector<int>& a, int k) {
        int n = static_cast<int>(a.size());

        for (int i = 1; i <= n + 1; i += 1) {
        	for (int j = 0; j <= k; j += 1) {
        		for (int mask = 0; mask < STATE; mask += 1) {
        			prefix_or[i][j][mask] = suffix_or[i][j][mask] = false;
        		}
        	}
        }
    
        prefix_or[0][0][0] = true;
        suffix_or[n + 1][0][0] = true;

        for (int i = 1; i <= n - k; i += 1) {
        	for (int j = 0; j <= std::min(i, k); j += 1) {
        		for (int mask = 0; mask < STATE; mask += 1) {
    				prefix_or[i][j][mask] = prefix_or[i][j][mask] | prefix_or[i - 1][j][mask];
        			if (j)
	        			prefix_or[i][j][mask | a[i - 1]] = prefix_or[i][j][mask | a[i - 1]] | prefix_or[i - 1][j - 1][mask];
        		}
        	}
        }

        for (int i = n; i >= k + 1; i -= 1) {
        	for (int j = 0; j <= std::min(n - i + 1, k); j += 1) {
        		for (int mask = 0; mask < STATE; mask += 1) {
        			suffix_or[i][j][mask] = suffix_or[i][j][mask] | suffix_or[i + 1][j][mask];
        			if (j)
        				suffix_or[i][j][mask | a[i - 1]] = suffix_or[i][j][mask | a[i - 1]] | suffix_or[i + 1][j - 1][mask];
        		}
        	}
        }

        int ans = 0;
        for (int i = k; i + k <= n; i += 1) {
        	for (int mask1 = 0; mask1 < STATE; mask1 += 1) {
        		if (!prefix_or[i][k][mask1]) {
        			continue;
        		}
        		for (int mask2 = 0; mask2 < STATE; mask2 += 1) {
        			if (!suffix_or[i + 1][k][mask2]) {
        				continue;
        			}
    				ans = std::max(ans, mask1 ^ mask2);
        		}
        	}
        }

        return ans;
    }
};

3288. 最长上升路径的长度

  • 二维 LIS，先按照 x 从小到大排序，对于 x 相同的点，按照 y 从大到小排序，保证计算 y 的 LIS 时，相同的 x 最多选一个 y。
  • 选择 x < kx && y < ky 或 x > kx && y > ky 的点，计算 LIS。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maxPathLength(vector<vector<int>>& coordinates, int k) {
    	int n = static_cast<int>(coordinates.size());
    	std::vector<int> order(n);
    	std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int i, int j) {
        	if (coordinates[i][0] == coordinates[j][0]) {
        		return coordinates[i][1] > coordinates[j][1];
        	}
        	return coordinates[i][0] < coordinates[j][0];
        });

        std::vector<int> u;
        for (int i = 0; i < n; i += 1) {
        	if ((coordinates[order[i]][0] < coordinates[k][0] and coordinates[order[i]][1] < coordinates[k][1]) 
        		or (coordinates[order[i]][0] > coordinates[k][0] and coordinates[order[i]][1] > coordinates[k][1])) {
        		auto it = std::lower_bound(u.begin(), u.end(), coordinates[order[i]][1]);
        		if (it == u.end()) {
        			u.push_back(coordinates[order[i]][1]);
        		} else {
        			*it = coordinates[order[i]][1];
        		}
        	}
        }

        return (int) u.size() + 1;
    }
};