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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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

未完成