Java教程

算法珠玑——双指针(3)

本文主要是介绍算法珠玑——双指针(3),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法珠玑——双指针(3)

用例太少了!我觉得这个代码比官方快多了,但是估计也被运气影响了。

class Solution {
public:
    string reverseWords(string s) {
        /*
            基本情况:left(1) = 0;
                    right(1) = k_1 - 1;
            声明在外,提高性能
        */
        int right;
        int len = s.size()+1;

        /*
            终止情况: k < s.size() 不成立
            归纳步骤: 若 s[k] == ' ' || !s[k]
                    left = k(n-1) + 1, right = k(n) - 1
                    然后使用这两个变量进行反转的第二个归纳应用
        */
        // 为了内存,left定义到这里了
        for (int k = 0, left = 0; k < len; k++)
        {
            // 这是个短路判断,只有最后一个单词会进入!s[k]情况
            if (s[k] == ' ' || !s[k])
            {
                /*
                    基本情况: left = k(n-1) + 1, right = k(n)-1
                    终止情况: left < right 不成立
                    归纳步骤: 交换s[left] 和 s[right]
                */
                for (right = k - 1; left < right; left++, right--)
                    swap(s[left], s[right]);
                left = k + 1;
            }
        }
        
        return s;
    }
};

这题在速度上可以将!s[k]部分单独提出来,不过这样的话内存就会加一点。

这篇关于算法珠玑——双指针(3)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!