409.最长回文串

LeetCode LeetCode 哈希表 贪心 字符串
发布时间 :
字数:1.6k 阅读 : 评论:
  1. 409.最长回文串f
    1. 409.1 题目
    2. 409.2 题解
      1. 字典计数
      2. 数组计数
    3. 409.3 代码
    4. 409.4 运行结果

409.最长回文串f

409.1 题目

给定一个包含大写字母和小写字母的字符串 s，返回通过这些字母构造成的最长的回文串的长度。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

示例 1:

输入：s = "abccccdd"
输出：7
解释：我们可以构造的最长的回文串是 “dccaccd”，它的长度是 7。

示例 2:

输入：s = "a"
输出：1
解释：可以构造的最长回文串是 “a”，它的长度是 1。

提示:

  • 1 <= s.length <= 2000
  • s 只由小写和/或大写英文字母组成

409.2 题解

字典计数

// 方法一：字典计数
// 创建一个字典统计每个字符出现的次数
// 遍历字典，计算回文串的长度
// 如果发现字符出现的次数是奇数说明 最长的回文串也可以是奇数
static int LongestPalindrome1(string s)
{
    // 创建一个字典用于统计每个字符出现的次数
    Dictionary<char, int> count = new Dictionary<char, int>();

    // 遍历字符串，统计每个字符出现的次数
    foreach (char c in s)
    {
        // 如果字符已经在字典中，则将其出现次数加一；否则，将其出现次数设为1
        if (count.ContainsKey(c))
            count[c]++;
        else
            count[c] = 1;
    }

    // 初始化回文串的长度为0，判断是否有奇数次的字符
    int palindromeLength = 0;
    bool hasOdd = false;

    // 遍历字典，计算回文串的长度
    foreach (var pair in count)
    {
        // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
        palindromeLength += pair.Value / 2 * 2;
        // 如果字符出现次数为奇数，将标记置为true
        if (pair.Value % 2 != 0)
            hasOdd = true;
    }

    // 如果存在出现奇数次的字符，回文串长度加一
    if (hasOdd)
        palindromeLength++;

    // 返回最长回文串的长度
    return palindromeLength;
}

数组计数

// 方法二：数组计数
// 和字典同理 不过用ASCII码统计
static int LongestPalindrome2(string s)
{
    // 用于存储字符出现次数的数组，ASCII码最多128个字符
    int[] count = new int[128];

    // 统计每个字符出现的次数
    foreach (char c in s)
    {
        // 字符对应的ASCII码作为数组下标，出现次数加一
        count[c]++;
    }

    // 初始化回文串的长度为0，判断是否有奇数次的字符
    int palindromeLength = 0;
    bool hasOdd = false;

    // 遍历统计数组，计算回文串的长度
    foreach (int cnt in count)
    {
        // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
        palindromeLength += cnt / 2 * 2;
        // 如果字符出现次数为奇数，将标记置为true
        if (cnt % 2 != 0)
            hasOdd = true;
    }

    // 如果存在出现奇数次的字符，回文串长度加一
    if (hasOdd)
        palindromeLength++;

    // 返回最长回文串的长度
    return palindromeLength;
}

409.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

        // 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

        // 示例 1:
        // 输入: s = "abccccdd"
        // 输出: 7
        // 解释: 我们可以构造的最长的回文串是 "dccaccd"，它的长度是 7。

        // 示例 2:
        // 输入: s = "a"
        // 输出: 1

        // 示例 3：
        // 输入: s = "aaaaaccc"
        // 输出: 7

        // 提示:
        // 1 <= s.length <= 2000
        // s 只由小写 和/或 大写英文字母组成

        #endregion

        #region 测试

        // 示例 1 方法 1
        string str1 = "abccccdd";
        int result1 = LongestPalindrome1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");

        // 示例 1 方法 2
        int result1_2 = LongestPalindrome2(str1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2 方法 1
        string str2 = "a";
        int result2 = LongestPalindrome1(str2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");

        // 示例 2 方法 2
        int result2_2 = LongestPalindrome2(str2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3 方法 1
        string str3 = "aaaaaccc";
        int result3 = LongestPalindrome1(str3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");

        // 示例 3 方法 2
        int result3_2 = LongestPalindrome2(str3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：字典计数
    // 创建一个字典统计每个字符出现的次数
    // 遍历字典，计算回文串的长度
    // 如果发现字符出现的次数是奇数说明 最长的回文串也可以是奇数
    static int LongestPalindrome1(string s)
    {
        // 创建一个字典用于统计每个字符出现的次数
        Dictionary<char, int> count = new Dictionary<char, int>();

        // 遍历字符串，统计每个字符出现的次数
        foreach (char c in s)
        {
            // 如果字符已经在字典中，则将其出现次数加一；否则，将其出现次数设为1
            if (count.ContainsKey(c))
                count[c]++;
            else
                count[c] = 1;
        }

        // 初始化回文串的长度为0，判断是否有奇数次的字符
        int palindromeLength = 0;
        bool hasOdd = false;

        // 遍历字典，计算回文串的长度
        foreach (var pair in count)
        {
            // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
            palindromeLength += pair.Value / 2 * 2;
            // 如果字符出现次数为奇数，将标记置为true
            if (pair.Value % 2 != 0)
                hasOdd = true;
        }

        // 如果存在出现奇数次的字符，回文串长度加一
        if (hasOdd)
            palindromeLength++;

        // 返回最长回文串的长度
        return palindromeLength;
    }

    // 方法二：数组计数
    // 和字典同理 不过用ASCII码统计
    static int LongestPalindrome2(string s)
    {
        // 用于存储字符出现次数的数组，ASCII码最多128个字符
        int[] count = new int[128];

        // 统计每个字符出现的次数
        foreach (char c in s)
        {
            // 字符对应的ASCII码作为数组下标，出现次数加一
            count[c]++;
        }

        // 初始化回文串的长度为0，判断是否有奇数次的字符
        int palindromeLength = 0;
        bool hasOdd = false;

        // 遍历统计数组，计算回文串的长度
        foreach (int cnt in count)
        {
            // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
            palindromeLength += cnt / 2 * 2;
            // 如果字符出现次数为奇数，将标记置为true
            if (cnt % 2 != 0)
                hasOdd = true;
        }

        // 如果存在出现奇数次的字符，回文串长度加一
        if (hasOdd)
            palindromeLength++;

        // 返回最长回文串的长度
        return palindromeLength;
    }

    #endregion
}

409.4 运行结果

示例1 方法1 输出：7
示例1 方法2 输出：7
示例2 方法1 输出：1
示例2 方法2 输出：1
示例3 方法1 输出：7
示例3 方法2 输出：7
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