liuchuo – 第165页

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;

}

};

LeetCode 434. Number of Segments in a String

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: “Hello, my name is John”
Output: 5

分析：一旦出现不是空格的s[i]并且他前一个不和他连续，那么就cnt++; 如果遇到是空格，重新将flag标记为0表示当前s[i]和下一个s[i]不连续～

class Solution {
public:
    int countSegments(string s) {
       int cnt = 0, flag = 0;
       for(int i = 0; i < s.length(); i++) {
           if(s[i] != ' ' && flag == 0) {
               cnt++;
               flag = 1;
           } else if(s[i] == ' ') {
               flag = 0;
           }
        }
        return cnt;
    }
};

class Solution {

public:

int countSegments(string s) {

int cnt = 0, flag = 0;

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

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

cnt++;

flag = 1;

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

flag = 0;

}

return cnt;

}

};

【C++】isalpha、islower、isupper、isalnum、isblank、isspace函数头文件

isalpha、islower、isupper、isalnum、isblank、isspace这些函数都在<cctype>的头文件里面，下图是它们所表示的范围：

总的来说就是：

isalpha 字母（包括大写、小写）islower（小写字母）isupper（大写字母）isalnum（字母大写小写+数字）isblank（space和\t）isspace（space、\t、\r、\n）

LeetCode 438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

分析：先将p字符串的所有字母的个数标记在hash数组中。设p的字符串长度为lenp，那么从字符串s的第一位开始分别找lenp长度的字串标记temphash，比较temphash是否等于hash，如果等于说明是anagram字符串，push_back到vector里面，最后返回vector

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result, hash(26, 0);
        int lenp = p.length(), lens = s.length();
        for(int i = 0; i < lenp; i++) {
            hash[p[i] - 'a']++;
        }
        for(int i = 0; i <= lens - lenp; i++) {
            vector<int> temphash(26, 0);
            for(int j = i; j < i + lenp; j++)
                temphash[s[j] - 'a']++;
            if(temphash == hash)
                result.push_back(i);
        }
        return result;
    }
};

class Solution {

public:

vector<int> findAnagrams(string s, string p) {

vector<int> result, hash(26, 0);

int lenp = p.length(), lens = s.length();

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

hash[p[i] - 'a']++;

}

for(int i = 0; i <= lens - lenp; i++) {

vector<int> temphash(26, 0);

for(int j = i; j < i + lenp; j++)

temphash[s[j] - 'a']++;

if(temphash == hash)

result.push_back(i);

}

return result;

}

};