Code – 第151页

LeetCode 498. Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
Explanation:

Note:
The total number of elements of the given matrix will not exceed 10,000.

题目大意：按照如图所示方向遍历一个m*n的二维数组，将元素按序放入一维数组中返回～

分析：先假设所有的方向都是斜向上的，也就是从matrix[0][0]开始，matrix[1][0]、matrix[2, 0]…matrix[m-1][0]也就是第一列的所有数为开头，然后还有最后一行的所有数为开头，寻找matrix[i-1][j+1]是否存在，存在就将它放入temp数组中，temp的每一行表示斜着的一行元素的序列。
这样当temp数组的行数是奇数的时候，就从后往前一次放入到result数组中，如果是偶数就从前往后依次放入result数组中，返回result数组即为所求～

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

class Solution {

public:

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

vector<int> result;

int m = matrix.size();

if (m == 0) return result;

int n = matrix[0].size(), index = 0;

vector<vector<int>> temp(m + n - 1);

for (int i = 0; i < m; i++, index++) {

temp[index].push_back(matrix[i][0]);

for (int x = i, y = 0; x - 1 >= 0 && y + 1 < n; x--, y++)

temp[index].push_back(matrix[x-1][y+1]);

}

for (int j = 1; j < n; j++, index++) {

temp[index].push_back(matrix[m-1][j]);

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

temp[index].push_back(matrix[x-1][y+1]);

}

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

if (i % 2 == 1) {

for (int j = temp[i].size() - 1; j >= 0; j--)

result.push_back(temp[i][j]);

} else {

for (int j = 0; j < temp[i].size(); j++)

result.push_back(temp[i][j]);

}

return result;

}

};

LeetCode 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

“bbbab”
Output:
4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:

“cbbd”
Output:
2
One possible longest palindromic subsequence is “bb”.

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

分析：使用动态规划解决～设立一个len行len列的dp数组～dp[i][j]表示字符串i～j下标所构成的子串中最长回文子串的长度～最后我们需要返回的是dp[0][len-1]的值～

dp数组这样更新：首先i指针从尾到头遍历，j指针从i指针后面一个元素开始一直遍历到尾部～一开始dp[i][i]的值都为1，如果当前i和j所指元素相等，说明能够加到i～j的回文子串的长度中，所以更新dp[i][j] = dp[i+1][j-1] + 2; 如果当前元素不相等，那么说明这两个i、j所指元素对回文串无贡献，则dp[i][j]就是从dp[i+1][j]和dp[i][j-1]中选取较大的一个值即可～

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len));
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if (s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }
    
};

class Solution {

public:

int longestPalindromeSubseq(string s) {

int len = s.length();

vector<vector<int>> dp(len, vector<int>(len));

for (int i = len - 1; i >= 0; i--) {

dp[i][i] = 1;

for (int j = i + 1; j < len; j++) {

if (s[i] == s[j])

dp[i][j] = dp[i+1][j-1] + 2;

else

dp[i][j] = max(dp[i+1][j], dp[i][j-1]);

}

return dp[0][len-1];

}

};

LeetCode 500. Keyboard Row

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.
Example 1:
Input: [“Hello”, “Alaska”, “Dad”, “Peace”]
Output: [“Alaska”, “Dad”]
Note:
You may use one character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.

题目大意：给一个单词数组，判断哪些单词是可以由键盘的一行中的字母构成的，返回这些单词～

分析：设立一个集合数组，v[0]、v[1]、v[2]集合分别插入键盘的第1～3行的所有字母的集合（大小写都包括），接着遍历每一个单词，首先判断单词的第一个字母是处于哪一行的，tag表示其所属行数的下标，接着对于单词的每一个字母，判断是否在v[tag]这个集合里面，如果所有的都存在就将这个单词放入result数组中返回～

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> result;
        vector<set<char>> v(3);
        string s1 = "QWERTYUIOPqwertyuiop", s2 = "ASDFGHJKLasdfghjkl", s3 = "ZXCVBNMzxcvbnm";
        for (int i = 0; i < s1.length(); i++) v[0].insert(s1[i]);
        for (int i = 0; i < s2.length(); i++) v[1].insert(s2[i]);
        for (int i = 0; i < s3.length(); i++) v[2].insert(s3[i]);
        for (int i = 0; i < words.size(); i++) {
            int tag = -1;
            bool flag = true;
            if (words[i].length() == 0) continue; 
            if (v[0].find(words[i][0]) != v[0].end()) tag = 0;
            if (v[1].find(words[i][0]) != v[1].end()) tag = 1;
            if (v[2].find(words[i][0]) != v[2].end()) tag = 2;
            for (int j = 1; j < words[i].length(); j++) {
                if (v[tag].find(words[i][j]) == v[tag].end()) {
                    flag = false;
                    break;
                }
            }
            if (flag == true)
                result.push_back(words[i]);
        }
        return result;
    }
};

class Solution {

public:

vector<string> findWords(vector<string>& words) {

vector<string> result;

vector<set<char>> v(3);

string s1 = "QWERTYUIOPqwertyuiop", s2 = "ASDFGHJKLasdfghjkl", s3 = "ZXCVBNMzxcvbnm";

for (int i = 0; i < s1.length(); i++) v[0].insert(s1[i]);

for (int i = 0; i < s2.length(); i++) v[1].insert(s2[i]);

for (int i = 0; i < s3.length(); i++) v[2].insert(s3[i]);

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

int tag = -1;

bool flag = true;

if (words[i].length() == 0) continue;

if (v[0].find(words[i][0]) != v[0].end()) tag = 0;

if (v[1].find(words[i][0]) != v[1].end()) tag = 1;

if (v[2].find(words[i][0]) != v[2].end()) tag = 2;

for (int j = 1; j < words[i].length(); j++) {

if (v[tag].find(words[i][j]) == v[tag].end()) {

flag = false;

break;

}

if (flag == true)

result.push_back(words[i]);

}

return result;

}

};

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;

}

};