LeetCode 解题报告

链接：
Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. 

Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路：不要忘记进位，其它基本上就是链表操作了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *result = NULL;
        int append = 0;
        ListNode *ptr, *pre;
        while (l1 && l2) {
            int sum = l1->val + l2->val + append;
            append = sum / 10;
            ptr = new ListNode(sum % 10);
            if (result == NULL) {
                result = ptr;
                pre = ptr;
            } else {
                pre->next = ptr;
                pre = ptr;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        ListNode *restList = l1 ? l1 : l2;
        while (restList) {
            int sum = restList->val + append;
            append = sum / 10;
            ptr = new ListNode(sum % 10);
            if (result == NULL) {
                result = ptr;
                pre = ptr;
            } else {
                pre->next = ptr;
                pre = ptr;
            }
            restList = restList->next;
        }
        if (append) {
            ptr = new ListNode(append);
            pre->next = ptr;
        }

        return result;
    }
};

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc",
which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路：有点DP的思想，每次计算一s[i]为结束点的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxLen = 0;
        int preLen = 0;
        for (int i=0; i<s.size(); i++) {
            int curLen = 1;
            for (int j=i-1; j>=i-preLen; j--)
                if (s[j] == s[i])
                    break;
                else
                    curLen++;
            if (curLen > maxLen)
                maxLen = curLen;
            preLen = curLen;
        }

        return maxLen;
    }
};

Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000,
and there exists one unique longest palindromic substring.

思路：求最长回文子串有线性的方法，我给的是O（n^2）的算法，不过也没有超时。
记录以s[i]结尾的所有回文子串的长度，那么在求以s[i+1]结尾的回文子串时候，遍历
以s[i]结尾回文串长度len, 如果s[i-len] == s[i+1]，那么形成新的更长回文串。不过求
当前点时候，只要记录前一点状态就可以了，有点DP的思想。

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() == 0)
            return "";

        int maxLen = 1;
        int pos = 0;
        const int SIZE = 1001;
        int dp[2][SIZE];
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = dp[1][1] = 1;
        dp[0][2] = -1;
        int pre = 0;
        int cur = 1;

        for (int i=1; i<s.size(); i++) {
            pre = (i + 1) % 2;
            cur = i % 2;
            int n = 1;
            for (int j=0; dp[pre][j] != -1; j++) {
                int lpos = i - 1 - dp[pre][j];
                if (lpos >= 0 && s[lpos] == s[i]) {
                    dp[cur][++n] = dp[pre][j] + 2;
                }
            }
            if (dp[cur][n] > maxLen) {
                maxLen = dp[cur][n];
                pos = i;
            }
            dp[cur][++n] = -1;
        }

        return s.substr(pos-maxLen+1, maxLen);
    }
};

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

思路：这道题目没什么难度，就是题意不是很明确。其实就是将原来字符串按照锯齿形排列，
然后按行输出。

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (nRows <= 1 || s.size() <=1 )
            return s;
        string cvStr = "";
        int base = nRows * 2 - 2;
        for (int n=0; n<nRows; n++) {
            for (int i=0; i<=s.size()/base; i++) {
                int bias = i*base;
                if (bias+n < s.size())
                    cvStr += s[bias+n];
                int complement = (base-n)%base;
                if (n != complement && bias+complement<s.size())
                    cvStr += s[bias+complement];
            }
        }
        return cvStr;
    }
};

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321
思路：水题

class Solution {
public:
    int reverse(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        int result = 0;
        while (x != 0) {
            int tail = x % 10;
            x /= 10;
            result = result*10 + tail;
        }

        return result;
    }
};