leetcode刷题报告6
📜个人简介 |
⭐️个人主页:摸鱼の文酱博客主页🙋♂️
🍑博客领域:java编程基础,mysql
🍅写作风格:干货,干货,还是tmd的干货
🌸精选专栏:【Java】【mysql】 【算法刷题笔记】
🎯博主的码云gitee,平常博主写的程序代码都在里面。
🚀支持博主:点赞👍、收藏⭐、留言💬
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
今日学习内容:贪心算法
今日刷题:
🎯1913. 两个数对之间的最大乘积差
题目描述:
两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。
例如,(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) = 16 。
给你一个整数数组 nums ,选出四个 不同的 下标 w、x、y 和 z ,使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。
返回以这种方式取得的乘积差中的 最大值 。
🐾思路一:先排序,然后求目标值
public int maxProductDifference(int[] nums) {
Arrays.sort(nums);
return ((nums[nums.length-1] * nums[nums.length-2]) - (nums[0] * nums[1]));
}
🐾思路二:贪心算法
class Solution { //最大两个数的乘积-最小两个数的乘积 public int maxProductDifference(int[] nums) { int c1 = 0;//乘积1 int c2 = 0;//乘积2 //取最大的数 int max1 = nums[0]; int max1Count = 0; int max1Index = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] > max1) { max1 = nums[i]; max1Count = 0; max1Index = i; } if (nums[i] == max1) { max1Count++; } } //遍历结束,如果最大的数相等的有两个及以上,那么就取两个这个数乘积 if (max1Count >= 2) { c1 = max1 * max1; } else { //最大的数只有一个 //寻找第二大的数 int max2Index = max1Index == nums.length - 1 ? nums.length - 2 : max1Index + 1; int max2 = nums[max2Index]; for (int i = 0; i < nums.length; i++) { if (nums[i] != max1) { //排除最大数 if (nums[i] > max2) { max2 = nums[i]; } } } c1 = max1 * max2; } //取最小的数 int min1 = nums[0]; int min1Count = 0; int min1Index = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] < min1) { min1 = nums[i]; min1Count = 0; min1Index = i; } if (nums[i] == min1) { min1Count++; } } //遍历结束,如果最小的数相等的有两个及以上,那么就取两个这个数乘积 if (min1Count >= 2) { c2 = min1 * min1; } else { //最小的数只有一个 //寻找倒数第二小的数 int min2Index = min1Index == nums.length - 1 ? nums.length - 2 : min1Index + 1; int min2 = nums[min2Index]; for (int i = 0; i < nums.length; i++) { if (nums[i] != min1) { //排除最大数 if (nums[i] < min2) { min2 = nums[i]; } } } c2 = min1 * min2; } return c1 - c2; }}
🎯1913. 两个数对之间的最大乘积差
题目描述:
给定由一些正数(代表长度)组成的数组 nums ,返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形,返回 0。
返回以这种方式取得的乘积差中的 最大值 。
🐾思路一:先排序,然后求目标值
public int largestPerimeter(int[] A) { Arrays.sort(A); for (int i = A.length - 1; i >= 2; --i) { if (A[i - 2] + A[i - 1] > A[i]) { return A[i - 2] + A[i - 1] + A[i]; } } return 0; }
🐾思路二:贪心
public int largestPerimeter(int[] A) { for(int i = 0; i < A.length; i++){ int t = i; for(int j = i + 1; j < A.length; j++){ if(A[t] < A[j])t = j; } int s = A[i]; A[i] = A[t]; A[t] = s; if(i > 1 && A[i] + A[i-1] > A[i-2])return A[i] + A[i-1] + A[i-2]; } return 0; }
🎯561. 数组拆分 I
题目描述:
给定长度为 2n 的整数数组 nums ,你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
🐾思路一:先排序,然后求目标值
public int arrayPairSum(int[] nums) { Arrays.sort(nums); int ans = 0; for (int i = 0; i < nums.length; i += 2) { ans += nums[i]; } return ans; }
🐾思路二:贪心
public int arrayPairSum(int[] nums) { int[] arr = new int[20001]; for (int i : nums) { arr[i + 10000]++; } boolean pick = true; int sum = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) { continue; } int val = i - 10000; while (arr[i] > 0) { if (pick) sum += val; pick = !pick; arr[i]--; } } return sum; }
🎯881. 救生艇
题目描述:
给定数组 people 。people[i]表示第 i 个人的体重 ,船的数量不限,每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
🐾思路一:贪心
public int numRescueBoats(int[] people, int limit) { int res = 0; int right = people.length - 1; int left = 0; Arrays.sort(people); while (left <= right) { if (left == right) { res++; // 只剩下最后一个,直接一个走,结束 break; } if (people[left] + people[right] > limit) { res++; right--; // 先载最重的, 而且最小的也无法一起载,那么就最重的单独走 } else { res++; right--; // 最重的与最轻的一起走 left++; } } return res; }
🎯324. 摆动排序 II
题目描述:
给你一个整数数组 nums,将它重新排列成 nums[0] nums[2] < nums[3]… 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
🐾思路一:桶排序
class Solution { public void wiggleSort(int[] nums) { int[]bucket=new int[5001]; for(int num:nums)bucket[num]++; int len=nums.length; int small,big;//穿插数字时的上界 //总长度为奇数时,“小 大 小 大 小”边界左右都为较小的数; //总长度为偶数时,“小 大 小 大”边界左为较小的数,边界右为较大的数 if((len&1)==1){ small=len-1; big=len-2; }else{ small=len-2; big=len-1; } int j=5000; //从后往前,将桶中数字穿插到数组中,后界为j //桶中大的数字在后面,小的数字在前面,所以先取出较大的数字,再取出较小的数字 //先将桶中的较大的数字穿插放在nums中 for(int i=1;i<=big;i+=2){ while (bucket[j]==0)j--;//找到不为0的桶 nums[i]=j; bucket[j]--; } //再将桶中的较小的数字穿插放在nums中 for(int i=0;i<=small;i+=2){ while (bucket[j]==0)j--;//找到不为0的桶 nums[i]=j; bucket[j]--; } }}
🐾思路二:贪心
public void wiggleSort(int[] nums) { int[] help = nums.clone(); //不能写成int[] help = nums,排序后两个数组都改变 Arrays.sort(help); int N = nums.length; //比如123456 for (int i = 1; i < nums.length; i += 2) { nums[i] = help[--N]; //遍历完成后 x 6 x 5 x 4 } for (int i = 0; i < nums.length; i += 2) { nums[i] = help[--N]; //便利完成后 3 6 2 5 1 4 } }
🎯455. 分发饼干
题目描述:
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
🐾思路一:贪心
class Solution { public int findContentChildren(int[] g, int[] s) { // 将数组进行升序排序 Arrays.sort(g); Arrays.sort(s); // 记录孩子数 int childCount = 0; int cookieCount = 0; while (childCount < g.length && cookieCount < s.length) { if (g[childCount] <= s[cookieCount]) { // 饼干尺寸能够满足孩子,孩子数加1 childCount++; } // 使用下一块饼干 cookieCount++; } return childCount;}}
🎯1827. 最少操作使数组递增
问题描述:
给你一个整数数组 nums (下标从 0 开始)。每一次操作中,你可以选择数组中一个元素,并将它增加 1 。
比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] 。
请你返回使 nums 严格递增 的 最少 操作次数。
我们称数组 nums 是 严格递增的 ,当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。
🐾思路一:暴力
public int minOperations(int[] nums) { int a=0; for(int i=0;i<nums.length-1;i++) { if(nums[i]>nums[i+1]-1) {a+=nums[i]+1-nums[i+1]; nums[i+1]=nums[i]+1;} } return a; }
🐾思路二:贪心
class Solution { public int minOperations(int[] nums) { int res=0; for(int i=1;i<nums.length;i++){ if(nums[i]>nums[i-1]){ continue; }else{ res+=nums[i-1]+1-nums[i]; nums[i]=nums[i-1]+1; } } return res; }}
🎯945. 使数组唯一的最小增量
问题描述:
给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i,并将 nums[i] 递增 1。
返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。
🐾思路一:先排序再遍历
public int minIncrementForUnique(int[] A) { Arrays.sort(A); // 先排序 int curmax = -1; // 当前数组最大值 int res = 0; for (int i = 0; i < A.length; i++) { if (A[i] <= curmax) { // 当前元素 A[i] 需要增加到 curmax + 1 res += (curmax + 1 - A[i]); // 记录自增次数 } curmax = Math.max(curmax + 1, A[i]); } return res;}
🐾思路二:先计数再遍历
public int minIncrementForUnique(int[] A) { int[] count = new int[40000]; int max = 0; for (int a : A) { count[a]++; // 计数 max = Math.max(max, a); // 计算数组中的最大值 } int res = 0; for (int j = 0; j < max; j++) { if (count[j] > 1) { // 有 count[j] - 1 个数需要增加 res += count[j] - 1; count[j+1] += count[j] - 1; } } // count[max] 单独计算,是因为可能超出 40000 的边界 if (count[max] > 1) { int d = count[max] - 1; // 有 d 个数需要增加 // 分别增加为 max + 1, max + 2, ... max + d // 使用等差数列公式求和 res += (1 + d) * d / 2; } return res;}
🐾思路三:贪心
public class Solution { public int minIncrementForUnique(int[] A) { int len = A.length; if (len == 0) { return 0; } Arrays.sort(A); // 打开调试 // System.out.println(Arrays.toString(A)); int preNum = A[0]; int res = 0; for (int i = 1; i < len; i++) { // preNum + 1 表示当前数「最好」是这个值 if (A[i] == preNum + 1) { preNum = A[i]; } else if (A[i] > preNum + 1) { // 当前这个数已经足够大,这种情况可以合并到上一个分支 preNum = A[i]; } else { // A[i] < preNum + 1 res += (preNum + 1 - A[i]); preNum++; } } return res; } public static void main(String[] args) { Solution solution = new Solution(); int[] A = new int[]{1, 2, 2}; // int[] A = new int[]{3, 2, 1, 2, 1, 7}; int res = solution.minIncrementForUnique(A); System.out.println(res); }}
🎯611. 有效三角形的个数
问题描述:
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
🐾思路一:贪心-先排序后二分
class Solution { public int triangleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int left = j + 1, right = n - 1, k = j; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] < nums[i] + nums[j]) { k = mid; left = mid + 1; } else { right = mid - 1; } } ans += k - j; } } return ans; }}
🐾思路二:排序 + 双指针
class Solution { public int triangleNumber(int[] nums) { if (nums.length < 3) { return 0; } Arrays.sort(nums); int count = 0; int n = nums.length; for (int i = 2; i < n; i++) { // 固定大边,利用双指针压缩两个小边的值 int left = 0, right = i - 1; while (left < right) { // nums[left]与nums[right]相加大于nums[i] // 说明left右边的数与nums[right]相加肯定大于nums[i] // 所以,这种情况直接累加结果即可 if (nums[left] + nums[right] > nums[i]) { count += right - left; // 尝试把right减一,继续比较 right--; } else { // nums[left]与nums[right]相加小于nums[i] // 尝试把left加一,继续比较 left++; } } } return count; }}
🐾思路三:排序 + 暴力枚举
class Solution { public int triangleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i - 1; j >= 0; j--) { for (int k = j - 1; k >= 0; k--) { if (nums[j] + nums[k] > nums[i]) ans++; } } } return ans; }}
🐾思路四:数学方法
class Solution { public int triangleNumber(int[] nums) { int n = nums.length; int[] sum = new int[1005]; for(int i = 0; i < n; i++) sum[nums[i]]++; // 0 毫无作用 sum[0] = 0; // 计算边长处于 [1, i] 之间的边的数目 for(int i = 1; i <= 1000; i++) sum[i] += sum[i - 1]; int ret = 0; for (int i = 1; i <= 1000; ++i) { // 边长为 i 的边数目 x int x = sum[i] - sum[i-1]; // 剪枝 if(!x) continue; for (int j = i + 1; j <= 1000; ++j) { // 边长为 j 的边数目 y int y = sum[j] - sum[j-1]; if(!y) continue; // 普通三角形,固定 i, j, 第三条边处于 [j + 1, i + j - 1] 范围内 ret += (sum[Math.min(i + j - 1, 1000)] - sum[j]) * x * y; } // 等腰三角形,固定 i,第三条边处于 [1, 2 * i - 1] 范围内,但不等于 i ret += (sum[Math.min(1000, i * 2 - 1)] - x) * (x * (x - 1) / 2); // 等边三角形,先除 2 再除 3 与直接除 6 结果相同,但可以防止乘法溢出 int 范围 ret+= x * (x - 1) / 2 * (x - 2) / 3; } return ret; }}