C++从零开始的打怪升级之路(day11)

发布时间:2024年01月18日

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料

那么开启正题

为了巩固前面的知识,最近更新刷题贴,C++进度暂缓

1.反转字符串中的单词

反转字符串中的单词 III

?由于还没学C++的字符串有些题的ac代码是用C语言写的

给定一个字符串?s?,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序

思路:实现一个子函数,来反转字符串,利用快慢指针在原字符串中“分隔单词”,利用子函数完成任务

void _reverseWords(char* left,char* right)
{
    while(left < right)
    {
        char tmp = *left;
        *left = *right;
        *right = tmp;

        ++left;
        --right;
    }
}

char* reverseWords(char* s) 
{
    char* fast = s;
    char* slow = s;
    while(*fast)
    {
        if(*fast == ' ')
        {
            _reverseWords(slow,fast - 1);
            ++fast;
            slow = fast;
        }
        else
        {
            ++fast;
        }
    }
    _reverseWords(slow,fast - 1);

    return s;
}

这是ac代码,要注意的是,出了while循环后还有最后一次翻转未完成

2.连续字符

1446. 连续字符

给你一个字符串?s?,字符串的「能量」定义为:只包含一种字符的最长非空子字符串的长度。

请你返回字符串?s?的?能量

用前后双指针遍历字符串,用conut记录同一字符连续次数,用max存储最大值

int maxPower(char* s) 
{
    int max = 0;
    int count = 0;
    char* slow = s;
    char* fast = s;
    while(*fast)
    {
        if(*fast == *slow)
        {
            ++count;
            ++fast;
        }
        else
        {
            if(count > max)
            {
                max = count;
            }
            count = 0;
            slow = fast;
        }
    }
    if(count > max)
    {
        max = count;
    }

    return max;
}

这是ac代码,同样要注意,出whlie循环后还有一次没有比较

3.字符串压缩

面试题 01.06. 字符串压缩

?字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)

和上面的题类似,利用快慢指针获取拷贝题目所需的数据,需要注意的是数字转换成字符串,还有最后的返回标准?

char* compressString(char* S) {
    char* slow = S;
    char* fast = S;
    char* ret = (char*)malloc(sizeof(char) * 100000);
    int reti = 0;
    int count = 0;
    while (*fast) 
    {
        if (*fast == *slow) 
        {
            ++count;
            ++fast;
        } else
        {
            ret[reti++] = *slow;
            if (count < 10) 
            {
                ret[reti++] = count + '0';
            } 
            else if (count >= 10 && count < 100) 
            {
                ret[reti++] = count / 10 + '0';
                ret[reti++] = count % 10 + '0';
            } 
            else if (count >= 100 && count < 1000) 
            {
                ret[reti++] = count / 100 + '0';
                ret[reti++] = count / 10 % 10 + '0';
                ret[reti++] = count % 10 + '0';
            } 
            else if (count >= 1000 && count < 10000) 
            {
                ret[reti++] = count / 1000 + '0';
                ret[reti++] = count / 100 % 10 + '0';
                ret[reti++] = count / 10 % 10 + '0';
                ret[reti++] = count % 10 + '0';
            }    
            else if (count >= 10000 && count < 100000) 
            {
                ret[reti++] = count / 10000 + '0';
                ret[reti++] = count / 1000 % 10 + '0';
                ret[reti++] = count / 100 % 10 + '0';
                ret[reti++] = count / 10 % 10 + '0';
                ret[reti++] = count % 10 + '0';
            }
            count = 0;
            slow = fast;
        }
    }

    ret[reti++] = *slow;
    if (count < 10) 
    {
        ret[reti++] = count + '0';
    } 
    else if (count >= 10 && count < 100) 
    {
        ret[reti++] = count / 10 + '0';
        ret[reti++] = count % 10 + '0';
    } 
    else if (count >= 100 && count < 1000) 
    {
        ret[reti++] = count / 100 + '0';
        ret[reti++] = count / 10 % 10 + '0';
        ret[reti++] = count % 10 + '0';
    }     
    else if (count >= 1000 && count < 10000) 
    {
        ret[reti++] = count / 1000 + '0';
        ret[reti++] = count / 100 % 10 + '0';
        ret[reti++] = count / 10 % 10 + '0';
        ret[reti++] = count % 10 + '0';
    } 
    else if (count >= 10000 && count < 100000) 
    {
        ret[reti++] = count / 10000 + '0';
        ret[reti++] = count / 1000 % 10 + '0';
        ret[reti++] = count / 100 % 10 + '0';
        ret[reti++] = count / 10 % 10 + '0';
        ret[reti++] = count % 10 + '0';
    }
    ret[reti] = '\0';

    int num1 = strlen(S);
    int num2 = strlen(ret);

    if (num2 >= num1) 
    {
        return S;
    } 
    else 
    {
        return ret;
    }
}

