目录
1、元素和最小的山型三元组 | - 三层for暴力循环
2、元素和最小的山型三元组 || - 维护前后最小值 遍历
3、合法分组的最少组数 - 思维 + 哈希表
1、元素和最小的山型三元组 | - 三层for暴力循环
100106. 元素和最小的山形三元组 I
class Solution {public int minimumSum(int[] nums) {int minx=Integer.MAX_VALUE;for(int i=0;i<nums.length-2;i++)for(int j=i+1;j<nums.length-1;j++)for(int k=j+1;k<nums.length;k++)if(nums[j]>nums[i]&&nums[k]<nums[j]){ System.out.println(nums[i]+" "+nums[j]+" "+nums[k]);int t=nums[i]+nums[j]+nums[k];if(t<minx) minx=t;}if(minx==Integer.MAX_VALUE) return -1;return minx;}
}2、元素和最小的山型三元组 || - 维护前后最小值 遍历
100114. 元素和最小的山形三元组 II
思路：
自己做出来的！没有看题解！
- 维护每一个nums[i]的前后最小值，然后遍历整个区间，如果该数的前后（pre和beh）满足山峰形式，则更新最小值
- 具体做法是开辟两个数组：pre[i]存nums[i]前的最小值，beh[i]存nums[i]后的最小值
class Solution {public int minimumSum(int[] nums) {int n=nums.length;int[] pre=new int[100001],beh=new int[100001];pre[0]=Integer.MAX_VALUE;beh[n-1]=Integer.MAX_VALUE;for(int i=1;i<n-1;i++)if(pre[i-1]>nums[i-1])pre[i]=nums[i-1];else pre[i]=pre[i-1];for(int i=n-2;i>0;i--)if(beh[i+1]>nums[i+1])beh[i]=nums[i+1];else beh[i]=beh[i+1];int minx=Integer.MAX_VALUE;for(int i=1;i<n-1;i++)if(pre[i]<nums[i]&&nums[i]>beh[i]){int t=pre[i]+nums[i]+beh[i];if(t<minx) minx=t;}if(minx==Integer.MAX_VALUE) return -1;return minx;}
}
3、合法分组的最少组数 - 思维 + 哈希表
100097. 合法分组的最少组数
思路：
用哈希表统计每个数字出现的个数mp[x]
设组内个数为k
要想分组最少，则k需要越大，而k最大不能超过最小出现个数
因此我们可以遍历整个哈希表找出最小出现次数k
然后倒着枚举k，查找最合适的组内个数
假设mp[x]=34，假如k=10，则34=10+10+10+4，如果k=11，则34=11+11+11+1就无法合理分配，也就是说，如果分组数<余数【mp[x]÷k < mp[x]%k】，因为分组内个数之差不能超过1，所以这种情况下即使每组个数+1，也分不完余数
分组越小，组内个数越大，因此如果能合理分组，尽量让组内个数大，也就是k+1
所以遍历mp[x]累加结果，
，一旦分组成功直接返回答案
class Solution {public int minGroupsForValidAssignment(int[] nums) {Map<Integer,Integer> mp=new HashMap<>();int k=Integer.MAX_VALUE;for(int x:nums) mp.put(x,mp.getOrDefault(x,0)+1);for(int x:mp.values())k=Math.min(k,x);int res=0;for(;;k--){res=0;for(int x:mp.values()){if(x/k < x%k) //如果余数>组数 因为分组之差不能大于1 所以这种情况下即使每组+1也分不完余数 分组失败{res=0;break;}res+=(x+k)/(k+1); //res+=x/(k+1)向上取整}if(res>0) return res;}}
}
