【c++5道练习题】①

目录

一、有限制的累加

二、计算日期到天数转换

三、仅仅反转字母

四、 字符串的第一个唯一字符

五、字符串最后一个单词的长度

---

一、有限制的累加

 题述：

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A？B：C）

 题中已给： 

class Solution
{
public:int Sum_Solution(int n){}
};

知识点考察:

类的构造函数+ static修饰

先给代码再说思路：

代码如下：

#include<iostream>
using namespace std;class Sum
{
public:Sum()//构造函数{_sum += _i;++_i;}static void Init(){//静态成员函数可以访问静态成员变量_i = 1;_sum = 0;}static int GetSum()//静态成员函数可访问静态成员变量{return _sum;}
private:static int _i;//静态成员变量类内声明static int _sum;
};
int Sum::_i = 1;//静态成员变量类外定义（定义的同时初始化）
int Sum::_sum = 0;class Solution
{
public:int Sum_Solution(int n){Sum::Init();//每调用一次Sum_Solution函数都要初始化一次，不然会一直累加Sum* p = new Sum[n];//创建的同时，会调用n次构造函数//Sum a[n];//c99下才支持的变长数组return Sum::GetSum();//静态成员函数可通过类名直接访问}
};int main()
{Solution st;//实例化一个对象cout << st.Sum_Solution(5) << endl;//累加cout << st.Sum_Solution(5) << endl;system("pause");return 0;
}

思路：

自定义类型都要调用构造函数初始化，比如Date a[10] -》10个对象就要调用10次构造函数

那么n个对象就会调用n次构造函数，就像一个变相的循环

问题： 

为什么要用GetSum函数？

因为成员变量_i和_sum都是private权限下的，故在类外无法直接访问，所以用GetSum进行返回

为什么要用static修饰？

因为static是属于类的，每个对象都可以修改静态变量，那就可以实现一个累加效果，那用全局变量不可以吗，当然可用，但是c++中不推荐用全局变量，因为c++强调封装的意义，如果是全局变量谁都可以修改了。

成员函数用static修饰是因为

①、static成员函数才可访问成员变量

②、静态成员函数可通过类名加::的方式直接访问

成员变量用static修饰是因为

①、所有对象调用时都会对同一个static变量上运算

要特别注意一个问题：

每求一次累加和，都要初始化一次，因为OJ上有多个测试用例，需要多次测试的，你在自己编译器下可能就运行一次就跑出来了，但OJ上还是不通过，对于本题，这可能就因为连续累加，每调用一次Sum_Solution函数都在之前基础上累加，为了避免这个问题，我们再每一次调用Sum_Solution函数时都初始化一次(Init函数)。

二、计算日期到天数转换

题述：

根据输入的日期（某年某月某日），计算是这一年的第几天。

输入描述：

输入三行，分别是年、月、日

输出描述：

返回计算后的第几天

输入:

2012

12

31

输出：

366

思路：

①、创建一个日期类，并写一个运算符相减的重载，用这个日期减去本年的1月1号即可，但是对于这道题复杂化了

②、从1月累加到本月的前一月，计算天数，时间复杂度:O(1)，这个方法简单，本题采用此方法  

代码如下：

#include<iostream>
using namespace std;int main()
{static int monthDays[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };int year, month, day;//这样可不断接收输入，直到按ctrl+z就结束while (cin >> year >> month >> day){int n = 0;//从1月累加到month的前一月的天数for (int i = 1; i < month; i++){n += monthDays[i];}n += day;//如果是闰年，且>2月的前提下if (month > 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0))n += 1;cout << n << endl;}return 0;
}

注意：

一定要加个while，因为OJ上有多个测试用例，不加while的话一个测试用例是能过，但是OJ上会连续输入，那OJ上也要手动按Ctrl+z结束吗？不是，是OJ把测试用例写入文件中了，然后运行时读文件，读完给后台发个信号就完成了。

三、仅仅反转字母

题述：给定一个字符串 s ，返回“反转后的”字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例1：

输入：“ab-cd”

输出：“dc-ba”

示例2：

输入：“a-bc-dEf-ghIj”

输出：“j-Ih-jfE-dcba”

题中已给：

class Solution{
public:string reverseOnlyLetters(string s) {}
};

思路：

遍历方法用下标访问方便，不采用迭代器遍历字符串。

本质思路类似于快速排序实现的单趟排序的左右指针法

仅仅交换字母，那就定义两个下标begin=0,end=字符串大小-1，begin从左向右走，end从右向左走，两者直到找到对应的值为字母才会停下并交换，那整个大前提就是begin<end才会继续，在begin和end找的过程中也要要求begin<end，不然若字符串全不是字母，begin会一直走，然后越界。

class Solution{
public://判断一个字符是不是字母bool Ischar(char ch){if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')){return true;}else{return false;}}//仅仅交换字母string reverseOnlyLetters(string s) {int begin = 0;int end = s.size() - 1;//算出s的大小，求出最后一个数的下标while (begin < end)//大前提是begin < end循环才继续{while (begin < end && Ischar(s[begin]) == false){//在走的过程中begin < end才能继续往下走，直到找到s[begin]是字母为止begin++;}while (begin < end && Ischar(s[end]) == false){//在走的过程中begin < end才能继续往下走，直到找到s[end]是字母为止end--;}swap(s[begin], s[end]);//c++自动提供swap交换函数//交换完后begin还要++,end还要--begin++;end--;}return s;//返回字符串}
};

四、 字符串的第一个唯一字符

题述：

给定一个字符串，找到他的第一个不重复的字符，并返回它的索引。若不存在，则返回-1.

案例：

s = "leetcode"

返回 0

s = "loveleetcode"

返回 2

要求：

时间复杂度：O（N）

空间复杂度：O（1）

注意事项：

您可假定该字符串只包含小写字母

题中已给：

class Solution {
public:int firstUniqChar(string s) {}
};

思路：

利用计数排序的思路，计数排序的本质就是哈希，若用暴力求解法时间复杂度：O（N*N）

和计数排序思路一样，不会计数排序就看我写的八大排序的文章

class Solution {
public:int firstUniqChar(string s) {//使用映射的方式统计次数int count[26] = { 0 };//26个小写字母for (auto ch : s){//范围for遍历scount[ch - 'a']++;//'a'-'a'就变为0}for (size_t i = 0; i < s.size(); ++i){if (count[s[i] - 'a'] == 1)return i;//出现一次则返回对应索引}return -1;//没有出现一次的则返回-1}
};

五、字符串最后一个单词的长度

题述：

计算字符串最后一个单词的长度，单词以空格隔开

输入描述：

一行字符串，非空，长度<5000

输出描述：

整数N，最后一个单词的长度

输入：

hello world

输出:

5

思路：

因为每个单词都以空格分隔，求长度简单，但怎么找最后一个单词，找最后一个空格即可，那就可用到rfind()，若找到对应字符返回其下标，若没找到返回-1，它会从后往前找，找到第一次的即可。

那一个单词也没有空格怎么办？rfind()没找到会返回-1，而代码中s.size() - 1 - pos，pos=-1,相当于直接求出长度，所以无需格外考虑 

典型的错误代码：

#include<iostream>
using namespace std;int main()
{string s;cin >> s;//输入字符串//从字符串后面往前找第一次出现的' '，并返回其下标给possize_t pos = s.rfind(' ');//利用下标计算最后一个单词的长度cout << s.size() - 1 - pos << endl;return 0;
}

 注意： 

 当输入的有空格、制表符、换行符时cin就不读了和scanf一样，但本题以空格为分隔，故用getline才行，getline只有遇到换行才结束

getline的使用说明如下：

 正确代码：

#include<iostream>
#include<string>
using namespace std;int main()
{string s;//cin >> s;//遇到空格、制表符、换行就结束了getline(cin, s);//遇到换行才结束//从字符串后面往前找第一次出现的' '，并返回其下标给possize_t pos = s.rfind(' ');//利用下标计算最后一个单词的长度cout << s.size() - 1 - pos << endl;return 0;
}