描述

这是一篇面对初级coder的题解。
知识点：数学 排序 快速幂
难度：二星

题解

题目：
一共n个人，已知之前站在他们左部分和站在他们右部分的人的人数差的绝对值，求有多少种不同的站法？（结果需要对1e9+7取模）
分析：
本题的关键在于判断队列是否存在，不难发现，站在他左部分和站在他右部分的人的人数差的绝对值是有一定规律的
如下图

之后只需要根据n是奇数和偶数，判断数组是否符合规范即可：
若数组符合规范，则最终结果为
但是由于数字较大，同时模的值也大需要用到

方法一：字典map

采用一个map存储

class Solution {
public:
      const long long mod=1000000007;
      long long power(long long base, long long exponent) {
        if(exponent==0)
            return 1;
        long long answer = 1;
        while(exponent){
            if(exponent&1)        //如果n的当前末位为1
                answer =muti(answer,base);  //ans乘上当前的a
            base =muti(base,base);        //a自乘
            exponent >>= 1;       //n往右移一位
        }
        return answer;
    }
    long long muti(long long a, long long b) {//防止越界 乘法 每次只乘2字节
        long long ans =0;
        while(b){
            ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
            b>>=16;//乘数右移2字节
            a=(a<<16)%mod;//被乘数左移2字节
        }
        return ans;
    }
    int solve(int n, vector<int>& a) {
        vector<int> map(n+1,0);//记录每个数字出现的次数
        for(int i=0;i<n;i++)
            map[a[i]]++;//记录
        int begin;
        if(n%2==1){//分奇数偶数讨论
            begin=2;//奇数 看2 4 6 8 是否为2
            if(map[0]!=1)//看 0是否为1
                return 0;
        }
        else
            begin=1;//偶数 看1 3 5 7 是否为2
        for(int i=begin;i<n+1;i+=2){
            if(map[i]!=2)
                return 0;
        }
        return (int)power(2,n/2);//若合法 返回2^(n/2)
        // write code here
    }
};

运行测试：
运行时间 3ms 占用内存 304KB

方法二：排序

先将a数组排序，再统计是否符合要求

class Solution {
public:
      const long long mod=1000000007;
      long long power(long long base, long long exponent) {
        if(exponent==0)
            return 1;
        long long answer = 1;
        while(exponent){
            if(exponent&1)        //如果n的当前末位为1
                answer =muti(answer,base);  //ans乘上当前的a
            base =muti(base,base);        //a自乘
            exponent >>= 1;       //n往右移一位
        }
        return answer;
    }
    long long muti(long long a, long long b) {//防止越界 乘法 每次只乘2字节
        long long ans =0;
        while(b){
            ans=(ans+a*(b&0xFFFFLL))%mod;//相乘累加
            b>>=16;//乘数右移2字节
            a=(a<<16)%mod;//被乘数左移2字节
        }
        return ans;
    }
    int solve(int n, vector<int>& a) {
        sort(a.begin(),a.end());
        int begin;
        int data;
        if(n%2==1){//分奇数偶数讨论
            begin=1;
            data=2;//奇数 从1开始是否为2 4 6 8
            if(a[0]!=0)//看 0是否为1
                return 0;
        }
        else{
            begin=0;//偶数 从0开始是否为1 3 5 7
            data=1;
        }
        for(int i=begin;i<n;i+=2)
        {
            if(a[i]!=data||a[i+1]!=data)//检验
                 return 0;
            data+=2;
        }
        return (int)power(2,n/2);//若合法 返回2^(n/2)
        // write code here
    }
};

时间复杂度：：快速排序sort函数，检查数组是否合法为,快速幂

空间复杂度：：主要是快速排序sort函数

运行测试：
运行时间 3ms 占用内存 428KB

总结