LeetCode OJ – 第18页

LeetCode 5. 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.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”

题目大意：给一个字符串，找它的回文子串中长度最长的一个子串～

分析：首先令result为第一个元素，如果没有第一个元素就返回空字串，遍历字串，对于每个元素都从中间向两边寻找是否有回文子串，返回这个子串，将它的长度与result比较，如果比result长就更新result～
要分为奇数还是偶数考虑，奇数就左右都是i，偶数就是左边是i右边是i+1然后扩展～

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if (len == 0) return "";
        string result = s.substr(0, 1);
        for (int i = 0; i <= len - 2; i++) {
            string temp = midToSide(s, i, i);
            if (temp.length() > result.length())
                result = temp;
            temp = midToSide(s, i, i + 1);
            if (temp.length() > result.length())
                result = temp;
        }
        return result;
    }
    
    string midToSide(string s, int left, int right) {
        while (left >= 0 && right <= s.length() - 1 && s[left] == s[right]) {
            left--; 
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
};

class Solution {

public:

string longestPalindrome(string s) {

int len = s.length();

if (len == 0) return "";

string result = s.substr(0, 1);

for (int i = 0; i <= len - 2; i++) {

string temp = midToSide(s, i, i);

if (temp.length() > result.length())

result = temp;

temp = midToSide(s, i, i + 1);

if (temp.length() > result.length())

result = temp;

}

return result;

}

string midToSide(string s, int left, int right) {

while (left >= 0 && right <= s.length() - 1 && s[left] == s[right]) {

left--;

right++;

}

return s.substr(left + 1, right - left - 1);

}

};

LeetCode 59. Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

题目大意：给一个n，输出一个n*n的数组，并且按照螺旋的方式填充入数字1～n*n。

分析：按照一个个矩阵的边框输入：x为矩阵的上界，n为矩阵的上界，每次输出这个围成的矩阵的第一行——最后一列——最后一行——第一列，然后将x自增1，m自减1～
注意：为了避免重复输出，当x和n相等的时候，就输入一次第一行和最后一列就可以，不用重复输入最后一行和第一列～

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n));
        n = n - 1;
        int num = 1;
        for (int x = 0; x <= n; x++, n--) {
            for (int j = x; j <= n; j++)
                result[x][j] = num++;
            for (int i = x + 1; i <= n - 1; i++)
                result[i][n] = num++;
            for (int j = n; j >= x && x != n; j--)
                result[n][j] = num++;
            for (int i = n - 1; i >= x + 1 && x != n; i--)
                result[i][x] = num++;
        }
        return result;
    }
};

class Solution {

public:

vector<vector<int>> generateMatrix(int n) {

vector<vector<int>> result(n, vector<int>(n));

n = n - 1;

int num = 1;

for (int x = 0; x <= n; x++, n--) {

for (int j = x; j <= n; j++)

result[x][j] = num++;

for (int i = x + 1; i <= n - 1; i++)

result[i][n] = num++;

for (int j = n; j >= x && x != n; j--)

result[n][j] = num++;

for (int i = n - 1; i >= x + 1 && x != n; i--)

result[i][x] = num++;

}

return result;

}

};

LeetCode 54. Spiral Matrix

54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
题目大意：给一个m*n的矩阵，以顺时针旋转的方式返回所有的元素到一个数组中～
分析：按照一个个矩阵的边框输出：x、m为行的上下界，y、n为列的上下界，每次输出这个围成的矩阵的第一行——最后一列——最后一行——第一列，然后将x和y自增1，m和n自减1～
注意：为了避免重复输出，当x和m相等或者y和n相等的时候，就输出一次第一行和最后一列就可以，不用重复输出最后一行和第一列～

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        if(matrix.empty()) return result;
        int m = matrix.size() - 1, n = matrix[0].size() - 1;
        for (int x = 0, y = 0; x <= m && y <= n; x++, y++, m--, n--) {
            for (int j = y; j <= n; j++)
                result.push_back(matrix[x][j]);
            for (int i = x + 1; i <= m - 1; i++)
                result.push_back(matrix[i][n]);
            for (int j = n; j >= y && x != m; j--)
                result.push_back(matrix[m][j]);
            for (int i = m - 1; i > x && y != n; i--)
                result.push_back(matrix[i][y]);
        }
        return result;
    }
};

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

vector<int> result;

if(matrix.empty()) return result;

int m = matrix.size() - 1, n = matrix[0].size() - 1;

for (int x = 0, y = 0; x <= m && y <= n; x++, y++, m--, n--) {

for (int j = y; j <= n; j++)

result.push_back(matrix[x][j]);

for (int i = x + 1; i <= m - 1; i++)

result.push_back(matrix[i][n]);

for (int j = n; j >= y && x != m; j--)

result.push_back(matrix[m][j]);

for (int i = m - 1; i > x && y != n; i--)

result.push_back(matrix[i][y]);

}

return result;

}

};

LeetCode 143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

题目大意：按照L0→Ln→L1→Ln-1→L2→Ln-2→…重新排列链表～

