写点什么

力扣 (LeetCode) 刷题,简单题 (第 19 期)

发布于: 2021 年 03 月 08 日
力扣(LeetCode)刷题,简单题(第19期)

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

第 1 题:两数之和 2-输入有序数组


试题要求如下:



回答(C 语言):


/** * Note: The returned array must be malloced, assume caller calls free(). */int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {    int* ret = (int*)malloc(sizeof(int) * 2);    *returnSize = 2;     for (int i = 0; i < numbersSize; ++i) {        int low = i + 1, high = numbersSize - 1;         while (low <= high) {            int mid = (high - low) / 2 + low;                        if (numbers[mid] == target - numbers[i]) {                ret[0] = i + 1, ret[1] = mid + 1;                return ret;            } else if (numbers[mid] > target - numbers[i]) {                high = mid - 1;            } else {                low = mid + 1;            }        }    }     ret[0] = -1, ret[1] = -1;    return ret;}
复制代码


运行效率如下所示:





第 2 题:换酒问题


试题要求如下:



回答(C 语言):


int numWaterBottles(int numBottles, int numExchange){    int temp_numBottles = numBottles;    int temp_num = 0;    int temp_data = numBottles;     while(temp_numBottles >= numExchange){        temp_num = temp_numBottles/numExchange;        temp_data += temp_num;        temp_numBottles %= numExchange;        temp_numBottles += temp_num;    }     return temp_data;}
复制代码


运行效率如下所示:





第 3 题:山脉数组的峰顶索引


试题要求如下:



回答(C 语言):


int peakIndexInMountainArray(int* A, int ASize){    int i=0;     while(A[i]<A[i+1]) i++;        return i;}
复制代码


运行效率如下所示:





第 4 题:矩阵中的幸运数


试题要求如下:



解答思路:


注意:题目有说数字都不同,那返回数组的 size 用行数或者列数都行。


第 1 次遍历:存下每行的最小值到数组;


第 2 次遍历:存下每列的最大值到数组;


第 3 次遍历:满足条件的加入要返回的结果数组。


回答(C 语言):


int* luckyNumbers (int** matrix, int matrixSize, int* matrixColSize, int* returnSize){    int i, j;    int *ret = (int*)malloc(sizeof(int) * matrixSize);    int minRow[matrixSize], maxCol[*matrixColSize];        for (i = 0; i < matrixSize; i++) {        minRow[i] = INT_MAX;        for (j = 0; j < *matrixColSize; j++) {            if (matrix[i][j] <= minRow[i]) {                minRow[i] = matrix[i][j];            }        }    }     for (i = 0; i < *matrixColSize; i++) {        maxCol[i] = INT_MIN;        for (j = 0; j < matrixSize; j++) {            if (matrix[j][i] >= maxCol[i]) {                maxCol[i] = matrix[j][i];            }        }    }     *returnSize = 0;    for (i = 0; i < matrixSize; i++) {        for (j = 0; j < *matrixColSize; j++) {            if (matrix[i][j] == minRow[i] && matrix[i][j] == maxCol[j]) {                ret[*returnSize] = matrix[i][j];                (*returnSize)++;            }        }    }     return ret;}
复制代码


运行效率如下所示:





第 5 题:去掉最低工资和最高工资后的工资平均值


试题要求如下:



解答思路:


一次遍历找出最大 max、最小 min 和总和 sum,平均值 average = (sum - max - min) / (salarySize - 2),没有难度,只需要注意数据类型即可。


回答(C 语言):


double average(int* salary, int salarySize){    int max = salary[0];    int min = salary[0];    int sum = 0;    double average = 0;     if(salarySize <= 2)        return 0;     for(int i = 0; i < salarySize; i++){        if(max < salary[i])            max = salary[i];        else if(min > salary[i])            min = salary[i];        sum += salary[i];    }     average = (double)(sum - max - min) / (double)(salarySize - 2);    return average;}
复制代码


运行效率如下所示:





