[数据结构与算法]【算法】剑指offer-字符串替换&&打印链表

字符串替换

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

做法1

使用容器:

class Solution {
public:
	void replaceSpace(char *str,int length) {
        string tmp ;
        //遍历字符串,如果不是空格:+=该字符
        //如果是空格+="%20"
        for(int i = 0;i<length;i++)
        {
            if(str[i] == ' ')
            {
                tmp+="%20";
            }
            else
            {
                tmp+=str[i];    
            }
        }
        //最后把tmp的内容拷贝回去
        //要先把tmp转化为c形式的字符串
        //c_str()的返回类型为const char* 即不可以修改字符串的内容
        const char*  s = tmp.c_str();
        strcpy(str,s);
	}
};

从前往后通过开辟空间来进行解决.也就是使用空间来换取时间.

做法2

不使用容器

• 因替换之后的内容比原内容长,所以,一定涉及到字符串中字符的移动问题,移动方向一定是向后移动
• 因为是 ’ ’ -> “%20”,是1换3,所以可以先统计原字符串中空格的个数,然后可以计算出新字符串的长度
• 新长度 = 旧长度 + 空格个数*2
• **遍历原字符串,如果是空格,连续放入“%20”,**其他字符平移即可
  • 定义两个指针,一个指向原来的尾,记为oldEnd,一个指向替换之后最后的尾,记为newEnd,
  • oldEnd最初指向\0位置,这样方便把原字符串的\0也拷贝上
  • oldEnd往前遍历原字符串,如果碰到了空格,newEnd就往前放"%20",否则就往前放当前字符

class Solution {
public:
	void replaceSpace(char *str,int length) {
        //1.统计空格个数
        char* tmp = str;//这里要使用临时变量,不能直接改变str
        int count = 0;
        while(*tmp)
        {
            if(*tmp == ' ')
            {
                count++;
            }
            tmp++;
        }
        int oldEnd = length;//原字符串的\0位置
        int newEnd = oldEnd + 2*count;//替换后的字符串的最后一个位置(\0位置)
        //从后往前遍历原字符串
        //[0,length] \0也要拷贝
        while(oldEnd>=0)
        {
            if(str[oldEnd] == ' ')
            {
                //newEnd往前拷 ”%20“
                str[newEnd--] = '0';
                str[newEnd--] = '2';
                str[newEnd--] = '%';
            }
            else
            {
                //正常拷贝当前字符
                str[newEnd--] = str[oldEnd];
            }
            //往前走
            oldEnd--;
        }
	}
};

打印链表

输入一个链表,按链表从尾到头的顺序返回一个ArrayList.

做法1

方法1:保存到容器中,然后逆序容器

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        //把链表的值都放到容器中
        while(head)
        {
            v.push_back(head->val);
            head = head->next;
        }
        reverse(v.begin(),v.end());//逆转容器
        return v;
    }
};

方法2

方法2:使用栈

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int> st;
        vector<int> v;
        //把链表的内容放到栈中
        //这样从栈顶->栈底 就是链表的逆序
        while(head)
        {
            st.push(head->val);
            head = head->next;
        }
        //把栈中的数据弹入到容器中
        while(!st.empty())
        {
            v.push_back(st.top());//把栈顶数据加入到容器中
            st.pop();//弹出栈顶数据
        }
        return v;
    }
};

方法3

方法3:递归

因为要从尾到头返回,所以要返回第一个节点的值,其后面的节点应该都已经被放到容器中了,当递归开始返回的时候,说明已经把后面的内容放进去了

class Solution {
public:
    void printListFromTailToHeadCore(ListNode* head,vector<int>& v)
    {
        //到了链表的尾部,此时递归开始返回
        if(head == nullptr)
        {
            return ;
        }
        printListFromTailToHeadCore(head->next,v);
        //当递归开始返回的时候,后面的数据都放进去了,往容器中插入当前数据
        v.push_back(head->val);
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        printListFromTailToHeadCore(head,v);
        return v;
    }
};