沈阳市网站建设企业,江苏网站快速排名优化,宿州住房和城乡建设局网站,企业推广策划书模板#x1f525; 个人主页: 黑洞晓威 #x1f600;你不必等到非常厉害#xff0c;才敢开始#xff0c;你需要开始#xff0c;才会变的非常厉害。 491. 非递减子序列
给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少… 个人主页: 黑洞晓威 你不必等到非常厉害才敢开始你需要开始才会变的非常厉害。 491. 非递减子序列
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
示例 1
输入nums [4,6,7,7]
输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2
输入nums [4,4,3,2,1]
输出[[4,4]]解题思路
要找出数组中的递增子序列可以采用回溯法Backtracking进行求解。回溯法是一种通过尝试所有可能的候选解来求解问题的方法。在这个问题中我们需要按照一定的规则来构建递增子序列并记录下符合条件的结果。
具体的解题思路如下
定义一个递归函数 backtrack传入以下参数 start当前处理的起始位置。path当前的递增子序列。 在递归函数中从 start位置开始遍历数组对于每个元素判断是否可以将其加入到当前的子序列中 如果可以加入即当前元素大于等于子序列的最后一个元素则将其加入到 path 中并递归调用 backtrack 函数继续处理下一个位置。处理完当前位置后需要将当前元素从 path 中移除以便尝试其他可能的组合。 在递归的过程中如果发现当前的 path 中至少有两个元素则将其加入到结果集中。
代码
import java.util.ArrayList;
import java.util.List;public class IncreasingSubsequences {public ListListInteger findSubsequences(int[] nums) {ListListInteger result new ArrayList();ListInteger path new ArrayList();backtrack(nums, 0, path, result);return result;}private void backtrack(int[] nums, int start, ListInteger path, ListListInteger result) {if (path.size() 2) {result.add(new ArrayList(path));}if (start nums.length) {return;}// 使用 Set 避免重复元素SetInteger used new HashSet();for (int i start; i nums.length; i) {if (!used.contains(nums[i]) (path.isEmpty() || nums[i] path.get(path.size() - 1))) {path.add(nums[i]);used.add(nums[i]);backtrack(nums, i 1, path, result);path.remove(path.size() - 1);}}}public static void main(String[] args) {int[] nums1 {4, 6, 7, 7};int[] nums2 {4, 4, 3, 2, 1};IncreasingSubsequences solution new IncreasingSubsequences();ListListInteger result1 solution.findSubsequences(nums1);ListListInteger result2 solution.findSubsequences(nums2);System.out.println(result1);System.out.println(result2);}
}
122. 买卖股票的最佳时机 II
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。总利润为 4 3 7 。示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。总利润为 4 。解题思路
要计算能获得的最大利润可以采用贪心算法的思想。贪心算法的核心思想是每一步都选择当前状态下最优的选择从而希望能够得到全局最优解。
具体解题思路如下
遍历股票价格列表计算相邻两天的价格差如果价格差为正数则表示可以在这两天进行交易并且利润增加。将所有正数的价格差相加即可得到总利润。
代码
public class MaxProfitII {public int maxProfit(int[] prices) {int maxProfit 0;for (int i 1; i prices.length; i) {if (prices[i] prices[i - 1]) {maxProfit prices[i] - prices[i - 1];}}return maxProfit;}public static void main(String[] args) {int[] prices1 {7, 1, 5, 3, 6, 4};int[] prices2 {1, 2, 3, 4, 5};MaxProfitII solution new MaxProfitII();System.out.println(solution.maxProfit(prices1)); // Output: 7System.out.println(solution.maxProfit(prices2)); // Output: 4}
}
