算法小计B3

---

每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

leetcode-5 Longest Palindromic Substring

best solution

class Solution
{
  public:
    string longestPalindrome(string s)
    {
        if (s.size() < 2)
            return s;
        int len = s.size();
        int middle = 0;
        int maxl = 1;
        int left,right;
        string maxs = s.substr(0, 1);

        while (middle<len&&len-middle>=maxl/2)
        {
            left = right = middle;

            while(right<len-1&& s[right]==s[right+1]) ++right;
            middle = right+1;
            while(right<len-1&&left>0&&s[right+1]==s[left-1]){
                ++right;
                --left;
            }

            if(maxl<right-left+1) {
                maxl = right-left+1;
                maxs = s.substr(left,maxl);
            }
        }
        return maxs;
    }
};

first commit

class Solution
{
  public:
    string longestPalindrome(string s)
    {
        int len = s.size();
        int b = 0, e = len - 1;
        int maxl = 1;
        string maxs = s.substr(0, 1);

        while (len - b > maxl)
        {

            while (e - b+1 > maxl)
            {
                int l = isPalindromic(s, b, e);
                if (!l)
                {
                    --e;
                    continue;
                }

                if (l > maxl)
                {
                    maxl = l;
                    maxs = s.substr(b, maxl);
                    break;
                }
                --e;
            }

            ++b;
            e = len - 1;
        }
        return maxs;
    }

    int isPalindromic(string s, int b, int e)
    {
        int i = b, j = e;
        while (i < j)
        {

            if (s[i] != s[j])
                return 0;
            else
            {
                ++i;
                --j;
            }
        }
        return (e - b + 1);
    }
};

leetcode-6 ZigZag Conversion

best solution

class Solution
{
  public:
    string convert(string s, int numRows)
    {
        if (numRows <= 1)
            return s;
        int len = s.size();
        vector<string> pa(numRows, "");
        int i = 0;
        while(i<len){

            for(int rows = 0; rows < numRows&&i<len; rows++)
            {
                pa[rows].push_back(s[i]);
                ++i;
            }
            for (int rows = numRows-2; rows > 0&&i<len; rows--)
            {
                pa[rows].push_back(s[i]);
                ++i;
            }
        }
        string zigzag;
        for (string &str : pa)
            zigzag += str;
        return zigzag;
    }
};

first commit

class Solution
{
  public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)
            return s;
        int len = s.size();
        vector<char> pa[numRows];
        int row = 0;
        bool jishu = 1;
        for (int i = 0; i < len;)
        {

            if (row == numRows)
            {
                jishu = !jishu;
                row = numRows-1;
            }
            if (row == -1)
            {
                jishu = !jishu;
                row = 0;
            }

            if (jishu)
            {
                pa[row].push_back(s[i]);
                ++i;
                ++row;
            }
            else
            {

                if (row == 0 || row == numRows - 1)
                {
                    pa[row].push_back('#');
                }
                else
                {
                    pa[row].push_back(s[i]);
                    ++i;
                }
                --row;
            }
        }
        string sout;
        for (int i = 0; i < numRows; i++)
        {
            for (auto j = pa[i].begin(); j != pa[i].end(); j++)
            {
                if (*j != '#')
                    sout.push_back(*j);
            }
        }
        return sout;
    }
};