摘要:示例输入输出解释区间和重叠将它们合并为示例输入输出解释区间和可被视为重叠区间。注意不允许使用任何内置指数函数和算符,例如或者。示例输入输出示例输入输出解释的算术平方根是由于返回类型是整数,小数部分将被舍去。
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. 不同路径 - 力扣(LeetCode) (leetcode-cn.com)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28
示例 2:
输入:m = 3, n = 2
输出: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. 加一 - 力扣(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) - 力扣(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; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/124462.html
摘要:三结对编程排位赛四个人为一组,由队长带队刷题,每周根据这周四个人的刷题总数进行队伍间排名。万人千题结对编程排位赛如果想参加的第二期的同学,可以先联系作者加群,看看第一期的同袍是如何奋斗的。 ...
摘要:万人千题结对编程排位赛如果想参加的第二期的同学,可以先联系作者加群,看看第一期的同袍是如何奋斗的。 ?付费专栏券(电脑打开有优惠)? 博主会带领大家进行...
摘要:文章目录零写在前面一概念定义二题目描述三算法详解四源码剖析暴力枚举哈希降维五推荐专栏六粉丝福利零写在前面这是算法零基础讲专栏打卡学习的第三十二天了。目前,万人千题社区每天都会有五六篇高质量的解题报告被我加精。 ...
摘要:万人千题结对编程排位赛如果想参加的第二期的同学,可以先联系作者加群,看看第一期的同袍是如何奋斗的。 博主会带领大家进行 《C语言入门100例》 和 《算法零基础...
摘要:双特惠付费专栏优惠券文章目录零写在前面一概念定义二题目描述三算法详解四源码剖析五推荐专栏六习题练习零写在前面这是算法零基础讲专栏打卡学习的第二十五天了。每天都会有五六篇高质量的解题报告被我加精。 ...
阅读 871·2021-11-24 09:39
阅读 329·2021-11-23 09:51
阅读 4101·2021-11-22 09:34
阅读 574·2021-09-07 09:59
阅读 3412·2021-09-02 15:21
阅读 2030·2021-08-24 10:01
阅读 559·2021-08-19 10:55
阅读 2219·2019-08-30 15:55