设计响应式网站多少钱,e4a怎么做点击跳转网站,英文网站字体大小,美食网站怎么做dw贪心算法七 1.整数替换2.俄罗斯套娃信封问题3.可被三整除的最大和4.距离相等的条形码5.重构字符串 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;#x1f… 贪心算法七 1.整数替换2.俄罗斯套娃信封问题3.可被三整除的最大和4.距离相等的条形码5.重构字符串 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.整数替换
题目链接 397. 整数替换
题目描述 算法原理
解法一模拟递归 记忆化搜索
假设n 18我们要干的事情是把18变成1最小的步数。因为18是一个偶数只能除2变成9拿到9这个数字要干的其实也是一件相同的事情要把9变成1最小的步数。
此时这里就出现了重复的子问题大问题是18变成1的最小步数18/29后就从了9变成1的最小步数的相同问题。因此我们可以把重复子问题拿到设计出函数头 int dfs(int n) 给一个整数n返回n变成1的最小步数。函数体 其实就是题目给的如果n是偶数/2如果n是奇数要么1要么-1我们求得是最小步数所以是 min(dfs(n-1)dfs(n1))递归出口 当 n 1是之间返回0就行了。 在递归过程中发现大量重复就可以用记忆化搜索建一个数组但是这道题的数据范围是1 n 2^31 - 1我们要开这么大的空间肯定不行因此搞一个hashint,int 第一个参数对应数字n第二个参数对应这个数变成1的最小步数。 class Solution {unordered_mapint,int hash;
public:int integerReplacement(int n) {return dfs(n);}// 递归int dfs(long long n) // 细节问题 数据范围1 n 2^31 - 1 加1会越界{if(n 1){return 0;}if(n % 2 0) // 如果是偶数 {return 1 dfs(n / 2);}else{return 1 min(dfs(n - 1), dfs(n 1));}}// 记忆化搜索int dfs(long long n){if(hash.count(n)){return hash[n];}if(n 1){hash[1] 0;return hash[1];}if(n % 2 0){hash[n] 1 dfs(n / 2);return hash[n];}else{hash[n] 1 min(dfs(n - 1), dfs(n 1));return hash[n];}}
};解法二贪心
补充知识二进制
偶数二进制表示中最后一位是 0奇数二进制表示中最后一位是 1/2 操作二进制表示中统一右移一位
我们这里研究的都是整数。 前两个可以自己举例看看。我们看最后一个 接下来想我们的贪心策略
如果n是偶数没法贪只能执行/2操作
是奇数就可以贪要么执行1要么执行-1操作。 在模拟解法我们就是试试1操作和-1操作看谁最小但是如果在没有试之前就已经知道是1好还是-1好直接让奇数沿着较好的选择走就可以舍去一个选择那我们的时间复杂度会变得更优。
所以我们的贪心就是判断是1好还是-1好。
如何判断分情况讨论
奇数的二进制最后一位是0所以我们可以把奇数分为两大类
第一类前面二进制位是 …最后两个二进制位是 01
第二类前面二进制位是 …最后两个二进制位是 11
其中第一类我们默认 n 1也就是说 … 有1如果没有1的话就是00…01了直接返回即可。第二类默认 n 3。 如果是 …01接下来要么执行1操作要么执行-1操作。 1操作会变成 …10-1操作会变成 …00那到底那个操作好呢? 1和-1操作都会变成偶数偶数只能执行/2操作。假设…01是 …10001执行1操作会变成10010在执行/2操作会变成1001执行-1操作会变成10000在执行/2操作会变成1000。这个时候就可以看出那个操作好了肯定是-1操作好因为1000我们可以一直/2操作尽快得到11001还需要在1和-1操作在/2操作。
所以是奇数二进制最后两位是01就执行-1操作然后/2操作会比较快得到1。
如果是 …11接下来也是要么执行1操作要么执行-1操作分析过程和上面一样。 但是n 3这里有一个意外当 n 3的时候我们需要特殊讨论n 3二进制位前面都是0后面虽然也是11。但是这里我们执行-1操作得到…10然后在执行/2操作直接就变成1了。这个和选择是不一样的。如果执行1操作就会多一步/2操作。 我们这个贪心不用证明分类讨论过程本身就是对这个贪心的证明。
那如何写代码呢
如何判断二进制最后两位是01还是11呢 拿n%4就可以了因为n是奇数%4只能得到1和3如果是1就是01情况如果是3就是11情况。
class Solution {unordered_mapint,int hash;
public:int integerReplacement(int n) {int ret 0;while(n 1){if(n % 2 0){n / 2;ret;}else{if(n 3){ret 2;n 1;}else if(n % 4 1){n n / 2;ret 2;}else{n n / 2 1;ret 2;}}}return ret;}
};2.俄罗斯套娃信封问题
题目链接 354. 俄罗斯套娃信封问题
题目分析 给一个二维数组每一行表示信封的宽度和高度当另一个信封的宽度和高度都比这个信封大的时候这个信封就可以放进另一个信封里如同俄罗斯套娃一样。最多能有多少个 信封能组成一组“俄罗斯套娃”信封即可以把一个信封放到另一个信封里面
算法原理
解法一常规解法通用解法- 动态规划
先对数组排序如果不排序的话去找某一个信封能去套谁的时候既要去它左边找找也要去右边找找。说白了就是要变量数组一遍才能去确定这个信封能去套谁。 但是如果我们把这个数组按照左端点排序后此时在去确定一个信封能去套谁的时候仅需去左边看看就行了。因为如果能套必须满足左大于左右大于右我们已经按左端点排好序右边的左都比当前的左大因此不用考虑右边。 此时我们的最长套娃序列特别像之前的最长递增子序列问题最长递增子序列是在原始的数组中挑选一些数出来形成递增的序列问最长的长度是多少。我们这里是在一些信封里面挑一些信封出来使它能形成一个套娃序列问最长的套娃序列是多少。这个问题就和最长递增子序列一模一样。无非最长子序列是在一个个数中挑我们这里是在一个个信封里面挑。 1.状态表示 dp[i] 表示以 i 位置的信封为结尾的所有套娃序列中最长套娃序列的长度 2.状态转移方程 根据最近一步划分情况
i 位置本身就是套娃序列 长度是1
以 i 位置为结尾的最长套娃长度那么就去 0 ~ i - 1 这段区间遍历一遍找到一个j位置只要发现 i 信封 能套到 j 信封 外面那此时用dp[j]在加上 i 这一个信封就是以 i 位置的信封为结尾套娃序列的长度。找到 0 ~ i -1 区间所有能套的 dp[j] 1 的最大值就是 i 位置的信封为结尾的所有套娃序列中最长套娃序列的长度。 3初始化 数组初始为1就可以不用考虑为的1情况 4.填表顺序 从左往右 5.返回值 dp[i] 表示以 i 位置的信封为结尾的所有套娃序列中最长套娃序列的长度。我们要的是整个区间最长套娃序列的长度所以返回dp表中的最大值。
class Solution {
public:int maxEnvelopes(vectorvectorint e) {// 动态规划sort(e.begin(), e.end());int n e.size();vectorint dp(n, 1);int ret 1;for(int i 1; i n; i){for(int j 0 ; j i; j){if(e[j][0] e[i][0] e[j][1] e[i][1])dp[i] max(dp[i], dp[j] 1);}ret max(ret, dp[i]);}return ret;}
};因为这道题的数据量太大我们的动规会超时但是动规是解决这类题的常规方法。这道题不行不代表相同类型的题不行比如1263. 推箱子这道题用动规是可以通过的。
解法二重写排序 贪心 二分
动态超时了肯定得用贪心 二分了但是为什么多一个重写排序呢?
如果我们仅仅只是按照左端点排序接下来用贪心和二分你会发现我们要分类讨论原因就是之前研究的最长递增子序列只有一个限定条件 只在一堆数中去挑然后贪心保留是长度为1长度为2 … 的最后一个元素的最小值比如长度为25现在来了一个3我们可以把5干掉保留3原因是能跟在5的后面更能跟在3的后面。但是我们这道题给的是一个个区间有的时候我们并不能直接删除有的时候是把之前结果保留而把新来的给删除。虽然能做但是需要分类讨论比较麻烦。所以我们先重写排序在贪心和二分。
下面我们给的是左端点都是不同的排完序后的样子如果左端点不一样我们其实可以把左端点删去。原因就是左端点都不一样我们还按照左端点从小到大排好序了那就相当于前面的是严格递增所以不考虑前边信封左端点是多少。那不就变成了在 3、1、8、12、3中挑一个最长递增子序列了嘛。 但是我们这里是可能有重复的左端点的假设有重复的话我们排完序是下面这种情况如果我们继续不看左端点我们可能会挑出来4、6、7、9长度为4的序列但是这并不符合原因就是我们的左必须大于左才能套。 那如何避免这种情况呢很简单当左端点相同的时候我们就按照右端点从大到小排序。当继续不看左端点我们在挑7的时候绝对不要9因为当左边相同的时候右边是按照从大到小排的同理挑4绝对不会考虑前三个。 重写排序后就完完全全变成只有一个限制的最长递增序列了。 class Solution {
public:int maxEnvelopes(vectorvectorint e) {// 重写排序 贪心 二分sort(e.begin(), e.end(),[](vectorint e1, vectorint e2){return e1[0] ! e2[0] ? e1[0] e2[0] : e1[1] e2[1];});// 贪心 二分vectorint ret;ret.push_back(e[0][1]);int n e.size();for(int i 1; i n; i){if(e[i][1] ret.back()){ret.push_back(e[i][1]);}else{int left 0, right ret.size() - 1;while(left right){int mid (left right) 1;if(ret[mid] e[i][1])left mid 1;elseright mid;}ret[left] e[i][1];}}return ret.size();}
};3.可被三整除的最大和
题目链接 1262. 可被三整除的最大和
题目分析 这道题的意思是给一个数组在这个数组中挑一些数使这些数的和能被3整除并且这些挑的这些数的和是最大的。
算法原理
解法一正难则反 贪心 分类讨论
题目要在数组中挑一些数的和能被3整除并且和是最大的我们可以直接把整个数组中的数全部挑出来%3正好等于0那我就不用考虑了如果%3不等于那我在全部挑选的基础上删一些数就可以了。
先把所有的数累加在一起根据累加和删除一些数
假设所有数的和是sum接下来就分类讨论
sum % 3 0
直接返回sum sum % 3 1
我们定义一些数x 标记 % 3 1 的数y 标记 % 3 2 的数
如果%3 1必定有下面几种情况
第一种情况 存在一个%3 1 的数剩下所有数的和%3 0 存在四个%3 1 的数剩下所有数的和%3 0其实可以把三个%3 1的数归到剩下所有数的和%3 0里面 存在七个%3 1 的数剩下所有数的和%3 0也可以把六个%3 1的数归到剩下所有数的和%3 0里面 剩下的也不用枚举了我们只用考虑第一种情况就行了原因就是不管这里有多少种情况我们仅需删去第一种情况的x1就可以让剩下的数的和%30。 那么贪心的地方来了要删除怎样的x1肯定是最小的x1。因为我们想让sum的和最大。 第二种情况
存在两个%3 2 的数 y1y2 (2 2 4 % 3 1)或者和上面一样存在y1、y2、y3、y4…但是和上面一样我们仅需第一种情况就行了此时删y1y2。此时贪的地方来了为了使sum最大删y1和y2一个是最小的一个是次小的。 因为sum %3 1 会分为这两种情况因此我们取这两种情况的最大值。 sum % 3 2
也是两种情况要么存在一个y1 使sum % 3 2要么存在一个x1一个x2 使 sum % 3 2。我们依旧取两种情况的最大值。 如何求一堆数中的最小值以及次小值 同理求一堆数中的最大值和次大值也是一样的求法。
第一种方法sort排序 O(nlogn)
第二种方法分类讨论
先定义两个数x1、x2然后初始化为无穷大。然后从左到右遍历根据新来的x分类讨论
x x1 x1 x x2 3. x x2
并不影响最小和次小的。所以不用考虑
class Solution {
public:int maxSumDivThree(vectorint nums) {const int INF 0x3f3f3f3f;int sum 0, x1 INF, x2 INF, y1 INF, y2 INF;for(auto x: nums){sum x;if(x % 3 1){if(x x1) x2 x1, x1 x;else if(x x2) x2 x;}else if(x % 3 2){if(x y1) y2 y1, y1 x;else if(x y2) y2 x;} }//分类讨论if(sum % 3 0) return sum;else if(sum % 3 1) return max(sum - x1, sum - y1 - y2);else return max(sum - y1, sum - x1 - x2);}
};解法二动态规划
从一堆数中选取一些数使这些数的和能被3整除。其实这道题就是一个01背包问题。 1.状态表示 dp[i][j] 表示从前 i 个数中选取一些数这些数的和模3等于 j (0 j 3) 时最大值的和是多少 2.状态转移方程 根据最后一个位置划分情况
不选 i 位置这个数那就去 0 ~ i - 1 区间去选一些数的和模3等于j 时最大值的和正好是 dp[i-1][j] 选 i 之后还是去 0 ~ i - 1 区间去选一些数的和模3但是此时就不是直接去找和模3等于 j 的了因为 i 位置这个数 nums[i] % 3 会等于0、1、2 中的任意一个数那么去 0 ~ i - 1区间去找和模3等于 的 j 也要随 nums[i] % 3 的改变而去改变。
以nums[i]%3 1为例如果求的dp[i][0]那就要去 0 ~ i -1 区间去找和%3 但是 j 为 2 的情况因为这个和 加上 nums[i] 才会有 和 % 3 等于 0比如 nums[i] 是 1去 0 ~ i - 1找的和是22 % 3 2 2 1% 3 0 。同理求dp[i][1]dp[i][2]也是一样。 我们要求的是最大和因此取两种情况的最大值 3.初始化 多开一行列开3个里面的值要保证后序的填表是正确的下标的映射关系
第一行为空表示没有数可以选此时和%3等于0不选就行了直接就是0第一格填0没有数可以选还要和%3 1 和 2 是不可能存在的可以给这两个位置得值位-1表示不存在得情况但是我们下面写代码要判断一下 不等于-1 才能要这个状态但是因为我们求得又是最大值我们可以使它俩足够小就行了这样就可以不用去判断了也不会影响填表。因此可以给-0x3f3f3f3f。
第一列除了第一格下面的不用初始化。直接放在填表里面就行了。 4.填表顺序 从上往下从左往右 5.返回值 dp[i][j] 表示从前 i 个数中选取一些数这些数的和模3等于 j (0 j 3) 时最大值的和是多少我们要得使从所有数种选一些数这些数得和%3 0 最大值是多少因此返回的是 dp[n][0]
class Solution {
public:int maxSumDivThree(vectorint nums) {// 动态规划const int INF 0x3f3f3f3f;int n nums.size();vectorvectorint dp(n 1, vectorint(3, -INF));dp[0][0] 0;for(int i 1; i n; i)for(int j 0; j 3; j)dp[i][j] max(dp[i - 1][j], dp[i - 1][(j - nums[i -1] % 3 3) % 3] nums[i - 1]);return dp[n][0];}
};优化利用滚动数组做优化
背包问题哪里我们使用的是一个数组充当滚动数组但是这里我们要用两个数组充当滚动数组因为%3可能会等于0、1、2那在一个数组中更新下一行的值及其可能会覆盖j 为 0 、1、2的任何位置比如 填 j 0会用到 j 1, 但是填 j 也可能会用到 j 0但是前面已经把 j 0 更新了找不到之前的值了所以这里我们用两个数组充当滚动数组就不担心这个问题了。并且如果是两个数组充当滚动数组01背包优化填表顺序从左往右从右往左都行。
class Solution {
public:int maxSumDivThree(vectorint nums) {// 利用滚动数组优化(二个数组)const int INF 0x3f3f3f3f;int n nums.size();vectorint dp(3, -INF);dp[0] 0;for(int i 1; i n; i){vectorint ndp(3);for(int j 0; j 3; j)ndp[j] max(dp[j], dp[(j - nums[i -1] % 3 3) % 3] nums[i - 1]);dp move(ndp);}return dp[0];}
};4.距离相等的条形码
题目链接 1054. 距离相等的条形码
题目分析 算法原理
解法贪心 模拟
我们这道题就是让我们把这些数重新排列一下相邻的两个不相同。此时我们这样考虑问题我们有9个格子把给的数放到格子里让相邻的两个不相同就可以了。此时我们可以这样处理把相同的数看出一批数每次摆放一批数摆放的时候仅需让这些相同的数不相邻就可以了。如何做到不相邻特别简单每次摆的时候隔一个格子。这样绝对会让相同的数不相邻。 我们先在偶数位上摆摆完后在摆奇数位。此时摆完后会发现相邻两个数是不相同的。
贪心策略
每次处理一批相同的数摆放的时候每次隔一个格子
但是这个策略还有一个问题可能会有把相同的数放在相邻的位置这里我们还要多加一个限定条件。
先处理出现次数最多的那个数剩下的数的处理顺序无所谓
证明
题目一定有解我们可以得到一个性质假设有n个数我们可以分成 (n1)/2 个组。如果题目一定有解我们可以证明的是出现次数最多的那个数不超过(n1)/2个。
假设出现次数最多的那个数超过(n1)/2个。那此时去摆这些数的时候必定会有一组里面出现相同的数。但是题目一定有解因此出现次数最多的那个数不超过(n1)/2个。 我们的策略是先处理出现次数最多的那个数剩下的数的处理顺序无所谓。
第一种情况出现次数最多的数正好出现 n 1/2。我们先处理最多的那个数剩下的数无论怎么放都不会相邻。 第二种情况出现次数最多的数小于n 1/ 2。此时我们也可以证明相同的数不相邻因为如果相邻必定是后面的数x出现次数还要比o还要多但是这种情况绝对不会存在。因为我们的前提就是出现次数最多的数小于n 1/ 2那就是x就是出现次数最多的数。但是我们是优先处理出现次数最多的那次数。所以如果是先填ox绝对不可能相邻。 class Solution {
public:vectorint rearrangeBarcodes(vectorint b) {// 统计每个数出现的频次unordered_mapint,int hash;int maxVal 0, maxCount 0;for(auto x : b){if(maxCount hash[x]){maxCount hash[x];maxVal x;}}// 先处理出现次数最多的那个数int n b.size();vectorint ret(n);int index 0;for(int i 0; i maxCount; i){ret[index] maxVal;index 2; }//处理剩下的数hash.erase(maxVal);for(auto [x, y] : hash){for(int i 0; i y; i){if(index n) index 1;ret[index] x;index 2;}}return ret;}
};5.重构字符串
题目链接 767. 重构字符串
题目分析 算法原理
解法贪心 模拟
每次处理一批相同的字符摆放的时候隔一个位置放一个字符优先处理出现次数最多的那一个字符
这道题并没有告诉我们一定会有排序所以我们要先判断一下是否有排列方法很简单出现次数最多的字符个数不超过n1/2就行了。
class Solution {
public:string reorganizeString(string s) {// 统计每个字符出现的频次int hash[26] { 0 };char maxChar ; int maxCount 0;for(auto ch : s){if(maxCount hash[ch - a]){maxCount hash[ch - a];maxChar ch;}}// 先判断⼀下int n s.size();if(maxCount ((n 1) / 2)) return ;// 先处理出现次数最多的那个字符string ret(n, );int index 0;for(int i 0; i maxCount; i){ret[index] maxChar;index 2;}//处理剩下的数hash[maxChar - a] 0;for(int i 0; i 26; i){for(int j 0; j hash[i]; j){if(index n) index 1;ret[index] a i;index 2;}} return ret;}
};
