5/11刷题_牛客博客

1.实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
思路一：快速幂+递归：基于分治的思想，例如求x的8次幂，只需求4次幂和2次幂即可。

class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;//如果除以2没有余数，直接y*y，如果有余数，额外再乘一个x
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

思路二：快速幂＋迭代

class Solution {
public:
    double quickMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

2.连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
思路：设置一个res，一个cur，一个存储当前最大结果，一个存储总的计算结果，从头开始遍历，如果cur小于等于0，就再次从头开始计算，否则，加入一个数，每次循环都让cur与res作比较，res取其中最大值。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int len=array.size();
        if(len<=0) return 0;
        int cur=0;
        int res=0x80000000;//最小负数
        for(int i=0;i<len;i++)
        {
            if(cur<=0)
                cur=array[i];//小于等于0，舍去记录的序列
            else
            {
                cur+=array[i];//否则序列加一个数
            }
            res=max(res,cur);//比较
        }
        return res;  
    }
};

3.整数中1出现的次数
求出1~~13的整数中1出现的次数,并算出100~~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n<=0)
            return 0;
        char strN[50];
        sprintf(strN,"%d",n);//转换成字符串
        return NumberOf1(strN);    
    }
    int NumberOf1(const char* strN)
    {
        if(!strN||*strN<'0'||*strN>'9'||*strN=='\0')
            return 0;//结束条件
        int first=*strN-'0';//最高位
        unsigned int length=static_cast<unsigned int>(strlen(strN));
        if(length==1&&first==0)
            return 0;
        if(length==1&&first>0)
            return 1;//0-9
        int numFirstDigit=0;//最高位
        if(first>1)
            numFirstDigit=pow(10,length-1);
        else if(first==1)
            numFirstDigit=atoi(strN+1)+1;//10000-12345
        int numOtherDigits=first*(length-1)*pow(10,length-2);//剩余位数排列组合
        int numRecursive=NumberOf1(strN+1);//递归
        return numFirstDigit+numOtherDigits+numRecursive;       
    }
};

4.把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路：定义一个新的排序规则，然后将数字转化为字符串。

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        int len=numbers.size();
        if(len<=0) return "";
        string s="";
        sort(numbers.begin(),numbers.end(),cmp);//基于新的排序规则，给数组排序
        for(int i=0;i<len;i++)
        {
            s+=to_string(numbers[i]);//数字转字符串
        }
        return s;
    }
    static bool cmp(int a,int b)
    {
        string s1=to_string(a)+to_string(b);
        string s2=to_string(b)+to_string(a);
        return s1<s2;//a+b若小于b+a，就不换
    }
};