7、整数反转：
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
思路：假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。
根据这个假设，如果反转后的整数溢出，则返回 0。
先判断正负，然后看在反转过程中会不会越界，越界则返回0；
注意：判断时用除法而不用乘法是为了避免溢出发生；
class Solution {
public:
// #define INT_MAX 2147483647
// #define INT_MIN (-INT_MAX-1)
int reverse(int x) {
int flag=x<0?-1:1;
int num=0;
while(x){
//判断是否溢出
if((flag==-1&&(INT_MIN/10>num))||(flag==1&&INT_MAX/10<num))return 0;
num=num*10+x%10;
x/=10;
}
return num;
}
};
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，
也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
思路：
对于快乐数，难度在于计算每个位置上的数字的平方和，这里我们可以对n取余数得到n的个位，求其平方并累加，对n /10的结果用int保存，得到去除个位的n的其他位数字，
重复上述步骤，直至其他位数字求取结果为零，得到n的各个位置的数字的平方和，重复操作直至平方和等于1。
对于非快乐数，肯定不能进入死循环，那么肯定循环进行到一定程度，数字会和之前出现过n重复，因此我们保存每一步骤的n，
并在得到新的n的时候判断该数字是否出现过，出现过就为非快乐数，跳出循环。
class Solution {
public:
bool isHappy(int n) {
set<int> recordN;
int sum = 0;
while(n != 1){
recordN.insert(n);
sum = 0;
while(n != 0){
//各个数字求平方和
sum += ((n % 10) * (n % 10));
n = n / 10;
}
//若构成死循环，则返回false
if(recordN.find(sum) != recordN.end())
return false;
n = sum;
}
return true;
}
};
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
- 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
- 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
- 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
- 本题中的空白字符只包括空格字符
' '。 - 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42" 输出: 42
示例 2:
输入: " -42" 输出: -42 解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。
思路：是否为空判断，然后处理空格和正负号情况，然后遍历数字，字符相减转换成int
溢出的情况下，返回INT_MIN或者INT_MAX，最后判断一下正负返回
class Solution {
public:
int myAtoi(string s) {
int len = s.length();
if(len==0){
return 0;
}
int i=0;
//跳过前面空格，判断正负
while(s[i]==' '){
i++;
}
bool neg = false;
//对非空和非+-号的有效数字进行处理
if(s[i]=='-'){
neg=true;
i++;
}else if(s[i]=='+'){
i++;
}
long ans =0;
for(;i<len;i++){
if(s[i]>='0'&&s[i]<='9'){
//***字符相减转换成int
ans = ans*10+(s[i]-'0');
if(ans > INT_MAX && neg) return INT_MIN;
if(ans > INT_MAX && !neg) return INT_MAX;
}
//碰到非有效数字就退出
else{
break;
}
}
return neg?-ans:ans;
}
};
9. 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
思路：反转数字后判断两个数是不是相等，需要注意数据反转后溢出的情况，所以将反转后的类型定义为long
或者，输入数字转化为字符串。回文数关于中心对称，只需比较对称的数是否相等即可
class Solution {
public:
bool isPalindrome(int x) {
if(x<0){
return false;
}
int num=x;
long res = 0;
while(x){
res = res*10+x%10;
x = x/10;
}
cout<<res;
if (res!=num){
return false;
}
return true;
}
};
43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
思路：
①m位数乘以n位数的结果，最长为m+n位。
②在计算机中，以string标示的数字，下标i乘以下标j的结果，理应放在下标(i+j)处。
但是，考虑到进位，需要留一位固定的answer[0]给最高位进位的数字。
于是(i,j)乘积的临时结果temp的实际下标应该为answer[i+j+1]。
注意，要从个位开始乘法累加，在string中是从str[str.size()-1]开始到str[0]结束。
③在①中可以证明，m位乘n位结果最多m+n位，因此我们申请m+n位的数组，下标最大值为m+n-1。
在②中显然，下标i<=m-1，下标j<=n-1，则下标i+j+1<=m+n-1，恰好为数组下标的最大值。
从两个方向获得的上界吻合，所申请空间的利用率为100%。
模拟正常算乘法的步骤就可以，需要注意最后结果的第一个字符不能为‘0’。
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
int size1 = num1.size(), size2 = num2.size();
string str(size1 + size2, '0');
for(int i = size1 - 1; i >= 0; i--){
int mulflag = 0;
int addflag = 0;
for(int j = size2 - 1; j >= 0; j--){
int tmp = (num1[i] - '0') * (num2[j] - '0') + mulflag;
mulflag = tmp / 10;
tmp = tmp % 10;
int tmp2 = str[i + j + 1] - '0' + tmp + addflag;
str[i + j + 1] = tmp2 % 10 + '0';
addflag = tmp2 / 10;
}
str[i] += mulflag + addflag;
}
if (str[0] == '0')
str = str.substr(1, str.size());
return str;
}
};
172. 阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
思路：阶乘后的零是因为5乘以一个偶数的结果，所以5的个数，决定了阶乘后零的个数。
但是怎样查看阶乘中5的个数呢，要根据因式分子
例如n=30，30！=1*2*3*4*5*6*7*8*9*10*...*30;
里面有多少个为5的因式分子的，先看里面有多少个元素可以整除5，
有5，10，15，20，25，30共6个这个6是怎么求出来的呢？6=30/5；
然后在这六个元素里分别提取分式因子5，可以提取出六个，提取后变成1，2，3，4，5，6，然后看这六个里面有多少个元素可以整除5，6/5=1，
所以有一个元素5还可以继续提取出一个因式分子5，这样就可以看出30！中总共包括7个因式分子5.，所以有7个零
class Solution {
public:
int trailingZeroes(int n) {
int num=0;
while(n){
num=num+n/5;
n=n/5;
}
return num;
}
};
258. 各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
思路：常规方法，每位数字相加，如果和小于10，则直接返回，否则将和继续按位求和，直到满足条件
class Solution {
public:
int addDigits(int num) {
int res = 0;
int sum= 0;
while(num){
sum=sum+num%10;
num=num/10;
if(num==0&&sum>=10){
num = sum;
sum = 0;
}
if(num==0&&sum<10){
return sum;
}
}
res= sum;
return res;
}
};