有趣的地方

有趣的地方

Leetcode-2810-故障键盘-c++

题目详见https://leetcode.cn/problems/faulty-keyboard/

题解

这道题的关键是如何合理地使用STL,毕竟是一道简单题。

  • 之前常用到的Vector容器是单向开口的连续内存空间

  • deque则是一种双向开口的连续线性空间,又称双端动态数组。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受

然而!他效率再差,也比我们自己实现一个字符串反转函数快并且简单。

这里再附上题解下面别人的一个题解,我觉得挺有意思

class Solution {
public:
    string finalString(string s) {
    	// 这里是我认为特别好的一个想法:
    	// 最终字符串的长度就等于原字符串的长度 减去 字母‘i’的个数。
        int n = s.size(), cnt = count(s.begin(), s.end(), 'i');
        string ret(n - cnt, ' ');	// 这里直接根据最后的长度开出string
        for(int i = 0, j = n - cnt - 1, p = n - 1, back = true; p >= 0; --p){
        // i是头(左)指针,j是尾(右)指针,p是从!!!右到左!!!遍历原string的指针
            if(s[p] == 'i') {back = !back; continue;}	// 是i跳过
            if(back) ret[j--] = s[p];	// 见下图
            else ret[i++] = s[p];	// 见下图
        }
        return ret;
    }
};
  • 浅画个图,从右到左:
  • 遇到第一个i之前(共遇到0个i,为偶数个),的不需要反转,因此从右到左遍历,从右到左输入,得到正序
  • 遇到第二个i之前(共遇到1个i,为奇数个),此时需要进行反转 ,因此从右到左遍历,从左到右输入,得到倒序
  • 遇到第二个i之后到遇到第三个i之前(共遇到2个i,为偶数个),此时不需要反转(蓝色部分,不是很蓝,见谅)
  • 简单理解为:偶数次反转相互抵消

在这里插入图片描述

官方题解比较简单

class Solution {
public:
    string finalString(string s) {
        deque<char> q;
        bool head = false;
        for (char ch: s) {
            if (ch != 'i') {
                if (head) {
                    q.push_front(ch);
                }
                else {
                    q.push_back(ch);
                }
            }
            else {
                head = !head;
            }
        }
        string ans = (head ? string{q.rbegin(), q.rend()} : string{q.begin(), q.end()});
        return ans;
    }
};

笔者也在新手学习期中,所写的内容主要与大家交流学习使用,如有发现任何问题敬请指正!

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图