【每日算法Day 18】数组基础4
这次练习的是使用数组的贪心算法，贪心算法一般用来解决需要 “找到要做某事的最小数量” 或 “找到在某些情况下适合的最大物品数量” 的问题，核心是用局部最优解累积得到全局最优解，感觉个人在很多情况下都对这种特性不敏感，还是多见识吧。
# LeetCode 55. 跳跃游戏 (opens new window)
# 题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
# 示例
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
2
3
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
2
3
# 解题思路
贪心思想：从某一个能到达的位置i往后跳最远能到达的位置j=i+nums[i]，并且只要j位置能到达，那么它之前的所有位置都能到达。
因此记录一个最远到达位置max，从nums[0]开始扫描数组，如果发现当前i+nums[i]大于最远到达位置则更新max（如果max>=nums.length则能到达最后一个位置返回true）。在扫描过程中如果发现当前i大于max则说明i前面的点都到不了i，返回false。nums只有1位时开头就是结尾，返回true。
public boolean canJump(int[] nums) {
int max=0;
for (int i = 0; i < nums.length; i++) {
if (i > max) {
return false;
} else {
max=Math.max(max,i+nums[i]);
if (max>=nums.length) return true;
}
}
return true;
}
2
3
4
5
6
7
8
9
10
11
12
# LeetCode 122. 买卖股票的最佳时机 II (opens new window)
# 题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
# 示例
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
2
3
4
5
6
7
# 解题思路
贪心思想：只要相邻的一天有增长，就在当天买入，第二天卖出，否则不买入。每次只在第二天会有收入的情况下买入并卖出。即每次都是做出使得第二天总利润增加的选择。
对于单调增的序列，第一天买入最后一天卖出的利润和拆成其中每一天买入第二天卖出的利润是相同的；对于包含递减序列的序列，第一天买入最后一天卖出和拆分成每一天买卖相比，就一定会承担递减部分带来的损失。
public int maxProfit(int[] prices) {
if(prices==null||prices.length<=1) return 0;
int totalProfit=0;
for(int i=1;i<prices.length;i++){
int tmp=prices[i]-prices[i-1];
totalProfit+=tmp>0?tmp:0;
}
return totalProfit;
}
2
3
4
5
6
7
8
9
# LeetCode 1338. 数组大小减半 (opens new window)
# 题目描述
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。返回 至少 能删除数组中的一半整数的整数集合的最小大小。
# 示例
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
2
3
4
5
# 解题思路
使用哈希表统计数组中出现的每一种数组的出现次数，之后取出次数并排序，从大到小累加直到和的值超过数组大小的一半，这时相加的项数就是所求的最小大小。
我一开始没想到什么好主意，就想着只能用HashSet统计出现次数，然后优先去掉出现次数多的，感觉这就是硬算暴力法啊。。。
后来看了他人的解释：每次都选剩下的数据中最多数量的那个删除呢，由于各个数据之间没有任何联系，那么这种思路其实是能直接得到最优解的，其实这就是用局部最优解累积得到全局最优解的过程，也就是贪心算法。
public int minSetSize(int[] arr) {
//用HashMap来统计每种数字出现的次数
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num,map.get(num)+1);
}
}
//将HashMap中所有的value取出放置到数组中并排序
Integer[] appearCount=map.values().toArray(new Integer[0]);
Arrays.sort(appearCount);
//从大往小加，发现和大于等于原数组一半的长度时就返回加法的项数
int minCount=1,appearance=0;
for (int i = appearCount.length - 1; i >= 0; i--) {
appearance+=appearCount[i];
if (appearance>=arr.length/2)
return minCount;
minCount++;
}
return minCount;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25