8. 字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
示例 1：
输入：s = "42" 输出：42 解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。 第 1 步："42"（当前没有读入字符，因为没有前导空格） ^ 第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'） ^ 第 3 步："42"（读入 "42"） ^ 解析得到整数 42 。 由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：
输入：s = " -42" 输出：-42 解释： 第 1 步：" -42"（读入前导空格，但忽视掉） ^ 第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数） ^ 第 3 步：" -42"（读入 "42"） ^ 解析得到整数 -42 。 由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：
输入：s = "4193 with words" 输出：4193 解释： 第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格） ^ 第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'） ^ 第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止） ^ 解析得到整数 4193 。 由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
示例 4：
输入：s = "words and 987" 输出：0 解释： 第 1 步："words and 987"（当前没有读入字符，因为没有前导空格） ^ 第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'） ^ 第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止） ^ 解析得到整数 0 ，因为没有读入任何数字。 由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
示例 5：
输入：s = "-91283472332" 输出：-2147483648 解释： 第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格） ^ 第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数） ^ 第 3 步："-91283472332"（读入 "91283472332"） ^ 解析得到整数 -91283472332 。 由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。
思路分析:
- 1.先移除字符串之前的空格
- 2.判断第一个字符是否是+/- 是的话做个标记.
- 3.判断是否超出范围.如果不超出,加到res上.
- 4.其他情况直接break
AC代码
#include<bits/stdc++.h> using namespace std; //题目思路: /** */ // //https://leetcode-cn.com/problems/string-to-integer-atoi/ int myAtoi(string s) { int sign = 1;//正负号标记 int res = 0 ;//结果 int i = 0;// while(s[i]==' '&&i<s.size()) { i++; } int start = i;//记录start for(; i<s.size(); i++) { if(s[i]=='+'&&i==start) { sign = 1; } else if(s[i]=='-'&&i==start) { sign = -1; } else if(s[i]>='0'&&s[i]<='9') { //数字 int num = s[i]-'0'; if(res>INT_MAX/10 || (res==INT_MAX/10&&num>INT_MAX%10)) { return INT_MAX; } if(res<INT_MIN/10||(res==INT_MIN/10&&-num<INT_MIN%10)) {//负数求余也是负数 return INT_MIN; } res = res*10+num*sign; }else{ break; } } return res; } int main() { string s = "-2147483646"; cout << myAtoi(s) << endl; return 0; }
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色
示例 2：
输入：height = [1,1] 输出：1
示例 3：
输入：height = [4,3,2,1,4] 输出：16
示例 4：
输入：height = [1,2,1] 输出：2
思路分析
双指针的使用
设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为 S(i, j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ：
S(i,j)=min(h[i],h[j])×(j−i)
若向内 移动短板 ，水槽的短板 min(h[i], h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板 min(h[i], h[j]) 不变或变小，因此下个水槽的面积 一定变小 。
因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。
AC代码
#include<bits/stdc++.h> using namespace std; //https://leetcode-cn.com/problems/container-with-most-water/ //思路:双指针. int maxArea(vector<int>& height) { int l = 0; int r = height.size()-1; int res = 0; while(l<r){ if(height[l]<height[r]){ res = max(res,height[l]*(r-l)); l++; }else{ res = max(res,height[r]*(r-l)); r--; } } return res; } int main() { vector<int> height = {4,3,2,1,4}; cout<<maxArea(height)<<endl; return 0; }
12. 整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
示例 1:
输入: num = 3 输出: "III"
示例 2:
输入: num = 4 输出: "IV"
示例 3:
输入: num = 9 输出: "IX"
示例 4:
输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.
思路分析:
Hash表+贪心
贪心法则：我们每次尽量使用最大的数来表示。 比如对于 1994 这个数，如果我们每次尽量用最大的数来表示，依次选 1000，900，90，4，会得到正确结果 MCMXCIV。
所以，我们将哈希表按照从大到小的顺序排列，然后遍历哈希表，直到表示完整个输入。
AC代码
#include<bits/stdc++.h> using namespace std; //https://leetcode-cn.com/problems/integer-to-roman/submissions/ //思路:Hash表+贪心思想. string intToRoman(int num) { int K[13] = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; string V[13] = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; string res=""; for(int i = 12;i >=0 ;i--){//13种进行枚举 while(num >= K[i]){ res+=V[i]; num-=K[i]; } } return res; } int main() { int num =9 ; cout<<intToRoman(num)<<endl; return 0; }
😜😜😜😜😜今天的刷题就结束了,好了,大家也卷起来!😝😝😝😝😝
