贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。
贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
1-煎饼排序
题目链接：题目链接戳这里！！！
思路:这题的思路和常规的冒泡排序很像，测试用例不唯一，只要满足题目要求就可以，就是每一轮先将最大值所在位置index，从0到index所有元素进行翻转，接下来将0到i的元素进行翻转，i是最后元素的位置，此时就可以把最大的元素放到最后了，如果当前元素已经在最后位置，则不需要翻转。
class Solution {
public List pancakeSort(int[] arr) {
List ans = new ArrayList<>() ;
for(int i=arr.length-1; i>0; i--){
int index = 0 ;
for(int j=1; j<=i; j++){
if(arr[index]<=arr[j]){
index = j ;
}
}
if(index==i){
continue ;
}
reverse(arr, index) ;
reverse(arr, i) ;
ans.add(index+1) ;
ans.add(i+1) ;
}
return ans ;
}
public void reverse(int [] arr, int end){
int begin = 0 ;
while(begin
2-三角形的最大周长
题目链接：题目链接戳这里！！！
思路：这一题如果对所有的数依次判断，复杂度就很高了，所以，我们仔细观察会发现，边按升序排序后，只要存在三角形，则三条边一定是连续着的，否则必然不存在三角形，知道这一点就可以立刻写出答案了。
class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums) ;
for(int i=nums.length-1; i>=2; i--){
int a = nums[i] ;
int b = nums[i-1] ;
int c = nums[i-2] ;
if(b+c>a){
return a+b+c ;
}
}
return 0 ;
}
}
3-坏了的计算器
题目链接：题目链接戳这里！！！
思路：逆向思维，用cnt计数，让target尽可能除以2，如果target是偶数，则直接除以2，同时cnt累加1次，如果target是奇数，则先加1除以2，cnt累加2次。
class Solution {
public int brokenCalc(int startValue, int target) {
int cnt = 0 ;
while(startValue < target){
if(target%2==0){
target /= 2 ;
cnt ++ ;
}else{
target = (target+1) / 2 ;
cnt += 2 ;
}
}
return cnt + startValue - target;
}
}
4-一手顺子
题目链接：题目链接戳这里！！！
思路：如果能进行分组，则n%groupSize必然等于0，否则，肯定不能分组，对hand数组按照升序排序，将每个数字出现的次数存入map中，然后遍历所有的hand中的数字，由于升序排序，每次出现在map中必然是最小的，判断连续groupSize的数是否存在即可。
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
int n = hand.length ;
if(n % groupSize != 0){
return false ;
}
Arrays.sort(hand) ;
Map map = new HashMap<>() ;
for(int hands : hand){
map.put(hands,map.getOrDefault(hands,0)+1) ;
}
for(int hands : hand){
if(!map.containsKey(hands)){ //如果当前值不存在了，则直接跳过
continue ;
}
for(int i=0; i
5-划分数组为连续数字的集合
题目链接：题目链接戳这里！！！
这一题和上一题是一样的，哈哈，就是题目名字不一样而已，AC代码如下：
class Solution {
public boolean isPossibleDivide(int[] nums, int k) {
int n = nums.length ;
if(n % k != 0){
return false ;
}
Arrays.sort(nums) ;
Map map = new HashMap<>() ;
for(int hands : nums){
map.put(hands, map.getOrDefault(hands,0)+1) ;
}
for(int hands : nums){
if(!map.containsKey(hands)){
continue ;
}
for(int i=0; i
6-K次取反后最大化的数组和
题目链接：题目链接戳这里！！！
思路：对数组元素进行升序排序，每次当k大于0，执行操作，如果是负数，直接翻转，如果是正数，则判断是否是第一个数，如果是，则剩下的翻转次数，都翻转第一个即可，如果不是第一个数，则比较当前值和前一个值得最小值，剩余得翻转次数都翻转最小值即可。
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums) ;
for(int i=0; i0){
if(nums[i] < 0){
nums[i] = -nums[i] ;
k -- ;
if(i==nums.length-1){
return (k%2)== 0 ? getSum(nums) : (getSum(nums)-2*nums[nums.length-1]) ;
}
}else{
if(i==0){
return (k%2==0) ? getSum(nums) : (getSum(nums)-2*nums[0]) ;
}else{
int min = Math.min(nums[i],nums[i-1]) ;
return (k%2==0) ? getSum(nums) : (getSum(nums)-2*min) ;
}
}
}
}
return getSum(nums) ;
}
public int getSum(int [] nums){
int sum = 0;
for(int num : nums){
sum += num ;
}
return sum ;
}
}
7-救生艇
题目链接：题目链接戳这里！！！
思路：每次尽量让目前体重最小得和体重最大的搭配，如果能搭配，就两个人一个船，否则就体重最大的一个船。
class Solution {
public int numRescueBoats(int[] people, int limit) {
int n = people.length ;
Arrays.sort(people) ;
int left = 0, right = n-1, ans = 0 ;
while(left<=right){
if(people[left]+people[right]<=limit){
left ++ ;
}
right -- ;
ans ++ ;
}
return ans ;
}
}
8-优势洗牌
题目链接：题目链接戳这里！！！
思路：每次对比nums2中最大值和nums1中的最大值，如果nums1中的最大值大于nums2中的最大值，则可以用nums1中的最大值，否则用nums1中的最小值。
class Solution {
public int[] advantageCount(int[] nums1, int[] nums2) {
//每次在数组nums1中寻找大于nums2[i]的最小值,如果没有，则选择nums1中的最小值
int [] ans = new int [nums1.length] ;
Arrays.sort(nums1) ;
PriorityQueue queue = new PriorityQueue<>(
(a,b) -> {
return b[1] - a[1] ;
}
) ;
for(int i=0; i arr[1]){
ans[arr[0]] = nums1[right--] ;
}else{
ans[arr[0]] = nums1[left++] ;
}
}
return ans ;
}
}
9-视频拼接
题目链接：题目链接戳这里！！！
思路：动态规划
dp[i]表示将区间0~i覆盖所需要的最少区间数量
初始时候设置dp数组中的值为最大，dp[0]=0
遍历区间上的点，如果当前点在子区间中，则得到递推式：
dp[i] = Math.min(dp[i],dp[clip[0]]+1) ;
class Solution {
public int videoStitching(int[][] clips, int time) {
int [] dp = new int [time+1] ;
//dp[i]表示将区间0~i覆盖所需要的最少区间数量
Arrays.fill(dp,Integer.MAX_VALUE-1) ;
dp[0] = 0 ;
for(int i=1; i<=time; i++){
for(int [] clip : clips){
if(i>clip[0] && i<=clip[1]){
dp[i] = Math.min(dp[i],dp[clip[0]]+1) ;
}
}
}
return dp[time] == Integer.MAX_VALUE-1 ? -1 : dp[time] ;
}
}
思路2：贪心
class Solution {
public int videoStitching(int[][] clips, int time) {
//贪心策略
int [] max = new int [time] ;
int pre=0, last=0, ans = 0 ;
for(int [] clip : clips){
if(clip[0]
10-分割平衡字符串
题目链接：题目链接戳这里！！！
思路：局部左右，全局最优，统计L和R的个数，每次相等则是一个平衡串，然后再重新开始统计L和R的个数。
class Solution {
public int balancedStringSplit(String s) {
int left = 0, right = 0, ans = 0 ;
for(int i=0; i
11-最长对数链
题目链接：题目链接戳这里！！！
思路：贪心策略，按照数组每行的第2列进行升序排序，然后依次判断能否添加为对数链即可。
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, new Comparator(){
public int compare(int [] a, int [] b){
return a[1] - b[1] ;
}
}) ;//按照第二个数进行升序排序
int ans = 0, cur = Integer.MIN_VALUE ;
for(int [] pair : pairs){
if(pair[0]>cur){
cur = pair[1] ;
ans ++ ;
}
}
return ans ;
}
}
12-交换字符使得字符串相同
题目链接：题目链接戳这里！！！
思路:当 s1 = “xx”，s2 = “yy” 时，只需交换一次，就可以使两个字符串相等
当 s1 = “xy”，s2 = “yx” 时，需要交换两次才可以使两个字符串相等
遍历比较两个字符串，如果s1[i] = s2[i] 则不用交换
xy 表示 s1[i] = x，s2[i] = y 的次数
yx 表示 s1[i] = yy，s2[i] = x 的次数
因为需要每两组字符才可以进行交换，如果 xy +yx 为奇数，必定有一组字符不能交换，返回 −1
优先交换所有的 “xx” “yy” 和 “yy” “xx”，因为只需一次交换
若还剩一组 “xy” “yx” 则再加 2 即可
class Solution {
public int minimumSwap(String s1, String s2) {
int xy=0, yx=0 ;
char [] c1 = s1.toCharArray() ;
char [] c2 = s2.toCharArray() ;
for(int i=0; i
13-6和9组成的最大的数字
题目链接：题目链接戳这里！！！
思路：从前向后遍历，将第一个6翻转成9即可，如果没有6就不翻转。
class Solution {
public int maximum69Number (int num) {
String s = String.valueOf(num) ;
char [] c = s.toCharArray() ;
for(int i=0; i
14-使括号有效的最少添加
题目链接：题目链接戳这里！！！
思路：左括号出现在右括号之前就是合法的括号，统计左括号的个数，如果出现右括号，则左括号个数减1，如果出现右括号且左括号没有多余的左括号与之匹配，则ans++，最后如果有多余的左括号，应该用右括号匹配。
class Solution {
public int minAddToMakevalid(String s) {
//左括号出现在右括号之前就是合法的括号
int ans = 0, left = 0 ;
for(int i=0; i0){
left -- ;
}else{
ans ++ ;
}
}else{
left ++ ;
}
}
return ans + left ;
}
}
15-破坏回文串
题目链接：题目链接戳这里！！！
思路：遍历前面一半，如果出现的字母不是a，则将其替换成啊，如果前一半全是a，则整个回文串都是a，则将回文串最后一个字符替换成b即可。
class Solution {
public String breakPalindrome(String palindrome) {
if(palindrome.length()==1){
return "" ;
}
char [] c = palindrome.toCharArray() ;
for(int i=0; i
**
千里之行，始于足下，前进吧，少年！！！
**
