DAY42：统计前后缀下标Ⅰ+反转链表

今天第一题不是链表的题，本来以为是哈希表的题，但是想到的思路不是哈希表。第二题是原来做过的反转链表，但这次是在力扣做，上次是自己测试，这次是官方的测试，代码也稍有不同。

题目一：统计前后缀下标Ⅰ★★☆☆☆

3042. 统计前后缀下标对 I

给你一个下标从0开始的字符串数组words。

定义一个布尔函数isPrefixAndSuffix，它接受两个字符串参数str1和str2：

• 当str1同时是str2的前缀（prefix）和后缀（suffix）时，isPrefixAndSuffix(str1, str2)返回true，否则返回false。

例如，isPrefixAndSuffix("aba", "ababa")返回true，因为"aba"既是"ababa"的前缀，也是"ababa"的后缀，但是isPrefixAndSuffix("abc", "abcd")返回false。

以整数形式，返回满足i < j且isPrefixAndSuffix(words[i], words[j])为true的下标对(i, j)的数量。

我的思路

在函数countPrefixSuffixPairs中遍历words数组，对于每一个符号条件的words[i]和words[j]，判断word[i]是否是word[j]的前缀和后缀，如果是count++，遍历结束后，返回count即可。

编写isPrefixAndSuffix(const string& str1,const string& str2)函数，分别判断str1是不是str2的前缀和后缀。前缀：str2的前几个字符需要等于str1；后缀：str2的后几个字符需要等于str1。

注意：在函数isPrefixAndSuffix判断前，需要先做简单的判断：str1和str2是否为空；str1的长度是否小于str2的长度，这两步简单的判断都是特殊情况：一个字符串为空 或 str1长度>str2的长度，str1都不可能str2的前缀和后缀，所以直接返回false

代码

class Solution { public: //判断str1是不是str2的前缀和后缀 //1.注意形参类型 bool isPrefixAndSuffix(const string& str1,const string& str2){ //2.判空 if(str1.size()==0 || str2.size()==0){ return false; } //3.str1更长不可能是str2的前缀和后缀 if(str1.size()>str2.size()){ return false; } //从前遍历str2 //while(str1[i] != '\0'){ for(int i=0,j=0;i<str1.size();i++,j++){ //有个字符不相等→不是前缀→返回false if(str1[i]!=str2[j]){ return false; } } //从后遍历str2 //4.后缀不用将str1倒过来 //while(str1[i] != '\0'){ for(int i=0,j=str2.size()-str1.size();i<str1.size();i++,j++){ //有个字符不相等→不是后缀→返回false if(str1[i]!=str2[j]){ return false; } } return true; } int countPrefixSuffixPairs(vector<string>& words) { int count=0; //数组中元素个数 int n=words.size(); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ bool flag=isPrefixAndSuffix(words[i],words[j]); if(flag){ count++; } } } return count; } };

遇到的错误

1.实参类型和形参类型不匹配：word是string类型的，但是我的形参类型设置为了char*

2.特殊情况没有处理：str1或str2为空、str1长度>str2长度

3.后缀理解错误：理解成了后缀是str1逆置后的，所以判断后缀时的str2的下标从str2,size()-1开始，就造成了错误

4.C++ 的string 不用\0判断结束：用size()更安全

修正

1.形参类型改为string

2.处理特殊情况

3.后缀时的str2的下标从str2,size()-str1.size()开始

复杂度

n为字符串个数，m为最长字符串长度

时间复杂度：O(n²)×O(L)=O(n²×L)。

循环结构的时间复杂度为：O(n²)，对于每一个word[i]，都要遍历 i 之后的每一个字符串，所以时间复杂度为：O(n+(n-1)+(n-2)+(n-3)+...+2+1)=O(n*(n+1)/2)=O(n²)；

函数isPrefixAndSuffix的时间复杂度由str1的长度决定：O(L1)（L1 是word[ i ] 的长度），最坏情况下，所有字符串的平均长度为 L（比如所有字符串长度都接近 L），因此单次调用的复杂度为 O(L)。

所以总的时间复杂度为O(n²)×O(L)=O(n²×L)。

空间复杂度：O(1)。无额外的动态空间，调用函数也只有一层。

题目二：反转链表

206. 反转链表 给你单链表的头节点head，请你反转链表，并返回反转后的链表。

这里就不赘述思路了，可以去练题100天——DAY37：五子棋项目-CSDN博客看详细的思路。

方法一：“头插”法

class Solution { public: ListNode* reverseList(ListNode* head) { //使用头插法 //1.记录头结点 //2.用另两个结点保存头结点的后面两个结点 //3.将链表置空 //4.将结点依次使用头插法加入链表 //判断链表是否为空/只有一个结点 if(head==nullptr||head->next==nullptr){ return head; } ListNode* prehead=new ListNode(0,head); ListNode* p=head->next; ListNode* q=p->next; head->next=nullptr; while(p!=nullptr){ p->next=prehead->next; prehead->next=p; p=q; if(q!=nullptr){ q=q->next; } } ListNode* res=prehead->next; delete prehead; return res; } };

方法二：三指针法

class Solution { public: ListNode* reverseList(ListNode* head) { //三指针法 //判断链表是否为空/只有一个结点 if(head==nullptr||head->next==nullptr){ return head; } ListNode* p=head; ListNode* q=p->next; ListNode* r=q->next; //头结点指向空 p->next=nullptr; while(q!=nullptr){ q->next=p; p=q; q=r; if(r!=nullptr){ r=r->next; } } return p; } };