liuchuo – 第103页 – 我不管，反正我最萌～

LeetCode 766. Toeplitz Matrix

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512

In the above grid, the diagonals are “[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”, and in each diagonal all elements are the same, so the answer is True.
Example 2:

Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal “[1, 2]” has different elements.
Note:

matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].

题目大意：如果从左上角到右下角的每个对角线具有相同的元素，则矩阵是Toeplitz。给一个矩阵判断它是否是Toeplitz矩阵~

分析：对于每一个元素matrix[i][j]，都判断它是否等于它的右上角元素matrix[i-1][j-1]，如果不相等就返回false，否则循环结束后返回true

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        for (int i = 1; i < matrix.size(); i++)
            for (int j = 1; j < matrix[0].size(); j++)
                if (matrix[i][j] != matrix[i-1][j-1]) return false;
        return true;
    }
};

class Solution {

public:

bool isToeplitzMatrix(vector<vector<int>>& matrix) {

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

for (int j = 1; j < matrix[0].size(); j++)

if (matrix[i][j] != matrix[i-1][j-1]) return false;

return true;

}

};

LeetCode 771. Jewels and Stones

You are given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”.

Example 1:

Input: J = “aA”, S = “aAAbbbb”
Output: 3
Example 2:

Input: J = “z”, S = “ZZ”
Output: 0
Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

题目大意：J是珠宝，S是自己拥有的石头，判断自己拥有的石头中有多少个珠宝～
分析：将J中的所有字符在hash数组中标记为1，再遍历S，统计hash == 1的个数即为所求～

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int ans = 0, hash[256] = {0};
        for (auto i : J) hash[i] = 1;
        for (auto i : S) if (hash[i]) ans++;
        return ans;
    }
};

class Solution {

public:

int numJewelsInStones(string J, string S) {

int ans = 0, hash[256] = {0};

for (auto i : J) hash[i] = 1;

for (auto i : S) if (hash[i]) ans++;

return ans;

}

};

LeetCode 775. Global and Local Inversions

We have some permutation A of [0, 1, …, N – 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.
Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.
Note:

A will be a permutation of [0, 1, …, A.length – 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

题目大意：全局反转次数是0 <= i <j <N且A [i]> A [j]的i <j的个数，局部反转的次数是0 <= i <N且A [i]> A [i + 1]的i的个数。当且仅当全局反转的次数等于本地反转的次数时才返回true。

分析：局部反转属于全局反转，所以说这个数组里只允许出现相邻的两个数字是大小反转的，其他的若是间隔的两个数字，都只能是从小到大的顺序~

A[i]必定只能在它本应在的位置或这个位置的左边一个或者右边一个，不然必定会把比它大的两个数字挤到前面或者把比它小的两个数字挤到后面，因为题目中已经说明它所有的数字是0～n-1的一个排列，那么A[i]-i的绝对值必定<=1，否则就不满足条件～

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) 
            if (abs(A[i] - i) >= 2) return false;
        return true;
    }
};

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

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

if (abs(A[i] - i) >= 2) return false;

return true;

}

};

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;

}

};