动态规划

343. 整数拆分 - 力扣（LeetCode）

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(len(dp)):
            for j in range(i):
                dp[i] = max((i - j) * dp[j], dp[i], (i - j) * j)
        return dp[-1]

1235. 规划兼职工作 - 力扣（LeetCode）

这题主要是要考虑到用 sorted+zip 方法按照 endTime 先排序
一开始的思路

class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        maxTime = max(endTime)
        curr = [0] * (maxTime + 1)
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        for p, j, k in jobs:
            pre = p
            pre_j = j
            while pre > 0 and curr[pre] == 0:
                pre -= 1
            curr[p] = curr[pre]
            while pre_j > 0 and curr[pre_j] == 0:
                pre_j -= 1
            curr[j] = curr[pre_j]
            if curr[p] + k > curr[j]:
                curr[j] = curr[p] + k
        return curr[-1]

然后被恶心到了, 艹,头一次见 Memory Limit Exceeded, 这就是 hard 的难度吗?

一个更好的答案,其中有用到 03 bisect模块

import bisect
class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        # 合并为一个列表
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        dp = [(0, 0)]  # (结束时间, 累积收益)
        for s, e, p in jobs:
            # 找到在当前作业之前结束的最后一个作业
            i = bisect.bisect_right(dp, (s, float('inf')))
            max_profit = dp[i - 1][1] + p
            # 只有当当前收益比之前的最大收益高时，才加入
            if max_profit > dp[-1][1]:
                dp.append((e, max_profit))
        return dp[-1][1]

一个 ts 实现

function jobScheduling(
  startTime: number[],
  endTime: number[],
  profit: number[]
): number {
  const jobs = startTime.map((start, index) => ({
    start,
    end: endTime[index],
    profit: profit[index],
  }));
  jobs.sort((a, b) => a.end - b.end);
  let dp = [0, 0](0,%200);
  for (let job of jobs) {
    let { start, end, profit } = job;
    let i = bisect(dp, start);
    let newProfit = dp[i - 1][1] + profit;
    if (newProfit > dp[dp.length - 1][1]) {
      dp.push([end, newProfit]);
    }
  }
  return dp[dp.length - 1][1];
}
function bisect(arr: number[][], insert: number) {
  let l = 0;
  let r = arr.length - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (arr[mid][0] <= insert) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return l;
}

1751. 最多可以参加的会议数目 II - 力扣（LeetCode）

1277. 统计全为 1 的正方形子矩阵 - 力扣（LeetCode）

想到 dp 就能秒

function countSquares(matrix: number[][]): number {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (i == 0 || j == 0) {
        continue;
      } else if (matrix[i][j] == 1) {
        matrix[i][j] =
          Math.min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]) +
          1;
      }
    }
  }
  return matrix.flat().reduce((a, b) => a + b, 0);
}