一.方法介绍

  1. 若面试时是关于n位的整数并且没有限定n的取值范围，或者说输入是一个任意大小的数字，则说明很可能要考虑大数问题，也即可能超出存储范围，这时可以换long long存储或者转为用字符串来表示。
  2. int型的最大值是0x7fffffff,最小值是0x8000000
  3. 若在计算和的时候超过int型，比如A+B+C+D==target的判定，可以把和的形式改成A+B==target-C-D的判定。

二.leetcode题

7.整数反转

题目链接
无论是正数还是负数，都可以用正常手段求解。
在求解过程中，一旦结果已经超过int型的最大值和最小值，则直接返回结束。
int型的最大值是0x7fffffff,最小值是0x8000000

9.回文数

题目链接

  1. 不申请额外的空间，只取出数字的一半进行反转，然后对比，比如1221，取出21反转12和12比较，
  2. 如何判断已经取了一半数字了：就是当取出的反转数revertNum大于等于剩下的数x时，则说明已经对半，
  3. 判断长度奇数偶数情况：如果是偶数的话，则revertNum是和x相等；若是奇数，则最中间的数字在revertNum的最低位上，将它除以10以后要和x相等， 所以得到 return x==revertNum || x==revertNum/10;

55.跳跃游戏-(最远距离)

题目链接
题目并没有说要把这个跳法给找出来，而是问能不能跳，因此，不需要纠结究竟是从哪开始起跳，起跳路径是什么，只需要知道能跳的最远距离能不能到达尾部即可。
解法:挨个跳,
1.依次遍历，把每个点都作为起跳点去尝试，然后更新能跳到的最远的位置maxh
2.跳不成功的退出条件: 能跳到的最远的位置maxh比当前遍历到的点的下标的位置还要小，说明没法到达了
3.对于能跳到的最远位置maxh，说明这个位置往左的所有位置都是可达的，都是可以依次遍历的

  1.  bool canJump(vector<int>& nums) {
  2.         int maxh=0,i,j;
  3.         for (i=0;i<nums.size();i++) {
  4.             if (maxh<i)
  5.                 return false;
  6.             maxh=((i+nums[i])>maxh) ? (i+nums[i]) : maxh;
  7.         }
  8.         return true;
  9.     }

168.Excel表列名称-(进制转换，余数除数)

题目链接
这里是将十进制转换成2位的26进制数，不过有一点要注意的是，这里映射的是1-26，而不是0-25，因此，需要在模的时候(x-1)%d, 人为将余数转换到0-25，再进行映射。

169.多数元素-(投票算法)-人多势众

题目链接
解法: 投票选举法 ，大于n/2
candidate是候选众数，count是候选众数出现的次数
如果count==0，则对candidate=nums[i],并且判断
则若candidate==nums[i],就count++;
若candidate!=nums[i],就count—;
最后投票选举出来的candidate就是众数。
也即若候选人不是众数，则众数会和其他数一起反对，即候选人一定会下台;若候选人是众数，则由于众数的数目是超过一半的，则众数一定会当选。

不妨假设整个数组的众数记做a，则最初的数组中a的数量大于其余所有数。当采用count计数的时候有两种情况： 1）假设candidate等于a，则当count从1变为0的过程，此区间内a的数量等于其余数的数量，因此以count=0为分界线，数组右端部分的众数仍然为a
2）假设candidate不等于a，则当count从1变为0的过程， 此区间内a的数量小于等于其余数的数量，因此以count=0为分界线，数组右端部分的众数仍然为a

172.阶乘后的零-(阶乘判0)

题目链接
每个尾部的0由2x5=10得到，因此，阶乘数里总共有多少对(2,5)，就是有多个0。
又由于质因子2的数量是远多于质因子5的数量的，因此，可以只统计阶乘结果里有多少个质因子5。与此同时，由于是阶乘，因此不需要真正将结果计算出来。
如何计算阶乘里面有多少个5？
25/5=5是有5个5相加，然后把5个5变成5个1，即为5，5/5=1,表示有1个5相加，
100/5=20表示有20个5相加，然后变成20个1相加，20/5=4表示有4个5相加，然后相当于4个1相加。
因此，有了下面的递归公式的代码

int trailingZeroes(int n) {
    return n == 0? 0: n / 5 + trailingZeroes(n / 5);
}

204.计数质数-(埃氏筛统计质数)

题目链接
埃氏筛—厄拉多塞筛法
基本思想：
若x是质数，则大于x的x的倍数2x, 3x,…一定不是质数
设isPrimes[i]表示数i是否是质数，若质数则为true，否则为false。
同时可以继续优化，可以不用从2x开始标记，可以直接从xx进行标记，因为显然，2x等在x之前的倍数已经被标记过了，从xx标记到x*j对于质数的个数，可以边标记边统计，因为从2,3…p开始，到下一个质数q前，所有的非质数都已经很巧妙地被标记了，所以只要isPrimes[i]=true，就count++。

代码细节注意：
这里有一点要注意的是，由于xx可能会超过int的存储，因此不建议用for (j=x;jx而是用
if((long)xxfor(j=xx;j}

326.3的幂

题目链接
一种是利用对数，数学问题 - 图1 ，则若n是3的整数次方，则m一定是整数.
另一种是比较取巧的，如在int型范围内3的最大次方是数学问题 - 图2=1162261467，则若n是3的整数次方，则1162261467除以n的余数一定是零。

剑指Offer面试题17：打印从1到最大的n位数

题目：

输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999。

这道题不能直接以整形进行按顺序输出打印，因为没有规定n的大小，因此，有可能会超出int型甚至是长整型（long long int），也即我们需要考虑大数问题。
因此，这道题要利用字符串进行加1操作。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string AddOne(string num) {
    reverse(num.begin(), num.end());
    int index = 1, i = 0, seat;
    for (i = 0; i < num.size() && index != 0; i++) {
        seat = (num[i] - '0' + index)%10;
        index = ((num[i] - '0') + index)/10;
        num[i] = '0' + seat;
    }
    if (index == 1)
        num.push_back('1');
    reverse(num.begin(), num.end());
    return num;
}
int main() {
    string num = "1";
    int n = 2;
    if (n<=0) 
        cout<<"InputError!";
    for (; num.size() <= n;) {
        cout << num << endl;
        num = AddOne(num);
    }
    return 0;
}

258.各位相加

题目链接

50.Pow(x,n)

题目链接

  1. 以成倍的形式进行计算，快速幂法+递归
  2. 由于是double，因此在判等时，不能是1e-8而是1e-10
    double Helper(long long int N,double x){
     if (N==1)
         return x;
     double y=Helper(N/2,x);
     return (N%2==0)? y*y:y*y*x;
 }
 double myPow(double x, int n) {
     long long int N=n;
     if (n==0||abs(x-1.00)<=1e-10)
         return 1.0;
     x=(n<0)? (1/x):x;
     N=(n<0)? -N:N;
     return Helper(N,x);
 }