LeetCode OJ – 第7页 – 柳婼の blog

LeetCode 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:
Input: s = “abcdefg”, k = 2
Output: “bacdfeg”
Restrictions:
The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

题目大意：给一个字符串s和一个整数k，每2k长度倒置前k个字符串，如果最后剩余的长度小于k则全都倒置，否则如果剩余的长度大于k小于2k，倒置前k个，返回倒置后的字符串～

分析：遍历字符串，步长为2k，每次倒置s.begin() + i～s.begin() + i + k的字符串，如果i + k > s.length()就倒置s.begin() + i～s.begin() + s.length()即可～O(∩_∩)O～

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.length(); i+=2*k) {
            int t = min((i + k), (int)s.length());
            reverse(s.begin() + i, s.begin() + t);
        }
        return s;
    }
};

class Solution {

public:

string reverseStr(string s, int k) {

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

int t = min((i + k), (int)s.length());

reverse(s.begin() + i, s.begin() + t);

}

return s;

}

};

LeetCode 739. Daily Temperatures

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

分析：用栈解决，i从0～len-1，每次将栈顶元素小于temperatures[i]的出栈，因为对于出栈的元素来说它已经找到了第一个大于它的值，剩余在栈中的都是未找到大于它本身的值的元素，则继续等待下一个temperatures[i]。每次将temperatures[i]压入栈中，等待接下来遇到比它大的值时出栈～将i与栈顶元素下标的差值保存在栈顶元素的下标所对应的ans中，最后返回ans即可～

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> s;
        int len = temperatures.size();
        vector<int> ans(len);
        for (int i = 0; i < len; i++) {
            while(!s.empty() && temperatures[i] > s.top().first) {
                ans[s.top().second] = i - s.top().second;
                s.pop();
            }
            s.push(pair<int, int>(temperatures[i], i));
        }
        return ans;
    }
};

class Solution {

public:

vector<int> dailyTemperatures(vector<int>& temperatures) {

stack<pair<int, int>> s;

int len = temperatures.size();

vector<int> ans(len);

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

while(!s.empty() && temperatures[i] > s.top().first) {

ans[s.top().second] = i - s.top().second;

s.pop();

}

s.push(pair<int, int>(temperatures[i], i));

}

return ans;

}

};

LeetCode 744. Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.

Examples:
Input:
letters = [“c”, “f”, “j”]
target = “a”
Output: “c”

Input:
letters = [“c”, “f”, “j”]
target = “c”
Output: “f”

Input:
letters = [“c”, “f”, “j”]
target = “d”
Output: “f”

Input:
letters = [“c”, “f”, “j”]
target = “g”
Output: “j”

Input:
letters = [“c”, “f”, “j”]
target = “j”
Output: “c”

Input:
letters = [“c”, “f”, “j”]
target = “k”
Output: “c”
Note:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

分析：用upper_bound返回第一个大于target的元素所在位置，如果这个位置等于letters.end()说明不存在，则返回letters的第一个值，否则返回it所在位置的元素值即可～

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        auto it = upper_bound(letters.begin(), letters.end(), target);
        return it == letters.end() ? letters[0] : *it;
    }
};

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

auto it = upper_bound(letters.begin(), letters.end(), target);

return it == letters.end() ? letters[0] : *it;

}

};

LeetCode 747. Largest Number At Least Twice of Others

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x. The index of value 6 is 1, so we return 1.
Example 2:
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn’t at least as big as twice the value of 3, so we return -1.
Note:
nums will have a length in the range [1, 50].
Every nums[i] will be an integer in the range [0, 99].

分析：找到最大值maxn、它对应的下标idx和次大值sec，如果次大值sec的两倍比maxn大说明不满足条件返回-1，否则返回idx

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int maxn = INT_MIN, idx = -1, sec = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxn) {
                sec = maxn;
                maxn = nums[i];
                idx = i;
            } else if(nums[i] > sec){
                sec = nums[i];
            }
        }
        return sec * 2 > maxn ? -1 : idx;
    }
};

class Solution {

public:

int dominantIndex(vector<int>& nums) {

int maxn = INT_MIN, idx = -1, sec = INT_MIN;

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

if (nums[i] > maxn) {

sec = maxn;

maxn = nums[i];

idx = i;

} else if(nums[i] > sec){

sec = nums[i];

}

return sec * 2 > maxn ? -1 : idx;

}

};

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;

}

};