面试资料

分割等和子集给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 示例 1： 123输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2： 123输入：nums = [1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。 提示： 1 <= nums.length <= 200 1 <= nums[i] <= 100 问题就相当于从数组中挑选数字组成的和恰好等于数组总和的一半，是01背包问题。 f[i][j]表示前i个数是否可以恰好组成j。 初始化f[i][0]=true,表示如果都不选，可以组成0. 123456789101112131415161718192021222324252627282930class Solution { public boolean canPartition(int[] nums) { int total = 0; ...

乘积最大子数组给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组 （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 示例 1: 123输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 123输入: nums = [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 提示: 1 <= nums.length <= 2 * 104 -10 <= nums[i] <= 10 nums 的任何子数组的乘积都 保证 是一个 32-位 整数 如果数组中都是正数问题很简单,f[i]表示以nums[i]结尾的子数组乘积最大值,f[i]=Math.max(nums[i],f[i-1]*nums[i]) 但是数组中既包括正数又包括负数，这种做法并不满足最优子结构，如果nums={5,6,−3,4,−3},f={5,6,−3,4,−3},这样得到的答案是6，但显然答案 ...

最长递增子序列给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列 。 示例 1： 123输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2： 12输入：nums = [0,1,0,3,2,3]输出：4 示例 3： 12输入：nums = [7,7,7,7,7,7,7]输出：1 提示： 1 <= nums.length <= 2500 -104 <= nums[i] <= 104 进阶： 你能将算法的时间复杂度降低到 O(n log(n)) 吗? f[i]表示以nums[i]结尾的最长子序列的长度。当i之前有小于nums[i]的数nums[j] 时状态转移,f[i]=Math.max(f[i],f[j]+1),答案就是f中的最大值 1234567891011121314151617 ...

单词拆分给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 示例 1： 123输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。 示例 2： 1234输入: s = "applepenapple", wordDict = ["apple", "pen"]输出: true解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用 ...

零钱兑换给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 123输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1 示例 2： 12输入：coins = [2], amount = 3输出：-1 示例 3： 12输入：coins = [1], amount = 0输出：0 提示： 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104 完全背包问题，f[i][j]表示从前i个零钱中选择组合成j的最小硬币数量 1234567891011121314151617181920212223class Solution { public int coinChange(int[] coins, int ...

完全平方数给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例 1： 123输入：n = 12输出：3 解释：12 = 4 + 4 + 4 示例 2： 123输入：n = 13输出：2解释：13 = 4 + 9 提示： 1 <= n <= 104 问题可以转化为从所有的完全平方数中选择，求出相加恰好等于n的最少数量，由于每个完全平方数的数量是无限的所以是一个完全背包问题。 f[i][j]表示从前i个完全平方数中组成j的最少数量。 f[i][j]=Math.min(f[i-1][j],f[i][j-i*i]) 123456789101112131415161718192021class Solution { public int numSquares(int n) { int N = 100; // f[i][j]表示用前i个完全平方数组成j的 ...

打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 1234输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2： 1234输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 提示： 1 <= nums.length <= 100 0 <= nums[i] <= 400 f[i]表示有i间房屋时的打劫金额最大值，假设有三间房子，一共有两种抢劫方法 打劫第一间和第三间：f[3]=f[0]+nums[ ...

杨辉三角给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。 示例 1: 12输入: numRows = 5输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 12输入: numRows = 1输出: [[1]] 提示: 1 <= numRows <= 30 把杨辉三角的每一排左对齐： 12345[1][1,1][1,2,1][1,3,3,1][1,4,6,4,1] 每一排的第一个数和最后一个数都是1 其余数字res[i][j] = res[i-1][j-1]+res[i-1][j]

爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1： 12345输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶 示例 2： 123456输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶 提示： 1 <= n <= 45 要解决从0爬到n有多少种方法， 如果最后1步爬了1个台阶，要解决的问题变成了从0爬到n-1有多少种方法。 如果最后1步爬了2个台阶，要解决的问题变成了从0爬到n-2有多少种方法。 所以原问题就拆解成从0爬到n-1的方法总和+从0爬到n-2的方法总和 可以使用递归解决 123456789101112class Solution { public int climbStairs(int n) { return dfs(n); } private int dfs(int n) ...

划分字母区间给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 示例 1： 123456输入：s = "ababcbacadefegdehijhklij"输出：[9,7,8]解释：划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。每个字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 示例 2： 12输入：s = "eccbbbbdec"输出：[10] 提示： 1 <= s.length <= 500 s 仅由小写英文字母组成 题目本质就是合并区间，统计每个字母出现的第一个位置和最后一个位置，将有重叠的区间合并起来。 因为字母的下标是天然有序的，所以只需 ...