力扣(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;
-
}
运行效率如下所示：
文章来源: blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/m0_38106923/article/details/107812726
- 点赞
- 收藏
- 关注作者
评论（0）