Code – 第102页

LeetCode 760. Find Anagram Mappings

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]
We should return
[1, 4, 3, 2, 0]
as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at B[4], and so on.
Note:

A, B have equal lengths in range [1, 100].
A[i], B[i] are integers in range [0, 10^5].

题目大意：给两个数组A和B，B是A的同字母异序词，返回一个等长数组P，其中P[i] = j，表示A的第i个元素在B的第j个元素处，如果有多个答案，返回一个即可～

分析：设置一个二维数组v，将数字i对应的在B数组中的下标放在v[i]中，这样遍历A数组，每次取出一个v[A[i]]放入ans数组对应的i下标处即可～

class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        int len = A.size();
        vector<int> ans(len), hash(len), v[100001];
        for (int i = 0; i < len; i++) v[B[i]].push_back(i);
        for (int i = 0; i < len; i++) {
            ans[i] = v[A[i]].back();
            v[A[i]].pop_back();
        }
        return ans;
    }
};

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

int len = A.size();

vector<int> ans(len), hash(len), v[100001];

for (int i = 0; i < len; i++) v[B[i]].push_back(i);

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

ans[i] = v[A[i]].back();

v[A[i]].pop_back();

}

return ans;

}

};

LeetCode 762. Prime Number of Set Bits in Binary Representation

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.
(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)
Example 1:
Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)
Example 2:
Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
Note:
L, R will be integers L <= R in the range [1, 10^6].
R – L will be at most 10000.

题目大意：给两个数L和R，在[L, R]区间寻找数字的二进制中1的个数是素数的数字个数。

分析：R不超过10的6次方，也就是不超过2的20次方，那么判断是否为素数只需判断是否等于2 3 5 7 11 13 17 19即可，用bitset也只需20位表示即可，用count函数计算1的个数，然后用cnt统计后返回～

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        int cnt = 0, hash[20] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1};
        for (int i = L; i <= R; i++) {
            bitset<20> b(i);
            if(hash[b.count()]) cnt++;
        }
        return cnt;
    }
};

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int cnt = 0, hash[20] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1};

for (int i = L; i <= R; i++) {

bitset<20> b(i);

if(hash[b.count()]) cnt++;

}

return cnt;

}

};

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;

}

};