第 214场周赛

本文主要是介绍第 214场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1646. 获取生成数组中的最大值

class Solution {public int getMaximumGenerated(int n) {int[] nums = new int[n+1];if(n==0){return 0;}if(n==1){return 1;}nums[0]=0;nums[1]=1;int max=0;for(int i=2;i<=n;i++){if(i%2==0){nums[i]=nums[i/2];}else{nums[i]=nums[i/2]+nums[i/2+1];}max=max>nums[i]?max:nums[i];}return max;}
}

1647. 字符频次唯一的最小删除次数

class Solution {public int minDeletions(String s) {int[] chars = new int[26];int len = s.length();for(int i=0;i<len;i++){chars[s.charAt(i)-'a']++;}int count=0;Set<Integer> sets = new HashSet<Integer>();for(int j=0;j<26;j++){if(chars[j]>0){while(chars[j]>0 && sets.contains(chars[j])){chars[j]--;count++;}sets.add(chars[j]);}}return count;}
}

1648. 销售价值减少的颜色球

class Solution {
public int maxProfit(int[] inventory, int orders) {int mod = 1000000007;int left = 0;int right = maxVal(inventory);int T = 0;while(left<=right){int mid = (right-left)/2+left;long count = sum(inventory,mid);// System.out.println("mid:"+mid+" count:"+count);if(count<orders){right  = mid-1;}else{T = mid;left = mid+1;}}// System.out.println("T:"+T);long ans=0;
//        int count =0;long l=0,r=0,num=0;for(int i=0;i<inventory.length;i++){if(inventory[i]>T && orders>0){
//        		num = (orders-count)>(inventory[i]-T+1)?(inventory[i]-T+1):(orders-count);r = inventory[i];
//        		l = inventory[i]-num+1;l = T+1;num = r-l+1;
//        		int curSum = ((l+r)*num/2)%mod;ans =(ans+((l+r)*num/2)%mod)%mod;orders-=num;// System.out.println("r:"+r+" ;l:"+l+" ;num="+num);}}System.out.println(orders);ans = (long) ((ans+ 1.0*T*orders%mod)%mod);return (int) ans;}public int maxVal(int[] inventory){int maxVal = 0;for(int i=0;i<inventory.length;i++){maxVal = maxVal>inventory[i]?maxVal:inventory[i];}return maxVal;}public long sum(int[] inventory,int T){
//    	System.out.println("sum!!!!!!!");long sum = 0;for(int i=0;i<inventory.length;i++){if(inventory[i]>=T){sum+= inventory[i]-T+1;
//    			System.out.println("sum:"+sum);}}return sum;}
}

1649. 通过指令创建有序数组

树状数组详解：https://www.cnblogs.com/xenny/p/9739600.html
x&(-x)含义：https://blog.csdn.net/qq_42635159/article/details/88739069

class Solution {
public int createSortedArray(int[] instructions) {int mod = (int) 1e9+7;long ans = 0;//去重Set<Integer> set = new HashSet<Integer>();for(int i=0;i<instructions.length;i++){set.add(instructions[i]);}//排序int[] nums = new int[set.size()];int idx = 0;for(int num:set){nums[idx++] = num;}Arrays.sort(nums);Map<Integer,Integer> map = new HashMap<Integer,Integer>();for(int i=0;i<nums.length;i++){map.put(nums[i], i+1);}//建树BIT bit = new BIT(nums.length);for(int i=0;i<instructions.length;i++){int t = map.get(instructions[i]);//比查询的数字小的个数int l = bit.getSum(t-1);int r = bit.getSum(t);ans += Math.min(l, i-r)%mod;ans = ans%mod;bit.update(t, 1);}return (int)ans;}class BIT{int n;int[] tree;public BIT(int n){this.n = n;tree = new int[n+1];}public int lowbit(int x){return x&(-x);}public void update(int i,int val){while(i<=n){tree[i]+= val;i += lowbit(i);}}public int getSum(int i){int res = 0;while(i>0){res += tree[i];i -= lowbit(i);}return res;}}
}

这篇关于第 214场周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---