1492. The kth Factor of n -------M

Given two positive integers n and k.

A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

 

Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Example 4:

Input: n = 1, k = 1
Output: 1
Explanation: Factors list is [1], the 1st factor is 1.

Example 5:

Input: n = 1000, k = 3
Output: 4
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].

 

Constraints:

• 1 <= k <= n <= 1000

 A:

不知道考什么。 一个个试就pass了

class Solution {
public:
    int kthFactor(int n, int k) {
        int c = 0;
        for(int i =1;i<=n;i++){
            if(n % i ==0){
                ++c;
                if(c==k){
                    return i;
                }
            }
        }
        return -1;
    }
};

1415. The k-th Lexicographical String of All Happy Strings of Length n -----M

 A happy string is a string that:

• consists only of letters of the set ['a', 'b', 'c'].
• s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings "abc", "ac", "b" and "abcbabcbcb" are all happy strings and strings "aa", "baa" and "ababbc" are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

 

Example 1:

Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".

Example 2:

Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.

Example 3:

Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"

Example 4:

Input: n = 2, k = 7
Output: ""

Example 5:

Input: n = 10, k = 100
Output: "abacbabacb"

 

Constraints:

• 1 <= n <= 10
• 1 <= k <= 100

A:

就是实现题。  一个个数呗  （唯一可能tricky的地方就是 需要k--, 来变成 0 based

class Solution {
public:
    string getHappyString(int n, int k) {
        vector<int> c(n+1,1);
        for(int j = n-1; j>=0; j--){
            c[j] = (j==0?3:2) * c[j+1];
        }
        string res = "";
        k--;// zero index
        if(c[0] <= k){ // since we have k-- above
            return res;
        }
        for(int i =0;i<n;i++){
            // find how many next iter count
            int count = k/c[i+1]; // count can be 0, 1,2
            if(i == 0){
                res+= ('a'+count);
            }else{
                res += getNext(res.back(), count);
            }
            k -= count * c[i+1];
        }
        return res;
    }
private:
    char getNext(char pre, int count){ // count can only be 0 or 1
        if(pre == 'a'){
            return count==0? 'b' : 'c';
        }else if(pre == 'b'){
            return count==0? 'a' : 'c';
        }else{// if(pre == 'c'){
            return count==0? 'a' : 'b';
        }
    }
};

1471. The k Strongest Values in an Array ------M

 Given an array of integers arr and an integer k.

A value arr[i] is said to be stronger than a value arr[j] if |arr[i] - m| > |arr[j] - m| where m is the median of the array.
If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j].

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

• For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
• For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

 

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

 

Constraints:

• 1 <= arr.length <= 10^5
• -10^5 <= arr[i] <= 10^5
• 1 <= k <= arr.length

A:

就是排序，然后前后取

class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());//default is the assending order
        int n = arr.size();
        int median = arr[(n-1)/2];
        
        vector<int> res;
        int begin = 0, end = n-1;
        while(res.size()<k){
            if(abs(arr[begin] -median) > abs(arr[end] - median)  ){
                res.push_back(arr[begin++]);
            }else{ // if(abs(arr[begin] -median) < abs(arr[end] - median)  ){
                res.push_back(arr[end--]);
            }
        }
        return res;
    }
};