leetcode20200701 贪心算法

    技术2022-07-11  74

    最小差值 II 使用贪心算法 这道题直接用贪心 可以做 因为你想 既然通过加减要让差值最小 那么这一排有序数组 第一个数一定是要加的 最后一个数是一定要减的 剩下的数可加可减 那么这个最小的差值一定是某一个数加了 下一个数减了产生的 就这样 class Solution { public: int smallestRangeII(vector<int>& A, int K) { if(A.size()==0){return 0;} sort(A.begin(),A.end()); int imin=0,imax=0; int len=A.size(); int res=A[len-1]-A[0]; for(int i=1;i<len;i++){ imax=max(A[i-1]+K,A[len-1]-K); imin=min(A[0]+K,A[i]-K); res=min(res,imax-imin); } return res; } }; 行相等的最少多米诺旋转 使用贪心算法 其实我也不知道怎么就使用贪心了 因为这个题他 就是多米诺骨 要全相等一行 所以分两个 首先从第一个数组看起 假如A或者B的第i个值都不等于A0 那么break 无法完成 假如有一个可以完成 那就计数谁不等 需要调换的次数 假如这个数组无法进行了 即换下一个数组 假如下一个数组也无法完成 那就-1 return class Solution: def minDominoRotations(self, A: List[int], B: List[int]) -> int: a, b, n = 0, 0, len(A) for i in range(n): if A[i] != A[0] and B[i] != A[0]: break if A[i] != A[0]: a += 1 if B[i] != A[0]: b += 1 if i == n - 1: return min(a, b) a, b = 0, 0 for i in range(n): if A[i] != B[0] and B[i] != B[0]: break if A[i] != B[0]: a += 1 if B[i] != B[0]: b += 1 if i == n - 1: return min(a, b) return -1

    写一个py的程序在这里先

    摆动序列 这道题的贪心算法在于 每次都尽量使得它摆动的最大 这样更有利于摆动继续下去 所以说对于解法 我们只需要对连续递增或者递减的取两端值 只有变号的时候才计数 这样就可以 class Solution { public: int wiggleMaxLength(vector<int>& nums) { if(nums.size()<2){return nums.size();} int prediff=nums[1]-nums[0]; int val=(prediff==0)?1:2; for(int i=2;i<nums.size();i++){ int diff=nums[i]-nums[i-1]; if((diff>0 && prediff<=0) ||(diff<0 && prediff>=0)){ val++; prediff=diff; } } return val; } }; 判断子序列 这道题就是什么狗屁贪心算法吗 我觉得这个是基操 class Solution { public: bool isSubsequence(string s, string t) { if(t.size()<s.size()){return false;} int len1=s.size(); int len2=t.size(); int i=0; int j=0; while((i<s.size()) && (j<t.size())){ if(s[i]==t[j]){ i++; j++; } else{ j++; } } if(i==s.size()){return true;} else{return false;} } }; 最多可以买到的苹果数量 为什么会出错呢 明明很简单 class Solution { public: int maxNumberOfApples(vector<int>& arr) { if(arr.empty()){return 0;} sort(arr.begin(),arr.end()); int count=0; int res=0; for(int i=0;i<arr.size();i++){ count+=arr[i]; res++; if(count>5000){break;} } return res; } }; 跳跃游戏 II 这道题是正儿八经的贪心算法 他不是考虑每一次走能走的最大步数,而是考虑在这些能走的步中找一个下一步能跳最远的 下一步贪心 是这样 class Solution { public: int jump(vector<int>& nums) { int count =0; //需要跳跃的次数 int num=nums.size();//需要跳跃的位置数 int cur=0;//存储最优跳跃点的跳跃的最大位置 int i=0; while (cur<num-1) { //没到最后一个位置的时候进行循环,而出循环说明可以达到最大位置num-1 count++ ; //最远跳跃没有到最大位置时,说明还要进行跳跃 int pre=cur; for (;i<=pre;i++){ //遍历可跳范围之内,找出最佳跳跃点,并用cur 保存新的最远跳跃距离 cur=max(cur,i+nums[i]); } } return count; } }; 坏了的计算器 弱弱的问一句 贪心算法真的存在吗 为什么我觉得这些题没有几个是贪心的 这道题完全依赖于数学问题 因为这里需要我们证明 X的减和乘 应该先换算成 Y的加和除 然后 需要证明如果要除 一定是先除再加的 在这个情况下 我们再来看次数 class Solution { public: int brokenCalc(int X, int Y) { if(X>=Y){return X-Y;} if(Y%2==0){return 1+brokenCalc(X,Y/2);} else{ return 2+brokenCalc(X,(Y+1)/2); } } }; 将数组拆分成斐波那契序列 既然是斐波那契 所以只要确定前两个数 剩下的都是固定的 那么我门只需要遍历前两个数的可能 然后判断是否符合即可
    Processed: 0.010, SQL: 9