[数据结构与算法]7.2算法打卡

7.2打卡

1.三个数的最大乘积 https://leetcode.cn/problems/maximum-product-of-three-numbers/
思路：

1. 三种情况。
   1. 情况1：只有三个数。答案就是三个数的乘积$nums[n?1]?nums[n?2]?nums[n?3]$。
   2. 情况2：不止三个数，且有至少一个正数。答案里面肯定是有一个正数或者三个正数，基本思路是正数负数都选绝对值大的数，所以先排序，然后$max(nums[0]?nums[1]?nums[n?1],nums[n?1]?nums[n?2]?nums[n?3])$
   3. 情况3：没有正数。答案是三个负数。先排序，然后选绝对值最小的三个负数$nums[n?1]?nums[n?2]?nums[n?3]$。
2. 综合起来就是一个式子：$max(nums[0]?nums[1]?nums[n?1],nums[n?1]?nums[n?2]?nums[n?3])$

class Solution {
    public int maximumProduct(int[] nums) {
        
        Arrays.sort(nums);
        int n=nums.length;
        return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
    }
}

2.有多少小于当前的数字 https://leetcode.cn/problems/how-many-numbers-are-smaller-than-the-current-number/
思路：
数据范围小，所以获取每个数的数目，然后求个前缀和，然后查询前缀和就可以。

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] a=new int[101];
        int n=nums.length;
        for(int i=0;i<n;i++){
            a[nums[i]]+=1;
        }
        for(int i=1;i<101;i++){
            a[i]+=a[i-1];
        }
        int[] ans=new int[n];
        for(int i=0;i<n;i++){
            if(nums[i]==0)ans[i]=0;
            else ans[i]=a[nums[i]-1];
        }
        return ans;
    }
}

3.使数组唯一的最小增量 https://leetcode.cn/problems/minimum-increment-to-make-array-unique/
思路：
基本思想：我们求结果数列的和，减去初始数组的和就是答案，比如初始为2,2,3,3,3，和为13最终肯定是2,3,4,5,6，和为20。结果就是20-13=7。
分析：其实如果只有两个2，结果数列就是2,3，也就是2开始的两个数。如果只有三个3结果数列就是3,4,5。也就是3开始的3个数。但是两个2,三个3的结果有重复元素3，所以最终就是以2开始的5(:=2+3)个数。我们设i为某一个count值不为0的数，对于一个数j (j>i)，要判断j是否再结果数组中，只要判断，pre[j]-pre[i-1]>=j-(i-1),不等式左边表示原始数列有几个数，右边表示i-j总共几个数，如果左边多，结果数列应该就包含j。比如这里j=5在结果数列中,i是前面count不为0的数字：2，因为pre[6]-pre[2-1]=5-0>=6-(2-1)=5,所以6在结果数列中，因为原始数列2-6中间有5个数，现在2-6也是5个数，所以结果数列包含6。
具体步骤：
1. 由于数字范围不大1e5内，所获取每个数的数目存count数组，再前缀和存pre数组，
2. 如果某个数i的count值不为0则依次遍历下一个数pre[j]-pre[i-1]>=j-(i-1)，(i<=j<=MAXN),满足条件，就加到sum。否则继续步骤2，指导i>maxn.
3. 由于看你最终数列有数字大于MAXN，做一下特殊处理，这里貌似我写的代码有点累赘，可以修改一下。

class Solution {
    public int minIncrementForUnique(int[] nums) {
        int MAXN=100001;
        int n=nums.length;
        int[] count=new int[MAXN];
        int[] pre=new int[MAXN];
        int sum0=0;
        for(int i=0;i<n;i++){
            count[nums[i]]+=1;
            sum0+=nums[i];
        }
        pre[0]=count[0];
        for(int i=1;i<MAXN;i++){
            pre[i]=pre[i-1]+count[i];
        }        
        int sum=0,t=0;
        for(int i=0;i<MAXN;i++){
            if(count[i]>0){
                t=i-1;
                for(;i<MAXN;i++){
                    if(pre[i]-(t<0?0:pre[t])>=i-t){
                        sum+=i;
                    }else{
                        break;
                    }
                }
            }
        }
        
        if(pre[MAXN-1]-(t<0?0:pre[t])>MAXN-1-t){
            for(int i=0;i<pre[MAXN-1]-pre[t]-(MAXN-1-t);i++){
                sum+=MAXN+i;
            }
        }
        // System.out.println(sum0);
        return sum-sum0;

    }
}

4.Rising Sand https://codeforces.com/contest/1698/problem/B
思路：
分析发现，只有k等于1可以增大原始序列的结果数目，所以特判一下k就好了。

import java.util.*;
public class Main{
    public static void main(String[] args){
        // System.out.println("hello world");
        Scanner scanner = new Scanner(System.in);
        int t=scanner.nextInt();
        while(t--!=0){
            int n=scanner.nextInt();
            int k=scanner.nextInt();
            int[] a=new int[n];
            for(int i=0;i<n;i++){
                a[i]=scanner.nextInt();
            }
            if(k==1){
                System.out.println((n-1)/2);continue;
            }
            int ans=0;
            for(int i=1;i<n-1;i++){
                if(a[i]>a[i-1]+a[i+1])ans++;
            }
            System.out.println(ans);
        }
    }
}