LeetCode[39] 组合总和

Problem:

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1: 输入:candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]

示例 2: 输入:candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

Read more

LeetCode[494] 目标和

Problem:

    • 难度:中等

      给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

      返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

      示例:

      输入:nums: [1, 1, 1, 1, 1], S: 3
      输出:5

      解释:
      -1+1+1+1+1 = 3
      +1-1+1+1+1 = 3
      +1+1-1+1+1 = 3
      +1+1+1-1+1 = 3
      +1+1+1+1-1 = 3

      一共有5种方法让最终目标和为3。

      提示:

      • 数组非空,且长度不会超过 20 。
      • 初始的数组的和不会超过 1000 。
      • 保证返回的最终结果能被 32 位整数存下。
Read more

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[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[518] 零钱兑换 II

Problem:

  • 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

    示例 1:

    输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

    示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。

    示例 3: 输入: amount = 10, coins = [10] 输出: 1

    注意,你可以假设:

    • 0 <= amount (总金额) <= 5000
    • 1 <= coin (硬币面额) <= 5000
    • 硬币种类不超过 500 种
    • 结果符合 32 位符号整数
Read more