贪心算法
如何判断是否使用贪心算法
选择是否影响未来可行性
比如凑硬币，存在硬币[1,5,8]，不可重复选，凑出金额6的最少硬币数：
如果是贪心的话，首先会考虑先选8，这显然是不行的，那么就要退回，退回的话就不能用贪心算法，也就是说这次的选择导致不能往后选了
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 青柠！
相关推荐
2025-09-08
【力扣45】跳跃游戏II
题目给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处： 0 <= j <= nums[i] 且 i + j < n 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。 示例 1: 1234输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2: 12输入: nums = [2,3,0,1,4]输出: 2 提示: 1 <= nums.length <= 104 0 <= nums[i] <= 1000 题目保证可以到达 n - 1 实现代码12345678910111213141516171819202122class Solution { public int jump(int[] nu...
2025-10-25
【Spring Framework】自动装配
问题思考 自动装配是什么？ 自动装配解决了什么问题？ 没有自动装配的时候是怎么注入依赖的？假设用xml方式进行元数据配置，如下： 未使用自动装配 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class Person { private Superpower superpower; public Superpower getSuperpower() { return superpower; } public void setSuperpower(Superpower superpower) { this.superpower = superpower; }}public class Superpower { private String name; private String description; ...
2025-09-17
【力扣104】二叉树的最大深度
题目给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1： 12输入：root = [3,9,20,null,null,15,7]输出：3 示例 2： 12输入：root = [1,null,2]输出：2 提示： 树中节点的数量在 [0, 104] 区间内。 -100 <= Node.val <= 100 实现代码 通过二叉树的递归遍历（DFS）实现 方式一 前序遍历 1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val)...
2025-09-13
【力扣142】环形链表
题目给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1： 123输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 123输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 123输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。 提示： 链表中节点的数目范围在范围 [0, 104] 内 -105 <= Node.val <= 105 pos 的值为 -1 或者...
2025-09-13
【力扣160】相交链表
题目给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 自定义评测： 评测系统 的输入如下（你设计的程序 不适用 此输入）： intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。 示例 1： 123456输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skip...
2025-09-13
【力扣167】两数之和II-输入有序数组
题目给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。 示例 1： 123输入：numbers = [2,7,11,15], target = 9输出：[1,2]解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 示例 2： 123输入：numbers = [2,3,4], target = 6输出：[1,3]解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, in...
评论
系列文章
