刷题代码

输入一个32位 的整数让它反转

(注意不能溢出)

#include<iostream> using namespace std; int reverse(int number) { int low, p, high = 0; int x = 1; while (number != 0) { low = number % 10; high = high * 10 + low; number = number / 10; ​ if (high > INT_MAX / 10 || (low > 7 && high == INT_MAX / 10)) { return 0; cout << "error\n"; } if (high < -INT_MAX / 10 || (low < -8 && high == INT_MAX / 10)) return 0; } return high; ​ } int main() { int number; cin >> number; int fan = reverse(number); cout << fan; ​ } ## ​罗马数字转化为整数 ```cpp ```cpp ```cpp class Solutio

n { public: int romanToInt(string s) { unordered_map<char, int> m = { {‘I’,1}, {‘V’,5}, {‘X’,10},{‘L’,50},{‘C’,100}, {‘D’,500},{‘M’,1000} }; int sum = 0; for (int i = 0; i < s.size(); ++i) m[s[i]] < m[s[i + 1]] ? sum -= m[s[i]] : sum += m[s[i]]; return sum;} ​

}

给定两个整数，被

除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符 。返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2。被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 −231, 231 − 1。本题中，如果除法结果溢出，则返回 231 − 1。31表示次方 ```cpp int div(int dividend,int divisor) { if(divisor>dividend) return 0; int res=1; int original_divisor=divisor; while(dividend-divisor>=divisor)//特别需要注意的地方是dividend-divisor之后还大于等于divisor，即是dividend>=2divisor { divisor+=divisor; res+=res; } res+=div(dividend-divisor,original_divisor); return res; ​ } int divide(int dividend, int divisor) { int res=0; int flag=((dividend>0&&divisor>0)||(dividend<0&&divisor<0)); //先处理特殊值，即是处理边界溢出问题 INT_MIN if(divisor==1) return dividend; if(divisor==INT_MIN) return dividend==INT_MIN?1:0; if(divisor==-1) return dividend==INT_MIN?INT_MAX:-dividend; if(dividend==INT_MIN)//如果被除数是32位最小整数必须进行一定的处理，先让其减或者加一次除数 { dividend=(flag)?(dividend-divisor):(dividend+divisor); res++; ​ } dividend=(dividend>0)?dividend:-dividend; divisor=(divisor>0)?divisor:-divisor; res+=div(dividend,divisor); return (flag)?res:-res; ​ } ​ ​ ## 二分查找 给一个排序好的数组和一个数字，找到这个数字

所在的位置，如果不存在这个数字，返回这个数字插入的位置序号

sort(nums.begin(),nums.end()); int n = nums.size(); int left = 0, right = n - 1,ans = n; while(left <= right) { int mid = ((right - left)>> 1 )+ left; if (target <= nums[mid]) { ans = mid; right = mid - 1; } else left = mid + 1; } return ans; int main() { vector<int>nums; int n; cin >> n; int a; for (int i = 0; i < n; i++) { cin >> a; nums.push_back(a); } int number; cin >> number; int m =search(nums, number); cout << m<<endl; ​ }

判断小于n的非负数中的质数 1和0不是质数 2是质数

int countPrimes(int n) { if(n < 3) return 0;; //从3开始验算，所以初始值为1（2为质数）。 int count = 1; for (int i = 3; i < n; i++){ //当某个数为 2 的 n 次方时（n为自然数），其 & (n - 1) 所得值将等价于取余运算所得值 //*如果 x = 2^n ，则 x & (n - 1) == x % n //if(i % 2 == 0) if ((i & 1) == 0) continue; ; bool sign = true; //用 j * j <= i 代替 j <= √i 会更好。 //因为我们已经排除了所有偶数，所以每次循环加二将规避偶数会减少循环次数 for (int j = 3; j * j <=i; j+=2){ if (i % j == 0){ sign = false; break; } } if (sign) count++; ; } return count; }