老板合作网站开发,加盟店,软件开发前景和收入,上海 设计网站建设贪心算法 是每次只考虑当前最优#xff0c;目标证明每次是考虑当前最优能够达到局部最优#xff0c;这就是贪心的思想#xff0c;一般情况下贪心和排序一起出现#xff0c;都是先根据条件进行排序#xff0c;之后基于贪心策略得到最优结果。 面试的时候面试官一般不会出贪…贪心算法 是每次只考虑当前最优目标证明每次是考虑当前最优能够达到局部最优这就是贪心的思想一般情况下贪心和排序一起出现都是先根据条件进行排序之后基于贪心策略得到最优结果。 面试的时候面试官一般不会出贪心算法如果可能贪心一般都可以使用动态规划解决面试官很喜欢出动态规划的题目。 1. 最大连续子序列 题目: 给定一个整数数组找到一个具有最大和的子数组返回其最大和。 扩展1: 给定一个整数数组找出两个 不重叠 子数组使得它们的和最大。 扩展2: 给定一个整数数组找出两个不重叠的子数组A和B使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。 分析: 使用这个s表示当前可能满足的最大和如果s0,我们认为s对接下来的加操作有帮助基于snums[i]if s 0, 认为s只会对后面造成负影响两snums[i]。 扩展问题: 可以将 数组从每个位置k分开分别结算[1,i]和[i1, n)的最值记录的过程中可以使用数组保存下来的已经计算好的值。 int maxSubArray(vectorint nums) {int s 0, ans -1000000;for(int i 0; i nums.size(); i ) {if(s 0) s nums[i];else s nums[i];ans max(s, ans);}return ans;
}2. 删除数字 题目: 给定一个以字符串表示的非负整数从该数字中移除掉k个数位让剩余数位组成的数字尽可能小求可能的最小结果。 分析: 从左到右遍历字符串找到第一个不满足递增的数字删除一定会保证当前操作之后剩下的数字最小。 string removeKdigits(string num, int k) {int i;while(k --) {for(i 0; i num.size() - 1 num[i] num[i1]; i );num.erase(num.begin() i);}// remove 0auto it num.begin();while(it ! num.end() *it 0) {num.erase(it);it num.begin();}if(num.size() 0) num 0;return num;
}
3. 无重叠区间 题目: 给定一些区间找到需要移除的最小区间数以使其余的区间不重叠。 分析: 贪心一般伴随着排序一起出现我们根据区间的结束使用升序排序之后进行遍历如果发现不满足条件则移除这个不满足的区间。 classs Interval {int start, end;Interval(int start, int end) {this-start start;this-end end;}
}
bool cmp(Interval a, Interval b) {if(a.end b.end) return 1;else return 0;
}
int eraseOverlapIntervals(vectorInterval intervals) {sort(intervals.begin(), intervals.end(), cmp); int cnt 0;Interval tmp intervals[0];for(int i 1; i intervals.size(); i ) {if(tmp.end intervals[i].start) tmp intervals[i];else {cnt ;}}return cnt;
}4. 合并数字 题目: 给出n个数现在要将这n个数合并成一个数每次只能选择两个数a,b合并每次合并需要消耗ab的能量输出将这n个数合并成一个数后消耗的最小能量。 分析: 参考哈夫曼树的构造每一次合并两个最小的数直到剩下一个数字因为每次要选择两个最小的需要用到最小堆来实现可以使用CSLT中的优先队列. 根据这个题目请大家自行补上哈夫曼树。 int mergeNumber(vectorint numbers) {priority_queueint, vectorint, greaterint pq;for(int i 0; i numbers.size(); i ) {pq.push(numbers[i]);}int cost 0;while(pq.size() 1) {int a pq.top();pq.pop();int b pq.top();pq.pop();cost (a b);pq.push(a b);}return cost;
}
5. 最小支撑树 题目: 使用kruskal算法构造最小支撑树。 分析: 详见百度百科或者wikipedia. 代码: kruskal code struct Edge { int src, dest, weight;
};
struct Graph { int V, E; struct Edge* edge;
};
struct Graph* createGraph(int V, int E) { struct Graph* graph new Graph; graph-V V; graph-E E; graph-edge new Edge[E]; return graph;
}
struct subset { int parent; int rank;
};
int find(struct subset subsets[], int i) { if (subsets[i].parent ! i) subsets[i].parent find(subsets, subsets[i].parent); return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y) { int xroot find(subsets, x); int yroot find(subsets, y); if (subsets[xroot].rank subsets[yroot].rank) subsets[xroot].parent yroot; else if (subsets[xroot].rank subsets[yroot].rank) subsets[yroot].parent xroot; else { subsets[yroot].parent xroot; subsets[xroot].rank; }
}
int myComp(const void* a, const void* b) { struct Edge* a1 (struct Edge*)a; struct Edge* b1 (struct Edge*)b; return a1-weight b1-weight;
}
void KruskalMST(struct Graph* graph) { int V graph-V; struct Edge result[V]; int e 0; int i 0; qsort(graph-edge, graph-E, sizeof(graph-edge[0]), myComp); struct subset *subsets (struct subset*) malloc( V * sizeof(struct subset) ); for (int v 0; v V; v) { subsets[v].parent v; subsets[v].rank 0; } while (e V - 1) { struct Edge next_edge graph-edge[i]; int x find(subsets, next_edge.src); int y find(subsets, next_edge.dest); if (x ! y) { result[e] next_edge; Union(subsets, x, y); } } return;
} 6. 补齐数组 题目: 给出一个正整数数组nums和一个整数n向数组添加patch元素使得范围[1, n]包含的任何数字都可以由数组中某些元素的总和形成。返回所需的最少补齐数。 分析 升序排序使用r表示目前可以表示的右边界如果当前值 r, 超出范围又因为 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示那么只需要有n/2以及 [1, n/2] 区间内任何数字都可以用 nums 中某几个数字的和来表示即可。所有我们将r扩大一倍继续判断是否满足。直到 r n。 int minPatches(vectorint nums, int n) {sort(nums.begin(), nums.end());long long r 1;int i 0;int cnt 0;while(r n) {if(i nums.size() nums[i] r) r nums[i];else {cnt ;r * 2;}}return cnt;
}7. 买卖股票的最佳时机 题目: 假设有一个数组它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 分析: 先低价买入再高价卖出因此从前向后记录最小值并且更新最有结果 int maxProfit(vectorint prices) {int minp prices[0];int ans 0;for(int i 1; i prices.size(); i ) {ans max(ans, prices[i] - minp);minp min(minp, prices[i]);}return ans;
}8. 买卖股票的最佳时机II 题目: 假设有一个数组它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。 分析: 多次买卖我们可以尽可能多的买卖股票如果满足prices[i1] price[i]就进行一次买卖其实我们知道如果是一个递增序列(prices[i1] - prices[i]) (prices[i] - prices[i-1]) prices[i1] - prices[i]可以保证我们将所有可能的买卖识别出来。 int maxProfit(vectorint prices) {int sum 0;for(int i1;iprices.size();i){if(prices[i] prices[i-1]){sum prices[i] - prices[i-1];}}return sum;
}9. 买卖股票的最佳时机含手续费 题目: 给定一个数组其中第i个元素是一支股票在第i天的价格以及一个非负数 fee 代表了交易手续费。只需要在卖出时支付 fee。你可以进行任意次交易而每次交易都必须付手续费而且你不能持有超过1支数量的股票也就是说你在买入之前需要先把之前买入的卖出。返回可以获得的最大利润。 分析: 我们考虑最朴素的方法对于每一天如果当前有股票考虑出售或者保留如果没股票考虑购买或者跳过进行dfs搜索。每天都有两种操作时间复杂度为O(2^n).如何优化呢我们用动态规划的思想来解决这个问题考虑每一天同时维护两种状态拥有股票(own)状态和已经售出股票(sell)状态。用own和sell分别保留这两种状态到目前为止所拥有的最大利润。 对于sell用前一天own状态转移比较卖出持有股是否能得到更多的利润即sell max(sell , own price - fee) 而对于own , 我们考虑是否买新的股票更能赚钱(换言之更优惠ownmax( own, sell-price).初始化我们要把sell设为0表示最初是sell状态且没有profit把own设为负无穷因为最初不存在该状态我们不希望从这个状态进行转移.因为我们保存的都是最优状态所以在买卖股票时候取max能保证最优性不变.最后直接返回sell即可.来自(https://www.jiuzhang.com/solution/best-time-to-buy-and-sell-stock-with-transaction-fee/#tag-highlight-lang-cpp) int maxProfit(vectorint prices, int fee) {int sell 0, buy -prices[0];for (int price : prices) {int sellOld sell;sell max(sell, buy price - fee);buy max(buy, sellOld - price);}return sell;
}10. 最后的猫 题目: 给你一个n只猫每一个猫都有一个初始化的萌系数当一只猫的萌系数变成0它就会离开你。现在你实在受不了这n只萌猫想要只留下一只猫并且使它的萌系数最低。每一个你可以选择任意一只猫A去消耗另外一只猫B的萌系数这样的话猫B的萌系数就会减去猫A的萌系数当猫A的萌系数不变。通过多次回合之后最后剩下的猫的萌系数最小是多少。 分析: 我们的目的是留下一只猫使它的萌系数最小从这个角度出发我们可以选择最小萌系数的猫去消耗其他的猫如果其他的猫萌系数变成0就离开了。例如最小萌系数的猫的系数是a对于其他的猫如果b%a 0则经过多次消耗之后b就会离开如果b%a!0, 则结果是经过多轮消耗之后变成(b%a, a)直到一方变成0我们可以发现这是一个求最大公约的算式。因此最后的猫萌系数是gcd(h[0],h[0],…,h[n-1]); int gcd(int a, int b) {if(a 0) return b;return gcd(b % a, a);
}
int solve(vectorint h) {if(h.size() 1) return h[0];int ans gcd(h[0], h[1]);for(int i 2; i h.size(); i ) {ans gcd(ans, h[i]);}return ans;
}
