Greedy-Algorithm

题目要求Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Example 1:Input: [[1,2],[2,3],[3,4],[1,3]]Output: 1Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.Example 2:Input: [[1,2],[1,2],[1,2]]Output: 2Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.Example 3:Input: [[1,2],[2,3]]Output: 0Explanation: You don't need to remove any of the intervals since they're already non-overlapping. Note:You may assume the interval's end point is always bigger than its start point.Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.使用二维数组表示区间组，每一个子数组的第一个值表示区间的开始坐标，第二个值表示区间的结束坐标。计算最少进行多少次删除操作，可以确保剩下的区间不会产生任何重叠。 ...

题目要求Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.Note:The number of people is less than 1,100.ExampleInput:[[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]]假设有一组人站成一堆，每个人都记录下了自己的高度，以及在自己前面有多少个不比自己矮的人。现在请按照这个信息将这组人放在队列中正确的位置上并返回。思路和代码刚开始我试图用分治法来解决，因为每一个小队列中，高度最矮且站在自己前面的高个最少的人一定位于k位置上。但是这样解决其实复杂化了问题。可以从另一个角度来想，首先我们知道，同等高度的人，其相对位置一定是根据k的值从小到大排列的。即k越大，则该同等高度的人一定在另一个同等高度的人后面。如果我们从高到低将人们插入队列中，可以知道，k的值就该人在当前队列中的下标，如：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]首先将其按照h和k排序，得出结果：[[7,0],[7,1],[6,1],[5,1],[5,0],[5,2],[4,4]]当前结果队列为[]将[7,0]插入下标为0的位置上 结果队列[[7,0]]将[7,1]插入下标为1的位置上 结果队列[[7,0],[7,1]]将[6,1]插入下标为1的位置上 结果队列[[7,0],[6,1],[7,1]]按照这种规则，依次按照顺序和k的值将数据插入结果队列中代码如下： public int[][] reconstructQueue(int[][] people) { int[][] result = new int[people.length][2]; Arrays.sort(people, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]; } }); for(int i = 0 ; i<people.length ; i++) { int pos = people[i][1]; for (int j = i; j > pos; j–) { result[j] = result[j - 1]; } result[pos] = people[i]; } return result; } ...

题目要求Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.Note:The length of num is less than 10002 and will be ≥ k.The given num does not contain any leading zero.Example 1:Input: num = “1432219”, k = 3Output: “1219"Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.Example 2:Input: num = “10200”, k = 1Output: “200"Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.Example 3:Input: num = “10”, k = 2Output: “0"Explanation: Remove all the digits from the number and it is left with nothing which is 0.假设现在有一个用字符串表示的非负的整数，问从中删除掉k个数字后能够得到的最小结果是多少？思路和代码直观的来说，删除数字得到最小的数字意味着我们应当尽可能的将越小的数字保留在高位，因此当我们从左往右遍历时，一旦遇到比前一个数字更小的数字，就应当删除前一个数字而保留这个数字。当我们用尽了所有删除时，就保留后面所有的数字，不再进行任何比较。因为我们已经尽可能获得了最小的最高位，因此无论后面的数字如何取值，其最高位上的数字一定是可以获得的最小的这个数字。举个例子：10200 k=1第一步： 0和1比较，此时0比1小，且还有一次可用的删除，因此删除1，保留0第二步：因为无可用的删除次数，因此剩下的值全部保留123450123 k=5第一步：2>1 保留第二步：3>2 保留第三步: 4>3 保留第四步: 5>4 保留第五步：0<5 删除5 保留0 k=4第六步: 0<4 删除4 保留0 k=3第七步：0<3 删除3 保留0 k=2第八步：0<2 删除2 保留0 k=1第九步：0<1 删除1 保留0 k=0第十步: 此时所有的删除次数用完，因此剩余的值全部保留可以看到，当我们遇到较小值时，我们会尽可能的将其往左边移动，因为只要它比左边的值小且剩余删除次数，则删除左边的值一定会得到一个更小的值。代码如下： public String removeKdigits(String num, int k) { if(num == null || num.length() == 0 || k==num.length()) return “0”; Stack<Character> stack = new Stack<>(); for(int i = 0 ; i < num.length() ; i++) { char c = num.charAt(i); while(k> 0 && !stack.isEmpty() && stack.peek() > c) { stack.pop(); k–; } stack.push(c); } while(k > 0) { stack.pop(); k–; } StringBuilder result = new StringBuilder(); while(!stack.isEmpty()) { result.append(stack.pop()); } while(result.length() > 1 && result.charAt(result.length()-1) == ‘0’) { result.deleteCharAt(result.length()-1); } return result.reverse().toString(); } ...

ProblemGiven a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.If possible, output any possible result. If not possible, return the empty string.Example 1:Input: S = “aab"Output: “aba"Example 2:Input: S = “aaab"Output: ““Note:S will consist of lowercase letters and have length in range [1, 500].Solutionclass Solution { public String reorganizeString(String S) { int n = S.length(); int[] cnt = new int[128]; char mc = ‘a’; for (char c : S.toCharArray()) { cnt[c]++; mc = (cnt[c] > cnt[mc]) ? c : mc; } if (cnt[mc] == 1) { return S; } if (cnt[mc] > (n+1)/2) { return “”; } StringBuilder[] sb = new StringBuilder[cnt[mc]]; for (int i = 0; i < sb.length; i ++) { sb[i] = new StringBuilder(); sb[i].append(mc); } int k = 0; for (char c = ‘a’; c <= ‘z’; c++) { while (c != mc && cnt[c] > 0) { sb[k++].append(c); cnt[c]–; k %= sb.length; } } for (int i = 1; i < sb.length; i++) { sb[0].append(sb[i]); } return sb[0].toString(); }} ...

题目要求Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.Example 1:Input: nums = [1,3], n = 6Output: 1 Explanation:Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].So we only need 1 patch.Example 2:Input: nums = [1,5,10], n = 20Output: 2Explanation: The two patches can be [2, 4].Example 3:Input: nums = [1,2,2], n = 5Output: 0假设有一个有序的正整数数组nums和一个整数n，最少添加几个元素到这个数组中，使得从1-n的所有整数都可以由这个数组中的值的或是几个值的和构成。思路和代码这里的核心思路在于如何找到一个规律，使得我们可以在前一个规律的基础上添加一个数达到下一个范围。假设当前的数组可以组成从[1…k]的所有整数，那么我们下一步如果往数组中添加x，则数组就可以组成从[1…k+x]的所有整数。因此，为了只打最少的补丁，我们会希望每一次往数组中添加的元素所能够到达的范围越远越好，因此我们会patch一个k+1上去从而使得数组最远扩展到[1…2k+1]。如果当前数组中存在一个数组m位于[k+1, 2k+1]这个范围中，则我们的数组可以再次扩展到[1…2k+m+1]。 public int minPatches(int[] nums, int n) { int count = 0; long max = 0; int index = 0; while(max < n) { if(index<nums.length && max + 1 >= nums[index]) { max += nums[index++]; } else { count++; max += max + 1; } } return count; }这里需要注意的细节是数组的溢出。这里用long型避免数组值的溢出。 ...