网站建设工作报告,西宁网站制作公司,网页编辑超级工具箱,注册万网后网站怎么赚钱的本文主要介绍算法中贪心算法的思想: 保证每次操作都是局部最优的#xff0c;并且最后得到的结果是全局最优的。贪心思想相关题目分配饼干455. Assign Cookies (Easy)Input: [1,2], [1,2,3]
Output: 2Explanation: You have 2 children and 3 cookies. The greed factors of 2 …本文主要介绍算法中贪心算法的思想: 保证每次操作都是局部最优的并且最后得到的结果是全局最优的。贪心思想相关题目分配饼干455. Assign Cookies (Easy)Input: [1,2], [1,2,3]
Output: 2Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.题目描述: 每个孩子都有一个满足度每个饼干都有一个大小只有饼干的大小大于等于一个孩子的满足度该孩子才会获得满足。求解最多可以获得满足的孩子数量。给一个孩子的饼干应当尽量小又能满足该孩子这样大饼干就能拿来给满足度比较大的孩子。因为最小的孩子最容易得到满足所以先满足最小的孩子。证明: 假设在某次选择中贪心策略选择给当前满足度最小的孩子分配第 m 个饼干第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略给该孩子分配第 n 个饼干并且 m n。我们可以发现经过这一轮分配贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略即贪心策略就是最优策略。public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int gi 0, si 0;while (gi g.length si s.length) {if (g[gi] s[si]) {gi;}si;}return gi;
}不重叠的区间个数435. Non-overlapping Intervals (Medium)Input: [ [1,2], [1,2], [1,2] ]Output: 2Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.Input: [ [1,2], [2,3] ]Output: 0Explanation: You dont need to remove any of the intervals since theyre already non-overlapping.题目描述: 计算让一组区间不重叠所需要移除的区间个数。计算最多能组成的不重叠区间个数然后用区间总个数减去不重叠区间的个数。在每次选择中区间的结尾最为重要选择的区间结尾越小留给后面的区间的空间越大那么后面能够选择的区间个数也就越大。按区间的结尾进行排序每次选择结尾最小并且和前一个区间不重叠的区间。public int eraseOverlapIntervals(Interval[] intervals) {if (intervals.length 0) {return 0;}Arrays.sort(intervals, Comparator.comparingInt(o - o.end));int cnt 1;int end intervals[0].end;for (int i 1; i intervals.length; i) {if (intervals[i].start end) {continue;}end intervals[i].end;cnt;}return intervals.length - cnt;
}使用 lambda 表示式创建 Comparator 会导致算法运行时间过长如果注重运行时间可以修改为普通创建 Comparator 语句:Arrays.sort(intervals, new ComparatorInterval() {Overridepublic int compare(Interval o1, Interval o2) {return o1.end - o2.end;}
});投飞镖刺破气球452. Minimum Number of Arrows to Burst Balloons (Medium)Input:
[[10,16], [2,8], [1,6], [7,12]]Output:
2题目描述: 气球在一个水平数轴上摆放可以重叠飞镖垂直投向坐标轴使得路径上的气球都会刺破。求解最小的投飞镖次数使所有气球都被刺破。也是计算不重叠的区间个数不过和 Non-overlapping Intervals 的区别在于[1, 2] 和 [2, 3] 在本题中算是重叠区间。public int findMinArrowShots(int[][] points) {if (points.length 0) {return 0;}Arrays.sort(points, Comparator.comparingInt(o - o[1]));int cnt 1, end points[0][1];for (int i 1; i points.length; i) {if (points[i][0] end) {continue;}cnt;end points[i][1];}return cnt;
}根据身高和序号重组队列406. Queue Reconstruction by Height(Medium)Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]题目描述: 一个学生用两个分量 (h, k) 描述h 表示身高k 表示排在前面的有 k 个学生的身高比他高或者和他一样高。为了在每次插入操作时不影响后续的操作身高较高的学生应该先做插入操作否则身高较小的学生原先正确插入第 k 个位置可能会变成第 k1 个位置。身高降序、k 值升序然后按排好序的顺序插入队列的第 k 个位置中。public int[][] reconstructQueue(int[][] people) {if (people null || people.length 0 || people[0].length 0) {return new int[0][0];}Arrays.sort(people, (a, b) - (a[0] b[0] ? a[1] - b[1] : b[0] - a[0]));Listint[] queue new ArrayList();for (int[] p : people) {queue.add(p[1], p);}return queue.toArray(new int[queue.size()][]);
}分隔字符串使同种字符出现在一起763. Partition Labels (Medium)Input: S ababcbacadefegdehijhklij
Output: [9,7,8]
Explanation:
The partition is ababcbaca, defegde, hijhklij.
This is a partition so that each letter appears in at most one part.
A partition like ababcbacadefegde, hijhklij is incorrect, because it splits S into less parts.public ListInteger partitionLabels(String S) {int[] lastIndexsOfChar new int[26];for (int i 0; i S.length(); i) {lastIndexsOfChar[char2Index(S.charAt(i))] i;}ListInteger partitions new ArrayList();int firstIndex 0;while (firstIndex S.length()) {int lastIndex firstIndex;for (int i firstIndex; i S.length() i lastIndex; i) {int index lastIndexsOfChar[char2Index(S.charAt(i))];if (index lastIndex) {lastIndex index;}}partitions.add(lastIndex - firstIndex 1);firstIndex lastIndex 1;}return partitions;
}private int char2Index(char c) {return c - a;
}种植花朵605. Can Place Flowers (Easy)Input: flowerbed [1,0,0,0,1], n 1
Output: True题目描述: 花朵之间至少需要一个单位的间隔求解是否能种下 n 朵花。public boolean canPlaceFlowers(int[] flowerbed, int n) {int len flowerbed.length;int cnt 0;for (int i 0; i len cnt n; i) {if (flowerbed[i] 1) {continue;}int pre i 0 ? 0 : flowerbed[i - 1];int next i len - 1 ? 0 : flowerbed[i 1];if (pre 0 next 0) {cnt;flowerbed[i] 1;}}return cnt n;
}判断是否为子序列392. Is Subsequence (Medium)s abc, t ahbgdc
Return true.public boolean isSubsequence(String s, String t) {int index -1;for (char c : s.toCharArray()) {index t.indexOf(c, index 1);if (index -1) {return false;}}return true;
}修改一个数成为非递减数组665. Non-decreasing Array (Easy)Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.题目描述: 判断一个数组能不能只修改一个数就成为非递减数组。在出现 nums[i] nums[i - 1] 时需要考虑的是应该修改数组的哪个数使得本次修改能使 i 之前的数组成为非递减数组并且 不影响后续的操作 。优先考虑令 nums[i - 1] nums[i]因为如果修改 nums[i] nums[i - 1] 的话那么 nums[i] 这个数会变大就有可能比 nums[i 1] 大从而影响了后续操作。还有一个比较特别的情况就是 nums[i] nums[i - 2]只修改 nums[i - 1] nums[i] 不能使数组成为非递减数组只能修改 nums[i] nums[i - 1]。public boolean checkPossibility(int[] nums) {int cnt 0;for (int i 1; i nums.length cnt 2; i) {if (nums[i] nums[i - 1]) {continue;}cnt;if (i - 2 0 nums[i - 2] nums[i]) {nums[i] nums[i - 1];} else {nums[i - 1] nums[i];}}return cnt 1;
}股票的最大收益122. Best Time to Buy and Sell Stock II (Easy)题目描述: 一次股票交易包含买入和卖出多个交易之间不能交叉进行。对于 [a, b, c, d]如果有 a b c d 那么最大收益为 d - a。而 d - a (d - c) (c - b) (b - a) 因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] 0那么就把 prices[i] - prices[i-1] 添加到收益中从而在局部最优的情况下也保证全局最优。public int maxProfit(int[] prices) {int profit 0;for (int i 1; i prices.length; i) {if (prices[i] prices[i - 1]) {profit (prices[i] - prices[i - 1]);}}return profit;
}
