颜色分类

题目

https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvg25c/

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

实现

思路：遍历每个字符作为回文中心，向左右扩展寻找最长回文。 注意：奇偶情况

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length < 2) return s;
    
    let start = 0, maxLength = 1;
    
    // 中心扩展函数
    const expandAroundCenter = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            const currentLength = right - left + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                start = left;
            }
            left--;
            right++;
        }
    };
    
    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);    // 奇数长度回文（中心为单个字符）
        expandAroundCenter(i, i + 1); // 偶数长度回文（中心为两个字符）
    }
    
    return s.slice(start, start + maxLength);
};
 
// 辅助函数：判断是否为回文（修正版）
var isPalindrome = function(s) {
    return s === s.split('').reverse().join('');
};