LeetCod刷题笔记
目录
2739.总行驶距离
思路：模拟
模拟即可：
每次循环主油箱减去5升
（1）主箱是有5升油，并且副油箱有油则，主油箱加一，副油箱减一。
（2） 主油箱有5升油，副油箱无油，继续下次循环
（3）主油箱没有5升油，返回，答案加上剩余的主箱油即可
代码
class Solution {
public:
int distanceTraveled(int mainTank, int additionalTank) {
for(int i=mainTank;i>=5;i-=5){
if(additionalTank) {
additionalTank--;
mainTank++;
i++;
}
}
return mainTank*10;
}
};
如果你的代码真是无敌了！那么这件事真的是泰裤辣！！！！！
6890.找出分区值
思路：急转弯
（1）sort排序从小到大
（2）取两两相邻的最小值即可
代码:
class Solution {
public:
int findValueOfPartition(vector<int>& nums) {
int len=nums.size();
sort(nums.begin(),nums.end());
int max_t=INT_MAX;
for(int i=0;i<len-1;i++){
max_t=min(nums[i+1]-nums[i],max_t);
if(max_t==0) return 0;
}
return max_t;
}
};
这件事真的是泰裤辣！！
1254.统计封闭岛屿的数目
思路：DFS
（1）从网格图的第一行、最后一行、第一列和最后一列的所有 0 出发，DFS 访问四方向的 0，并把这些 0 标记成「访问过」。代码实现时可以直接把 0 修改成 1。
（2）然后从剩下的 0 出发，按照同样的方式 DFS 访问四方向的 0，同时把 0 改成 1。每次从一个新的 0 出发（起点），就意味着找到了一个新的封闭岛屿，答案加一。
（3）此外，如果行数或列数不足 3，此时没有封闭岛屿，可以直接返回 0。
代码：
class Solution {
public:
//dfs只管填充
void dfs(vector<vector<int>>& grid,int x,int y){
int hang=grid.size();
int lie=grid[0].size();
if(x<0||y<0||x>=hang||y>=lie||grid[x][y]) return;
grid[x][y]=1; //标记已经遍历过
dfs(grid,x-1,y);
dfs(grid,x+1,y);
dfs(grid,x,y-1);
dfs(grid,x,y+1);
}
int closedIsland(vector<vector<int>>& grid) {
int hang=grid.size();
int lie=grid[0].size();
int count=0;
if(hang<3||lie<3) return 0;
for(int i=0;i<hang;i++){
if(i==0||i==hang-1){
for(int j=0;j<lie;j++){
dfs(grid,i,j);
}
}else{
dfs(grid,i,0);
dfs(grid,i,lie-1);
}
}
for(int i=1;i<hang-1;i++){
for(int j=1;j<lie-1;j++){
if(!grid[i][j]){
count++;
dfs(grid,i,j);
}
}
}
return count;
}
};6447.给墙壁刷油漆
思路：动态规划
dp[i][j]表示墙[0,i]中粉刷至少j面的最小花费，答案应该为dp[n-1][n]。
状态转移
按照01背包的套路，最外层循环是枚举0 <= i < n。内层循环枚举 j（相当于体积）：
（1）付费油漆匠刷墙 i，那么免费油漆匠就会刷另外time[i]面墙，付费油漆匠刷完墙 i 花费为cost[i]，付费和免费两位油漆匠一共刷了time[i]+1面墙。
状态转移方程为 ：dp[i][j]=dp[i-1][j-time[i]-1]+cost[i]
（2）免费油漆匠刷墙i，说明此时付费油漆匠正在刷某一面墙，“墙[0,i]中粉刷至少 j 面的最小花费”与“墙[0,i)中粉刷至少 j 面的最小花费”是一样的。
状态转移方程为：dp[i][j]=dp[i-1][j]。
以上两种情况取较小值进行转移即可。
代码：
class Solution {
public:
int paintWalls(vector<int> &cost, vector<int> &time) {
int n = cost.size(), f[n + 1];
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int i = 0; i < n; i++) {
int c = cost[i], t = time[i] + 1;
for (int j = n; j; j--)
f[j] = min(f[j], f[max(j - t, 0)] + c);
}
return f[n];
}
};
6893.特别的排列
思路：状态DP
首先定义 dfs(i,j) 表示当前可以选的下标集合为 i，上一个选的数的下标是 j 时，可以构造出多少个特别排列。
递归边界：dfs(0,j)=1，表示找到了一个特别排列。
递归入口：dfs(U\{j},j)，其中全集 U={0,1,2,⋯,n−1}。枚举特别排列的第一个数的下标 j，累 加所有 dfs(U\{j},j)，即为答案。
代码：
class Solution {
public:
const int mod=1e9+7;
//取模用
int specialPerm(vector<int>& nums) {
int len=nums.size();
int U=(1<<len)-1;
//全集，1代表还可以进入排列
int flage[U][len];
memset(flage,-1,sizeof(flage));
//标记是否已经判断过
function<int(int,int)> dfs=[&](int i,int j)->int{
if(i==0) return 1;
//整数都用完了
int& res=flage[i][j];
if(res!=-1) return res;
//已经判断过了
int ans=0;
for(int k=0;k<len;++k){
int x=nums[k];
if((i>>k)&1 && ((nums[j]%x)==0||(x%nums[j]==0))){
ans=(ans+dfs(i^(1<<k),k))%mod;
}
}
res=ans;
return res;
};
int res=0;
for(int i=0;i<len;i++){
res = (res + dfs((U)^(1 << i), i)) % mod;
}
return res;
}
}; 
泰裤辣！！
1262.可被三整除的最大和
思路：贪心
由于数组中没有负数，如果整个数组的元素和 s 可以被 3 整除，那么 s 就是最大的元素和。
否则，如果 s 不能被 3 整除，那就看看能否让 s 减去某些 nums[i]，使得 s 可以被 3 整除。
找到所有 nums[i]%3=1 的 nums[i]，放到数组中；
(1)如果 s%3=1：
a1 不为空，那么答案可能是 s−a1[0]
如果 a2中至少有两个数，那么答案可能是 s−a2[0]−a2[1]这两种情况取最大值。
如果没有这样的数，返回0。(2)如果s%3=2：
如果a2不为空，那么答案可能是s−a2[0]；
如果 中至少有两个数，那么答案可能是 s−a1[0]−a1[1]；
这两种情况取最大值。如果没有这样的数，返回 0。
代码：
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int SUM=accumulate(nums.begin(),nums.end(),0);
if(SUM%3==0) return SUM;
vector<int> a[3];
for(int x:nums) a[x%3].push_back(x);
sort(a[1].begin(),a[1].end());
sort(a[2].begin(),a[2].end());
if(SUM%3==2) swap(a[1],a[2]);
int ans=a[1].size()?SUM-a[1][0]:0;
if(a[2].size()>1) ans=max(ans,SUM-a[2][0]-a[2][1]);
return ans;
}
};
- 点赞
- 收藏
- 关注作者
评论（0）