写点什么

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

发布于: 2021 年 03 月 07 日
力扣(LeetCode)刷题,简单题+中等题(第20期)

力扣(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 <= 3 的时候,由提议 n >=2 ,因此当 n = 2 的时候,只有 1 + 1,因此返回 1,当 n = 3 的时候,2 + 1 ,则返回 2,所以 n <= 3 的时候直接返回 n - 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 <= 3) return n - 1;    int* dp = (int*) malloc(sizeof(int) * (n + 1));    memset(dp, 0, sizeof(int) * (n + 1));    dp[1] = 1;    dp[2] = 2;    dp[3] = 3;        for (int i = 2; i <= n; i++) {        for (int j = 1; j < i ; j++) {            dp[i] = fmax(dp[i], dp[i - j] * j);        }    }     return dp[n];}
复制代码


运行效率如下所示:





第 3 题:魔术索引


试题要求如下:



回答(C 语言):


int findMagicIndex(int* nums, int numsSize){    for(int i = 0; i < numsSize; i++){        if(nums[i] == i){            return i;        }    }     return -1;}
复制代码


运行效率如下所示:





第 4 题:连续数列


试题要求如下:



回答(C 语言):


int maxSubArray(int* nums, int numsSize){    int sum = 0;    int max = nums[0];     if (numsSize < 1)        return 0;        for (int i = 0; i < numsSize; i++) {        sum += nums[i];         if (max < sum)            max = sum;        if (sum < 0)            sum = 0;  //为负数时忽略其的奉献为0    }     return max;}
复制代码


运行效率如下所示:





第 5 题:字符串相加


试题要求如下:



解答思路:




回答(C 语言):


char* addStrings(char* num1, char* num2) {    int i = strlen(num1) - 1, j = strlen(num2) - 1, add = 0;    char* ans = (char*)malloc(sizeof(char) * (fmax(i, j) + 3));    int len = 0;     while (i >= 0 || j >= 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 <= 0,返回 0;


2、利用快速排序对 scores 进行排序;


3、遍历数组 scores,统计不相同的元素的个数 count;


4、返回 count。


回答(C 语言):


int cmp( const void * a , const void * b ){     return *( int * )a - *( int * )b; } int expectNumber( int * scores , int scoresSize ){     if( scoresSize <= 0 ){         return 0;     }     qsort( scores , scoresSize , sizeof( int ) , cmp );     int count = 1;     for( int i = 1 ; i < scoresSize ; i++ ){         if( *( scores + i ) != *( scores + i - 1 ) ){             count++;         }     }     return count;}
复制代码


运行效率如下所示:





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


试题要求如下:



回答(C 语言):


int isPrefixOfWord(char *sentence, char *searchWord){    int cnt = 1;    char *token = NULL;    const char space[2] = " ";     /* 获取第一个子字符串,使用空格分隔 */    token = strtok(sentence, space);    /* 继续获取其他的子字符串 */    while (token != NULL ) {        if (strstr(token, searchWord) == token) {            return cnt;        }        cnt++;        token = strtok(NULL, space);    }     return -1;}
复制代码


运行效率如下所示:





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


试题要求如下:



回答(C 语言):


#define MIN(a, b) (((a) < (b)) ? (a) : (b)) int maxNumberOfBalloons(char * text){	int charCount[26] = {0};	int i, len, ret;    	len = strlen(text);	for (i = 0; i < len; i++) {		charCount[text[i] - 'a']++;	} 	charCount['l' - 'a'] /= 2;	charCount['o' - 'a'] /= 2;	ret = INT_MAX;	ret = MIN(ret, charCount['b' - 'a']);	ret = MIN(ret, charCount['a' - 'a']);	ret = MIN(ret, charCount['l' - 'a']);	ret = MIN(ret, charCount['o' - 'a']);	ret = MIN(ret, charCount['n' - 'a']); 	return ret;}
复制代码


运行效率如下所示:



发布于: 2021 年 03 月 07 日阅读数: 9
用户头像

【研究方向】物联网、嵌入式、AI、Python 2018.02.09 加入

【公众号】美男子玩编程

评论

发布
暂无评论
力扣(LeetCode)刷题,简单题+中等题(第20期)