目录
55. 跳跃游戏 - 力扣（LeetCode）
?思路：贪心算法。贪心算法是每一次都关注局部最优解，当局部最优解能够构造出全局最优解的时候，贪心算法就可以使用。没有固定模板，基本思路就是：
- 建立数学模型；
- 分解问题分解成若干个子问题；
- 对每一个子问题求解，得到子问的局部最优解；
- 将子问题的局部最优解合并成全局最优解，就是问题的最优解；
本题就是遍历数组中每一个位置，实时维护最远可以达到的位置，使用i + nums[i] 更新可以达到的最远的位置。如果最远的位置大于等于数组中的最后一个位置，输出True，反之为false。（python and c++）
class Solution:
def canJump(self, nums: List[int]) -> bool:
n,rightmost = len(nums),0
for i in range(n):
if i <= rightmost:
rightmost = max(rightmost,nums[i]+i)
if rightmost >= n-1:return True
return Falseclass Solution {
public:
bool canJump(vector<int>& nums) {
int rightmost = 0,n = nums.size();
for (int i = 0;i < n;i++){
if (i <= rightmost) rightmost = max(rightmost,i + nums[i]);
if (rightmost >= n-1) return true;
}
return false;
}
};时间复杂度：O（n）,n为数组大小；
空间复杂度：O（1），不需要额外的空间开销；
56. 合并区间 - 力扣（LeetCode）
思路：使用排序，将数组中最左端排序，之后遍历数组中的每一个列表，若遍历到的列表的右端小于先前的左端点，则合并，比较当前和前一个的右端点的大小；若当前遍历到的列表的右端点大于先前列表的左端点，则无需合并，存储到merged列表中即可。（python and c++）
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
if (!n) return {};
sort(intervals.begin(),intervals.end());
vector<vector<int>> merged;
for (int i = 0;i <n;i++){
if (!merged.size() || merged.back()[1] < intervals[i][0]) merged.push_back({intervals[i][0],intervals[i][1]});
else{
merged.back()[1] = max(merged.back()[1],intervals[i][1]);
}
}
return merged;
}
};class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x:x[0])
mergerd = []
for interval in intervals:
if not mergerd or mergerd[-1][1] < interval[0]: # 不重合
mergerd.append(interval)
else:
# 重合情况，需要合并区间
mergerd[-1][1] = max(mergerd[-1][1],interval[1])
return mergerd时间复杂度：O（nlogn）；排序的时间开销
空间复杂度：O(nlogn)；排序的空间开销；
62. 不同路径 - 力扣（LeetCode）
?思路：使用动态规划，机器人每一次只能往右走或者往下走，定义dp[i][j]是走到当前位置的总的路径数，dp[i][j] = dp[i][j-1] + dp[i-1][j],定义边界条件，当dp[i][0]
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 定义初始化值
dp = [[1] * n] +[[1] + [0] * (n-1) for _ in range(m-1)]
print(dp)
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i][j-1] +dp[i-1][j]
return dp[-1][-1]
?
class Solution {
public:
int uniquePaths(int m, int n) {
if (m == 0 || n == 0) return 0;
//定义初始值
vector<vector<int>> dp(m,vector<int>(n));
for (int i = 0;i < m;i++) dp[i][0] = 1;
for (int j = 0;j < n;j++) dp[0][j] = 1;
for (int i = 1;i < m;i++){
for (int j = 1;j < n;j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};注意：python中的列表推导式的写法需要注意；c++中定义二维数组的方式需要注意。
时间复杂度：O(mn)；
空间复杂度：O(mn)；如果用滚动数组代替代码中的二维数组，可以使空间负责度降低为O（n）;
75. 颜色分类 - 力扣（LeetCode）
思路：
待补
?