本篇博客旨在整理记录自己刷的一些基础题的思路、代码以及注解，同时希望可给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉 ?。
文章目录
贪心算法1005.K次取反后最大化的数组和1323. 6 和 9 组成的最大数字1217. 玩筹码942. 增减字符串匹配605. 种花问题860. 柠檬水找零 最后
贪心算法
1005.K次取反后最大化的数组和
难度：简单
题目：给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
提示：
1 <= nums.length <= 104-100 <= nums[i] <= 1001 <= k <= 104 示例 1：
输入：nums = [4,2,3], k = 1输出：5解释：选择下标 1 ，nums 变为 [4,-2,3] 。示例 2：
输入：nums = [3,-1,0,2], k = 3输出：6解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2输出：13解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。解题代码：
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { //先排序 Arrays.sort(nums); int i=0,ans=0,n=nums.length; //给数组中的负数从小到大取反 while(k>0&&i<n&&nums[i]<0) { nums[i]=-nums[i++]; k--; } //k=0的话，数组已经达到取反最大数组和 //k>0，说明nums已经全是非负数，剩余取反只要反复操作最小数即可，且次数为奇数才会发生变化 if(k>0&&k%2==1){ //i==0说明nums原本就是非负数，最小数为nums[i] //0<i<n，说明数组中原先就有非负数，此时最小数为nums[i]和最后一个取反的负数nums[i-1]的较小数 //i=n,，说明数组原先全为负数，取反后最小数为最后一个取反负数，即nums[i-1] if(i==0||(i<n&&nums[i-1]>nums[i])) nums[i]=-nums[i]; else nums[i-1]=-nums[i-1]; } //求和 for(int num:nums) ans+=num; return ans; }}1323. 6 和 9 组成的最大数字
难度：简单
题目：给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。
提示：
1 <= num <= 10^4num 每一位上的数字都是 6 或者 9 。 示例 1：
输入：num = 9669输出：9969解释：改变第一位数字可以得到 6669 。改变第二位数字可以得到 9969 。改变第三位数字可以得到 9699 。改变第四位数字可以得到 9666 。其中最大的数字是 9969 。示例 2：
输入：num = 9996输出：9999解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。示例 3：
输入：num = 9999输出：9999解释：无需改变就已经是最大的数字了。思路：
输入6和9，反转6和9只能反转一个，要求组成最大数字，所以直接把最高位的6转换为9，就是最大数字。
首先将数字转换为字符串再转换为字符数组；
然后从左到右遍历，判断为6转换为9，输出即可结束！
解题代码：
class Solution { public int maximum69Number (int num) { String s = Integer.toString(num); char[] ch = s.toCharArray(); for(int i = 0;i < ch.length;i++){ if(ch[i] == '6'){ ch[i] = '9'; break; } } return Integer.parseInt(new String(ch)); }}1217. 玩筹码
难度：简单
题目：有 n 个筹码。第 i 个筹码的位置是 position[i] 。
我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从 position[i] 改变为:
position[i] + 2 或 position[i] - 2 ，此时 cost = 0position[i] + 1 或 position[i] - 1 ，此时 cost = 1 返回将所有筹码移动到同一位置上所需要的 最小代价 。
提示：
1 <= position.length <= 1001 <= position[i] <= 10^9 示例 1：
输入：position = [1,2,3]输出：1解释：第一步:将位置3的筹码移动到位置1，成本为0。第二步:将位置2的筹码移动到位置1，成本= 1。总成本是1。示例 2：
输入：position = [2,2,2,3,3]输出：2解释：我们可以把位置3的两个筹码移到位置2。每一步的成本为1。总成本= 2。示例 3：
输入：position = [1,1000000000]输出：1思路：
把所有的筹码移到同一位置，移动奇数位（+1/-1）代价为1，移动偶数位（+2/-2）代价为0；
遍历数组中的所有值，统计所有筹码位置（数组）的奇偶值；
返回奇数或偶数的最小值。
（当奇数位置上少，就直接全部移动到偶数位，所付出的代价就为奇数值；反之代价就为偶数值）
解题代码：
class Solution { public int minCostToMoveChips(int[] position) { int even = 0;//单数位 int add = 0;//双数位 for (int i = 0; i < position.length; i++) { if((position[i] % 2) != 0){ even++; }else{ add++; } } return Math.min(even,add); }}942. 增减字符串匹配
难度：简单
题目：由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
perm[i] < perm[i + 1] ，那么 s[i] == 'I'如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
提示：
1 <= s.length <= 105s 只包含字符 "I" 或 "D" 示例 1：
输入：s = "IDID"输出：[0,4,1,3,2]示例 2：
输入：s = "III"输出：[0,1,2,3]示例 3：
输入：s = "DDI"输出：[3,2,0,1]思路：
从题意上来看,对字符串进行遍历,需输出一个整数排序后的数组
字符串中只有‘I’或‘D’,遇‘I’数开始从0自增,遇‘D’后从字符串的长度开始依次递减;所以整数数组长度为字符串长度+1.
遇到‘I’就是赋值剩余的最小值;遇到‘D’就是赋值剩余的最大值。
解题代码：
class Solution { public int[] diStringMatch(String s) { int[] arr = new int[s.length()+1]; int left = 0,rigth = s.length(); for(int i = 0;i < s.length();++i){ if(s.charAt(i) == 'D'){ arr[i] = rigth; rigth--; }else{ arr[i] = left; left++; } } arr[s.length()] = left; return arr; }}605. 种花问题
难度：简单
题目：假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
提示：
1 <= flowerbed.length <= 2 * 10^4
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length
示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1输出：true示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2输出：false思路：
体现出来的贪心就在：应该在不打破种植规则的情况下种入尽可能多的花，然后判断可以种入的花的最多数量是否大于或等于n。
先对整个flowerbed进行遍历，遍历结束就停止。
① 判断如果当前位置已种植，则i+2位置可种植，因flowebed中不能出现两个相邻的花朵；
② 如果遍历到的元素下标i恰好为length-1，因为flowebed不能有相邻的花朵，所以说明这个位置是可以直接种花。或者判断i + 1是否为未种植的位置；可以进行种植，同时可直接（i+=2;）找到下一个未种植的位置。
③ 若当前位置（为0）不能种植（有相邻的花朵），直接使用i += 3;找到未种植位置
如果n已全部种植完就返回true，反之就为false。
解题代码：
class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { for (int i = 0,len = flowerbed.length; i < len && n > 0;) { if(flowerbed[i] == 1){ i += 2; } else if(i == flowerbed.length - 1 || flowerbed[i + 1] == 0){ n--; //种植完后，同时可以找出下一个可以种植的位置 i += 2; }else{ i+=3; } } //n朵全部种完 return n <= 0; }}860. 柠檬水找零
难度：简单
题目：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
提示：
1 <= bills.length <= 10^5bills[i] 不是 5 就是 10 或是 20 示例 1：
输入：bills = [5,5,5,10,20]输出：true解释：前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。由于所有客户都得到了正确的找零，所以我们输出 true。示例 2：
输入：bills = [5,5,10,10,20]输出：false解释：前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。由于不是每位顾客都得到了正确的找零，所以答案是 false。思路：
贪心也就主要体现在优先考虑10元面额的优先支出，毕竟五元面额可用性多
1、找零面额分为5元和10元或20元；当他们支付一个5元面额，找零金额可以直接递增；
2、当支付10面额时无5元面额，则导致无法找零，就返回false，否则就五元面额递减，10元面额递增；
3、当支付面额大于10元时，只有20元；所以找零时直接5元面额减去一张，10元面额减去一张；当无10元面额时且5元面额大于3时，直接5元面额减去三张就行。反之就返回false；
解题代码：
class Solution { public boolean lemonadeChange(int[] bills) { int five = 0,ten = 0;//定义五元和十元的找零面额 for (int bill:bills) { if (bill == 5){ five++; } else if(bill == 10){ if(five == 0) { return false; } five--; ten++; }else{ if(five > 0 && ten > 0){ five--; ten--; }else if(five >= 3){ five -= 3; }else{ return false; } } } return true; }}最后
建议结合力扣一起刷题?，有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~???