今天记录了3道题，难度范围：★★~★★★★。前两道题还是哈希表/哈希集合的使用，第三题是共同体的使用。
今天终于开始继续敲代码了，前几天在复习+完成一个大作业，熬到3点，真敲不动，但是现在有空了，虽然还有3门考试+2个实验，但课程基本都结束了，还是大大滴有时间的，所以续上练题计划！
一.罗马数字转整数 ★★☆☆☆
题目
13. 罗马数字转整数
思路1
1.将基础的罗马数字存在哈希表中，并创建一个数组num存放对应的数值
2.遍历字符串的每一个字符：遇到特殊情况特殊处理——加上对应数值，将两个字符看作一个，所以 i+2；反之，直接加上对应的数值即可。
代码
class Solution { public: int romanToInt(string s) { //罗马数字数组 string luoma="IVXLCDM"; int num[]={1,5,10,50,100,500,1000}; //创建哈希表保存 unordered_map<char,int> map; for(int i=0;i<7;i++){ char ch=luoma[i]; //将基础罗马数字放入哈希表 map.insert({ch,i}); } //遍历字符串 int len=s.size(); int res=0; int i=0; while(i<len){ //获取字符串各个字符 char ch=s[i]; if(ch=='I' && i<len-1){ if(s[i+1]=='V') { res+=4; i+=2; continue; } if(s[i+1]=='X') { res+=9; i+=2; continue; } } else if(ch=='X' && i<len-1){ if(s[i+1]=='L') { res+=40; i+=2; continue; } if(s[i+1]=='C') { res+=90; i+=2; continue; } } else if(ch=='C' && i<len-1){ if(s[i+1]=='D') { res+=400; i+=2; continue; } if(s[i+1]=='M') { res+=900; i+=2; continue; } } //存在哈希表对应索引 int index=map[ch]; //结果加上对应数字 res+=num[index]; i++; } return res; } };复杂度
时间复杂度：O(n)。将罗马数字用循环存入哈希表，循环次数为7；计算结果的循环次数最多为字符串长度，设为n，所以时间复杂度为O(1)+O(n)=O(n)
空间复杂度：O(1)。数组长度为7，哈希表长度为7，所以空间复杂度为O(1)+O(1)=O(1)
思路2
基于思路1的改进：
1.充分利用哈希表存储罗马数字和对应数值
2.对特殊情况的处理理解为：当 当前字符对应的数值 小于 后一个字符对应的数值 时，结果减去当前字符对应的数值即可，后一个字符对应的数值正常处理。
代码
class Solution { public: int romanToInt(string s) { //1.创建哈希表保存:罗马数字和对应数值 unordered_map<char,int> map={ {'I',1}, {'V',5}, {'X',10}, {'L',50}, {'C',100}, {'D',500}, {'M',1000} }; //遍历字符串 int len=s.size(); int res=0; for(int i=0;i<len;i++){ if(i<len-1 && map[s[i]]<map[s[i+1]]){ res-=map[s[i]]; }else{ res+=map[s[i]]; } } return res; } };复杂度
时间复杂度：O(n)。循环次数为n，n为字符串长度
空间复杂度：O(1)。变量＋哈希表（只存储7 个固定的键值对）占用的空间都是常数级，所以最后两者相加还是常数级
二.环形链表 ★★★☆☆
题目
141. 环形链表
给你一个链表的头节点head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回true。 否则，返回false。
这道题我试图用哈希表的方式求解，最后没有解除了，所以看了官方题解，发现哈希集合就能解决问题。
官方题解——思路1：哈希集合
首先，解释链节点的结构体ListNode。val表示节点的值，next是一个ListNode类型的指针，指向下一节点。
利用哈希集合无重复数据的特点，将链表节点依次放入哈希集合，若在哈希集合中找到了该结点说明所属链表是环形链表，返回true；反之，将该结点加入哈希表中。
注意：这道题的哈希集合类型设为ListNode*，因为函数的参数就是ListNode*类型的头结点，通过不断移动头结点，不断放入哈希表已经不断的判断，就能得出结论。
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { //用哈希集合保存以访问的节点 unordered_set<ListNode*> seen; while(head!=NULL){ if(seen.find(head)!=seen.end()){ //seen.count() return true; } seen.insert(head); head=head->next; } return false; } };官方题解——思路2：快慢指针
（个人感觉快慢指针跟双指针有一点相似——通过两个指针的区别/差异判断）
这里的快慢指针均设为ListNode类型，通过模拟“龟兔赛跑”，让快指针每次移动两步，慢指针每次移动一步，如果是环形链表，那么快指针最后移动会“追上”慢指针，实际是套圈，再次和慢指针相遇。
假定快慢指针的起始位置分别是：head->next，head。为什么不能同时从head出发——因为后面判断是否是环形链表的条件就是快慢指针是否相遇，即快慢指针是否相等，所以不能从同一位置出发。而此处的head->next，head，可以理解为快慢指针实际从head头结点的前一个“虚结点”一起出发，两者都移动了一次，只是快指针走了两步到head->next，慢指针走了一步到head。
1.判断head和head->next是否为空：根据快慢指针的初始值，知道我们首先要判断head和head->next是否为空，才能进行赋值，所以在一开始就进行判断，如果一方是，就直接返回false，也可以理解为：根据链表头结点判断链表长度是否为0/1，如果头结点为空，说明链表长度为0；如果头结点的下一节点为空，说明链表长度为1，不可能是环形链表。
2.在while循环内移动指针：因为fast走得更快，所以如果链表不是环形链表，那么fast或者fast->next可以为空，此时可以直接返回false；除此之外，移动slow和fast。循环直到slow==fast，说明slow被fast套圈了，即两者相遇了，说明链表是环形链表，返回true。
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { //链表为空 / 链表长度为1 if(head==NULL || head->next==NULL){ return false;//不是环形链表 } //设定快慢指针并初始化 ListNode* slow=head; ListNode* fast=head->next; while(slow!=fast){ //当快指针追上慢指针时，说明链表是环形链表 //如果快指针已经/即将为空，说明链表不是环形链表 if(fast==NULL || fast->next ==NULL){ return false; } //移动两个指针 slow=slow->next; fast=fast->next->next; } return true; } };复杂度
时间复杂度：O(n)。需要分析两种情况：无环和有环。无环则循环次数等于快指针移动次数，快指针最多移动n/2次，所以时间复杂度为O(n)；有环需要分为两个阶段——指针进入环之前和快指针在环内追上慢指针。
空间复杂度：O(1)。指针变量空间是常数级，与链表节点数n无关。
三.判断系统的大小端 ★★★★☆
题目
判断当前系统是大端还是小端
（我自己做的时候丝毫没有思路，也没有去问豆包，而且有一种只要我放弃一次，后面再有精力也不想做这道题的感觉，不行不行，这万万不行）下面给出老师的思路
思路
利用共同体共享同一片空间的特点解决这道题，下面是两种不同的做法：
1.创建一个共同体创建一个int类型数据a，并初始化为0x12345678，再创建一个char类型变量b，通过b的值就能判断系统是大端还是小端。如果系统是大端，高位数字存储在低地址，低位数字存储在高地址，所以b的值是0x12；反之如果系统是小端，b的值是0x78。
2.创建一个int类型数据a，并初始化为0x12345678，再创建一个char*类型变量p，使其指向a的地址，通过查看p所指地址的值就能判断结果。
代码
typedef union Data { int a; char b; }Data; int main() { Data data; data.a = 0x12345678; if (data.b == 0x78) { printf("小端模式\n"); } else { printf("大端模式\n"); } return 0; }int main() { int a = 0x12345678; char* p = (char*)&a; if (*p == 0x78) { printf("小端模式\n"); } else { printf("大端模式\n"); } return 0; }