这是ac代码,数字转换成字符串的方式很粗糙,大家有更好的办法可以评论

4.数组中出现次数超一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网

给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2?

1.计数法

创建一个数组初始化全0,遍历给定数组,给创建数组++,遍历创建数组,根据条件改变返回值

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) 
{
    int ret = 0;
    int a[10000] = {0};
    int i=0;
    for(i=0;i<numbersLen;i++)
    {
        ++a[numbers[i]];
    }
    for(i=0;i<10000;i++)
    {
        if(a[i] > numbersLen/2)
        {
            ret = i;
        }
    }
    return ret;
}

?这是ac代码

2.特殊法

利用题目特性,我们可以设计一个计数count,记录x数据出现的次数。遍历数组,拿到numbers[i]后,进行如下操作:

1. 如果count等于0,表明该元素第一次出现,使用x记录该元素,并将count设置为1

2. 否则:如果numbers[i] == x,count++;否则count-- 上述操作结束后,x中标记的元素可能是出现次数刚好超过一般的元素

int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) 
{
    int count = 0;
    int x = numbers[0];
    int i=0;
    for(i=0;i<numbersLen;i++)
    {
        if(count == 0)
        {
            x = numbers[i];
            count++;
        }
        else
        {
            if(x == numbers[i])
            {
                count++;
            }
            else 
            {
                count--;
            }
        }
    }

    return x;
}

这是ac代码?

5.两数之和

LCR 006. 两数之和 II - 输入有序数组

给定一个已按照?升序排列??的整数数组?numbers?,请你从数组中找出两个数满足相加之和等于目标数?target?。

函数应该以长度为?2?的整数数组的形式返回这两个数的下标值numbers?的下标?从 0?开始计数?,所以答案数组应当满足?0?<= answer[0] < answer[1] <?numbers.length?。

假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。

这题首先肯定不能用暴力枚举,因为时间有限制

下面介绍两种方法

1.左右指针法

初始两个指针,一个指向数组的第一个元素,另一个指向数组最后一个元素,将下标对应的值之和与目标数进行比较,如果大了,就让右指针向左偏移一次,如果小了,就让左指针向右偏移一次,直到得到目标结果

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
{
    int* str = (int*)malloc(sizeof(int)*2);
    *returnSize = 2;
    int i = 0;
    int j = numbersSize - 1;
    while(1)
    {
        if(numbers[i] + numbers[j] == target)
        {
            str[0] = i;
            str[1] = j;
            break;
        }
        else if(numbers[i] + numbers[j] < target)
            i++;
        else
            j--;
    }

    return str;
}

这是ac代码,具体怎么证明这样不会错过答案,可以自行看官方题解

2.二分法

假定一个数已经找到,将数组元素都减去目标值,另一个数必然存在改变后的数组当中,且数组有序,利用二分法即可求解

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
{
    int* ret = (int*)malloc(sizeof(int)*2);
    *returnSize = 2;
    int i=0;
    for(i=0;i<numbersSize - 1;i++)
    {
        int left = i + 1;
        int right = numbersSize - 1;

        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(numbers[mid] + numbers[i] == target)
            {
                ret[0] = i;
                ret[1] = mid;
                return ret;
            }
            else if(numbers[mid] + numbers[i] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
    }

    return ret;
}

这是ac代码

6.几道难题

394. 字符串解码

43. 字符串相乘

这两道题有些难懂,待我功力深一点了再回头解决,明天开始继续C++学习?

今天的博客就到这里了,后续内容明天分享,最近因为考试周原因不能更新太多内容,等考试周结束了再"快马加鞭"

新手第一次写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!!!?

文章来源:https://blog.csdn.net/2301_80764270/article/details/135598951
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。