剑指offer----字符串、链表

作者: 世界上的一道风 | 来源:发表于2019-08-10 22:32 被阅读0次

前言

c/c++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，他们实际上会指向相同的内存地址：

int main()
{
    char str1[] = "hello world";
        char str2[] = "helle world";
        char* str3 = "hello world";
        char* str4 = "hello world";
        
        if(str1 == str2)
            cout << "str1 and str2 are same.\n";
        else
            cout << "str1 and str2 are not same.\n";

        if(str3==str4)
            cout << "str3 and str4 are same.\n";
        else
            cout << "str3 and str4 are not same.\n";

        return 0;   
}


 ./main
str1 and str2 are not same.
str3 and str4 are same.

第一个不同是因为两个不同的数组地址；第二个相同是因为常量字符串在内存中只有一个拷贝，他们都指向同一地址。

替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解析：先计算增大串长后的长newStrLength，用指针2指向该位置，同时指针1指向未增长时串中字符的结尾'\0'，从后遍历复制指针1、2上的字符。

class Solution {
public:
    void replaceSpace(char *str,int length) {
        if(str==nullptr || length<=0)
            return;
        int strLength=0, space=0;
        //先求替换后的字符串大小
        while(str[strLength]!='\0')
        {
            
            if(str[strLength]==' ')
                ++space;
            ++strLength;
        }
        //strLength指向终止符处
        //增大后的串长
        int newStrLength = strLength+2*space;
        if (newStrLength > length)//length为该串总容量
            return;
        while(strLength>=0 && newStrLength>strLength)
        {
            if(str[strLength]==' ')
            {
                str[newStrLength--] = '0';
                str[newStrLength--] = '2';
                str[newStrLength--] = '%';
            }
            else
            {
                str[newStrLength--]=str[strLength]; 
            }
            --strLength;
        }
    }
};

19、正则表达式

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

解：当遇到*的时候可以当做前面的字符（一个字符）出现了0次，也就是忽略*直接前移2步，也可以当做出现n次，在原处待着不动，让str前移n步去比较；退出条件是看str是否为空且模式也为空就是匹配上，否则没有匹配上，递归的调用看各种情况下返回的是否有一个满足条件。

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(str==nullptr || pattern==nullptr)
            return false;
        return matchCore(str, pattern);
    }
private:
    bool matchCore(char* str, char* pattern)
    {
    //若同时结束对比为匹配
    if(*str=='\0' && *pattern=='\0')
        return true;
    
    if(*str!='\0' && *pattern=='\0')
        return false;
    
    if(*(pattern+1)=='*')//若下一个字符为需要匹配的字符
    {
        //当前以及匹配
        if(*pattern==*str || (*pattern =='.' && *str!='\0'))
        {    
            //move on the next state || stay on current state || 向前移动2步，忽略一个‘*’匹配；
            return matchCore(str+1, pattern+2) || matchCore(str+1,pattern) || matchCore(str, pattern+2);
        }
        else
            //向前移动2步，忽略一个‘*’匹配；
            return matchCore(str,pattern+2);
    }
    // 当前字符以及匹配，去往下面的字符；
    if (*str==*pattern || (*pattern=='.' && *str!='\0'))
        return matchCore(str+1, pattern+1);
    return false;
    }  
};

38、字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解析：第一个字符固定为i，剩下其他字符的全排列在后面；i的取值是整个字符串的取值，因此，每次交换头字符，还有后面字符串中的下一个字符；递归结束条件是该字符串已经找到；

class Solution {
public:
    vector<string> Permutation(string str)
    {
        vector<string> result;
        if(str.empty()) return result;
         
        Permutation(str,result,0);
         
        // 此时得到的result中排列并不是字典顺序，可以单独再排下序
        sort(result.begin(),result.end());
         
        return result;
    }
     
