Code – 第152页

LeetCode 79. Word Search

79. Word Search
Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

题目大意：给一个char型二维数组和一个word字符串，寻找网格中是否含有word字符串，只能通过相邻（垂直或者水平）的格子连接～
分析：对于二维数组中的每一个点都开始遍历，如果当前点的字母正好等于word[0]就进入dfs，设立flag标记是否找到，设立visit标记是否访问：
首先令起始节点visit[j][k]标记为已经访问过，接着dfs，如果flag为true直接return，如果当前index正好为word的最后一个字符下标就标记flag为true，return。
从四个方向开始对结点进行深度优先搜索，首先要保证搜索的结点满足：1.是合法的在网格之内的 2.未被访问过 3.当前字符与要找的word[index+1]相同。满足则标记visit[tx][ty] = true,且dfs tx和ty以及index+1，两个dfs后要把他重新置为false～
这样最后返回flag的值即为是否能找到的结果～

class Solution {
private:
    bool flag = false;
    vector<vector<bool>> visit;
    vector<vector<char>> board;
    string word = "";
    int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int m, n;
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.size() == 0) return word == "";
        m = board.size(), n = board[0].size();
        this->word = word;
        this->board = board;
        visit.resize(m, vector<bool>(n));
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                if (board[j][k] == word[0]) {
                    visit[j][k] = true;
                    dfs(j, k, 0);
                    visit[j][k] = false;
                }
            }
        }
        return flag;
    }
    
    void dfs(int x, int y, int index) {
        if (flag == true) return ;
        if (index == word.length() - 1) {
            flag = true;
            return ;
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0], ty = y + dir[i][1];
            if (tx >= 0 && tx < m && ty >= 0 && ty < n && board[tx][ty] == word[index + 1] && visit[tx][ty] == false) {
                visit[tx][ty] = true;
                dfs(tx, ty, index + 1);
                visit[tx][ty] = false;
            }
        }
    }
};

class Solution {

private:

bool flag = false;

vector<vector<bool>> visit;

vector<vector<char>> board;

string word = "";

int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int m, n;

public:

bool exist(vector<vector<char>>& board, string word) {

if (board.size() == 0) return word == "";

m = board.size(), n = board[0].size();

this->word = word;

this->board = board;

visit.resize(m, vector<bool>(n));

for (int j = 0; j < m; j++) {

for (int k = 0; k < n; k++) {

if (board[j][k] == word[0]) {

visit[j][k] = true;

dfs(j, k, 0);

visit[j][k] = false;

}

return flag;

}

void dfs(int x, int y, int index) {

if (flag == true) return ;

if (index == word.length() - 1) {

flag = true;

return ;

}

for (int i = 0; i < 4; i++) {

int tx = x + dir[i][0], ty = y + dir[i][1];

if (tx >= 0 && tx < m && ty >= 0 && ty < n && board[tx][ty] == word[index + 1] && visit[tx][ty] == false) {

visit[tx][ty] = true;

dfs(tx, ty, index + 1);

visit[tx][ty] = false;

}

};

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;

}

};