【每日刷题】Day145
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 375. 猜数字大小 II - 力扣（LeetCode）
2. LCR 112. 矩阵中的最长递增路径 - 力扣（LeetCode）
3. 75. 颜色分类 - 力扣（LeetCode）
1. 375. 猜数字大小 II - 力扣（LeetCode）
//思路：记忆化搜索（dfs+备忘录(哈希)+剪枝）
class Solution {
public:
int dfs(int left,int right,vector<vector<int>>& hash)//left、right维护区间
{
if(left>=right) return 0;//当区间不存在或区间内只有一个值时，猜到了数字；返回0是因为我们不需要支付猜到了的数字的金钱
if(hash[left][right]!=-1) return hash[left][right];//如果当前路径已经找过，则无需再次查找，直接返回这条路径记录的最小金额
int ret = INT_MAX;
for(int head = left;head<=right;head++)
{
int l = dfs(left,head-1,hash);//左区间查找
int r = dfs(head+1,right,hash);//右区间查找
ret = min(ret,head+max(l,r));//max(l,r)是左、右区间最坏情况所需要花费的金额
//min(ret,head+max(l,r))是最终所需花费的最少金额
}
hash[left][right] = ret;//备忘录，用于记录已经找过的路径的最小金额
return ret;
}
int getMoneyAmount(int n)
{
vector<vector<int>> hash(n+1,vector<int>(n+1,-1));
return dfs(1,n,hash);
}
};
2. LCR 112. 矩阵中的最长递增路径 - 力扣（LeetCode）
//思路：记忆化搜索
//本题看似是困难题，实则与前面 记忆化搜索 和 floodfill 的题一模一样，这里不再画图讲解。
class Solution {
public:
int row,col;
int hash[201][201] = {0};
int dx[4] = {0,0,1,-1};//x坐标变化范围
int dy[4] = {1,-1,0,0};//y坐标变化范围
int dfs(vector<vector<int>>& matrix,int i,int j)
{
if(hash[i][j]) return hash[i][j];//这条路径查找过，无需重复dfs，直接返回长度
int ret = 1;
for(int k = 0;k<4;k++)
{
int x = i+dx[k],y = j+dy[k];//从该位置上、下、左、右查找
if(x<row&&x>=0&&y<col&&y>=0&&matrix[x][y]>matrix[i][j])
ret = max(ret,dfs(matrix,x,y)+1);//记录最大路径
}
hash[i][j] = ret;//记录当前查找过的路径的长度
return ret;
}
int longestIncreasingPath(vector<vector<int>>& matrix)
{
int ret = 1;
row = matrix.size(),col = matrix[0].size();
for(int i = 0;i<row;i++)
{
for(int j = 0;j<col;j++)//以每一个位置为起点进行 dfs 查找，记录最长路径
ret = max(ret,dfs(matrix,i,j));
}
return ret;
}
};
3. 75. 颜色分类 - 力扣（LeetCode）
//思路：分治(三指针)
class Solution {
public:
void swap(int& x,int& y)
{
int tmp = x;
x = y;
y = tmp;
}
void sortColors(vector<int>& nums)
{
int i = 0,left = -1,right = nums.size();
while(i<right)//结束条件必须为 i < right
{
if(!nums[i]) swap(nums[++left],nums[i++]);//遍历到0的情况
else if(nums[i]==2) swap(nums[--right],nums[i]);//遍历到2的情况
else i++;//遍历到1的情况
}
}
};
