LeetCode OJ – 第28页

LeetCode 401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

分析：小时数h从0～11，分钟数m从0～59，把他们每一个转换为一个二进制整体，初始化为bitset，看bitset中1的个数是否为num，如果是就将h和m构成一个字符串加入到result字符串数组中，最后返回result～～

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        for(int h = 0; h < 12; h++) {
            for(int m = 0; m < 60; m++) {
                bitset<10> b(h << 6 | m);
                if(b.count() == num) {
                    string temp = to_string(h) + ":";
                    if(m < 10)
                        temp += "0";
                    temp += to_string(m);
                    result.push_back(temp);
                }
            }
        }
        return result;
    }
};

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> result;

for(int h = 0; h < 12; h++) {

for(int m = 0; m < 60; m++) {

bitset<10> b(h << 6 | m);

if(b.count() == num) {

string temp = to_string(h) + ":";

if(m < 10)

temp += "0";

temp += to_string(m);

result.push_back(temp);

}

return result;

}

};

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;

}

};