    void Permutation(string str,vector<string> &result,int begin)
    {
        if(begin == str.size()-1) // 递归结束条件：索引已经指向str最后一个元素时
        {
            if(find(result.begin(),result.end(),str) == result.end())
            {
                // 如果result中不存在str，才添加；避免aa和aa重复添加的情况
                result.push_back(str);
            }
        }
        else
        {
            // 第一次循环i与begin相等，相当于第一个位置自身交换，关键在于之后的循环，
            // 之后i != begin，则会交换两个不同位置上的字符，直到begin==str.size()-1，进行输出；
            for(int i=begin;i<str.size();++i)
            {
                swap(str[i],str[begin]);
                Permutation(str,result,begin+1);
                swap(str[i],str[begin]); // 复位，用以恢复之前字符串顺序，达到第一位依次跟其他位交换的目的
            }
        }
    }
     
    void swap(char &fir,char &sec)
    {
        char temp = fir;
        fir = sec;
        sec = temp;
    }
};

链表

前言

内存分配不是在创建链表时一次完成的，而是每次添加一个节点是分配内存；因此没有闲置的内存，链表的空间效率比数组高。

指针的指针：

// Example program
#include <iostream>
#include <string>
#include<vector>
using namespace std;

int main()
{
    int i=1;
    int *pi = &i;
    int **ppi = &pi;
    cout<<"*pi :" << *pi << endl;
    cout<<"&pi :" << &pi << endl;
    cout <<"*ppi :" << *ppi<<endl;
    return 0;   
}

*pi :1
&pi :0x70aa208f64e8
*ppi :0x70aa208f64e4

链表的尾部添加节点和删除值为某数的节点如下：

// Example program
#include <iostream>
#include <string>
#include<vector>
using namespace std;

struct ListNode
{
    int value;
    ListNode *pNext;
};
//pHead是二级指针，指向指针的指针
void AddToTail(ListNode** pHead,int value)
{
    ListNode* pNew = new ListNode();
    pNew->value = value;
    pNew->pNext = nullptr;
    
    //是否为根节点
    if((*pHead)==nullptr)
    {
        //取出头指针指向当前新节点
        *pHead = pNew;
    }
    else
    {
        ListNode *pNode=*pHead;
        //通过指针链接新节点在尾部
        while(pNode->pNext!=nullptr)
                    pNode = pNode->pNext;
        pNode->pNext =pNew;
    }
}

//删除某值元素
void RemoveNode(ListNode** pHead, int value)
{
    if(pHead==nullptr || *pHead==nullptr)
                return;
    //指向要删除的元素标记指针
    ListNode* pToBeDeleted = nullptr;
    
    
    //判断是否删除位置在头结点
    if((*pHead)->value == value)
    {
        //标记
        pToBeDeleted = *pHead;
        //新的头结点位置在下一个位置
        *pHead=(*pHead)->pNext;
    }
    else
    {
        //根节点的地址
        ListNode* pNode=*pHead;
        while(pNode->pNext != nullptr
        && pNode->pNext->value!=value)
            pNode=pNode->pNext;
        //找到该元素的位置,为pNode的下一个位置
        if(pNode->pNext!=nullptr && pNode->pNext->value==value)
        {
            //该元素位置下一个位置赋给pToBeDeleted
            pToBeDeleted = pNode->pNext;
            //删除元素前一个位置的pNext链接到删除元素的下一个位置;之后就可以安全的删除了
            pNode->pNext = pNode->pNext->pNext;
        }
    }
    //删除该标记指针
    if(pToBeDeleted!=nullptr)
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr; //避免出错，赋为空
    }

}
int main()
{
        ListNode *test;
        ListNode** PP = &test;
        AddToTail(PP, 20);
        cout << test->value << endl;
        AddToTail(PP, 30);
        cout << test->pNext->value << endl;
        RemoveNode(PP,20);
        cout << test->value << endl;
        return 0;   
}

20
30
30

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

class Solution {
public:
    //递归求解，或者用栈来求解。
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ans;
        stack<ListNode*> st;
        while(head!=nullptr)
        {
            st.push(head);
            head = head->next;
        }
        while(!st.empty())
        {
            ans.push_back(st.top()->val);
            st.pop();
        }
        return ans;
            
    }

