Code – 第152页

LeetCode 508. Most Frequent Subtree Sum

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

5
/ \
2 -3
return [2, -3, 4], since all the values happen only once, return all of them in any order.
Examples 2
Input:

5
/ \
2 -5
return [2], since 2 happens twice, however -5 only occur once.
Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

题目大意：给一棵树，找出现次数最多的子树和。子树和就是一个结点以及它下方所有结点构成的子树的总和，在这些总和中找一个出现次数最多的结果，如果有很多个这样的结果，返回这些结果构成的数组～

分析：首先深度优先搜索，先遍历左子树再遍历右子树，遍历的同时更新子树的根结点的值为自身+左子树和+右子树和。最后将这个子树根结点的值放入一个map中++，表示这个值出现的次数+1。这样深度优先搜索后的树的每一个结点的值都是子树和的值～
然后遍历这个map，找到最大值maxn。遍历map将出现次数为maxn的所有值放入result数组中，返回result数组即为所求～

class Solution {
private:
    map<int, int> m;
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> result;
        dfs(root);
        int maxn = 0;
        for (auto it = m.begin(); it != m.end(); it++)
            maxn = max(maxn, it->second);
        for (auto it = m.begin(); it != m.end(); it++)
            if (it->second == maxn)
                result.push_back(it->first);
        return result;
    }
    
    void dfs(TreeNode* root) {
        if (root == NULL) return ;
        if (root->left != NULL) {
            dfs(root->left);
            root->val += root->left->val;
        }
        if (root->right != NULL) {
            dfs(root->right);
            root->val += root->right->val;
        }
        m[root->val]++;
    }
};

class Solution {

private:

map<int, int> m;

public:

vector<int> findFrequentTreeSum(TreeNode* root) {

vector<int> result;

dfs(root);

int maxn = 0;

for (auto it = m.begin(); it != m.end(); it++)

maxn = max(maxn, it->second);

for (auto it = m.begin(); it != m.end(); it++)

if (it->second == maxn)

result.push_back(it->first);

return result;

}

void dfs(TreeNode* root) {

if (root == NULL) return ;

if (root->left != NULL) {

dfs(root->left);

root->val += root->left->val;

}

if (root->right != NULL) {

dfs(root->right);

root->val += root->right->val;

}

m[root->val]++;

}

};

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;

}

};