leetcode 409最长回文串 双百写法

题目描述

思路

思路1->运用全排列进行判断 结果超时

思路2:利用回文串特性，统计字符串中字符出现次数，将字符出现次数除以2 乘以2，此时统计了偶数次的字符，正好放两边，

剩下奇数怎么办呢，只有第一个奇数字符才加1.

例题:

a 出现4次 b出现5次，那么答案4/2*2 + 5/2*2，最后加上1等于9，aabbbbbaa 

代码

class Solution {
public:
    string temp;

/*
    void dfs(string &s,int &maxVal,int index,vector<bool> &vis)
    {
        if(temp.size()>=s.size())
        {
            return;
        }
        for(int i=0;i<s.size();i++)
        {
            if(vis[i]==0)
            {
                temp+=s[i];
                int cur=0;
                if(valid(temp))
                {
                    cur = temp.size();
                    //cout<<temp<<" ";
                    maxVal = max(maxVal,cur);
                }
                vis[i]=1;
                dfs(s,maxVal,i+1,vis);
                temp.pop_back();
                vis[i]=0;
            }
            
        }

    }
    int valid(string temp)
    {
        for(int i=0,j=temp.size()-1;i<=j;i++,j--)
        {
            if(temp[i]!=temp[j])
                return false;
        }
        return true;
    }
*/

/*

call
int method1(string s)
{
        int maxVal=0;
        vector<bool> vis(s.size(),0);
        dfs(s,maxVal,0,vis);
        return maxVal;
}
        

*/
    int longestPalindrome(string s) {
        //hash统计出现次数
        unsigned int hash[129];
        memset(hash,0,sizeof(hash));
        for(char str:s)
        {
            hash[str-'0']++;
        }
        int ret=0;
        for(int ha:hash)
        {
            if(ha!=0)
            {
                cout<<ha;
                //除以2乘以2，移位代替
                ret+= (ha>>1)<<1;
                //只进入一次，出现首个奇数时
                if((ret&1)==0&&(ha&1)==1)
                ret+=1;
            } 
        }
        return ret;
    }
};

重难点分析

此题中==号优先级高于移位，所以在用移位加快运算速度时，需要使用括号来代替

小数量的hash表直接用数组代替，未调用库函数map，unorderedmap

全排列需要用到visit去重。

组合需要用到dfs（i+1）进行去重