公司的网站可以用个人备案吗,施工企业主要负责人包括,大连网站设计公司,上海十大装修公司品牌Leetcode 第 139 场双周赛题解 Leetcode 第 139 场双周赛题解题目1#xff1a;3285. 找到稳定山的下标思路代码复杂度分析 题目2#xff1a;3286. 穿越网格图的安全路径思路代码复杂度分析 题目3#xff1a;3287. 求出数组中最大序列值思路代码复杂度分析 题目4#xff1a;… Leetcode 第 139 场双周赛题解 Leetcode 第 139 场双周赛题解题目13285. 找到稳定山的下标思路代码复杂度分析 题目23286. 穿越网格图的安全路径思路代码复杂度分析 题目33287. 求出数组中最大序列值思路代码复杂度分析 题目43288. 最长上升路径的长度思路代码复杂度分析 Leetcode 第 139 场双周赛题解
题目13285. 找到稳定山的下标
思路
遍历。
代码
class Solution
{
public:vectorint stableMountains(vectorint height, int threshold){vectorint ans;for (int i 1; i height.size(); i)if (height[i - 1] threshold)ans.push_back(i);return ans;}
};复杂度分析
时间复杂度O(n)其中 n 是数组 height 的长度。
空间复杂度O(n)其中 n 是数组 height 的长度。
题目23286. 穿越网格图的安全路径
思路
广度优先搜索。
代码
#
# lc appleetcode.cn id3286 langpython3
#
# [3286] 穿越网格图的安全路径
## lc codestart
class Solution:def findSafeWalk(self, grid: List[List[int]], health: int) - bool:m, n len(grid), len(grid[0])vis [[False] * n for _ in range(m)]vis[0][0] Truedx [0, 1, 0, -1]dy [1, 0, -1, 0]cachedef dfs(x: int, y: int, h: int) - bool:if h 0:return Falseif x m - 1 and y n - 1 and h 0:return Truefor i in range(4):nx x dx[i]ny y dy[i]if nx 0 and nx m and ny 0 and ny n and vis[nx][ny] False:vis[nx][ny] Trueif dfs(nx, ny, h - grid[nx][ny]):return Truevis[nx][ny] Falsereturn Falsereturn dfs(0, 0, health - grid[0][0])
# lc codeend复杂度分析
时间复杂度O(m * n)其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度O(m * n)其中 m 和 n 分别为 grid 的行数和列数。
题目33287. 求出数组中最大序列值
思路
前后缀分解。
把数组nums 分成左右两部分左部和右部分别计算所有长为 k 的子序列的 OR 都有哪些值。
两两组合计算 XOR取其中最大值作为答案。
代码
/** lc appleetcode.cn id3287 langcpp** [3287] 求出数组中最大序列值*/// lc codestart
class Solution
{
private:static const int MX 1 7;public:int maxValue(vectorint nums, int k){int n nums.size();vectorarraybool, MX pre(k 1);vectorarraybool, MX suf(n - k 1);vectorarraybool, MX dp(k 1);dp[0][0] true;// 状态转移for (int i n - 1; i k; i--){int v nums[i];for (int j min(k - 1, n - 1 - i); j 0; j--){for (int x 0; x MX; x)if (dp[j][x])dp[j 1][x | v] true;}if (i n - k)suf[i] dp[k];}int ans 0;pre[0][0] true;for (int i 0; i n - k; i){int v nums[i];for (int j min(k - 1, i); j 0; j--)for (int x 0; x MX; x)if (pre[j][x])pre[j 1][x | v] true;if (i k - 1)continue;for (int x 0; x MX; x)if (pre[k][x])for (int y 0; y MX; y)if (suf[i 1][y])ans max(ans, x ^ y);}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(nkUnU2其中 n 是数组 nums 的长度U 是数组 nums 所有元素的 OR本题至多为 27−1。DP 是 O(nkU) 的计算 XOR 最大值是 O(U2) 的。
空间复杂度O(nU其中 n 是数组 nums 的长度U 是数组 nums 所有元素的 OR本题至多为 27−1。
题目43288. 最长上升路径的长度
思路
将每个点按横坐标从小到大排序之后我们就只要考虑纵坐标单调递增。因此问题就变成了经过某个点的最长上升子序列有多长。
经过某个点的最长上升子序列可以分成以它为终点的、从左到右看的最长上升子序列加上以它为终点的、从右到左看的最长下降子序列。
注最长上升 / 下降子序列问题可以用二分查找求解。
代码
/** lc appleetcode.cn id3288 langcpp** [3288] 最长上升路径的长度*/// lc codestart
class Solution
{
public:int maxPathLength(vectorvectorint coordinates, int k){int n coordinates.size();vectorarrayint, 3 vec;for (int i 0; i n; i)vec.push_back({coordinates[i][0], coordinates[i][1], i});sort(vec.begin(), vec.end(),[](arrayint, 3 a, arrayint, 3 b){if (a[0] ! b[0])return a[0] b[0];elsereturn a[1] b[1];});int ans -1;// 以规定点为终点的从左到右看的最长上升子序列vectorint dp(n 1, INT_MAX);dp[0] INT_MIN;for (int i 0; i n; i){int head 0, tail n;while (head tail){int mid (head tail 1) 1;if (dp[mid] vec[i][1])head mid;elsetail mid - 1;}dp[head 1] vec[i][1];if (vec[i][2] k){ans head 1;break;}}// 以规定点为终点的从右到左看的最长下降子序列fill(dp.begin() 1, dp.end(), INT_MIN);dp[0] INT_MAX;for (int i n - 1; i 0; i--){int head 0, tail n;while (head tail){int mid (head tail 1) 1;if (dp[mid] vec[i][1])head mid;elsetail mid - 1;}dp[head 1] vec[i][1];if (vec[i][2] k){ans head 1;break;}}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(nlogn)其中 n 是数组 coordinates 的长度。
空间复杂度O(n)其中 n 是数组 coordinates 的长度。
