漫漫长夜

题目描述 解法 动态规划 dp[i]为存储第i个元素结尾的乘积最大的子数值的乘积 很容易得到动态方程：dp[i]=dp[i-1]*nums[i]与num[i]当前值进行比较 问题是，当dp[i-1]与num[i]异号时，该动态方程就失效了 考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。 如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。 状态转移方程为 1234567dpMax[i]=Math.max(Math.max(dpMax[i-1]*nums[i],dpMin[i-1]*nums[i]),nums[i]);//假设当前为正数。正数与前子序列最大积相乘---dpMax[i-1]*nums[i]//假设当前为负数。负数与前子序列最小积相乘，负负得正---dpMin[i-1]*nums[i]//如果存在子序列最大乘积和子序列最小乘积都为0,就东山再起，当前元素---nums[i]//三种情况取最 ...

题目描述给你一个 只包含正整数 的 非空 数组 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 解法 动态规划 将问题转换为：判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半 特殊判断 元素个数>2 元素和为偶数 数组内不得有单个数>sum/2； 定义dp[i][j]为表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数的和等于 j 边界情况 如果不选取任何正整数，则被选取的正整数和等于0。因此对于所有 0≤i<n，都有 dp[i][0]&# ...

题目描述给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例 1： 123输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输出：3解释：和等于 8 的路径有 3 条，如图所示。 示例 2： 12输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：3 提示: 二叉树的节点个数的范围是 [0,1000] -10^9 <= Node.val <= 10^9 -1000 <= targetSum <= 1000 解法 前缀和+深度优先搜索 记录下根节点 root到当前节点 p的路径上除当前节点以外所有节点的前缀和 在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 currentS ...

题目描述 解法 动态规划 dp[i]表示以i之前的子数组之和的最大值 那么dp[i+1]的值就取决于dp[i]和nums[i]的关系 如果dp[i-1]<0,那就另起炉灶dp[i]=nums[i] 如果dp[i-1]>0,那么dp[i]=dp[i-1]+num[i] 1234567891011121314151617181920212223242526272829class Solution { public int maxSubArray(int[] nums) { if(nums.length==1){ return nums[0]; } //dp为 前面n项数的和的最大值 int []dp=new int[nums.length]; dp[0]=nums[0]; for (int i = 1; i < nums.length; i++) { ...

打家劫舍I 解法 动态规划 偷窃第i间房，所获得的金额应该为第i间房的金额+前i-2间房的最高总金额之和 不偷第i间房，所获得的金额应该为前i-1间房的最高总金额之和 在两个选项中选择最大的即可 dp[i]=max(dp[i−2]+nums[i],dp[i−1]) 1234567891011121314class Solution { public int rob(int[] nums) { if(nums.length==1){ return nums[0]; } int dp[]=new int[nums.length]; dp[0]=nums[0]; dp[1]=Math.max(nums[0],nums[1]); for (int i = 2; i < nums.length; i++) { dp[i]=Math.max(dp[i-2]+nums[i],dp[ ...

题目描述 解法 贪心 我们所持有的面额只有5 10 20 相应我们需要找的钱为0 5 15 5块钱直接忽略 10块钱看还有没有5元的零钱 20块钱的分两种情况 5+10 5+5+5 这里优先考虑5+10，因为5元的用处更多，我们要尽可能的保留5元面值的钱 123456789101112131415161718192021222324252627282930313233343536class Solution { public boolean lemonadeChange(int[] bills) { boolean result = true; int money5 = 0; int money10 = 0; //定义两种面额的持有量，默认为0 for (int i = 0; i < bills.length; i++) { if (bills[i] == 5) { money5++; ...

题目描述 解法 贪心 求最大利润，及为求卖出和买入的最大差值 只要不亏钱就买卖 123456789101112class Solution { public int maxProfit(int[] prices) { int result=0; for (int i = 1; i <= prices.length-1; i++) { if(prices[i]>prices[i-1]){ //只要今天比昨天要高就进行买卖 result+=prices[i]-prices[i-1]; } } return result; }} 时间复杂度 O(n) 来源：力扣（LeetCode）链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com) 题目描述 解法 动态规划 转移方 ...

题目描述 解法 贪心 每次都找能跳的最远的距离，最后跟数组长度比较 注意当前位置是否可达，才能更新最大长度 i++相当于一步一步走 maxLen相当于是跳着走 如果i>=maxLen，说明该位置不可达 1234567891011121314151617class Solution { public boolean canJump(int[] nums) { int maxLength=0; for (int i = 0; i < nums.length; i++) { //遍历数组 if(i<=maxLength){ //当前位置可以到达，才能动态更新最大长度 maxLength=Math.max(maxLength,i+nums[i]); }//对当前最大长度前的数组的每一个元素求跳跃最大值 if(maxLength& ...

题目描述 解法 贪心 能种就种 这里可以种花的条件是： 自己为空 左边为空 或者 自己是最左 右边为空 或者 自己是最右 123456789101112131415class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { for (int i = 0; i < flowerbed.length; i++) { if(flowerbed[i]==0&&(i==0||flowerbed[i-1]==0)&&(i==flowerbed.length-1||flowerbed[i+1]==0)){ //&&与||运算符具有短路效果，所以不会产生数组越界 n--; if(n<=0){ break; ...

题目描述 解法 双指针+贪心 通过题目描述，需要获得最大的面积，很容易想到双指针，通过左右指针进行变换，改变面积 指针如何移动：为了获得最大的面积 ->即长*宽，让这两个相乘的因子最大（贪心思想） 长：就是左右指针的距离，一开始分别在左右两端—-长度最大 宽：就是垂线的高度，由于盛水的短板效应，这里应该选择两者短的那个。 所以我们应该移动短的那个指针，让高度的落差减小。 最后题目要求是要求最大面积，每次移动后还需要对面积进行比较，更新最大面积 代码1234567891011121314151617181920212223class Solution { public int maxArea(int[] height) { int area=0; int left=0,right=height.length-1; while (left<right){ //当左右指针相遇，遍历结束 area=Math.max(area ...