Code – 第103页

LeetCode 768. Max Chunks To Make Sorted II

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn’t sorted.
Example 2:

Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Note:

arr will have length in range [1, 2000].
arr[i] will be an integer in range [0, 10**8].

题目大意：给一个排列，可能有重复元素，我们将数组拆分成一些“块”（分区），并对每个块进行单独排序。连接它们之后，结果等于排序后的数组。问最多能够分成多少个分区（块）

分析：因为有重复元素，可以考虑判断累加和的方式，排序后的数组前i个元素累加的和等于原数组前i个数累加的和时可以分为一个块～

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int sum1 = 0, sum2 = 0, ans = 0;
        vector<int> t = arr;
        sort(t.begin(), t.end());
        for(int i = 0; i < arr.size(); i++) {
            sum1 += t[i];
            sum2 += arr[i];
            if(sum1 == sum2) ans++;
        }
        return ans;
    }
};

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int sum1 = 0, sum2 = 0, ans = 0;

vector<int> t = arr;

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

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

sum1 += t[i];

sum2 += arr[i];

if(sum1 == sum2) ans++;

}

return ans;

}

};

LeetCode 769. Max Chunks To Make Sorted

Given an array arr that is a permutation of [0, 1, …, arr.length – 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn’t sorted.
Example 2:

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
Note:

arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, …, arr.length – 1].

题目大意：给0～arr.length-1的一个排列，我们将数组拆分成一些“块”（分区），并对每个块进行单独排序。连接它们之后，结果等于排序后的数组。问最多能够分成多少个分区（块）

分析：因为数组的排序后正确顺序应该是arr[i]处的数是i。所以，遍历数组，每次将最大的那个值标记为maxn，maxn必须在i处才能满足对0～i数字排序后能够恰好是正确的位置，此时ans+1，表示前面的可以组为一个“块”，最后ans即为所求的值～
再解释详细些：maxn是第0～i个数字中的最大值，遍历的过程中如果maxn==i，就保证了前面i-1个数字必然都比maxn小（因为maxn是0～i中的最大值），则第0～i个数字必然能排列成正确顺序，以此类推，找到下一个满足maxn==i的地方（记为j），则i+1～j又能分为一个块…直到遍历到最后一个数为止得到答案～

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0;
        for (int i = 0, maxn = 0; i < arr.size(); i++) {
            maxn = max(arr[i], maxn);
            if (maxn == i) ans++;
        }
        return ans;
    }
};

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

for (int i = 0, maxn = 0; i < arr.size(); i++) {

maxn = max(arr[i], maxn);

if (maxn == i) ans++;

}

return ans;

}

};

LeetCode 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

题目大意：给一组区间，合并他们所有的重叠区间

分析：先对所有区间按左区间从小到大排序，排序后将第一个区间放入ans结果数组中，遍历原数组，如果当前ans数组的最后一个区间的end小于intervals[i]的start，说明与其没有交集，那么就将这个intervals[i]放入结果数组中。否则说明有交集，就将当前ans数组的最后一个区间的end更新为ans.back().end和intervals[i].end()中较大的那一个，最后返回ans数组即为所求～注意如果intervals中不含元素要返回空集～

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> ans;
        if (intervals.size() == 0) return ans;
        sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
        ans.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if(ans.back().end < intervals[i].start) 
                ans.push_back(intervals[i]);
            else
                ans.back().end = max(ans.back().end, intervals[i].end);
        }
        return ans;
    }
};

/**

* Definition for an interval.

* struct Interval {

* int start;

* int end;

* Interval() : start(0), end(0) {}

* Interval(int s, int e) : start(s), end(e) {}

* };

class Solution {

public:

vector<Interval> merge(vector<Interval>& intervals) {

vector<Interval> ans;

if (intervals.size() == 0) return ans;

sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});

ans.push_back(intervals[0]);

for (int i = 1; i < intervals.size(); i++) {

if(ans.back().end < intervals[i].start)

ans.push_back(intervals[i]);

else

ans.back().end = max(ans.back().end, intervals[i].end);

}

return ans;

}

};

LeetCode 49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note: All inputs will be in lower-case.

题目大意：给一组字符串，将这些字符串分组，按照同字母异序词为一组

分析：每一个s排序后的字符串为t，将s保存在以t为键的map中，这样同字母异序词即为一组。遍历map中的每一个vector<string>，将其保存在ans中，ans即为结果～

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        map<string, vector<string>> mp;
        for (auto s : strs) {
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        for (auto m : mp) {
            vector<string> temp(m.second.begin(), m.second.end());
            ans.push_back(temp);
        }
        return ans;
    }
};

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> ans;

map<string, vector<string>> mp;

for (auto s : strs) {

string t = s;

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

mp[t].push_back(s);

}

for (auto m : mp) {

vector<string> temp(m.second.begin(), m.second.end());

ans.push_back(temp);

}

return ans;

}

};

LeetCode 561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

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

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

题目大意：给2n个数，请把数字分为2个一组，问所有组（取每组数的较小的那一数字）累加的和最大为多少～

分析：把数组从小到大排列，第1个、第3个、…第2n-1个数字之和即为所求～

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i+=2)
            ans += nums[i];
        return ans;
    }
};

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

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

int ans = 0;

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

ans += nums[i];

return ans;

}

};

LeetCode 43. Multiply Strings

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

Note:

The length of both num1 and num2 is < 110.
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.

题目大意：给两个用字符串表示的非负整数，计算他们的乘积，结果用string表示～

分析：先将字符串num1和num2倒置，然后i和j分别遍历num1和num2，将num1[i] * num2[j]的结果加上v[i+j]本身的结果保存为temp，temp的余数保存在v[i+j]中，temp的进位累加在v[i+j+1]中。从后向前从第一个非0数字开始将数字转化为字符保存在result字符串中，result即为所求字符串～

class Solution {
public:
    string multiply(string num1, string num2) {
        string result = "";
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int len1 = num1.length(), len2 = num2.length();
        vector<int> v(len1 + len2, 0);
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                int temp = v[i + j] + (num1[i] - '0') * (num2[j] - '0');
                v[i + j] = temp % 10;
                v[i + j + 1] += temp / 10;
            }
        }
        int flag = 0;
        for (int i = len1 + len2 - 1; i >= 0; i--) {
            if (flag == 0 && v[i] != 0) flag = 1;
            if (flag == 1) result += to_string(v[i]);
        }
        return result == "" ? "0" : result;
    }
};

class Solution {

public:

string multiply(string num1, string num2) {

string result = "";

reverse(num1.begin(), num1.end());

reverse(num2.begin(), num2.end());

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

vector<int> v(len1 + len2, 0);

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

for (int j = 0; j < len2; j++) {

int temp = v[i + j] + (num1[i] - '0') * (num2[j] - '0');

v[i + j] = temp % 10;

v[i + j + 1] += temp / 10;

}

int flag = 0;

for (int i = len1 + len2 - 1; i >= 0; i--) {

if (flag == 0 && v[i] != 0) flag = 1;

if (flag == 1) result += to_string(v[i]);

}

return result == "" ? "0" : result;

}

};