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; } };
思路：急转弯
从小到大sort排序 （1） （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.统计封闭岛屿的数目
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; } };