删除链表中重复的元素

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

class Solution {
public:
    //需要三个指针前中后
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==nullptr) return nullptr;
        ListNode *pPreNode = nullptr; //前一个节点
        ListNode *pNode = pHead; //当前节点
        while(pNode!=nullptr)
        {
            ListNode * pNextNode = pNode->next;//重置为当前节点的下一节点
            bool needDelete=false;
            //下一节点和当前节点是否是重复的
            if(pNextNode!=nullptr && pNode->val==pNextNode->val)
                needDelete = true;
            
            if(!needDelete)//没有重复，往下走
            {
                pPreNode = pNode;
                pNode = pNode->next;
            }
            else //重复节点
            {
                //取出值，删除连续等于该值的节点
                int value = pNode->val;
                ListNode* pToBeDel = pNode;
                //连续删除
                while(pToBeDel != nullptr && pToBeDel->val == value)
                {
                    pNextNode = pToBeDel->next;
                    delete pToBeDel;
                    pToBeDel = nullptr;
                    pToBeDel = pNextNode;
                }
            //确定是否是头结点
            if(pPreNode == nullptr)
                pHead = pNextNode;
            else//删除之后重链接删除后的节点
                pPreNode->next = pNextNode;
            pNode=pNextNode;
            }
        }
        return pHead;
    }
};

输入一个链表，输出该链表中倒数第k个结点。

双指针开始走，第一个走到k-1步时，第二个开始从根节点走。判断链长是否有k，没有解返回。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(!pListHead || k==0) return nullptr;
        ListNode* preListNode=nullptr;
        ListNode* curListNode=pListHead;
        //第一个指针走了k-1步，加上本身是一个位移，总共k位移，第二个指针开始从头结点走1步
        for(unsigned i=1;i<k;++i)
        {
            if(curListNode->next!=nullptr)
            {
                curListNode=curListNode->next;
            }
            else //链表长度不足
            {
                return nullptr;
            }
        }
        //开始走
        preListNode = pListHead;
        //下一个节点指针非空
        while(curListNode->next!=nullptr)
        {
            curListNode=curListNode->next;
            preListNode=preListNode->next;
        }
        return preListNode;
    }
};

23.链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解：1. 确定链表是否有环；（设置一个走得快的指针是否能追上走得慢的指针；）
2. 环的大小是多少；
3. 快指针先走环的大小步数，慢指针再走，必然在环的入口处相遇。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //meetingnode返回该链表是否有环，有的情况下，返回快慢指针相遇的节点
        ListNode* ListMeetNode=MeetingNode(pHead);
        if(ListMeetNode==nullptr)
            return nullptr;
        int countLoop=1;
        ListNode* pNode = ListMeetNode;
        while(pNode->next!=ListMeetNode)
        {
            countLoop++;
            pNode=pNode->next;
        }
        pNode=pHead;
        ListNode *slowNode=pHead;
        //先走k-1步
        for(int i=0;i<countLoop;++i)
        {
            pNode=pNode->next;
        }
        while(pNode!=slowNode)
        {
            pNode=pNode->next;
            slowNode=slowNode->next;
        }
        return slowNode;
    }
private:
    ListNode* MeetingNode(ListNode* head)
    {
        if(head == nullptr)//空链表的情况
            return nullptr;
        ListNode* pslow=head->next;
        if(pslow==nullptr)//无环的情况
            return nullptr;
        ListNode* pfast=pslow->next;//快一步
        while(pfast!= nullptr && pslow!=nullptr)
        {
            if(pfast==pslow)//有环
                return pfast;
            pslow = pslow->next;
            pfast = pfast->next;
            if(pfast!=nullptr)//多走一步
                pfast=pfast->next;
        }
        return nullptr;
    }
};

35、复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解析：重复各个节点，然后关联新的重复节点的random，再然后重链接取出偶数链接的链表。

