算法思路:折叠字符串 (c++)6ms!!!!!!


  • 1
    H

    email:ruanban@ztgame.com
    QQ:294050792
    我的分析:
    字符串: "a.b.c.d.e" ,"."代表虚折点,"字母"是实折点
    将字符串从中间开始,按照折点做"折叠",找到第一个最大"对称"的地方
    1.长为len的字符串,有 m = std::max(1,(len - 2) * 2 + 1) 个折点,并且一定是奇数
    2.在第n个折点最前面的那个"实折点"的索引是 :p = n / 2 ,n点对折,最大可能的长度是: n + (n >= mid ? 1 : -1), n % 2 == 0 为true,表示是在实折点。false表示在虚折点.
    3.从中间开始对折,因为这样可能先找到最长的符合条件的子串,可以提前停止查找
    4.可以抽象成一个模板函数,不一定是找字符串

    string longestPalindrome(string s) 
    {
    	int len = s.length(); int pts = std::max(1, ((int)len - 2) * 2 + 1);
    	int mid = pts / 2 + 1; int max_begin = 0, max_len = 0;
    	for (int i = 0; i < pts; ++i) {
    		//0,1,2,3,4,5,6
    		//0,-1,1,-2,2,-3,3
    		//从中间到两边,
    		int pt = mid + (i % 2 ? -(int)std::ceil(i / 2.0) : (int)std::ceil(i / 2.0));
    		int index = pt / 2; int n = pt + (pt <= mid ? 1 : -1); int b = pt % 2 == 0 ? 1 : 0;
    		if (n <= max_len) break; //后面找到的不可能比现在的长了
    
    		int begin = 0, end = 0, m = n / 2;
    		for (int j = 0; j < m; ++j) {
    			int p_1 = index - j - b, p_2 = index + j + 1;
    			if (p_1 < 0 || p_2 >= len || s[p_1] != s[p_2]) break;
    			begin = p_1; end = p_2;
    		}
    		int cur_len = end - begin + 1;
    		if (cur_len > max_len) {
    			max_begin = begin; max_len = cur_len;
    		}
    	}
    	return s.substr(max_begin, max_len);
    }
    
    模板函数如下:
    

    class Solution2 {
    public:

    	template<typename T>
    	T longestPalindrome(const T& s) {
    		int len = s.end() - s.begin(); int pts = std::max(1, ((int)len - 2) * 2 + 1);
    		int mid = pts / 2 + 1; int max_begin = 0, max_len = 0;
    		for (int i = 0; i < pts; ++i) {
    			int pt = mid + (i % 2 ? -(int)std::ceil(i / 2.0) : (int)std::ceil(i / 2.0));
    			int index = pt / 2; int n = pt + (pt <= mid ? 1 : -1); int b = pt % 2 == 0 ? 1 : 0;
    			if (n <= max_len) break; //后面找到的不可能比现在的长了
    
    			int begin = 0, end = 0, m = n / 2;
    			for (int j = 0; j < m; ++j) {
    				int p_1 = index - j - b, p_2 = index + j + 1;
    				if (p_1 < 0 || p_2 >= len || *(s.begin() + p_1) != *(s.begin() + p_2)) break;
    				begin = p_1; end = p_2;
    			}
    			int cur_len = end - begin + 1;
    			if (cur_len > max_len) {
    				max_begin = begin; max_len = cur_len;
    			}
    		}
    		auto it_begin = s.begin() + max_begin;
    		return std::move(T(it_begin, it_begin + max_len));
    	}
    

    };

    测试函数:

    template<typename Container,typename Element = Container::value_type>
    void printLongestPalindrome(initializer_list<Element> list) {
    	auto ret = Solution2().longestPalindrome<Container>(list);
    	std::copy(ret.begin(), ret.end(), ostream_iterator<Element>(cout));
    	cout << endl;
    }
    
    template<typename Container>
    void printLongestPalindrome(Container list) {
    	typedef typename Container::value_type Element;
    	auto ret = Solution2().longestPalindrome<Container>(list);
    	std::copy(ret.begin(), ret.end(), ostream_iterator<Element>(cout));
    	cout << endl;
    }
    
    int main()
    {
        printLongestPalindrome(vector<int>{ 1, 2, 3, 4, 4, 3, 2, 1 });
        printLongestPalindrome<string>("12344321");
        system("pause");
        return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.