江阴网站设计,在线logo设计免费,wordpress评论打卡,淘宝网店设计制作1 2题元素和最小的山形三元组
经典动规
题目内容
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为它是一个 山形三元组 #xff1a;
i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出 num…1 2题元素和最小的山形三元组
经典动规
题目内容
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个 山形三元组
i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出 nums 中 元素和最小 的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -1 。
样例
输入nums [5,4,8,7,10,2] 输出13 解释三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组因为
1 3 5nums[1] nums[3] 且 nums[5] nums[3] 这个三元组的元素和等于 nums[1] nums[3] nums[5] 13 。可以证明不存在元素和小于 13 的山形三元组。
数据范围
3 nums.length 105 1 nums[i] 108
思路
左右算最小值点记录然后动态规划 复杂度O(n)。
class Solution {public int minimumSum(int[] nums) {int n nums.length;int[] left_min new int[n];int[] right_min new int[n];int min nums[0];for(int i1;in-1;i){minMath.min(min,nums[i-1]);left_min[i] min;}min nums[n-1];for(int in-2;i0;i--){minMath.min(min,nums[i1]);right_min[i] min;}int result Integer.MAX_VALUE;for(int i1;in-1;i)if(nums[i]left_min[i]nums[i]right_min[i])result Math.min(result,nums[i]left_min[i]right_min[i]);return resultInteger.MAX_VALUE?-1:result;}
}3 题 元素和最小的山形三元组
题目内容
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立我们说这个分组方案是合法的
对于每个组 g 同一组内所有下标在 nums 中对应的数值都相等。 对于任意两个组 g1 和 g2 两个组中 下标数量 的 差值不超过 1 。 请你返回一个整数表示得到一个合法分组方案的 最少 组数。
样例
示例 1
输入nums [3,2,3,2,3] 输出2 解释一个得到 2 个分组的方案如下中括号内的数字都是下标 组 1 - [0,2,4] 组 2 - [1,3] 所有下标都只属于一个组。 组 1 中nums[0] nums[2] nums[4] 所有下标对应的数值都相等。 组 2 中nums[1] nums[3] 所有下标对应的数值都相等。 组 1 中下标数目为 3 组 2 中下标数目为 2 。 两者之差不超过 1 。 无法得到一个小于 2 组的答案因为如果只有 1 组组内所有下标对应的数值都要相等。 所以答案为 2 。 示例 2
输入nums [10,10,10,3,1,1] 输出4 解释一个得到 2 个分组的方案如下中括号内的数字都是下标 组 1 - [0] 组 2 - [1,2] 组 3 - [3] 组 4 - [4,5] 分组方案满足题目要求的两个条件。 无法得到一个小于 4 组的答案。 所以答案为 4 。
范围
1 nums.length 105 1 nums[i] 109
思路
先记录nums的值进行一个每个数出现次数进行排序生成数组members 然后根据出现次数来获取可以组成的最小组数 这里 从出现次数的最小值遍历到1遍历选取当前值和当前值1(now和now1)。然后对members数组进行判断、遍历、加和答案。 复杂度 O ( n ) O(n) O(n)
ac代码
class Solution {public int isgroup(int member,int now){int result Integer.MAX_VALUE;for(int i0;i2;i){if(nowi0)continue;int remain nowi;int group member/remain;int leave member%remain;if(leave0)result Math.min(group,result);else{int remeber member - group*remain;if(i0remebergroup)result Math.min(group,result);if(i1((remain-remeber)group))result Math.min(group1,result);}}return result;}public int minGroupsForValidAssignment(int[] nums) {HashMapInteger,Integer map new HashMap();int now0;for(int x:nums){now map.getOrDefault(x,0);map.put(x,now1);}int[] members new int[map.size()];now 0;for(Map.EntryInteger,Integer x:map.entrySet())members[now] x.getValue();Arrays.sort(members);int max_num members[0];for(int imax_num;i0;i--){int result 0;for(now0;nowmembers.length;now){int group_num isgroup(members[now],i);System.out.println(group_num i);if(group_num Integer.MAX_VALUE)break;resultgroup_num;}if(nowmembers.length)return result;}return -1;}
}4 6920. 得到 K 个半回文串的最少修改次数
未完成
