368周赛leetcode

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 < 5
• nums[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 i=1;i<n-1;i++){min=Math.min(min,nums[i-1]);left_min[i] = min;}min = nums[n-1];for(int i=n-2;i>0;i--){min=Math.min(min,nums[i+1]);right_min[i] = min;}int result = Integer.MAX_VALUE;for(int i=1;i<n-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 result==Integer.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和now+1)。然后对members数组进行判断、遍历、加和答案。
复杂度：$$O(n)$$

ac代码

class Solution {public int isgroup(int member,int now){int result = Integer.MAX_VALUE;for(int i=0;i<2;i++){if(now+i<=0)continue;int remain  = now+i;int group = member/remain;int leave  = member%remain;if(leave==0)result = Math.min(group,result);else{int remeber = member - group*remain;if(i==0&&remeber<=group)result = Math.min(group,result);if(i==1&&((remain-remeber)<=group))result = Math.min(group+1,result);}}return result;}public int minGroupsForValidAssignment(int[] nums) {HashMap<Integer,Integer> map = new HashMap<>();int now=0;for(int x:nums){now = map.getOrDefault(x,0);map.put(x,now+1);}int[] members = new int[map.size()];now = 0;for(Map.Entry<Integer,Integer> x:map.entrySet())members[now++] = x.getValue();Arrays.sort(members);int max_num = members[0];for(int i=max_num;i>0;i--){int result = 0;for(now=0;now<members.length;now++){int group_num = isgroup(members[now],i);System.out.println(group_num+" "+i);if(group_num == Integer.MAX_VALUE)break;result+=group_num;}if(now==members.length)return result;}return -1;}
}

4 6920. 得到 K 个半回文串的最少修改次数

未完成