每日算法刷题Day25 6.7:leetcode二分答案3道题，用时1h40min(遇到两道动态规划和贪心时间较长)

3. 1631.最小体力消耗路径(中等,dfs不熟练)

1631. 最小体力消耗路径 - 力扣（LeetCode）

思想

1.你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
2.单调性检验：二分答案的是体力消耗值(最大高度差绝对值)，如果它越小，越不容易满足条件，所以有个最小值，而一旦一个值满足条件，大于它的值一定满足条件，符合单调性
3.dfs注意点:
(1)用vis数组记录已访问过的元素，避免重复反复，但是不要回溯
(2)dfs返回值是bool，这个用作判断条件，而不是直接return，避免找到一条可能路径就退出

if (dfs(heights, nx, ny, mid,vis)) { // 写判断条件而不是写return dfs(heights, nx, ny,// mid, vis),不然不会搜索其他路径return true;
}

代码

c++:

class Solution {
private:vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};public:bool inmap(int x, int y, int n, int m) {return 0 <= x && x < n && 0 <= y && y < m;}bool dfs(vector<vector<int>>& heights, int x, int y, int mid,vector<vector<bool>>& vis) {int n = heights.size(), m = heights[0].size();if (x == n - 1 && y == m - 1)return true;vis[x][y] = true; // 避免重复遍历for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (!inmap(nx, ny, n, m) || vis[nx][ny])continue;if (abs(heights[x][y] - heights[nx][ny]) <= mid) {if (dfs(heights, nx, ny, mid,vis)) { // 写判断条件而不是写return dfs(heights, nx, ny,// mid, vis),不然不会搜索其他路径return true;}}}// vis[x][y]=false; //不需要回溯return false;}bool check(vector<vector<int>>& heights, int mid) {int n = heights.size(), m = heights[0].size();vector<vector<bool>> vis(n, vector<bool>(m, false));if (dfs(heights, 0, 0, mid, vis))return true;elsereturn false;}int minimumEffortPath(vector<vector<int>>& heights) {check(heights, 2);int left = 0, right = INT_MIN, res = 0;for (int i = 0; i < heights.size(); ++i) {for (int j = 0; j < heights[0].size(); ++j) {if (j + 1 < heights[0].size())right = max(right, abs(heights[i][j + 1] - heights[i][j]));if (i + 1 < heights.size())right = max(right, abs(heights[i + 1][j] - heights[i][j]));}}while (left <= right) {int mid = left + ((right - left) >> 1);if (check(heights, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

4. 2560.打家劫舍IV(中等，学习动态规划和贪心证明)

2560. 打家劫舍 IV - 力扣（LeetCode）

思想

1.沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i]美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
2.单调性检验:二分答案是偷窃能力，偷窃能力越小，越不容易偷到k间房屋，所以存在一个最小值，而一旦一个值满足条件，大于它的值肯定满足条件，符合单调性
3.我的思路是dfs取搜索，但是会存在重复子问题(比如连续两个房屋都可以偷，但他们后面偷的房屋都一样，连续的第2个就要再求解重复子问题了)，会超时，所以要用动态规划来消除冗余，解决重复子问题
4.学习动态规划:

• 状态定义:f[i]表示到第i间房屋可以偷的房屋数量，所以最终答案是f[n-1]
• 初始状态:如果nums[0]<=mid,则f[0]=1,否则f[0]=0,f1为1的情况是n>1 && (nums[1]<=mid || f[0]=1)
• 状态转移方程:
  (1)nums[i]>mid,说明第i家不可以偷，f[i]=f[i-1]
  (2)nums[i]<=mid,说明第i家可以偷，偷的话f[i]=f[i-2]+1,所以综上,f[i]=max(f[i-1],f[i-2]+1)(取最大的)
• 遍历方式:i从2遍历到n-1即可
  5.学习贪心
  上式:
  f[i]=max(f[i-1],f[i-2]+1)说明f[i]>=f[i-1],而f[i]至多比f[i-1]多1，所以f[i-1]+1>=f[i],即f[i-2]+1>=f[i-1],所以f[i]=f[i-2]+1,此式说明能偷则偷，最终答案是最大的

代码

c++:
我的dfs:

