c语言单词内部反转的思路,力扣(LeetCode)刷题，简单题(第19期)

柔光的暖阳◎ 2022-10-15 05:58 97阅读 0赞

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

第2题：换酒问题

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

第4题：矩阵中的幸运数

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

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

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

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

第9题：玩筹码

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

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

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

试题要求如下：

![096f2f8ffe8688445a1d828f3326af77.png][]

回答(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;

运行效率如下所示：

![45af5d94b426df2ab02d392828375a7c.png][]

第2题：换酒问题

试题要求如下：

![5ed2db649881b783672b254b7f7c0908.png][]

回答(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;

运行效率如下所示：

![bf80c45e3825e8f0fd785f7cb316204b.png][]

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

试题要求如下：

![77f8bd05fa5218e02b9e54473f9a4437.png][]

回答(C语言)：

int peakIndexInMountainArray(int\* A, int ASize)\{

int i=0;

while(A\[i\]

运行效率如下所示：

![c9e412e89f8c50b5e009affec82bd108.png][]

第4题：矩阵中的幸运数

试题要求如下：

![67675353c19231e0da4307e196567c2a.png][]

解答思路：

注意：题目有说数字都不同，那返回数组的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;

运行效率如下所示：

![3af7070e4f443afeb8a3f7bacb5b6e04.png][]

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

试题要求如下：

![ffb39aaebc91eb38c097e619b63ddb13.png][]

解答思路：

一次遍历找出最大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;

运行效率如下所示：

![775ee0c7c7810577a9932492a66adb93.png][]

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

试题要求如下：

![23b52d929f60e70bff51039e2e574c93.png][]

回答(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;

运行效率如下所示：

![71278ead307ff10ee9aa1f8b1c9a29ba.png][]

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

试题要求如下：

![d1e4482c3b4f92d38214f0e214bd495f.png][]

回答(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;

运行效率如下所示：

![4bfdfb5fa0e749d09e7d31be05429488.jpg][]

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

试题要求如下：

![dc06b87f5d0916841765d151790485dc.png][]

解答思路：

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

运行效率如下所示：

![7469219e659f123c1fac704dc7d8fc8e.png][]

第9题：玩筹码

试题要求如下：

![0bd1f553be604e84847441711ae35167.jpg][]

解答思路：

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;

运行效率如下所示：

![250e8aa454e0231f458fb55ac4504548.png][]

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

试题要求如下：

![37c09176016ed020fc017c6fe8ebf8f5.png][]

回答(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;

运行效率如下所示：

![ff4df78138439d388a1b9b46e36aa4f0.png][]

[096f2f8ffe8688445a1d828f3326af77.png]: /images/20221014/a3796612e1a14ce58355899ecc3fa608.png
[45af5d94b426df2ab02d392828375a7c.png]: /images/20221014/263b74b4a4a74f2ba9e43ded4b995cc3.png
[5ed2db649881b783672b254b7f7c0908.png]: /images/20221014/9421a4682dfc4b9796e1d897a6b3187d.png
[bf80c45e3825e8f0fd785f7cb316204b.png]: /images/20221014/b39b058340ee49998a53133997fb577e.png
[77f8bd05fa5218e02b9e54473f9a4437.png]: /images/20221014/2c3dbe30ad2e4f2aa6e3e0ee7e1b8973.png
[c9e412e89f8c50b5e009affec82bd108.png]: /images/20221014/3073385255674ce79f6230bfd95ead88.png
[67675353c19231e0da4307e196567c2a.png]: /images/20221014/a8c4fbe0e4fa44dcbc60e982c5a86e9d.png
[3af7070e4f443afeb8a3f7bacb5b6e04.png]: /images/20221014/ceb636f774514b29869663a9b0b3e87b.png
[ffb39aaebc91eb38c097e619b63ddb13.png]: /images/20221014/b4a499ac72924e838761a4ed420f25ea.png
[775ee0c7c7810577a9932492a66adb93.png]: /images/20221014/a17afe0339bd4cba80a1547d2c18d421.png
[23b52d929f60e70bff51039e2e574c93.png]: /images/20221014/599d68cd26dc4e5f8fdd7855da6e8d48.png
[71278ead307ff10ee9aa1f8b1c9a29ba.png]: /images/20221014/3957c183c82d46c0969cfd3a322c801f.png
[d1e4482c3b4f92d38214f0e214bd495f.png]: /images/20221014/49f809e234044ad48100732a161809fa.png
[4bfdfb5fa0e749d09e7d31be05429488.jpg]: /images/20221014/4a4c0af8ae4d42599e2a7fcb71ecf005.png
[dc06b87f5d0916841765d151790485dc.png]: /images/20221014/134c2d429831438d866a4512c90442a5.png
[7469219e659f123c1fac704dc7d8fc8e.png]: /images/20221014/85600d5e288045289707533031719a01.png
[0bd1f553be604e84847441711ae35167.jpg]: /images/20221014/aa9e278c85dd45edbddaeefe8bb8b732.png
[250e8aa454e0231f458fb55ac4504548.png]: /images/20221014/62c31c93a7864eee8ae8e6354b6c38ac.png
[37c09176016ed020fc017c6fe8ebf8f5.png]: /images/20221014/28b4ecf69f9d4b46892c35e441537533.png
[ff4df78138439d388a1b9b46e36aa4f0.png]: /images/20221014/a525e2b945c64e1c96e832e1349d67d5.png