LeetCode_Nov_5th_Week

November 29th : 786. 第 K 个最小的素数分数
December 1st : 1446. 连续字符
December 2nd : 506. 相对名次
December 3rd : 1005. K 次取反后最大化的数组和
December 4th : 383. 赎金信

---

November 29th : 786. 第 K 个最小的素数分数

class Solution {
    
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
    
        int n = arr.size();
        auto cmp = [&](const pair<int, int>& x, const pair<int, int>& y) {
    
        	//Fractions are cross-multiplied,The comparison relationship can be obtained as follows：
            return arr[x.first] * arr[y.second] > arr[x.second] * arr[y.first];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
		//Initialize the elements in the priority queue,将n-1The elements in the list are added to the priority queue 
        for (int j = 1; j < n; ++j) q.emplace(0, j);
		//Take the smallest value from the priority queue in order,And join the next smallest value in the corresponding list,循环k次,The head of the priority queue is what is requested
        for (int _ = 1; _ < k; ++_) {
    
            auto [i, j] = q.top();
            q.pop();
            if (i + 1 < j) q.emplace(i + 1, j);
        }
        return {
    arr[q.top().first], arr[q.top().second]};
    }
};
/********************************************************************************************/
//brutal force. 超时
class Solution {
    
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
    
        unordered_map<float, vector<int>> mp;
        priority_queue<float, vector<float>, greater<float>> pq;
        for(int i = 0; i < arr.size(); ++i) {
    
            for(int j = i+1; j < arr.size(); ++j) {
    
                float frac = (float)arr[i] / (float)arr[j];
                pq.push(frac);
                mp[frac] = {
    arr[i], arr[j]};
            }
        }
        while(k-- != 1) {
    cout << pq.top() << endl; pq.pop();};
        return mp[pq.top()];
    }
};

---

December 1st : 1446. 连续字符

典型的滑动窗口问题,Whether the characters newly added to the window are consistent with the characters in the window,If they are consistent, the window will expand,If not, reset the window.

class Solution {
    
public:
    int maxPower(string s) {
    
        int ret = 0, l = 0, r = 0;
        while(r < s.size()) {
    
            if(s[l] == s[r]) ret = max(ret, r-l+1);
            else l = r;
            r++;
        }
        return ret;
    }
};

---

December 2nd : 506. 相对名次

哈希表+排序,时间复杂度$O(nlogn)$.

class Solution {
    
public:
    vector<string> findRelativeRanks(vector<int>& score) {
    
        unordered_map<int, int> mp;
        vector<string> vecStr(score.size());
        for(int i = 0; i < score.size(); ++i) mp[score[i]] = i;
        sort(score.begin(), score.end(), greater<int>());
        vecStr[mp[score[0]]] = "Gold Medal";
        if(score.size() > 1) vecStr[mp[score[1]]] = "Silver Medal";
        if(score.size() > 2) vecStr[mp[score[2]]] = "Bronze Medal";
        for(int i = 3; i < score.size(); ++i) vecStr[mp[score[i]]] = to_string(i+1);
        return vecStr;
    }
};

---

open anotherO(n+k)的数组,进行一次遍历,Get each score inscore数组中的下标,Then traverse the array from left to right,And modify the resulting string array according to the table below.

class Solution {
    
public:
    vector<string> findRelativeRanks(vector<int>& score) {
    
        int max_score = *max_element(score.begin(), score.end()); //Get the maximum value of the score
        vector<int> index(max_score + 1, -1);  // 申请一个包含max+1个全是-1的数组
        // Set the value at the corresponding subscript of this element to the index subscript in the original array
        for(int i = 0; i < score.size(); i++) index[score[i]] = i; 

        vector<string> vecStr(score.size());//存放输出结果
        int rank = score.size(), j = 0; //rank排名, j是index数组的下标.
        while(rank > 0){
    
            if(index[j] != -1){
    
                if(rank == 1)      vecStr[index[j]] = "Gold Medal"; 
                else if(rank == 2) vecStr[index[j]] = "Silver Medal"; 
                else if(rank == 3) vecStr[index[j]] = "Bronze Medal"; 
                else vecStr[index[j]] = to_string(rank); 
                rank--;
            }
            j++;
        }
        return vecStr;
    }
};

---

December 3rd : 1005. K 次取反后最大化的数组和

Sorts an array by the absolute value of the numbers in the array,Then invert the non-positive numbers in it,If the non-positive number is greater than $k$ 个,Then if the remaining inversion times are even, the sum of the array can be directly returned,If it is odd, it will be the first element of the array/The element with the smallest absolute value is reversed and returned to the array to accumulate the sum.

//思想：If they can be all non-negative numbers, they will all become non-negative numbers,
//If all are non-negative, there are still an odd number of inversions remaining,
//Then the smallest non-negative number after the reversal operation is reversed and returned to the accumulated sum
class Solution {
    
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() && k > 0; ++i) {
    
            if(nums[i] > 0) break;
            nums[i] = -nums[i];
            k--;
        }
        sort(nums.begin(), nums.end()); //Get the new numerical ordering,A non-positive number with a larger absolute value was previously inverted
        if(k & 0x1) return -nums[0] + accumulate(nums.begin()+1, nums.end(), 0);
        else return accumulate(nums.begin(), nums.end(), 0);
    }
};
/*********************************************************************************************************/
//more intuitive
class Solution {
    
    static bool cmp(int a, int b) {
    return abs(a) > abs(b);}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end(), cmp);  //按照绝对值大小排序,大的在前 
        for (int i = 0; i < nums.size() && k > 0; ++i) {
     //遍历数组,Reverse non-negative numbers
            if (nums[i] < 0) {
    
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k & 0x1) nums[nums.size() - 1] *= -1; //If there are an odd number of inversion operations remaining,Invert the number with the smallest absolute value
		return accumulate(nums.begin(), nums.end(), 0); //Returns the cumulative sum of the array
    }
};

---

December 4th : 383. 赎金信

统计$magazine$The frequency of the characters in it,然后对应$ransom-note$The frequency of characters in .If it traverses the whole$ransom-note$,所有$magazine$The frequency of characters in is greater than or equal to$ransom-note$The character frequency is returnedtrue,否则返回false.

class Solution {
    
public:
    bool canConstruct(string ransomNote, string magazine) {
    
        int dict[26] = {
    0};
        //vector<int> dict(26, 0);
        for(int i = 0; i < magazine.size(); ++i) dict[magazine[i]-'a']++;
        for(int i = 0; i < ransomNote.size(); ++i) {
    
            if(dict[ransomNote[i]-'a'] == 0) return false;
            dict[ransomNote[i]-'a']--;
        }
        return true;
    }
};

---