56 合并区间
56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com)
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 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] 可被视为重叠区间。
//可以先根据开始位置排序 比较器 小->大
//先把第一个拿出来 开始 结束 看下一个的开始有没有 前边的 结束位置大 能不能拿下 再看结束位置要不要更新
// 到新的 的开始位置的值 比你之前的 结束位置的 值大了 ，生成 再拿下一对 继续...
public int[][] merge(int[][] intervals) {
if(intervals.length == 0){
return new int[0][0];
}
//按照起点 排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> ans = new ArrayList<>();
int i = 0;
while(i < intervals.length){
int start = intervals[i][0];
int end = intervals[i][1];
while(i < intervals.length - 1 && intervals[i + 1][0] <= end){
end = Math.max(end,intervals[++i][1]);
}
ans.add(new int[]{start,end});
i++;
}
return ans.toArray(new int[0][]);
}
62 不同路径
62. 不同路径 - 力扣（LeetCode） (leetcode-cn.com)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
//方法1 动态规划 当前位置 依赖左侧 和 上侧
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
//第0行 0列 设置成1
for(int i = 0; i < m; i++){
dp[i][0] = 1;
}
for(int i = 0; i < n; i++){
dp[0][i] = 1;
}
for(int row = 1; row < m ; row++){
for(int col = 1; col < n; col++){
dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
}
}
return dp[m - 1][n - 1];
}
//方法2 C(n,m) 所以是 m-1+n-1 ,m n
// (m + n)! / m!*n!
public int uniquePaths(int m, int n) {
long ans = 1;
// for (int i = n, j = 1; j < m; i++, j++) {
// ans = ans * i / j;
// }
// int a = m < n ? m -1 : n -1;
// for(int i = 0; i < a; i++){
// ans *= m+n-2 -i;
// ans /= i + 1;
// }
for(int i = 0; i<Math.min(m,n) - 1; i++){
ans *= m+n-2 -i;
ans /= i + 1;
}
return (int) ans;
}
66 加一
66. 加一 - 力扣（LeetCode） (leetcode-cn.com)
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
//从后往前加呗，9999的情况 0位置 是1
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] res = new int[digits.length + 1];
res[0] = 1;
return res;
}
69 Sqrt(x)
69. Sqrt(x) - 力扣（LeetCode） (leetcode-cn.com)
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
//二分开方
public static int mySqrt(int x) {
if (x == 0) {
return 0;
}
long ans = 1;
long L = 1;
long R = x;
long M = 0;
while (L <= R) {
M = (L + R) / 2;
if (M * M <= x) {
ans = M;
L = M + 1;
} else {
R = M - 1;
}
}
return (int) ans;
}