class Solution {
public:
    //复制原始链表的任一节点N并创建新节点N'，再把N'链接到N的后边
    void CloneNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        while(pNode!=NULL)
        {
            RandomListNode* pCloned=new RandomListNode(0);
            pCloned->label=pNode->label;
            pCloned->next=pNode->next;
            pCloned->random=NULL;
              
            pNode->next=pCloned;
              
            pNode=pCloned->next;
        }
    }
    //如果原始链表上的节点N的random指向S，则对应的复制节点N'的random指向S的下一个节点S'
    void ConnectRandomNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        while(pNode!=NULL)
        {
            RandomListNode* pCloned=pNode->next;
            if(pNode->random!=NULL)
                pCloned->random=pNode->random->next;
            pNode=pCloned->next;
        }
    }
    //把得到的链表拆成两个链表，奇数位置上的结点组成原始链表，偶数位置上的结点组成复制出来的链表
    RandomListNode* ReConnectNodes(RandomListNode* pHead)
    {
        RandomListNode* pNode=pHead;
        RandomListNode* pClonedHead=NULL;
        RandomListNode* pClonedNode=NULL;
          
        //初始化
        if(pNode!=NULL)
        {
            pClonedHead=pClonedNode=pNode->next;
            pNode->next=pClonedNode->next;
            pNode=pNode->next;
              
        }
        //循环
        while(pNode!=NULL)
        {
            pClonedNode->next=pNode->next;
            pClonedNode=pClonedNode->next;
            pNode->next=pClonedNode->next;
            pNode=pNode->next;
        }
          
        return pClonedHead;
          
    }
    //三步合一
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneNodes(pHead);
        ConnectRandomNodes(pHead);
        return ReConnectNodes(pHead);
    }
};

52、两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。

解：方法1：对链表1中每一个节点，都遍历一遍链表2，复杂度为O(mn);m\n分别为两个链表的长度；
方法2：若中间某一个节点相同，之后剩下的节点都是一样的地址存在，因此结尾处都一样，
设置栈结构，从尾部排除，遇到不相等的元素时，之前的那个元素便是第一个相同的元素点，空间换时间
的O(m+N)空间换取时间为O(m+n);
方法3：先遍历两个链表得到最长链表的长度s1与短链表的长度s2，在最长链表上先移动s1-s2,再同时移动
链表1,2，且不断比较直到相等；

方法3的原因是：链表 $A$ 长度是 $LA$ ，链表 $B$ 长度是 $LB$ ，他们的公共部分长度是 $LC$ ，那么不妨设 $LA$ 长度更长，那么有： $LA>LB \ge LC$ ,那么 $A$ 与 $B$ 的公共部分至少在 $A$ 后面的长度还有 $B$ 这么长的时候才有可能。

public:
    /*
    */
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1 || !pHead2) return nullptr;
        ListNode *pDupHead1 = pHead1;
        ListNode *pDupHead2 = pHead2;
        int  count1=0, count2=0;
        while(pHead1)
        {
            count1++;
            pHead1=pHead1->next;
        }
        while(pHead2)
        {
            count2++;
            pHead2=pHead2->next;
        }
        if(count1>count2) //链表1最长
        {
            int lCount = count1 - count2;
            while(lCount--)
                pDupHead1=pDupHead1->next;
        }
        else
        {
            int lCount = count2 - count1;
            while(lCount--)
               pDupHead2 = pDupHead2->next; 
        }
        while(pDupHead1 && pDupHead2 && (pDupHead1!=pDupHead2))
        {
            pDupHead1 = pDupHead1->next;
            pDupHead2 = pDupHead2->next;
        }
        ListNode * pFirstCommonNode = pDupHead1;
        return pFirstCommonNode;
    }
};

50、第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

