• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

算法刷题打卡(十)

互联网 diligentman 44分钟前 3次浏览

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 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  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 加一

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;
	}


程序员灯塔
转载请注明原文链接:算法刷题打卡(十)
喜欢 (0)