高端设计网站建设,福州市鼓楼区建设局网站,深圳中小型网站建设公司,广州市网站建设报价目录 坏了的计算器#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码
合并区间#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码 坏了的计算器#xff08;medium#xff09;
题目解析
1.题目链接#xff1a;. - 力扣#xff08;Leet…目录 坏了的计算器medium
题目解析
讲解算法原理
编写代码
合并区间medium
题目解析
讲解算法原理
编写代码 坏了的计算器medium
题目解析
1.题目链接. - 力扣LeetCode
2.题目描述 在显⽰着数字 startValue 的坏计算器上我们可以执⾏以下两种操作 ◦ 双倍Double将显⽰屏上的数字乘2 ◦ 递减Decrement将显⽰屏上的数字减 1 。 给定两个整数 startValue 和 target 。返回显⽰数字 target 所需的最⼩操作数。 ⽰例1 输⼊startValue2,target3 输出2 解释先进⾏双倍运算然后再进⾏递减运算{2-4-3}. ⽰例2 输⼊startValue5,target8 输出2 解释先递减再双倍{5-4-8}. ⽰例3 输⼊startValue3,target10 输出3 解释先双倍然后递减再双倍{3-6-5-10}. 提⽰ ◦ 1 startValue, target 10^9 讲解算法原理
解法贪⼼ 贪⼼策略 正难则反 当「反着」来思考的时候我们发现 i. 当 end begin 的时候只能执⾏「加法」操作ii. 当 end begin 的时候对于「奇数」来说只能执⾏「加法」操作对于「偶数」来 说最好的⽅式就是执⾏「除法」操作 这样的话每次的操作都是「固定唯⼀」的。
编写代码
c算法代码
class Solution
{
public:int brokenCalc(int startValue, int target) {// 正难则反 贪⼼int ret 0;while(target startValue){if(target % 2 0) target / 2;else target 1;ret;}return ret startValue - target;}
};
java算法代码
class Solution
{public int brokenCalc(int startValue, int target) {// 正难则反 贪⼼int ret 0;while(target startValue){if(target % 2 0) target / 2;else target 1;ret;}return ret startValue - target;}
}
合并区间medium
题目解析
1.题目链接. - 力扣LeetCode
2.题目描述 以数组 intervals 表⽰若⼲个区间的集合其中单个区间为 intervals[i] [start(i), end(i)] 。请你合并所有重叠的区间并返回⼀个不重叠的区间数组该数组需恰好覆盖输⼊中的所有区间。 ⽰例1 输⼊intervals[[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间[1,3]和[2,6]重叠,将它们合并为[1,6]. ⽰例2 输⼊intervals[[1,4],[4,5]] 输出[[1,5]] 解释区间[1,4]和[4,5]可被视为重叠区间。 提⽰ ◦ 1 intervals.length 10^4 ◦ intervals[i].length 2 ◦ 0 start(i) end(i) 10^4 讲解算法原理
解法排序贪⼼ 贪⼼策略 a. 先按照区间的「左端点」排序此时我们会发现能够合并的区间都是连续的b. 然后从左往后按照求「并集」的⽅式合并区间。 如何求并集 由于区间已经按照「左端点」排过序了因此当两个区间「合并」的时候合并后的区间a. 左端点就是「前⼀个区间」的左端点 b. 右端点就是两者「右端点的最⼤值」。
编写代码
c算法代码
class Solution
{
public:vectorvectorint merge(vectorvectorint intervals) {// 1. 先按照左端点排序sort(intervals.begin(), intervals.end());// 2. 合并区间int left intervals[0][0], right intervals[0][1];vectorvectorint ret;for(int i 1; i intervals.size(); i){int a intervals[i][0], b intervals[i][1];if(a right) // 有重叠部分{// 合并 - 求并集right max(right, b);}else // 没有重叠部分{ret.push_back({left, right}); // 加⼊到结果中 left a;right b;}}// 别忘了最后⼀个区间ret.push_back({left, right});return ret;}
};
java算法代码
class Solution
{public int[][] merge(int[][] intervals) {// 1. 按照左端点排序Arrays.sort(intervals, (v1, v2) - {return v1[0] - v2[0];});// 2. 合并区间 - 求并集int left intervals[0][0], right intervals[0][1];Listint[] ret new ArrayList();for(int i 1; i intervals.length; i){int a intervals[i][0], b intervals[i][1];if(a right) // 有重叠部分{// 合并 - 求并集right Math.max(right, b);}else // 不能合并{ret.add(new int[]{left, right});left a;right b;}}// 别忘了最后⼀个区间ret.add(new int[]{left, right});return ret.toArray(new int[0][]);}
}
