每日一题

336.回文对

题目比较简单,上来可以先判断两个拼接好的字符串是否符合,然后遍历判断。

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int len=words.size();
        vector<vector<int>> all;
        for(int i=0;i<len;i++)
        {
            for(int j=0;j<len;j++)
            {
                if(i!=j&&Judge(words[i],words[j]))
                {
                    vector<int> temp;
                    temp.push_back(i);
                    temp.push_back(j);
                    all.push_back(temp);
                }
            }
            
        }
        return all;


    }
    bool Judge(string& w1,string& w2)
    {
        string str = w1+w2;
        int len = str.size();
        for(int i=0;i<len;i++)
        {
            if(str[i]!=str[len-1-i])
                return false;
        }
        return true;
    }
};

提交结果,有一半能够通过,其他的超出了时间限制。看到题解说不能直接用str = w1+w2;,移动指针会快一些。

bool Judge(string& w1,string& w2)
{
    int len1 = w1.size();
    int len2 = w2.size();
    int len = len1 +len2;
    int i;
    
    for(i=0;i<len/2;i++)
    {
        if(len1>len2)
        {
            if(i<len2)
            {
                if(w1[i]!=w2[len2-1-i])
                return false;
            }
            else
            {
                if(w1[i]!=w1[len-1-i])
                return false;
            }
        }
        else
        {
            if(i<len1)
            {
                if(w1[i]!=w2[len2-1-i])
                return false;
            }
            else
            {
                if(w2[i-len1]!=w2[len2-1-i])
                return false;
            }
        }
            
    }
    return true;
}

执行结果:通过
执行用时:1528 ms, 在所有 C++ 提交中击败了7.14%的用户。
内存消耗:21.6 MB, 在所有 C++ 提交中击败了100.00%的用户。

另一个方法使用 manacher算法,竞赛难度就算了。只能做人下人了,哈哈。

后面评论实在太逗了。

100. 相同的树

很简单的一道题,没什么好多的递归调用判断就行

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p!=nullptr&& q!=nullptr)
        {
            return p->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);             
        }
        else if(p==nullptr && q== nullptr)
            return true;
        else 
            return false; 
    }
};

5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

  • 暴力搜索,失败,耗费时间太长。
  • 动态规划,通过。

使用动态规划时首先要找到题目的状态转移方程,以字符串的长度进行增长。

方程: P(i,j) = P(i+1,j-1) && s[i]==s[j] (s是字符串)

class Solution {
public:
    bool Is(string s,int st,int len)
    {
        for(int i=0;i<len/2;i++)
        {
            if(s[st+i]!=s[st+len-i-1])
                return false;
        }
        return true;
    }
    string longestPalindrome(string s) {
        int len = s.length();
        int max=-1;
        string res;
        vector<vector<bool>> dp(len,vector<bool>(len));
        for(int l=0;l<len;l++)
        {
            for(int i=0;i+l<len;i++)
            {
                if(l==0)
                {
                    dp[i][i+l]=true;
                }
                else if(l==1)
                {
                    dp[i][i+l]= s[i]==s[i+l];
                }
                else
                {
                    dp[i][i+l] = dp[i+1][i+l-1] && s[i]==s[i+l];
                }
                if(dp[i][i+l] &&l>max)
                {
                    max=l;
                    res=s.substr(i,max+1);
                }
            }
        }
        return res;         
    }
};

226. 翻转二叉树

easy 递归交换左右节点就行。