LeetCode[435] 无重叠区间

Problem:

  • 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

    注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。

    示例 1:

    • 输入: [ [1,2], [2,3], [3,4], [1,3] ]
    • 输出: 1
    • 解释: 移除 [1,3] 后,剩下的区间没有重叠。

    示例 2:

    • 输入: [ [1,2], [1,2], [1,2] ]
    • 输出: 2
    • 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

    示例 3:

    • 输入: [ [1,2], [2,3] ]
    • 输出: 0
    • 解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
Read more

LeetCode[134] 加油站

Problem:

在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。

说明:

  • 如果题目有解,该答案即为唯一答案。
  • 输入数组均为非空数组,且长度相同。
  • 输入数组中的元素均为非负数。

示例 1: 输入:

  • gas = [1,2,3,4,5]
  • cost = [3,4,5,1,2]

输出: 3 解释:

  • 从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
  • 开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
  • 开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
  • 开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
  • 开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
  • 开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
  • 因此,3 可为起始索引。

示例 2: 输入:

  • gas = [2,3,4]
  • cost = [3,4,3]
  • 输出: -1
  • 解释: 你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。因此,无论怎样,你都不可能绕环路行驶一周。
Read more

LeetCode[376] 摆动序列

Problem:

  • 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

    例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

    给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

    示例 1:

    • 输入: [1,7,4,9,2,5]
    • 输出: 6
    • 解释: 整个序列均为摆动序列。

    示例 2:

    • 输入: [1,17,5,10,13,15,10,5,16,8]
    • 输出: 7
    • 解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。

    示例 3:

    • 输入: [1,2,3,4,5,6,7,8,9]
    • 输出: 2
Read more

LeetCode[300] 最长递增子序列


Related Topics:
“数组”: https://leetcode.com/tag/array/
“二分查找”: https://leetcode.com/tag/binary-search/
“动态规划”: https://leetcode.com/tag/dynamic-programming/
Similar Questions:
“递增的三元子序列”: https://leetcode.com/problems/increasing-triplet-subsequence/
“俄罗斯套娃信封问题”: https://leetcode.com/problems/russian-doll-envelopes/
“最长数对链”: https://leetcode.com/problems/maximum-length-of-pair-chain/
“最长递增子序列的个数”: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
“两个字符串的最小ASCII删除和”: https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

Problem:

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

提示:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶:

  • 你可以设计时间复杂度为 O(n2) 的解决方案吗?
  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
Read more