题目详情

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

示例:

输入: m = 3, n = 2

输出: 3

解释:
从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

思路

  • 这是一个基本的DP问题
  • 由于机器人只能向右和向下移动，当它到达某一点时，只有两种可能性：
  • 1.它从上面到达那个点（向下移动到那一点）
  • 2.它从左边到达那个点（向右移动到那一点）
  • 因此，我们有下面的状态方程：假设到达某一点的路径数(i, j)表示为P[i][j]，很容易得出结论P[i][j] = P[i - 1][j] + P[i][j - 1]
  • 然而实际上我们得出最后结果并用不到整个矩阵，只需要当前列上一个cell和左列的当前cell就够了。整理优化得：

具体代码

  1. /**
  2.  * @param {number} m
  3.  * @param {number} n
  4.  * @return {number}
  5.  */
  6. var uniquePaths = function(m, n) {
  7.     if (m > n) return uniquePaths(n, m)
  9.     let arr = Array(m).fill(1)
  11.     for(let i = 1; i < n; i ++) {
  12.         for(let j = 1; j < m; j++) {
  13.             arr[j] += arr[j - 1]
  14.         }
  15.     }
  16.     return arr[m - 1]
  17. };

Array - 729. My Calendar I

题目详情

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

示例:
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true

解释:
第一个日程安排可以添加到日历中
第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了
第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20 。

思路

  • 要求两个日程范围不存在重复。
    每次添加时需要和以往所有的日程进行比较。才可以确实是否可以添加。
    现罗列出重叠的情况。

a为已存在日程，b为待添加日程。

a　　 a0 l——————l a1
b 　　　 b0 l——l b1

a a0 l——————l a1
b 　　b0 l————-l b1

a 　 a0 l——————l a1
b b0 l———l b1

  • 根据以上重叠情况，可以得到一个抽象的描述
    max(a0, b0) < min(a1, b1)

具体代码

var MyCalendar = function() {
    this.calendar = {}
};

/** 
 * @param {number} start 
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function(start, end) {
    for(let key in this.calendar) {
        if(!((key < start && this.calendar[key] <= start) || (key >= end && this.calendar[key] > end))) return false
    }
    this.calendar[start] = end
    return true
};

/** 
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = Object.create(MyCalendar).createNew()
 * var param_1 = obj.book(start,end)
 */