:方法1：暴力求解,对当前每一个字符，搜索后面的真个字符串，复杂度是O(n^2);
方法2：哈希表：自建一个简单哈希表；
可以把哈希表设为256，因为char是8bit的类型，总共只有256个字符，
可以设置哈希表为负，第一次插入后为正，再次插入同样的字符，设为负，下次只有找出数组非负的位置便是对应的第一次出现的字符

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.empty()) return -1;
        vector<int> arr(26*2,0);
        for(auto i:str)
        {
            if('a'<=i && i<='z')
                arr[int(i-'a')]+=1;
            else
                arr[int(i-'A')+26]+=1;
        }
        
        
        for(int j=0; j<str.size(); ++j)
        {
            int numj;
            if('a'<=str[j] && str[j]<= 'z')
                numj=int( str[j]-'a');
            else
                numj=int( str[j]-'A'+26);
            if(arr[numj] == 1)
                return j;
        }
    }

};

58、反转单词顺序字符串

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

先反转整个串，再反转每一个单词；

class Solution {
public:
    string ReverseSentence(string str) {
        if(str.empty()) return str;
        int begin=0,end=0;
        reverse(str.begin(),str.end());
        int size = str.size();
        while(begin<size)
        {
            //起点为空，重置游标
            while(begin<size && str[begin]==' ') begin++;
            end=begin;
            //终点不为空，一直往前走到头
            while(end<size && str[end]!=' ') end++;
            reverse(str.begin()+begin, str.begin()+end);
            //反转之后，起点的顺序是重点的顺序
            begin = end;
        }
        return str;
    }
};

2。左旋转字符串

字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

先翻转这个串的前后两部分，然后再全部一次性翻转

class Solution {
public:

    string LeftRotateString(string str, int n) {
        if(str.empty() || n<=0) return str;
        reverse(str.begin(),str.begin()+n);
        reverse(str.begin()+n,str.end());
        reverse(str.begin(),str.end());
        return str;
    }
};

67、将一个字符串转换成一个整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

public:
    int StrToInt(string str) {
        long long int num = 0;
        if(str.empty()) return num;
        int minus;
        if(str[0] == '+')
            minus = 1;
        if(str[0] == '-')
            minus = -1;
        int i;
        if(str[0]!='+' && str[0]!='-') i=0;
        else i=1;
        for(;i<str.size();++i)
        {           
            if(str[i]>='0' && str[i]<='9')
            {
                num = num * 10 + minus * (str[i]-'0');
            }
            else
            {
                num = 0;
                break;
            }
        }
        return (int)num; //类型转换
    }
};

50、字符流中第一个出现的字符

方法1：用常规方法来解：

class Solution
{
public:
  //Insert one char from stringstream
    string str;
    //全部初始化为0
    int hash[256]= {0};
    void Insert(char ch)
    {
        str+=ch;
        hash[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        int size = str.size();
        for(int i=0; i<size; ++i)
        {
            if(hash[str[i]]==1)
                return str[i];
        }
        return '#';
    }
};

方法2：用stl来解：

class Solution
{
public:
  //Insert one char from stringstream
    string str;
    map<char,int> m;    //用map来记录字符出现的次数
    void Insert(char ch)
    {
        str += ch;
        m[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        for(auto it : str)
        {
            if(m[it] == 1)
            {
                return it;
            }
        }
        return '#';
    }

};

、请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

class Solution {
public:
    bool isNumeric(char* str) {
        // 标记符号、小数点、e是否出现过
        bool sign = false, decimal = false, hasE = false;
        for (int i = 0; i < strlen(str); i++) {
            if (str[i] == 'e' || str[i] == 'E') {
                if (i == strlen(str)-1) return false; // e后面一定要接数字
                if (hasE) return false;  // 不能同时存在两个e
                hasE = true;
            } else if (str[i] == '+' || str[i] == '-') {
                // 第二次出现+-符号，则必须紧接在e之后
                if (sign && str[i-1] != 'e' && str[i-1] != 'E') return false;
                // 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
                if (!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false;
                sign = true;
            } else if (str[i] == '.') {
              // e后面不能接小数点，小数点不能出现两次
                if (hasE || decimal) return false;
                decimal = true;
            } else if (str[i] < '0' || str[i] > '9') // 不合法字符
                return false;
        }
        return true;
    }
};

剑指offer----字符串、链表

前言

链表

前言

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读