中文域名是网站名称吗,诱导视频网站怎么做,电商网站开发模块,互动网站建设多少钱0简介
0.1什么是贪心算法
贪心算法是用贪婪(鼠目寸光)的角度#xff0c;找到解决问题的最优解
贪心策略#xff1a;(从局部最优 -- 整体最优) 1把解决问题的过程分为若干步#xff1b; 2解决每一个问题时#xff0c;都选择当前“看上去”最优的解法#xff1b; 3“…0简介
0.1什么是贪心算法
贪心算法是用贪婪(鼠目寸光)的角度找到解决问题的最优解
贪心策略(从局部最优 -- 整体最优) 1把解决问题的过程分为若干步 2解决每一个问题时都选择当前“看上去”最优的解法 3“希望”得到全局最优解 0.2贪心算法特点 1贪心策略的提出 a.没有任何模板和标准 b.可能每道题的贪心标准是不同的 2贪心策略的正确性 a有可能贪心策略是错误的例二和例三 b也就是正确的贪心策略是需要证明的 0.3证明找零问题 1柠檬水找零
oj链接柠檬水找零 class Solution
{
public:bool lemonadeChange(vectorint bills){int five 0, ten 0;for (auto bill : bills){if (bill 5)five;else if (bill 10){if (five 0)return false;elseten, five--;}else{if (ten 0){if (five 3)five - 3;elsereturn false;}else{ten--;if (five 1)five - 1;elsereturn false;}}}return true;}
};
//简化版
class Solution
{
public:bool lemonadeChange(vectorint bills){int five 0, ten 0;for (int i 0; i bills.size(); i){if (bills[i] 5)five;else if (bills[i] 10){five--;ten;}else{if (ten)ten--, five--;elsefive - 3;}if (five 0)return false;}return true;}
}; 2将数组和减半的最小操作次数
oj链接将数组和减半的最少操作次数 class Solution
{
public:int halveArray(vectorint nums){priority_queuedouble qe;double sum 0; // 不能用intfor (auto num : nums){qe.push(num);sum num;}int cnt 0;double aim sum / 2;while (true){double maxval qe.top();qe.pop();sum - maxval;cnt;maxval / 2;sum maxval;if (sum aim)return cnt;qe.push(maxval);}}
};class Solution
{
public:int halveArray(vectorint nums){priority_queuedouble qe;double sum 0.0;for (auto num : nums){qe.push(num);sum num;}sum / 2.0;int cnt 0;while (sum 0){double t qe.top() / 2.0;qe.pop();sum - t;cnt;qe.push(t);}return cnt;}
}; 3最大数
oj链接最大数 class Solution
{
public:class cmp{public:bool operator()(const string s1, const string s2){return s1 s2 s2 s1;}};string largestNumber(vectorint nums){vectorstring str;for (auto e : nums)str.push_back(to_string(e));sort(str.begin(), str.end(), cmp());string ret;for (auto e : str)ret e;if (ret[0] 0)return 0;return ret;}
}; 4摆动序列
oj链接摆动序列 class Solution
{
public:int left 0, ret 0;int wiggleMaxLength(vectorint nums){for (int i 0; i nums.size() - 1; i){int right nums[i 1] - nums[i];if (right 0)continue; // 有连续相等的情况if (left * right 0)ret; // left0 - 开始处于第一个位置也要加left right;}return ret 1; // 加上最后一个位置}
}; 5最长递增子序列
oj链接最长递增子序列 class Solution
{
public:int lengthOfLIS(vectorint nums){vectorint ret;ret.push_back(nums[0]);for (int i 1; i nums.size(); i){int x nums[i];if (x ret.back())ret.push_back(x);else{// 二分插入位置int left 0, right ret.size() - 1;while (left right){int mid left (right - left) / 2;if (ret[mid] x)left mid 1;elseright mid;}ret[left] x;}}return ret.size();}
};
6递增的三元子序列
oj链接递增的三元子序列 思路与上题类似 class Solution
{
public:bool increasingTriplet(vectorint nums){vectorint ret;ret.push_back(nums[0]);for (int i 1; i nums.size(); i){int x nums[i];if (x ret.back())ret.push_back(x);else{int left 0, right ret.size() - 1;while (left right){int mid left (right - left) / 2;if (ret[mid] x)left mid 1;elseright mid;}ret[left] x;}}return ret.size() 3;}
};
7最长连续递增序列
oj链接最长连续递增序列 该方法是从暴力解法两层for循环优化来的所以暴力解法对这个贪心一定对
class Solution
{
public:int findLengthOfLCIS(vectorint nums){int n nums.size(), ret 1;for (int i 0; i n; i){int j i;while (j 1 n nums[j] nums[j 1])j;ret max(j - i 1, ret);i j;}return ret;}
};
8买卖股票的最佳时机 oj链接买卖股票的最佳时机 该方法是从暴力解法两层for循环优化来的所以暴力解法对这个贪心一定对
class Solution
{
public:int maxProfit(vectorint prices){int n prices.size(), ret 0;int MinPrice INT_MAX;for (int i 0; i n; i){int profit prices[i] - MinPrice;MinPrice min(MinPrice, prices[i]);ret max(profit, ret);}return ret;}
};
此题也可以采用 动态规划58道算法题 中的买卖股票的最佳时机Ⅲ的思路来解决~
9买卖股票的最佳时机Ⅱ oj链接买卖股票的最佳时机 II //双指针
class Solution
{
public:int maxProfit(vectorint prices){int n prices.size(), ret 0;for (int i 0; i n; i){int j i;while (j 1 n prices[j] prices[j 1])j;ret prices[j] - prices[i];i j;}return ret;}
};//一天一天拆分
class Solution
{
public:int maxProfit(vectorint prices){int n prices.size(), ret 0;for (int i 0, right 0; i n - 1; i){right prices[i 1] - prices[i];if (right 0)ret right;}return ret;}
};
10K次取反后最大化的数组和
oj链接K 次取反后最大化的数组和 //解法1原始分类讨论
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {int m 0, minElem INT_MAX, n nums.size();for (auto x : nums) {if (x 0)m;minElem min(minElem, abs(x)); // 求绝对值最⼩的那个数}// 分类讨论int ret 0;if (m k) {sort(nums.begin(), nums.end());for (int i 0; i k; i) // 前 k ⼩个负数变成正数{ret -nums[i];}for (int i k; i n; i) // 后⾯的数不变{ret nums[i];}} else {// 把所有的负数变成正数for (auto x : nums)ret abs(x);if ((k - m) % 2) // 判断是否处理最⼩的正数{ret - minElem * 2;}}return ret;}
};
//解法2利用小堆
class Solution
{
public:int largestSumAfterKNegations(vectorint nums, int k){priority_queueint, vectorint, greaterint qe;for (auto num : nums)qe.push(num);while (k){int tmp qe.top();qe.pop();tmp -tmp;qe.push(tmp);k--;}int ret 0;while (!qe.empty()){ret qe.top();qe.pop();}return ret;}
};
11按身高排序
oj链接按身高排序 // 解法1
class Solution
{
public:vectorstring sortPeople(vectorstring names, vectorint heights){int n names.size();pairint, string pr[n];for (int i 0; i n; i){pr[i].first heights[i];pr[i].second names[i];}sort(pr, pr n, greater());vectorstring ret(n);for (int i 0; i n; i)ret[i] pr[i].second;return ret;}
};// 解法2
class Solution
{
public:vectorstring sortPeople(vectorstring names, vectorint heights){int n names.size();mapint, string hash;for (int i 0; i n; i)hash[heights[i]] names[i];vectorstring ret;for (auto [a, b] : hash)ret.push_back(b);reverse(ret.begin(), ret.end());return ret;}
};// 解法3
class Solution
{
public:vectorstring sortPeople(vectorstring names, vectorint heights){int n names.size();vectorint index(n);for (int i 0; i n; i)index[i] i;sort(index.begin(), index.end(), [](int i, int j){ return heights[i] heights[j]; });vectorstring ret(n);for (int i 0; i n; i)ret[i] names[index[i]];return ret;}
};
12优势洗牌
oj链接优势洗牌 class Solution
{
public:vectorint advantageCount(vectorint nums1, vectorint nums2){int n nums2.size();vectorint index2(n);for (int i 0; i n; i)index2[i] i;sort(index2.begin(), index2.end(), [](int i, int j){ return nums2[i] nums2[j]; });sort(nums1.begin(), nums1.end());vectorint ret(n);// 田忌赛马int left 0, right n - 1;for (int i 0; i n; i){if (nums1[i] nums2[index2[left]])ret[index2[left]] nums1[i]; // 比你大elseret[index2[right--]] nums1[i]; // 比你小/相等 取对付你最大的数: nums2[index[right]]}return ret;}
}; 13最长回文串
oj链接最长回文串 class Solution
{
public:int longestPalindrome(string s){unordered_mapchar, int hash;for (auto a : s)hash[a];int ret 0, tmp 0;for (auto [a, b] : hash){// if(b%20) retb;// else retb-1;ret b / 2 * 2;}if (ret s.size())ret;return ret;}
};
14增减字符串匹配
oj链接增减字符串匹配 class Solution
{
public:vectorint diStringMatch(string s){vectorint ret;int l 0, r s.size();for (auto ch : s){if (ch I)ret.push_back(l);elseret.push_back(r--);}ret.push_back(l /*r*/);return ret;}
};
15分发饼干 oj链接分发饼干 class Solution
{
public:int findContentChildren(vectorint g, vectorint s){if (s.size() 0)return 0;sort(g.begin(), g.end());sort(s.begin(), s.end());int i 0, j 0;while (i g.size() j s.size()){if (g[i] s[j]){i;j;}elsej;}return i;}
}; 16最优除法
oj链接最优除法 class Solution
{
public:string optimalDivision(vectorint nums){if (nums.size() 1){return to_string(nums[0]);}else if (nums.size() 2){return to_string(nums[0]) / to_string(nums[1]);}string ret to_string(nums[0]) /( to_string(nums[1]);for (int i 2; i nums.size(); i){ret / to_string(nums[i]);}ret );return ret;}
};
17跳跃游戏Ⅱ
oj链接跳跃游戏 II // 解法1
class Solution
{
public:int jump(vectorint nums){int n nums.size();vectorint dp(n, INT_MAX);dp[0] 0;for (int i 1; i n; i){for (int j 0; j i; j){if (nums[j] i - j)dp[i] min(dp[i], dp[j] 1);}}return dp[n - 1];}
};// 解法2
class Solution
{
public:int jump(vectorint nums){int n nums.size();int left 0, right 0, ret 0, maxpos 0;while (left n right n){if (maxpos n - 1)return ret;ret;for (int i left; i right; i)maxpos max(maxpos, nums[i] i);left right 1;right maxpos;}return ret;}
};
18跳跃游戏
oj链接跳跃游戏 与上面的思路一致只不过在while循环更换判断条件即可 class Solution {
public:bool canJump(vectorint nums) {int nnums.size(),left0,right0,maxpos0;while(leftright)//如果到不了n-1:leftright{if(maxposn-1) return true;for(int ileft;iright;i) maxposmax(maxpos,nums[i]i);leftright1;rightmaxpos;}return false;}
};
19加油站 oj链接加油站 class Solution
{
public:int canCompleteCircuit(vectorint gas, vectorint cost){int n gas.size();for (int i 0; i n; i){int pos 0, cnt 0;for (; pos n; pos){int index (pos i) % n;cnt gas[index] - cost[index];if (cnt 0)break;}if (cnt 0)return i;i i pos;}return -1;}
};
20单调递增的数字 oj链接单调递增的数字 class Solution
{
public:int monotoneIncreasingDigits(int n){string s to_string(n);int i 0, m s.size();// 找递减位置while (i 1 m s[i] s[i 1])i;if (i m - 1)return n;cout i endl;// 回退找相等数的第一个while (i - 1 0 s[i - 1] s[i])i--;s[i] - 1;for (int j i 1; j m; j)s[j] 9;return stoi(s);}
}; 21坏了的计算器
oj链接坏了的计算器 class Solution
{
public:int brokenCalc(int startValue, int target){// 第一种情况// if(targetstartValue) return startValue-target;// 第二种情况int cnt 0;while (target startValue){if (target % 2 ! 0)target 1;elsetarget / 2;cnt;}return cnt startValue - target;}
};
22合并区间
oj链接合并区间 class Solution
{
public:vectorvectorint merge(vectorvectorint intervals){if (intervals.size() 1)return intervals;sort(intervals.begin(), intervals.end()); // 左端点排序vectorvectorint ret;int n intervals.size(), left intervals[0][0], right intervals[0][1];for (int i 1; i n; i){int next_left intervals[i][0], next_right intervals[i][1];if (right next_left)right max(right, next_right);else{ret.push_back({left, right});left next_left;right next_right;}if (i n - 1)ret.push_back({left, right}); // 最后一组区间放到ret中}return ret;}
};
23无重叠区间
oj链接无重叠区间 class Solution
{
public:int eraseOverlapIntervals(vectorvectorint intervals){if (intervals.size() 1)return 0;sort(intervals.begin(), intervals.end());int n intervals.size(), ret 0, left intervals[0][0], right intervals[0][1];for (int i 1; i n; i){int next_left intervals[i][0], next_right intervals[i][1];if (right next_left){ret;right min(right, next_right); // 删除最大的right区间}else{left next_left;right next_right;}}return ret;}
}; 24用最少量的箭引爆气球
oj链接用最少数量的箭引爆气球 class Solution
{
public:int findMinArrowShots(vectorvectorint points){if (points.size() 1)return 1;sort(points.begin(), points.end());int left points[0][0], right points[0][1];int n points.size(), ret 1;for (int i 1; i n; i){int next_left points[i][0], next_right points[i][1];if (right next_left){// 相交的区间去与下一个比// leftmax(left,next_left);right min(right, next_right);}else{// leftnext_left;right next_right;ret;}}return ret;}
}; 25整数替换
oj链接整数替换 //解法1
class Solution
{
public:unordered_mapint, int memo; // 不用vector:存不下int integerReplacement(int n){return MinCount(n);}int MinCount(long long n) // n越界处理{// 记忆化if (memo.count(n))return memo[n];if (n 1){memo[n] 0;return memo[n];}int ret 0;if (n % 2 ! 0)ret min(MinCount(n 1), MinCount(n - 1)) 1;elseret MinCount(n / 2) 1;// 记忆化memo[n] ret;return memo[n];}
};//解法2
class Solution
{
public:int integerReplacement(long long n){int ret 0;while (n ! 1){if (n % 2 0)n / 2;else{if (n % 4 1 || n 3)n - 1;elsen 1;}ret;}return ret;}
};
26俄罗斯套娃信封问题
oj链接俄罗斯套娃信封问题 class Solution
{
public:int maxEnvelopes(vectorvectorint envelopes){int ret 0, n envelopes.size();sort(envelopes.begin(), envelopes.end());vectorint dp(n, 1);for (int i 0; i n; i){for (int j 0; j i; j){if (envelopes[j][1] envelopes[i][1] envelopes[j][0] envelopes[i][0])dp[i] max(dp[i], dp[j] 1);}ret max(ret, dp[i]);}return ret;}
};class Solution
{
public:int maxEnvelopes(vectorvectorint envelopes){sort(envelopes.begin(), envelopes.end(), [](vectorint v1, vectorint v2){ return v1[0] v2[0] ? v1[1] v2[1] : v1[0] v2[0]; });// 重排完序后就变成了最长递增子序列的问题(以每个区间的第二个数为基准)vectorint ret;ret.push_back(envelopes[0][1]);int n envelopes.size();for (int i 1; i n; i){int t envelopes[i][1];if (ret.back() t)ret.push_back(t);else{int left 0, right ret.size() - 1;while (left right){int middle left (right - left) / 2;if (ret[middle] t)right middle;elseleft middle 1;}ret[left] t;}}return ret.size();}
};
27可被三整除的最大和
oj链接可被三整除的最大和 class Solution
{
public:int maxSumDivThree(vectorint nums){int sum 0, ret 0;for (auto e : nums)sum e;if (sum % 3 0)return sum;else if (sum % 3 1){// 定义y1和y2来求最小值和次小值 注意数据溢出问题int x 0x3f3f3f3f3f, y1 0x3f3f3f3f3f, y2 0x3f3f3f3f3f;for (auto e : nums){if (e % 3 1)x min(x, e);else if (e % 3 2){if (e y1){y2 y1;y1 e;}else if (y1 e e y2)y2 e;}}ret max(sum - x, sum - y1 - y2);}else{int y 0x3f3f3f3f3f, x1 0x3f3f3f3f3f, x2 0x3f3f3f3f3f;for (auto e : nums){if (e % 3 1){if (e x1){x2 x1;x1 e;}else if (x1 e e x2)x2 e;}else if (e % 3 2)y min(y, e);}ret max(sum - y, sum - x1 - x2);}return ret;}
};
