13. 罗马数字转整数
罗马数字包含以下七种字符: 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 到 3999 的范围内
示例 1:
输入: "III" 输出: 3
示例 2:
输入: "IV" 输出: 4
示例 3:
输入: "IX" 输出: 9
示例 4:
输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
方法1
Hash表+模拟
罗马数字从前往后,数字是越来越小的.但有时候是一个字母表示,有时候是两个字母表示.但通过观察可以得知,这个是间隔出现的.所以我们可以从前往后进行遍历罗马序列,判断其1或2位罗马字符是否出现在V中.如果在,则累加即可,不在则直接判断下一个罗马字符是否在序列中.
AC代码
#include<bits/stdc++.h> using namespace std; int romanToInt(string s) { 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"}; int ans = 0; int flag = 1;// int j = 0; string temp = ""; for(int i = 12; i>=0; i--) { if(i%2==0) { flag = 1; } else { flag = 0; } while(j<s.size()) { temp = ""; if(flag) { //奇数 1个 temp += s[j]; if(V[i]==temp) { ans += K[i]; j++; } else { break; } } else { //2个 if(j+1<s.size()) { temp=s[j]; temp+=s[j+1]; if(temp==V[i]) { ans += K[i]; j = j + 2; }else{ break; } } else { break;//肯定不符合. } } } } return ans; } int main() { string s = "MCMXCIV"; cout<<romanToInt(s)<<endl; return 0; }
方法2
观察得规律.
罗马数字由 I,V,X,L,C,D,M 构成；
当小值在大值的左边，则减小值，如 IV=5-1=4；
当小值在大值的右边，则加小值，如 VI=5+1=6；
由上可知，右值永远为正，因此最后一位必然为正。
一言蔽之，把一个小值放在大值的左边，就是做减法，否则为加法。
在代码实现上，可以往后看多一位，对比当前位与后一位的大小关系，从而确定当前位是加还是减法。当没有下一位时，做加法即可。
也可保留当前位的值，当遍历到下一位的时，对比保留值与遍历位的大小关系，再确定保留值为加还是减。最后一位做加法即可。
AC代码
#include<bits/stdc++.h> using namespace std; int getValue(char ch) { switch(ch) { case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; default: return 0; } } int romanToInt(string s) { int ans = 0; int preNum = getValue(s[0]); int len= s.size() ; int curNum; int i = 0; for(i = 1;i < len;i++){ curNum = getValue(s[i]); if(preNum<curNum){ ans -= preNum; }else{ ans += preNum; } preNum = curNum; } ans += preNum; return ans; } int main() { string s = "D"; cout<<romanToInt(s)<<endl; return 0; }
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
题目分析:
排序 + 双指针
(1). 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
(2). 对数组进行排序。
(3).遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
令左指针 L=i+1，右指针 R=n-1，当 L
(4) 当 nums[i]+nums[L]+nums[R]==0执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
(5).若和大于 0，说明nums[R] 太大，R左移
(6).若和小于 0，说明 nums[L] 太小，L右移
复杂度分析
- 时间复杂度：O(n^2)
数组排序 O(n logn)，遍历数组O(n)，双指针遍历 O(n)，总体 O(n logn)+O(n)∗O(n)， - 空间复杂度：O(1)
AC代码
#include<bits/stdc++.h> using namespace std; //https://leetcode-cn.com/problems/3sum/submissions/ //思路分析:https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/ vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; int len = nums.size(); int L,R; if(nums.size()<3){ return ans; } sort(nums.begin(),nums.end());//进行排序 if(nums[0]>0){ return ans;//如果第一个数>0 } for(int i = 0;i < len;i++){ L = i+1; R = len - 1; while(L<R){ int X = nums[i]+nums[L]+nums[R]; if(X==0){ ans.push_back({nums[i],nums[L],nums[R]}); //去除 重复元素,防止出现重复解 while(L<R&&nums[L]==nums[L+1]){ L++; } while(L<R&&nums[R]==nums[R-1]){ R--; } L++; R--; }else if(X>0){ R--; }else if(X<0){ L++; } } //去除num[i]的重复元素,防止出现重复解. while(i+1<len&&nums[i]==nums[i+1]){ i++; } } return ans; } int main() { vector<int> nums = {0}; cout<<threeSum(nums).size()<<endl; return 0; }
😜😜😜😜😜今天的刷题就结束了,好了,大家也卷起来!😝😝😝😝😝