分析：1.找到链表的中间结点mid——使用mid走一步、tail走两步的方式，直到tail走到链表尾部的时候，mid正好指向中间位置。2.从mid结点开始将后面的链表反转，返回反转后的头结点 3.p指向前面一段链表，q指向后面一段链表，将p和q合并：首先令a和b是p和q的临时结点，然后将pq分别向后移动一位，最后将a->next = b;b->next = p;

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *p = head, *a = head, *b = head;
        ListNode *mid = findMidNode(head);
        ListNode *q = reverseList(mid);
        while (p != NULL && q != NULL) {
            a = p;
            b = q;
            p = p->next;
            q = q->next;
            a->next = b;
            b->next = p;
        }
        if (q != NULL) b->next = q;
    }
    
    ListNode* findMidNode(ListNode* head) {
        ListNode *mid = head, *tail = head, *last = head;
        while (tail != NULL && tail->next != NULL) {
            last = mid;
            mid = mid->next;
            tail = tail->next->next;
        }
        if (last != NULL) last->next = NULL;
        return mid;
    }
    
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) return head;
        ListNode *cur = head, *pre = NULL, *temp = NULL;
        while (cur != NULL) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

class Solution {

public:

void reorderList(ListNode* head) {

ListNode *p = head, *a = head, *b = head;

ListNode *mid = findMidNode(head);

ListNode *q = reverseList(mid);

while (p != NULL && q != NULL) {

a = p;

b = q;

p = p->next;

q = q->next;

a->next = b;

b->next = p;

}

if (q != NULL) b->next = q;

}

ListNode* findMidNode(ListNode* head) {

ListNode *mid = head, *tail = head, *last = head;

while (tail != NULL && tail->next != NULL) {

last = mid;

mid = mid->next;

tail = tail->next->next;

}

if (last != NULL) last->next = NULL;

return mid;

}

ListNode* reverseList(ListNode* head) {

if (head == NULL) return head;

ListNode *cur = head, *pre = NULL, *temp = NULL;

while (cur != NULL) {

temp = cur->next;

cur->next = pre;

pre = cur;

cur = temp;

}

return pre;

}

};

LeetCode 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

题目大意：给一个整型数组，求该数组中所有连续子数组的元素乘积的最大值～

分析：需要保存临时最大值和最小值，因为最大值乘以一个正数可能构成新的最大值，而最小值乘以负数也可能构成新的最大值。result是要求的结果，maxValue为nums[i]之前的，和nums[i]相邻的乘积的最大值，minValue为nums[i]之前的，和nums[i]相邻的乘积的最小值。首先令result、maxValue和minValue都为nums[0], i从nums[1]开始一直到结束，tempMax为考虑是否选择之前的maxValue与nums[i]相乘，如果相乘结果更大就保留，否则就选择nums[i]本身为最大。tempMin同理～然后maxValue和minValue比较tempMax/tempMin与minValue * nums[i]的大小关系，maxValue取较大值，minValue取较小值～而result是取所有maxValue中的最大值～最后返回result～

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = nums[0], maxValue = nums[0], minValue = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int tempMax = max(nums[i], maxValue * nums[i]);
            int tempMin = min(nums[i], maxValue * nums[i]);
            maxValue = max(tempMax, minValue * nums[i]);
            minValue = min(tempMin, minValue * nums[i]);
            result = max(maxValue, result);
        }
        return result;
    }
};

class Solution {

public:

int maxProduct(vector<int>& nums) {

if (nums.size() == 0) return 0;

int result = nums[0], maxValue = nums[0], minValue = nums[0];

for (int i = 1; i < nums.size(); i++) {

int tempMax = max(nums[i], maxValue * nums[i]);

int tempMin = min(nums[i], maxValue * nums[i]);

maxValue = max(tempMax, minValue * nums[i]);

minValue = min(tempMin, minValue * nums[i]);

result = max(maxValue, result);

}

return result;

}

};

LeetCode 501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2],
1
\
2
/
2
return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

题目大意：给一个二叉搜索树，求出现次数最多的数是哪个（哪些）～

分析：二叉搜索树的中序遍历的结果恰好是所有数的递增序列，根据中序遍历结果，对于当前遍历结点，标记maxCount为最大出现次数，tempCount为当前数字出现的次数，currentVal为当前保存的值。
首先，tempCount++表示当前的数字出现次数+1，如果当前结点的值不等于保存的值，就更新currentVal的值，并且将tempCount标记为1～
接下来，如果tempCount即当前数字出现的次数大于maxCount，就更新maxCount，并且将result数组清零，并将当前数字放入result数组中；如果tempCount只是等于maxCount，说明是出现次数一样的，则将当前数字直接放入result数组中～

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        inorder(root);
        return result;
    }
private:
    vector<int> result;
    int maxCount = 0, currentVal, tempCount = 0;
    void inorder(TreeNode* root) {
        if (root == NULL) return;
        inorder(root->left);
        tempCount++;
        if (root->val != currentVal) {
            currentVal = root->val;
            tempCount = 1;
        }
        if (tempCount > maxCount) {
            maxCount = tempCount;
            result.clear();
            result.push_back(root->val);
        } else if (tempCount == maxCount) {
            result.push_back(root->val);
        }
        inorder(root->right);
    }
};

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

return result;

}

private:

vector<int> result;

int maxCount = 0, currentVal, tempCount = 0;

void inorder(TreeNode* root) {

if (root == NULL) return;

inorder(root->left);

tempCount++;

if (root->val != currentVal) {

currentVal = root->val;

tempCount = 1;

}

if (tempCount > maxCount) {

maxCount = tempCount;

result.clear();

result.push_back(root->val);

} else if (tempCount == maxCount) {

result.push_back(root->val);

}

inorder(root->right);

}

};