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[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

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

LeetCode[1143] 最长公共子序列

  1. Related Topics:
    “字符串”: https://leetcode.com/tag/string/
    “动态规划”: https://leetcode.com/tag/dynamic-programming/

    Problem:

    给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0

    一个字符串的 子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

    • 例如,"ace""abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

    两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

    示例 1:

    输入:text1 = "abcde", text2 = "ace" 
    输出:3  
    解释:最长公共子序列是 "ace" ,它的长度为 3 。

    示例 2:

    输入:text1 = "abc", text2 = "abc"
    输出:3
    解释:最长公共子序列是 "abc" ,它的长度为 3 。

    示例 3:

    输入:text1 = "abc", text2 = "def"
    输出:0
    解释:两个字符串没有公共子序列,返回 0 。

    提示:

    • 1 <= text1.length, text2.length <= 1000
    • text1text2 仅由小写英文字符组成。
Read more

LeetCode[198] 打家劫舍

Related Topics:
“数组”: https://leetcode.com/tag/array/
“动态规划”: https://leetcode.com/tag/dynamic-programming/
Similar Questions:
“乘积最大子数组”: https://leetcode.com/problems/maximum-product-subarray/
“打家劫舍 II”: https://leetcode.com/problems/house-robber-ii/
“粉刷房子”: https://leetcode.com/problems/paint-house/
“栅栏涂色”: https://leetcode.com/problems/paint-fence/
“打家劫舍 III”: https://leetcode.com/problems/house-robber-iii/
“不含连续1的非负整数”: https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/
“金币路径”: https://leetcode.com/problems/coin-path/
“删除并获得点数”: https://leetcode.com/problems/delete-and-earn/

Problem:

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
Read more