LeetCode OJ – 第29页

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;

}

};

LeetCode 412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
“1”,
“2”,
“Fizz”,
“4”,
“Buzz”,
“Fizz”,
“7”,
“8”,
“Fizz”,
“Buzz”,
“11”,
“Fizz”,
“13”,
“14”,
“FizzBuzz”
]

分析：几个if else 语句分别对是否能被15整除、5整除、3整除进行赋值～

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> result(n);
        for(int i = 0; i < n; i++) {
            if((i + 1) % 15 == 0)
                result[i] = "FizzBuzz";
            else if((i + 1) % 5 == 0)
                result[i] = "Buzz";
            else if((i + 1) % 3 == 0)
                result[i] = "Fizz";
            else
                result[i] = to_string(i + 1);
        }
        return result;
    }
};

class Solution {

public:

vector<string> fizzBuzz(int n) {

vector<string> result(n);

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

if((i + 1) % 15 == 0)

result[i] = "FizzBuzz";

else if((i + 1) % 5 == 0)

result[i] = "Buzz";

else if((i + 1) % 3 == 0)

result[i] = "Fizz";

else

result[i] = to_string(i + 1);

}

return result;

}

};

LeetCode 455. Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

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

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

分析：先将g数组和s数组从小到大排序～ i指针遍历g数组，j指针遍历s数组，如果当前g[i] <= s[j]，也就是当前糖果j能够分给当前小朋友i，那就分配，并且将i指针指向下一个小朋友，cnt同时也要累加一个～如果当前糖果不能分配给当前小朋友，说明糖果j不能分给任何人了，因为没有比小朋友i需要的还要少的小朋友了（i后面的数都比i大）。所以无论是否分配，都把j向后移动一次～这样能保证需求量小的所有小朋友都分配得到能够分配的糖果，此时的cnt也是所求的贪心最大值～避免了大材小用（大糖果分配给需求量小的小朋友）的情况～

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int cnt = 0, i = 0, j = 0;
        while(i < g.size() && j < s.size()) {
            if(g[i] <= s[j]) {
                cnt++;
                i++;
            }
            j++;
        }
        return cnt;
    }
};

class Solution {

public:

int findContentChildren(vector<int>& g, vector<int>& s) {

sort(g.begin(), g.end());

sort(s.begin(), s.end());

int cnt = 0, i = 0, j = 0;

while(i < g.size() && j < s.size()) {

if(g[i] <= s[j]) {

cnt++;

i++;

}

j++;

}

return cnt;

}

};