liuchuo – 第164页

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();

}

};

LeetCode 414. Third Maximum Number

414. Third Maximum Number
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

分析：因为set会自动排序，所以每次将数字放入set，如果set里面容量超过三个就把最小的那个移除～
到最后如果set的大小不是3个，那就输出最大值，也就是*s.rbegin(), 如果set的大小是3个就输出*s.begin()即为第三大～

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> s;
        for(int i = 0; i < nums.size(); i++) {
            s.insert(nums[i]);
            if(s.size() > 3)
                s.erase(s.begin());
        }
        return s.size() == 3 ? *s.begin() : * s.rbegin();
    }
};

class Solution {

public:

int thirdMax(vector<int>& nums) {

set<int> s;

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

s.insert(nums[i]);

if(s.size() > 3)

s.erase(s.begin());

}

return s.size() == 3 ? *s.begin() : * s.rbegin();

}

};

LeetCode 415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

分析：先将num1和num2倒置，然后从头到尾依次加，记得标记是否有进位sign，每次也要把进位的值加进去～如果num1加完了num2还没加完，就继续加num2的～反之同理～最后sign也要考虑有没有最高位1～所有都处理完后把result倒置～

class Solution {
public:
    string addStrings(string num1, string num2) {
        int len1 = num1.length(), len2 = num2.length();
        for(int i = 0; i < len1 / 2; i++)
            swap(num1[i], num1[len1 - i - 1]);
        for(int i = 0; i < len2 / 2; i++)
            swap(num2[i], num2[len2 - i - 1]);
        string result = "";
        int sign = 0, p = 0, q = 0;
        while(p < len1 && q < len2) {
            int t = (num1[p] - '0') + (num2[q] - '0') + sign;
            if(t >= 10) {
                t = t - 10;
                sign = 1;
            } else {
                sign = 0;
            }
            result += (char)(t + '0');
            p++;
            q++;
        }
        while(p < len1) {
            int t = (num1[p] - '0') + sign;
            if(t >= 10) {
                t = t - 10;
                sign = 1;
            } else {
                sign = 0;
            }
            result += (char)(t + '0');
            p++;
        }
        while(q < len2) {
            int t = (num2[q] - '0') + sign;
            if(t >= 10) {
                t = t - 10;
                sign = 1;
            } else {
                sign = 0;
            }
            result += (char)(t + '0');
            q++;
        }
        if(sign == 1)
            result += '1';
        int len = result.length();
        for(int i = 0; i < len / 2; i++) {
            swap(result[i], result[len - 1 - i]);
        }
        return result;
    }
};

class Solution {

public:

string addStrings(string num1, string num2) {

int len1 = num1.length(), len2 = num2.length();

for(int i = 0; i < len1 / 2; i++)

swap(num1[i], num1[len1 - i - 1]);

for(int i = 0; i < len2 / 2; i++)

swap(num2[i], num2[len2 - i - 1]);

string result = "";

int sign = 0, p = 0, q = 0;

while(p < len1 && q < len2) {

int t = (num1[p] - '0') + (num2[q] - '0') + sign;

if(t >= 10) {

t = t - 10;

sign = 1;

} else {

sign = 0;

}

result += (char)(t + '0');

p++;

q++;

}

while(p < len1) {

int t = (num1[p] - '0') + sign;

if(t >= 10) {

t = t - 10;

sign = 1;

} else {

sign = 0;

}

result += (char)(t + '0');

p++;

}

while(q < len2) {

int t = (num2[q] - '0') + sign;

if(t >= 10) {

t = t - 10;

sign = 1;

} else {

sign = 0;

}

result += (char)(t + '0');

q++;

}

if(sign == 1)

result += '1';

int len = result.length();

for(int i = 0; i < len / 2; i++) {

swap(result[i], result[len - 1 - i]);

}

return result;

}

};