LeetCode OJ – 第8页 – 柳婼の blog

LeetCode 763. Partition Labels

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Input: S = “ababcbacadefegdehijhklij”
Output: [9,7,8]
Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.
Note:

S will have length in range [1, 500].
S will consist of lowercase letters (‘a’ to ‘z’) only.

题目大意：给出一个小写字母的字符串S. 我们想把这个字符串分成尽可能多的部分，这样每个字母最多只出现一个部分，并返回一个表示这些部分大小的整数列表。

分析：遍历字符串，找到S[i]在S中最后一次出现的位置标记为end，end位置是当前要切割的字串部分最短的结尾处，当i == end时候说明start～end可以组成一个最短部分串，将这个部分串的长度(end – start + 1)放入ans数组中，然后将start标记为下一个部分串的开始(end+1)，最后返回ans数组～

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> ans;
        for (int i = 0, start = 0, end = 0; i < S.length(); i++) {
            end = max(end, (int)S.find_last_of(S[i]));
            if (i == end) {
                ans.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return ans;
    }
};

class Solution {

public:

vector<int> partitionLabels(string S) {

vector<int> ans;

for (int i = 0, start = 0, end = 0; i < S.length(); i++) {

end = max(end, (int)S.find_last_of(S[i]));

if (i == end) {

ans.push_back(end - start + 1);

start = end + 1;

}

return ans;

}

};

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;

}

};