LeetCode OJ – 第17页

LeetCode 503. Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number;
The second 1’s next greater number needs to search circularly, which is also 2.

题目大意：给一个循环数组，返回一个等长的数组，数组中的每一个元素是：它后面的第一个大于它的元素（如果后面没有就循环一遍到最前面找，直到循环了一圈为止），如果不存在这样的数，就返回-1～

分析：首先建立一个等长的result数组，起始都是-1。和Next Greater Element I类似，不过这个题目要两个循环解决，第一个循环i从0～n-1，对于每一个nums[i]，把他们的下标index都放入栈中。但是在放入栈之前需要做这样的事情：比较栈顶元素和nums[i]，如果恰好比nums[i]小，说明nums[i]就是它的第一大元素，就将result[s.top()]的值变为nums[i]，这样栈中的下标始终是它的后面找不到比他大的元素的下标，也就是说栈中在遍历一遍后剩下的元素的值都是递减次序的～
开始第二次循环，依旧i从0～n-1，但是这次不需要push入栈了，只需要处理栈中剩下的元素，对于nums[i]，如果栈顶元素和nums[i]比较，恰好nums[i]大，说明nums[i]就是他们这些没在后面找到最大元素的最大元素，出栈，result[s.top()] = nums[i]。这样所有遍历完毕后栈中只会剩下唯一一个元素，也就是该数组中最大的元素，它的result依旧是-1，其他的都已经更新完毕。也就是说，第一次遍历是为了找它后面比它大的元素，而第二次遍历是为了找前面比他大的元素～

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && nums[s.top()] < nums[i]) {
                result[s.top()] = nums[i];
                s.pop();
            }
            s.push(i);
        }
        for (int i = 0; i < n; i++) {
            while (!s.empty() && nums[s.top()] < nums[i]) {
                result[s.top()] = nums[i];
                s.pop();
            }
        }
        return result;
    }
};

class Solution {

public:

vector<int> nextGreaterElements(vector<int>& nums) {

int n = nums.size();

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

stack<int> s;

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

while (!s.empty() && nums[s.top()] < nums[i]) {

result[s.top()] = nums[i];

s.pop();

}

s.push(i);

}

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

while (!s.empty() && nums[s.top()] < nums[i]) {

result[s.top()] = nums[i];

s.pop();

}

return result;

}

};

LeetCode 496. Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

题目大意：给两个数组findNums和nums，返回一个和findNums等长的数组，其返回的内容为：对于findNums[i]，返回的result[i]为nums[i]数组中，findNums[i]的后面的元素中第一个比findNums[i]大的元素。如果不存在这样的元素就写-1。其中findNums数组是nums数组的子数组～

分析：使用栈，从后往前遍历nums[i]，每当栈不为空的时候，一直出栈直到遇到比nums[i]大的数字停止。设立一个map<int, int> m，存储nums中每一个元素以及它对应的下一个最大元素构成的映射。如果停止后栈为空就将m[nums[i]]标记为-1，否则就写栈的栈顶元素～
最后将findNums中出现的每一个元素对应的map的值放入result数组中返回～

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        vector<int> result;
        stack<int> s;
        map<int, int> m;
        for (int i = nums.size() - 1; i >= 0; i--) {
            while (!s.empty() && s.top() <= nums[i]) 
                s.pop();
            m[nums[i]] = s.empty() ? -1 : s.top();
            s.push(nums[i]);
        }
        for (int i = 0; i < findNums.size(); i++)
            result.push_back(m[findNums[i]]);
        return result;
    }
};

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

vector<int> result;

stack<int> s;

map<int, int> m;

for (int i = nums.size() - 1; i >= 0; i--) {

while (!s.empty() && s.top() <= nums[i])

s.pop();

m[nums[i]] = s.empty() ? -1 : s.top();

s.push(nums[i]);

}

for (int i = 0; i < findNums.size(); i++)

result.push_back(m[findNums[i]]);

return result;

}

};

LeetCode 506. Relative Ranks

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:
Input: [5, 4, 3, 2, 1]
Output: [“Gold Medal”, “Silver Medal”, “Bronze Medal”, “4”, “5”]
Explanation: The first three athletes got the top three highest scores, so they got “Gold Medal”, “Silver Medal” and “Bronze Medal”.
For the left two athletes, you just need to output their relative ranks according to their scores.
Note:
N is a positive integer and won’t exceed 10,000.
All the scores of athletes are guaranteed to be unique.

题目大意：给一个数组，为几个运动员的分数，返回他们的排名，如果前三名应该为”Gold Medal”, “Silver Medal”, “Bronze Medal”，否则是数字名次，保证所有的分数不重复～

分析：拷贝一个相同的数组arr，然后排序，从nums[i]中寻找与arr[j]相同的分数，名次即为j+1。如果j为0，1，2则需要特殊处理～

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        vector<int> arr = nums;
        auto cmp = [](int a, int b) {return a > b;};
        sort(arr.begin(), arr.end(), cmp);
        vector<string> result(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (nums[i] == arr[j]) {
                    switch(j) {
                        case 0: result[i] = "Gold Medal"; break;
                        case 1: result[i] = "Silver Medal"; break;
                        case 2: result[i] = "Bronze Medal"; break;
                        default: result[i] = to_string(j + 1); break;
                    }
                    break;
                }
            }
        }
        return result;
    }
};

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<int> arr = nums;

auto cmp = [](int a, int b) {return a > b;};

sort(arr.begin(), arr.end(), cmp);

vector<string> result(nums.size());

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

for (int j = 0; j < nums.size(); j++) {

if (nums[i] == arr[j]) {

switch(j) {

case 0: result[i] = "Gold Medal"; break;

case 1: result[i] = "Silver Medal"; break;

case 2: result[i] = "Bronze Medal"; break;

default: result[i] = to_string(j + 1); break;

}

break;

}

return result;

}

};

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--];

}

};