liuchuo – 第164页

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;

}

};

LeetCode 453. Minimum Moves to Equal Array Elements

Contributors: amehrotra2610
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

分析：每次n-1个数都+1，最后所有数都相等，其实等价于每次将其中一个数-1，最后所有数都相等。
因为每次只能减一个数，那肯定是将除了最小数minn之外的其他所有数一次次减，直到他们等于都最小数minn。所以cnt就等于所有数与最小数之间的差距的和（因为每次只能减去一个数，且只能减去1，所以差为多少就要减去多少次～）
先求出数组的最小值minn，然后累加的所有数和minn之间的差即为所求～

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int minn = INT_MAX;
        for(int i = 0; i < nums.size(); i++)
            minn = min(minn, nums[i]);
        int cnt = 0;
        for(int i = 0; i < nums.size(); i++)
            cnt += nums[i] - minn;
        return cnt;
    }
};

class Solution {

public:

int minMoves(vector<int>& nums) {

int minn = INT_MAX;

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

minn = min(minn, nums[i]);

int cnt = 0;

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

cnt += nums[i] - minn;

return cnt;

}

};