第 6 题:非递增顺序的最小子序列


试题要求如下:



回答(C 语言):


/** * Note: The returned array must be malloced, assume caller calls free(). */int cmp(int *a,int *b){    return *b - *a;} int* minSubsequence(int* nums, int numsSize, int* returnSize){    qsort(nums,numsSize,sizeof(int),cmp);    int left = 0,right = numsSize-1,leftsum = nums[left],rightsum = nums[right];     while(left < right)    {        if(leftsum > rightsum)        {            right--;            rightsum += nums[right];        }        else        {            left++;            leftsum +=nums[left];        }    }     *returnSize = left+1;    return nums;}
复制代码


运行效率如下所示:





第 7 题:独一无二的出现次数


试题要求如下:



回答(C 语言):


bool uniqueOccurrences(int* arr, int arrSize){    int result[2001];    int result_nums[2001];    memset(result, 0, 2001 * sizeof(int));    memset(result_nums, 0, 2001 * sizeof(int));     for(int i=0; i < arrSize;++i){        if(arr[i] < 0){            result[arr[i]*(-1)+1000] += 1;        }        else{            result[arr[i]] += 1;        }       }     for(int j=0;j < 2001 ;++j){        if(result[j]>0){            result_nums[result[j]] += 1;        }        if(result_nums[result[j]]>1){            return false;        }    }        return true;}
复制代码


运行效率如下所示:





第 8 题:反转字符串中的单词 3


试题要求如下:



解答思路:


1、用 i 和 j 锁定单词的首尾;


2、用 revers 对 s[i]到 s[j]进行翻转;


3、反复执行 1、2 直到遍历完字符串结束。


回答(C 语言):


void revers(char *s,int i,int j){    char temp;     while(i<j){        temp=s[i];        s[i]=s[j];        s[j]=temp;        i++;j--;    }} char * reverseWords(char * s){    int i=0,j=0;int slen=strlen(s);     for(int n=0;n<slen;n++){        if(s[n]!=' '){            i=n;n++;             while(s[n]!='\0'&&s[n]!=' '){                n++;            }             j=n-1;             revers(s,i,j);        }    }     return s;}
复制代码


运行效率如下所示:





第 9 题:玩筹码


试题要求如下:



解答思路:


1、首先分析发现:偶数位置转移到任意偶数位置代价为 0,同理奇数位置转移到任意奇数位置代价也为 0;


2、其次,我们简化筹码位置,将所有偶数集中到 2X 位置,所有奇数集中到 2X+1(或 2X-1)位置;


3、要想代价最小,就是移动数量最小的集合。


4、综合分析,发现实际上就是统计奇数和偶数的个数,取小者。


回答(C 语言):


int minCostToMoveChips(int* chips, int chipsSize){    int odd =0, even = 0;     for(int i = 0; i < chipsSize; i++){        if(chips[i]%2)            odd++;        else            even++;    }     return (odd <= even)? odd: even;}
复制代码


运行效率如下所示:





第 10 题:字母大小写全排列


试题要求如下:



回答(C 语言):


/** * Note: The returned array must be malloced, assume caller calls free(). */char ** letterCasePermutation(char * S, int* returnSize){	int len = strlen(S), size = 1;	char **res = (char**)malloc(sizeof(char*)*pow(2, len));	*res = (char*)calloc(len + 1, sizeof(char));	strcpy(*res, S); 	for (int i = 0; i < len; i++){		if (S[i]>'9'){			int k = size;            			for (int j = 0; j < k; j++){				res[k + j] = (char*)calloc(len + 1, sizeof(char));				strcpy(res[k + j], res[j]);				res[k + j][i] = S[i] < 'a' ? S[i] + 32 : S[i] - 32;				size++;			}		}	} 	*returnSize = size;	return res;}
复制代码


运行效率如下所示:



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

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

【公众号】美男子玩编程

评论

发布
暂无评论
力扣(LeetCode)刷题,简单题(第19期)