力扣(LeetCode)刷题，简单+中等题(第28期)
力扣(LeetCode)刷题，简单+中等题(第28期)
不脱发的程序猿
发布于 2021-01-20 11:36:10
发布于 2021-01-20 11:36: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;
}运行效率如下所示：
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-11-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录