class Solution {
public:bool dfs(int x, vector<int>& nums, int k, int mid, int cnt) {if (cnt == k)return true;int n = nums.size();for (int i = x + 2; i < n; ++i) {if (nums[i] <= mid) {if (dfs(i, nums, k, mid, cnt + 1))return true;}}return false;}bool check(vector<int>& nums, int k, int mid) {int n = nums.size();int id = 0;for (int i = 0; i < n; ++i) {if (nums[i] <= mid) {id = i;break;}}if (dfs(id, nums, k, mid, 1) ||(id + 1 < n && nums[id + 1] <= mid && dfs(id + 1, nums, k, mid, 1)))return true;elsereturn false;}int minCapability(vector<int>& nums, int k) {int n = nums.size();int res = 0, left = INT_MAX, right = INT_MIN;for (const int x : nums) {left = min(left, x);right = max(right, x);}while (left <= right) {int mid = left + ((right - left) >> 1);if (check(nums, k, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

学习动态规划:

class Solution {
public:bool check(vector<int>& nums, int k, int mid) {int n = nums.size();vector<int> f(n, 0);if (nums[0] <= mid)f[0] = 1;// f[1]情况复杂一点if (n > 1 && (nums[1] <= mid || f[0] == 1))f[1] = 1;for (int i = 2; i < n; ++i) {f[i] = f[i - 1];if (nums[i] <= mid) {f[i] = max(f[i - 1], f[i - 2] + 1);}}if (f[n - 1] >= k)return true;elsereturn false;}int minCapability(vector<int>& nums, int k) {check(nums, k, 2);int n = nums.size();int res = 0, left = INT_MAX, right = INT_MIN;for (const int x : nums) {left = min(left, x);right = max(right, x);}while (left <= right) {int mid = left + ((right - left) >> 1);if (check(nums, k, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

学习贪心:

bool check(vector<int>& nums, int k, int mid) {int n = nums.size();int cnt = 0, i = 0;while (i < n) {if (nums[i] <= mid) {++cnt; // 能偷则偷if (cnt >= k)return true;i += 2;} else++i;}return false;
}

5. 2616.最小化数对的最大差值(中等，学习动态规划和贪心)

2616. 最小化数对的最大差值 - 力扣（LeetCode）

思想

1.给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
2.单调性检验:二分答案的是最大差值，该值越小，越不能选择p个下标对，所以存在一个最小值，而一旦一个值成立，大于它的值一定满足条件
3.我想到先排序，但是无法证明就是选连续两个就是最优的，下面还是先写动态规划式子，然后能证明贪心最优
4.动态规划(与2560.打家劫舍IV一模一样):

• 状态定义:f[i]在nums前i个数 中选择的最多有序对,所以答案为f[n-1]
• 初始状态:f[0]=0,f[1]=1的条件为n>1 && abs(nums[1]-nums[0]<=mid)
• 状态转移方程:
  (1)nums[i]与nums[i-1]不能选，即abs(nums[i]-nums[i-1])>mid,f[i]=f[i-1]
  (2)nums[i]与nums[i-1]能选，即abs(nums[i]-nums[i-1])<=mid,f[i]=max(f[i-1],f[i-2]+1)
• 遍历顺序:i从2开始到n-1
  5.贪心证明:
  f[i]=max(f[i-1],f[i-2]+1),而f[i-1]与f[i-2]最多差1，所以f[i-2]+1>=f[i-1],所以f[i]=f[i-2]+1,说明有连续两个满足条件就直接选择即可，满足贪心条件

代码

c++:
动态规划:

class Solution {
public:bool check(vector<int>& nums, int p, int mid) {int n = nums.size();vector<int> f(n, 0); // f[i]表示前i个元素中最多能选出的数对数f[0] = 0;if (n > 1 && abs(nums[1] - nums[0]) <= mid)f[1] = 1;for (int i = 2; i < n; ++i) {f[i] = f[i - 1];if (abs(nums[i] - nums[i - 1]) <= mid) {f[i] = max(f[i], f[i - 2] + 1);}}if (f[n - 1] >= p)return true;elsereturn false;}int minimizeMax(vector<int>& nums, int p) {int n = nums.size();int res = 0, left = 0, right = 0;sort(nums.begin(), nums.end());right = nums[n - 1] - nums[0];while (left <= right) {int mid = left + ((right - left) >> 1);if (check(nums, p, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

贪心:

bool check(vector<int>& nums, int p, int mid) {if (p == 0)return true;int n = nums.size();int cnt = 0;int i = 0;while (i + 1 < n) {if (abs(nums[i] - nums[i + 1]) <= mid) {++cnt;if (cnt >= p)return true;i += 2;} else++i;}return false;
}