Code – 第163页

LeetCode 151. Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

分析：我用的方法是把字符串中的所有单词放入栈里，然后将栈里的所有字符串弹栈到字符串s中～

class Solution {
public:
    void reverseWords(string &s) {
        stack<string> sstack;
        int flag = 0;
        string temp = "";
        for(int i = 0; i < s.length(); i++) {
            if(s[i] != ' ' && flag == 0) {
                temp = "";
                temp += s[i];
                flag = 1;
            } else if(s[i] != ' ') {
                temp += s[i];
            } else if(s[i] == ' ' && flag == 1){
                sstack.push(temp);
                flag = 0;
            }
            if(i == s.length() - 1 && flag == 1)
                sstack.push(temp);
        }
        s = "";
        while(!sstack.empty()) {
            string temp = sstack.top();
            s += temp;
            sstack.pop();
            if(!sstack.empty())
                s += " ";
        }
    }
};

class Solution {

public:

void reverseWords(string &s) {

stack<string> sstack;

int flag = 0;

string temp = "";

for(int i = 0; i < s.length(); i++) {

if(s[i] != ' ' && flag == 0) {

temp = "";

temp += s[i];

flag = 1;

} else if(s[i] != ' ') {

temp += s[i];

} else if(s[i] == ' ' && flag == 1){

sstack.push(temp);

flag = 0;

}

if(i == s.length() - 1 && flag == 1)

sstack.push(temp);

}

s = "";

while(!sstack.empty()) {

string temp = sstack.top();

s += temp;

sstack.pop();

if(!sstack.empty())

s += " ";

}

};

LeetCode 350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

分析：将nums1的每一个数字以及对应数字的个数存储在map里面，遍历nums2中的所有元素，如果当前元素在map中存在，就把它放入result数组中，并将其数量-1。最终返回result即为所求交集～

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        map<int, int> m;
        for(int i = 0; i < nums1.size(); i++)
            m[nums1[i]]++;
        for(int i = 0; i < nums2.size(); i++) {
            if(m[nums2[i]] != 0) {
                m[nums2[i]]--;
                result.push_back(nums2[i]);
            }
        }
        return result;
    }
};

class Solution {

public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

vector<int> result;

map<int, int> m;

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

m[nums1[i]]++;

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

if(m[nums2[i]] != 0) {

m[nums2[i]]--;

result.push_back(nums2[i]);

}

return result;

}

};

LeetCode 378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

分析：使用multiset，因为是求第k小的，而且允许相同的元素，所以使用可以存储相同元素的multiset。当multiset里面的元素大于k个的时候，删除集合中最大的那个（即最后一个元素，也就是s.end()的前一个），最后输出最后一个元素即可～即 *s.rbegin()～

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        multiset<int> s;
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[i].size(); j++) {
                s.insert(matrix[i][j]);
                if(s.size() > k)
                    s.erase(--s.end());
            }
        }
        return *s.rbegin();
    }
};

class Solution {

public:

int kthSmallest(vector<vector<int>>& matrix, int k) {

multiset<int> s;

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

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

s.insert(matrix[i][j]);

if(s.size() > k)

s.erase(--s.end());

}

return *s.rbegin();

}

};

LeetCode 389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = “abcd”
t = “abcde”

Output:
e

Explanation:
‘e’ is the letter that was added.

分析：将字符串s和字符串t的字符个数标记在hash1和hash2数组中，然后比较hash1和hash2，值不同的那个字符即为所求～

class Solution {
public:
    char findTheDifference(string s, string t) {
        int hash1[256] = {0}, hash2[256] = {0};
        for(int i = 0; i < s.length(); i++)
            hash1[s[i]]++;
        for(int i = 0; i < t.length(); i++)
            hash2[t[i]]++;
        for(int i = 0; i < 256; i++)
            if(hash1[i] != hash2[i])
                return (char)i;
        return '0';
    }
};

class Solution {

public:

char findTheDifference(string s, string t) {

int hash1[256] = {0}, hash2[256] = {0};

for(int i = 0; i < s.length(); i++)

hash1[s[i]]++;

for(int i = 0; i < t.length(); i++)

hash2[t[i]]++;

for(int i = 0; i < 256; i++)

if(hash1[i] != hash2[i])

return (char)i;

return '0';

}

};

LeetCode 409. Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
“abccccdd”

Output:
7

Explanation:
One longest palindrome that can be built is “dccaccd”, whose length is 7.

分析：统计每个字母出现的字数，如果是偶数就能放到回文串里；如果是奇数就只能hash[i] – 1个放到回文串里面，而且如果存在是奇数个数的字母，则最后可以加1，也就是把落单的字母中的任意一个放到回文串的最中间使长度加1～

class Solution {
public:
    int longestPalindrome(string s) {
        int hash[256] = {0}, len = 0, flag = 0;
        for(int i = 0; i < s.length(); i++)
            hash[s[i]]++;
        for(int i = 0; i < 256; i++) {
            if(hash[i] % 2 == 0) {
                len += hash[i];
            } else {
                len += (hash[i] - 1);
                flag = 1;
            }
        }
        return len + flag;
    }
};

class Solution {

public:

int longestPalindrome(string s) {

int hash[256] = {0}, len = 0, flag = 0;

for(int i = 0; i < s.length(); i++)

hash[s[i]]++;

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

if(hash[i] % 2 == 0) {

len += hash[i];

} else {

len += (hash[i] - 1);

flag = 1;

}

return len + flag;

}

};

LeetCode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

分析：一开始用set，后来发现是“not the kth distinct element”，所以说不能用set，set里面元素必须是不相同的，所以这里用multiset就能解决。
因为multiset会自动排序，所以每次将数字放入multiset，如果集合里面容量超过k个就把最小的那个移除～
到最后输出*s.begin()即为第k大～

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        multiset<int> s;
        for(int i = 0; i < nums.size(); i++) {
            s.insert(nums[i]);
            if(s.size() > k)
                s.erase(s.begin());
        }
        return *s.begin();
    }
};

class Solution {

public:

int findKthLargest(vector<int>& nums, int k) {

multiset<int> s;

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

s.insert(nums[i]);

if(s.size() > k)

s.erase(s.begin());

}

return *s.begin();

}

};