目录
坏了的计算器（medium）
题目解析
讲解算法原理
编写代码
合并区间（medium）
题目解析
讲解算法原理
编写代码
坏了的计算器（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
在显⽰着数字 startValue 的坏计算器上，我们可以执⾏以下两种操作：
◦ 双倍（Double）：将显⽰屏上的数字乘2；
◦ 递减（Decrement）：将显⽰屏上的数字减 1 。
给定两个整数 startValue 和 target 。返回显⽰数字 target 所需的最⼩操作数。
⽰例1：
输⼊：startValue=2,target=3
输出：2
解释：先进⾏双倍运算，然后再进⾏递减运算{2->4->3}.
⽰例2：
输⼊：startValue=5,target=8
输出：2
解释：先递减，再双倍{5->4->8}.
⽰例3：
输⼊：startValue=3,target=10
输出：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:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
// 1. 先按照左端点排序
sort(intervals.begin(), intervals.end());
// 2. 合并区间
int left = intervals[0][0], right = intervals[0][1];
vector<vector<int>> 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];
List<int[]> 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][]);
}
}
