力扣(LeetCode)刷题，简单题+中等题(第20期)

目录

第1题：判断能否形成等差数列

第2题：整数拆分

第3题：魔术索引

第4题：连续数列

第5题：字符串相加

第6题：数组拆分1

第7题：找出数组中的幸运数

第8题：期望个数统计

第9题：检查单词是否为句中其他单词的前缀

第10题："气球”的最大数量

力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。

第1题：判断能否形成等差数列

试题要求如下：

回答（C语言）：

int cmp(const void *a, const void *b)
{
    return *((int*)a) - *((int*)b);
}

bool canMakeArithmeticProgression(int* arr, int arrSize){
    qsort(arr, arrSize, sizeof(int), cmp);

    int minus = arr[1] - arr[0];
    
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] != (arr[0] + i * minus)) {
            return false;
        }
    }
    
    return true;
}

运行效率如下所示：

第2题：整数拆分

试题要求如下：

解答思路：

1、当n =2 ,因此当n = 2的时候，只有 1 + 1，因此返回1，当n = 3的时候，2 + 1 ，则返回2,所以n 3的时候，我们用动态规划，dp[n] = Max(dp[n - 1] * 1, dp[n - 2] * 2，dp[n - 3] * 3 ....,dp[1] * (n - 1)) 这里面对dp中1,2,3的初始化很重要，比如dp[4] = Max(dp[3] * 1, dp[2] * 2, dp[1] * 3),显然这里面的dp[1],dp[2],dp[3]分别对应的是值1,2,3,所以初始值就是这样子；

再后面的比如dp[5] = Max(dp[4] * 1, dp[3] * 2, dp[2] * 3, dp[1] * 4),4以及之后的由于都是根据前面正确计算得到的，因此不用再初始化，直接在公式里面循环即可。

回答（C语言）：

int integerBreak(int n){
    if (n = 0 || add != 0) {
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;
        int result = x + y + add;

        ans[len++] = '0' + result % 10;
        add = result / 10;
        i--, j--;
    }

    // 计算完以后的答案需要翻转过来
    for (int i = 0; 2 * i < len; i++) {
        int t = ans[i];

        ans[i] = ans[len - i - 1], ans[len - i - 1] = t;
    }
    
    ans[len++] = 0;
    return ans;
}

运行效率如下所示：

第6题：数组拆分1

试题要求如下：

回答（C语言）：

int cmp(int *a, int *b) {
    return *(int *)a > *(int *)b;
}

int arrayPairSum(int* nums, int numsSize){
    int i, j;
    int sum = 0;

    if (numsSize < 2) {
        return 0;
    }
    qsort(nums, numsSize, sizeof(int), cmp);

    for (sum = nums[0], i = 2; i < numsSize; i = i + 2) {
        sum += nums[i];
    }
    
    return sum;
}

运行效率如下所示：

第7题：找出数组中的幸运数

试题要求如下：

回答（C语言）：

int findLucky(int* arr, int arrSize){
    int ret = -1;
    int temp[501] = {0};
    int i = 0;

    for(; i < arrSize; i++)
    {
        temp[arr[i]]++;
    }

    i = 500; 

    for(; i > 0; i--)
    {
        if(temp[i] == i)
            return i;
    } 

    return ret;
}

运行效率如下所示：

第8题：期望个数统计

试题要求如下：

解答思路：

1、如果数组的长度scoresSize