力扣(LeetCode)刷题，简单+中等题(第28期)
【摘要】 目录
第1题：翻转单词顺序
第2题：顺时针打印矩阵
第3题：总持续时间可被 60 整除的歌曲
第4题：字符串的最大公因子
第5题：上升下降字符串
第6题：将数组分成和相等的三个部分
第7题：可被 5 整除的二进制前缀
第8题：去除重复字母
第9题：重构字符串
第10题：三角形的最大周长
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以...
目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：翻转单词顺序
试题要求如下：
回答（C语言）：
-
char* reverseWords(char* s){
-
// 去掉尾部的空格。最终至少留下一个空格，除非本身长度就为0
-
int n = strlen(s);
-
while(n > 0 && s[n-1] == ' ')
-
n--;
-
-
// 去掉头部的空格
-
int front = 0;
-
if(n > 0){
-
while(s[front] == ' ')
-
front++;
-
}
-
-
// 如果为空，返回
-
if( n - front == 0)
-
return "";
-
-
// 创建字符指针，长度大于等于实际长度
-
char *p = (char *)calloc(n + 1 - front, sizeof(char));
-
-
int index = 0; // 这是新字符串的下标
-
-
for( int i = n-1 , j = n-1; i >= front ; i--){
-
// 该写入单词了
-
if(i == front || (s[i] == ' ' && i != j) ){
-
int k = i + 1;
-
// 如果到头了，那头也应该写入
-
if(i == front)
-
k--;
-
for(; k <= j ; k++,index++){
-
p[index] = s[k];
-
}
-
// 注意！单词后要加上空格
-
if(i != front)
-
p[index] = s[i];
-
j = i - 1;
-
index = index + 1;
-
}
-
// 中间空格多时要跳过
-
else if(s[i] == ' '){
-
j--;
-
}
-
}
-
return p;
-
}
运行效率如下所示：
第2题：顺时针打印矩阵
试题要求如下：
解题思路：
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
-
if(!matrixSize){
-
*returnSize=0;
-
return NULL;
-
}
-
-
int ColSize=*matrixColSize;
-
*returnSize=matrixSize*ColSize;
-
int num=*returnSize;
-
int* val=(int*)malloc(sizeof(int)*num);
-
int x=0,y=0;
-
int count=0;
-
int no;
-
-
while(count<num){
-
no=0;
-
//左到右
-
while(no++<ColSize&&count<num){
-
val[count++]=matrix[y][x++];
-
}
-
y++,x--,matrixSize--,no=0;
-
//上到下
-
while(no++<matrixSize&&count<num){
-
val[count++]=matrix[y++][x];
-
}
-
y--,x--,ColSize--,no=0;
-
//右到左
-
while(no++<ColSize&&count<num){
-
val[count++]=matrix[y][x--];
-
}
-
x++,y--,matrixSize--,no=0;
-
//下到上
-
while(no++<matrixSize&&count<num){
-
val[count++]=matrix[y--][x];
-
}
-
ColSize--,y++,x++;
-
}
-
-
return val;
-
}
运行效率如下所示：
第3题：总持续时间可被 60 整除的歌曲
试题要求如下：
回答（C语言）：
-
int numPairsDivisibleBy60(int* time, int timeSize){
-
int temp[61] = {0};
-
int cnt = 0;
-
-
//统计余数出现的次数，余数作为下标
-
for(int i = 0;i < timeSize;i++)
-
{
-
temp[time[i]%60]++;
-
}
-
-
//余数为0和30的情况，对数为组合Cn2 = n*（n-1）/2
-
cnt = temp[0]*(temp[0] - 1)/2 + temp[30]*(temp[30] - 1)/2;
-
//余数为其他情况，每个余数i都能够与余数60-i配对，所以对数为temp[i]*temp[60-i]
-
for(int i = 0;i < 30;i++)
-
{
-
cnt = cnt +temp[i]*temp[60-i];
-
}
-
-
return cnt;
-
}
运行效率如下所示：
第4题：字符串的最大公因子
试题要求如下：
解题思路：
递归法。
1、保证当前str1长度大于等于str2(通过判断交换实现)；
2、如果当前str1长度大于str2，且str1的前部与str2不一致，那么它们之间不存在公因字串；
3、如果当前str1长度大于str2，且str1的前部与str2一致，否则截取str1后面部分重新与str2比较；
4、如果当前str1与str2一致，则最大公因子就是本身。
回答（C语言）：
-
char * gcdOfStrings(char * str1, char * str2){
-
int len1 = strlen(str1);
-
int len2 = strlen(str2);
-
-
if (len2 > len1) {
-
char *tmp = str1;
-
str1 = str2;
-
str2 = tmp;
-
len2 = len1;
-
}
-
-
if (memcmp(str1, str2, len2)) {
-
return "";
-
}
-
else if (str1[len2] == '\0' && str2[len2] == '\0') {
-
return str1;
-
}
-
-
return gcdOfStrings(str1 + len2, str2);
-
}
运行效率如下所示：
第5题：上升下降字符串
试题要求如下：
回答（C语言）：
-
char* sortString(char* s) {
-
int num[26];
-
memset(num, 0, sizeof(num));
-
int n = strlen(s);
-
for (int i = 0; i < n; i++) {
-
num[s[i] - 'a']++;
-
}
-
-
char* ret = malloc(sizeof(char) * (n + 1));
-
int retSize = 0;
-
while (retSize < n) {
-
for (int i = 0; i < 26; i++) {
-
if (num[i]) {
-
ret[retSize++] = i + 'a';
-
num[i]--;
-
}
-
}
-
for (int i = 25; i >= 0; i--) {
-
if (num[i]) {
-
ret[retSize++] = i + 'a';
-
num[i]--;
-
}
-
}
-
}
-
ret[retSize] = 0;
-
return ret;
-
}
运行效率如下所示：
第6题：将数组分成和相等的三个部分
试题要求如下：
解题思路：
1、求和，若和不是3的倍数，直接false；
2、求和的三分之一，从头开始遍历累加，遇到等于和三分之一，跳出循环，并指向下一个元素；
3、继续遍历求和，若等于和的三分之二，跳出循环；
4、判断此时的位置，如果是最后一位，则不符合条件，false，否则true。
回答（C语言）：
-
bool canThreePartsEqualSum(int* A, int ASize){
-
int sum = 0,i,j,temp,sum1 = 0;
-
-
//求和，若和不是3的倍数，直接false
-
for(int i = 0;i < ASize;i++)
-
{
-
sum = sum + A[i];
-
}
-
if(sum%3 != 0) return false;
-
-
//求和的三分之一
-
temp = sum/3;
-
//遍历累加，遇到等于和三分之一，跳出循环，并指向下一个元素
-
for(i = 0;i < ASize;i++)
-
{
-
sum1 = sum1 + A[i];
-
if(sum1 == temp) break;
-
}
-
//继续遍历求和，若等于和的三分之二，跳出循环
-
for(j = i + 1;j < ASize;j++)
-
{
-
sum1 = sum1 + A[j];
-
if(sum1 == temp*2) break;
-
}
-
//判断此时的位置，如果是最后一位，则不符合条件，false，否则true
-
if(j > ASize - 2)
-
return false;
-
else
-
return true;
-
}
运行效率如下所示：
第7题：可被 5 整除的二进制前缀
试题要求如下：
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
bool* prefixesDivBy5(int* A, int ASize, int* returnSize)
-
{
-
int temp = 0;
-
*returnSize = ASize;
-
-
bool* ret = (bool*)malloc(ASize * sizeof(bool));
-
-
for (int i = 0; i < ASize; i++) {
-
temp = (temp << 1) + A[i];
-
temp = temp % 5;
-
if (temp == 0) {
-
ret[i] = true;
-
} else {
-
ret[i] = false;
-
}
-
}
-
-
return ret;
-
}
运行效率如下所示：
第8题：去除重复字母
试题要求如下：
解题思路：
1、初始化一个数组recode[26];
2、遍历s记录每个字母出现的次数;
3、新建一个栈，遍历s进行入栈；
4、遍历栈，如果s[i]存在于栈中，则recode[s[i]-’a‘]--,并且继续下一次遍历；
5、否则比较栈顶字母和s[i]的大小，如果stack[top]>s[i]并且recode[stack[top]-'a']>1(说明stack[top]在后边还会出现)就出栈，并且recode[s[i]-’a‘]--；
6、入栈；
7、最后stack[++top]=’\0‘转成字符串。
回答（C语言）：
-
char * removeDuplicateLetters(char * s){
-
if (s == NULL || strlen(s) == 0) {
-
return "";
-
}
-
if (strlen(s) == 1) {
-
return s;
-
}
-
int len = (int)strlen(s);
-
//注意，这里需要初始化为0
-
char recode[26] = {0};
-
-
for (int i=0; i<len; i++) {
-
recode[s[i] - 'a']++;
-
}
-
-
char * stack = (char *)malloc(sizeof(char) * (len+1));
-
int top = -1;
-
-
int isExist;
-
for (int i=0; i<len; i++) {
-
isExist = 0;
-
for (int j=0; j<=top; j++) {
-
if (s[i] == stack[j]) {
-
isExist = 1;
-
break;
-
}
-
}
-
-
if (isExist) {
-
recode[s[i] - 'a']--;
-
}else{
-
while(top>-1 && stack[top] > s[i] && recode[stack[top] - 'a'] > 1) {
-
//如果栈顶字符比当前大，并且后边还会出现
-
recode[stack[top] - 'a']--;
-
//出栈
-
top--;
-
}
-
//入栈
-
stack[++top] = s[i];
-
}
-
}
-
stack[++top] = '\0';
-
return stack;
-
}
运行效率如下所示：
第9题：重构字符串
试题要求如下：
回答（C语言）：
-
int cmp(const void* a , const void* b)
-
{
-
int *aa = (int*)a;
-
int *bb = (int*)b;
-
/* sort from big to small */
-
return bb[0] - aa[0];
-
}
-
-
char * reorganizeString(char * S){
-
-
int rcnt = 0;
-
int len = strlen(S);
-
char * ret = (char *)malloc(sizeof(char)*len+1);
-
memset(ret, 0, sizeof(char)*len+1);
-
int a[26][2] = {0};
-
for (int i = 0; i < len; i++) {
-
a[S[i] - 'a'][0]++;
-
a[S[i] - 'a'][1] = S[i] - 'a';
-
}
-
int tmp = 0;
-
while (rcnt < len) {
-
tmp = 0;
-
qsort(a, 26, sizeof(int)*2, cmp);
-
for (int i = 0; i < 26 && tmp < 2; i++) {
-
if (a[i][0] > 0) {
-
ret[rcnt++] = 'a' + a[i][1];
-
tmp++;
-
a[i][0]--;
-
}
-
}
-
}
-
-
for (int i = 1; i < rcnt; i++) {
-
if (ret[i] == ret[i-1]) {
-
return "";
-
}
-
}
-
return ret;
-
}
运行效率如下所示：
第10题：三角形的最大周长
试题要求如下：
解题思路：
三角形两边之和，一定大于第三边。
回答（C语言）：
-
int cmp(void *_a, void *_b) {
-
int a = *(int *)_a, b = *(int *)_b;
-
return a - b;
-
}
-
-
int largestPerimeter(int *A, int ASize) {
-
qsort(A, ASize, sizeof(int), cmp);
-
for (int i = ASize - 1; i >= 2; --i) {
-
if (A[i - 2] + A[i - 1] > A[i]) {
-
return A[i - 2] + A[i - 1] + A[i];
-
}
-
}
-
return 0;
-
}
运行效率如下所示：
文章来源: blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/m0_38106923/article/details/109735614
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）