算法奇妙屋(四十三)-贪心算法学习之路10

文章目录一. 力扣 [397. 整数替换](https://leetcode.cn/problems/integer-replacement/description/)1. 题目解析2. 算法原理3. 代码二. 力扣 [354. 俄罗斯套娃信封问题](https://leetcode.cn/problems/russian-doll-envelopes/description/)1. 题目解析2. 算法原理3. 代码一. 力扣397. 整数替换1. 题目解析要注意 n 的取值范围很大, 为int类型的极限2. 算法原理记忆化搜索解法贪心解法3. 代码解法一代码classSolution{MapLong,IntegerhashnewHashMap();publicintintegerReplacement(intn){hash.put(1L,0);returndfs(n*1L);}intdfs(longn){if(hash.containsKey(n)){returnhash.get(n);}if(n%20){intretdfs(n/2)1;hash.put(n,ret);returnret;}else{intretMath.min(dfs(n1),dfs(n-1))1;hash.put(n,ret);returnret;}}}解法二代码classSolution{publicintintegerReplacement(intn){intret0;while(n1){if(n%20){n/2;ret;}else{if(n3){n1;ret2;}elseif(n%41){n/2;// 在计算机中, 奇数-1后再/2的操作, 与直接/2的结果一样ret2;}else{nn/21;// 在计算机中, 奇数1后再/2的操作, 与/2后再1的结果一样, 这里主要是为了防止n1溢出ret2;}}}returnret;}}二. 力扣354. 俄罗斯套娃信封问题1. 题目解析题意很好理解, 但是里面用到的算法思想有三个, 相当于区间题目最长递增子序列的题目版本2. 算法原理动态规划(超时), 这个算法虽然超时, 但是可以从中发现规律排序 贪心 二分:我们换一种排序方式, 就可以发现新大陆3. 代码classSolution{publicintmaxEnvelopes(int[][]envelopes){Arrays.sort(envelopes,(a,b)-{if(a[0]!b[0]){returna[0]-b[0];}else{returnb[1]-a[1];}});intnenvelopes.length;ListIntegerretnewArrayList();ret.add(envelopes[0][1]);for(inti1;in;i){intxenvelopes[i][1];intrightret.size()-1;if(xret.get(right)){ret.add(x);}else{intleft0;while(leftright){intmidleft(right-left)/2;if(ret.get(mid)x){leftmid1;}else{rightmid;}}ret.set(left,x);}}returnret.size();}}