-
【leetcode】70-greedy 贪心算法
chat
详细介绍一下 贪心算法
贪心算法(Greedy Algorithm)是一种在每一步选择当前状态下局部最优解的算法策略,希望通过一系列局部最优选择得到全局最优解。
贪心算法通常比其他方法(如动态规划)简单、高效,但它并不总是适用,也无法保证在所有情况下找到最优解。
因此,使用贪心算法时需要先确认问题是否满足贪心选择的条件。
贪心算法的特点
贪心选择性质:
...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】62-337. house-robber-iii 力扣 337. 打家劫舍 III dynamic-programming
题目
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
给定二叉树的 root 。
返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
示例...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】62-213. house-robber-ii 力扣 213. 打家劫舍 II dynamic-programming
题目
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 1:
输入:nums ...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】61-198. house-robber 力扣 198. 打家劫舍 dynamic-programming
题目
你是一个专业的小偷,计划偷窃沿街的房屋。
每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】57-1371. find-the-longest-substring-containing-vowels-in-even-counts 力扣 1371. 每个元音包含偶数次的最长子字符串
开源地址
为了便于大家学习,所有实现均已开源。欢迎 fork + star~
https://github.com/houbb/leetcode
题目
题目描述
给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 ‘a’,’e’,’i’,’o’,’u’ ,在子字符串中都恰好出现了偶数次。
示例 1:
输入:s = “eleetminicowo...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】56-560. subarray-sum-equals-k 力扣 560. 和为 k 的子数组 前缀和+HashMap
开源地址
为了便于大家学习,所有实现均已开源。欢迎 fork + star~
https://github.com/houbb/leetcode
题目
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】53-525. continuous-subarray-sum 力扣 525. 连续的子数组和 同余定理 前缀和+HashMap
开源地址
为了便于大家学习,所有实现均已开源。欢迎 fork + star~
https://github.com/houbb/leetcode
题目
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长...
2020-06-08 07:13:08 |
Algorithm
-
【leetcode】54-325. max-size-subarray-sum-equals-k 力扣 325:和等于 k 的最长子数组长度
开源地址
为了便于大家学习,所有实现均已开源。欢迎 fork + star~
https://github.com/houbb/leetcode
说明
这一题实际上非常重要,很多题目都是这一题的变形或者转换。
题目
给定一个数组 nums 和一个目标值 k,找出和为 k 的最长子数组的长度。如果不存在这样的子数组,返回 0。
示例 1:
给定 nums = [1, -...
2020-06-08 07:13:08 |
Algorithm