算法打卡第六天,今天你刷题了吗
😄😄😄😄😄😄😄😄😄😄
😃😃😃😃😃😃😃😃😃😃
💓💓💓大家一起来刷题!💓💓💓
😍😍😍😍😍😍😍😍😍😍
😘😘😘😘😘😘😘😘😘😘
😆😆😆😆😆😆😆😆😆😆
讯享网

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<R 时，执行循环：

(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; } 

😜😜😜😜😜今天的刷题就结束了,好了,大家也卷起来!😝😝😝😝😝