2016-9-21

[zhaokuohaha]

5. Longest Palindromic Substring

[zhaokuohaha]

5

public class Solution {
    int start = 0;// 回文串的开始 
    int end = 0;//回文串的 结束 
    int max = 0;// 最大长度 
    public string LongestPalindrome(string s) {
        if(s==null || s.Length==1) return s;
        int middle = (s.Length+1)/2-1;
        int left = middle;
        int right = (s.Length%2)==0 ? middle+1 : middle;//hhhh把取余写成了/找了一天bug
        for(;left >= max/2;left--,right++){
            count(s, left, left);
            count(s, left-1, left);
            count(s, right, right);
            count(s, right-1, right);
           // Console.WriteLine(left+"+++++++++++++"+ right);
        }
       // Console.WriteLine(start +"---"+ max);
        return s.Substring(start, max);
    }

    private void count(string s, int left, int right){
        if(left < 0 || s[left] != s[right])
            return;
        while(left-1>=0 && right+1 < s.Length && s[left-1] == s[right+1]){
            left--;
            right++;
        }
        if(right-left+1 > max){
            start = left;
            end = right;
            max = right-left+1;
           // Console.WriteLine(right +"==="+ left);
        }
    }
}

[zhaokuohaha]

6

public class Solution {
    public string Convert(string s, int numRows) {
        if(s.Length<numRows || numRows == 1) return s;
        StringBuilder sb = new StringBuilder();
        if(numRows==2){
            for(int i=0; i<s.Length; i+=2)
                sb.Append(s[i]);
            for(int i=1; i<s.Length; i+=2)
                sb.Append(s[i]);
            return sb.ToString();
        }
        for(int i=0; i<numRows; i++){
            for(int j=i; j<s.Length; j+=2*(numRows-1)){
                sb.Append(s[j]);
                if(i!=0 && i!=numRows-1 && j+2*(numRows-i-1) < s.Length)
                    sb.Append(s[j+2*(numRows-i-1)]);
            }
        }
        return sb.ToString();
    }
}

2并不特殊

public class Solution {
    public string Convert(string s, int numRows) {
        if(s.Length<numRows || numRows == 1) return s;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<numRows; i++){
            for(int j=i; j<s.Length; j+=2*(numRows-1)){
                sb.Append(s[j]);
                if(i!=0 && i!=numRows-1 && j+2*(numRows-i-1) < s.Length)
                    sb.Append(s[j+2*(numRows-i-1)]);
            }
        }
        return sb.ToString();
    }
}