liuchuo – 第153页 – 我不管，反正我最萌～

LeetCode 324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

题目大意：给一个数组，按照nums[0] < nums[1] > nums[2] < nums[3]…的顺序重排序数组～

分析：先给数组排序，然后拷贝一份一样的数组arr。然后p指针从数组中间开始向前，q指针从数组最后一位开始向前，依次赋值给nums[i]和nums[j]——其中i是偶数下标，j是奇数下标～

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> arr = nums;
        int p = (nums.size() - 1) / 2, q = nums.size() - 1;
        for (int i = 0, j = 1; i < nums.size(); i += 2, j += 2) {
            nums[i] = arr[p--];
            if (j < nums.size()) nums[j] = arr[q--];
        }
    }
};

class Solution {

public:

void wiggleSort(vector<int>& nums) {

sort(nums.begin(), nums.end());

vector<int> arr = nums;

int p = (nums.size() - 1) / 2, q = nums.size() - 1;

for (int i = 0, j = 1; i < nums.size(); i += 2, j += 2) {

nums[i] = arr[p--];

if (j < nums.size()) nums[j] = arr[q--];

}

};

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;

}

};