注意点：题目要求了不能使用 long long 就需要特殊判断一下溢出的情况
class Solution {public:int reverse(int x) {int r = 0;while(x) {if(x > 0 && r > (INT_MAX - x % 10) / 10) return 0;if(x < 0 && r < (INT_MIN - x % 10) / 10) return 0;//以上两个if就是用来判断r可能溢出INT的情况r = r * 10 + x % 10;x /= 10;}return r;}};
8. 字符串转换整数 (atoi)
思想
我们一步一步考虑可能出现情况 ， 并将他处理了即可
class Solution {public:int myAtoi(string s) {//首先需要判断一下' ' ， 把前面的空格全部删除int k = 0;while(s[k] == ' ') k++;if(k == s.size()) return 0;//再判断可能遇到的 - 和 +int f = 1;if(s[k] == '-') f = -1, k++;else if(s[k] == '+') k++;//取出每一个数字int res = 0;while(k < s.size() && s[k] >= '0' && s[k] <= '9') {int x = s[k++] - '0';//可能存在溢出情况需要特殊判断if(f > 0 && res > (INT_MAX - x) / 10) return INT_MAX;if(f < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;//由于正负区间不是对称的 ， 所以需要特殊判断一下范围更大的负数边界if(-res * 10 - x == INT_MIN) return INT_MIN;res = res * 10 + x;}return res * f;}};
9. 回文数
思想
这题目的方法很多也比较简单 ， 这里主要介绍翻转法和数值法
翻转法
()表示翻转后的第一个元素 ， rend()同理 。
class Solution {public:bool isPalindrome(int x) {if(x < 0) return false;string s = to_string(x);return s == string(s.rbegin(), s.rend()); }};
数值法
数值法就是和前面整数翻转思想一模一样 ， 并且这道题目没有long long的限制
class Solution {public:bool isPalindrome(int x) {if(x < 0) return false;long long res = 0, k = x;while(x) {res = res * 10 + x % 10;x /= 10;}return k == res;}};
11. 盛最多水的容器
思想
使用双指针算法 ， i从数组的起点开始 ， j从数组的结尾开始 ， 每次都先计算一下[i, j]范围内的结果 ， 和上一次计算结果比较取最大值 。随后比较i ， j两个位置的大小 ， 小的一侧移动一位 。
class Solution {public:int maxArea(vector& height) {int res = 0;for(int i = 0, j = height.size() - 1; i < j;) {res = max(res, min(height[i], height[j]) * (j - i));if(height[i] < height[j]) i++;else j--;}return res;}};
12. 整数转罗马数字
思想
我们根据题干和数据得内容判断 ， 这个题目应该可以枚举找出其中的规律
[图片]
其中每一位的情况中有几个特殊的情况比如 ， 900、500、400、90、50、40、9、5、4
给定的整数我们从高位开始从大到小判断整数属于哪个区间 ， 减去对应区间的数值 ， 这样描述比较抽象 ， 我按照2469距离：
class Solution {public:string intToRoman(int num) {int a[] = {1000,900, 500, 400, 100,90, 50, 40, 10,9, 5, 4, 1};string b[] = {"M","CM", "D", "CD", "C","XC", "L", "XL", "X","IX", "V", "IV", "I"};string res;for(int i = 0; i < 13; i++) {while(num >= a[i]) {num -= a[i];res += b[i];}}return res;}};
13. 罗马数字转整数
这道题目就是上一题目的逆运算 ， 需要特殊判断的情况是：前一位小于后一位 ， 例如4、40…
class Solution {public:int romanToInt(string s) {unordered_map heap;heap['I'] = 1, heap['V'] = 5,heap['X'] = 10, heap['L'] = 50,heap['C'] = 100, heap['D'] = 500,heap['M'] = 1000;int res = 0;for(int i = 0; i