周赛350（模拟、脑经急转弯、状压DP、动态规划）

您所在的位置：网站首页 › 力扣周赛题目难度 › 周赛350（模拟、脑经急转弯、状压DP、动态规划）

周赛350（模拟、脑经急转弯、状压DP、动态规划）

2023-06-20 18:05| 来源: 网络整理| 查看: 265

文章目录周赛350[2739. 总行驶距离](https://leetcode.cn/problems/total-distance-traveled/)模拟数学 [2740. 找出分区值](https://leetcode.cn/problems/find-the-value-of-the-partition/)转换题意（脑经急转弯） [2741. 特别的排列](https://leetcode.cn/problems/special-permutations/)状态压缩DP[996. 正方形数组的数目](https://leetcode.cn/problems/number-of-squareful-arrays/)（相似） [2742. 给墙壁刷油漆](https://leetcode.cn/problems/painting-the-walls/)选或不选DP

周赛350 2739. 总行驶距离

难度简单4

卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。

该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。

返回卡车可以行驶的最大距离。

注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。

示例 1：

输入：mainTank = 5, additionalTank = 10 输出：60 解释：在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。总行驶距离为 60km 。

示例 2：

输入：mainTank = 1, additionalTank = 2 输出：10 解释：在用掉 1 升燃料后，主油箱变为空。总行驶距离为 10km 。

提示：

1 int ans = 0; while(mainTank >= 5){ ans += 50; mainTank -= 5; if(additionalTank > 0){ additionalTank -= 1; mainTank += 1; } } ans += mainTank * 10; return ans; } } 数学 class Solution { public int distanceTraveled(int mainTank, int additionalTank) { return (mainTank + Math.min(additionalTank, (mainTank-1) / 4)) * 10; } } 2740. 找出分区值

难度中等1

给你一个正整数数组 nums 。

将 nums 分成两个数组：nums1 和 nums2 ，并满足下述条件：

数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。两个数组都非空。分区值最小。

分区值的计算方法是 |max(nums1) - min(nums2)| 。

其中，max(nums1) 表示数组 nums1 中的最大元素，min(nums2) 表示数组 nums2 中的最小元素。

返回表示分区值的整数。

示例 1：

输入：nums = [1,3,2,4] 输出：1 解释：可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4] 。 - 数组 nums1 的最大值等于 2 。 - 数组 nums2 的最小值等于 3 。分区值等于 |2 - 3| = 1 。可以证明 1 是所有分区方案的最小值。

示例 2：

输入：nums = [100,1,10] 输出：9 解释：可以将数组 nums 分成 nums1 = [10] 和 nums2 = [100,1] 。 - 数组 nums1 的最大值等于 10 。 - 数组 nums2 的最小值等于 1 。分区值等于 |10 - 1| = 9 。可以证明 9 是所有分区方案的最小值。

提示：

2 Arrays.sort(nums); int ans = nums[1] - nums[0]; for(int i = 2; i // 定义dfs(i, j) 表示当前可以选的下标集合为 i, 上一个选的数的下标是j, // 转移：从i中选一个下标k // 如果 nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0 // 则 dfs(i, j) += sum(dfs(i\{k}, k) for k in i) // 递归边界：dfs(空集【0】, j) = 1 // 递归到i是空集，说明找到了一个特别的排列 // 递归入口：dfs(U\{j}, j) // 答案： sum(dfs(U\{j}, j) for j in range(n)) // 时间复杂度 = O(状态个数) * O(单个状态的计算时间) // 初始状态下每个数都可以选 ans = (ans + dfs(u ^ (1 // 判断元素k是否在集合i中(是否可以选) if(((i >> k) & 1) == 1){ if(nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0){ // 题目要求 res = (res + dfs(i ^ (1 int n = nums.length; // 定义f[i][j] 表示当前可以选的下标集合为 i, 上一个选的数的下标是j, int[][] f = new int[1 for(int k = 0; k ans = (ans + f[((1 this.nums = nums; n = nums.length; int u = (1 res /= getFactorial(entry.getValue()); } return res; } // 定义dfs(i, j) 表示当前可以选的下标集合为 i, 上一个选的数的下标是j, public int dfs(int i, int j){ if(i == 0) return 1; if(cache[i][j] >= 0) return cache[i][j]; int res = 0; for(int k = 0; k res += dfs(i ^ (1 int cnt = 1; for(int i = 1; i public int numSquarefulPerms(int[] nums) { int n = nums.length; int[][] f = new int[1 for(int k = 0; k res /= getFactorial(entry.getValue()); } return res; } public boolean isSqrt(int x){ int i = (int)Math.sqrt(x); return i * i == x; } public int getFactorial(int x){ int cnt = 1; for(int i = 1; i // 付费的油漆匠选或不选，只有一个付费油漆匠，time[i]需要加起来 // 如果第 i 面墙分配给免费的油漆匠，那么消耗 1 单位的时间 // 定义dfs(i,j)：刷完0 ~ i 的墙，且当前累计付费时间为j（已经赊给免费的时间），最少开销为多少 // 付费：dfs(i,j) = dfs(i-1, j+time[i]) + cost[i] // 免费：dfs(i,j) = dfs(i-1, j-1) // 转移：dfs(i,j) = min(dfs(i-1, j+time[i])+cost[i], dfs(i-1, j-1)) // 递归边界：dfs(-1, i(时间超过了剩下需要刷的墙) // 递归入口：dfs(n-1, 0) int[] cost, time; int[][] cache; int n; public int paintWalls(int[] cost, int[] time) { this.cost = cost; this.time = time; n = cost.length; cache = new int[n][2*n+1]; // 免费时长可以为负数，因此需要加偏移量 for(int i = 0; i

【本文地址】

周赛350（模拟、脑经急转弯、状压DP、动态规划）

周赛350（模拟、脑经急转弯、状压DP、动态规划）

今日新闻

推荐新闻