LeetCode_Dec_3rd_Week

December 20th : 475. 供暖器
December 21st : 1154. 一年中的第几天

December 20th : 475. 供暖器

对于每个房屋,Either use the front heater,Either use the latter,the two are close,得到距离;for all houses,Choose the largest of the above distances.

这里需要注意的是,for a house,It has heating only in the front or only in the back,This situation needs to be considered.

during the search for boundary values,Commonly used in binary search(For the bisection of the boundary,Intuitively, it is to divide the ordered sequence in half),这里stl algorithm中的upper_bound和lower_bound很好用,具体的函数签名如下：

lower_boundCorrespondingly, the first one is not less thanvalueThe iterator corresponding to the value of ,That is, greater than or equal to the left boundary of the interval,这样称为lower bound就不难理解了.

同理,upper_boundWhat is sought is not greater thanvaluethe right boundary of the interval,That is, the first greater thanvalue的值的迭代器,That is to sayupper bound.

class Solution {
    
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
    
        sort(heaters.begin(), heaters.end()); //Sort the heat sink locations
        int ret = 0; 
        for(auto house : houses) {
    
            int cur = INT_MAX; //The minimum heating radius required for the current house
            auto right = lower_bound(heaters.begin(), heaters.end(), house); //Find the corresponding radiator location on the right
            if(right != heaters.end()) cur = *right - house; //If there is a radiator on the right side,Then update the heating radius
            if(right != heaters.begin()) cur = min(cur, house - *(right-1)); //If there is a radiator on the left side as well
            ret = max(cur, ret); //The final result takes the maximum value of the heating radius of each house
        }
        return ret;
    }
};

December 21st : 1154. 一年中的第几天

若是dayOfYearas part of the resident process,and frequently called,可以在SolutionOpen up a prefix and array in the class,Records the date sum of the month preceding the current month,If only called occasionally,You can add it on the spot.

闰年的定义,我都记不清了,难受(摘自百度百科)：

• 普通闰年：公历年份是4的倍数,且不是100的倍数的,为闰年（如2004年、2020年等就是闰年）.
• 世纪闰年：公历年份是整百数的,必须是400的倍数才是闰年（如1900年不是闰年,2000年是闰年）

class Solution {
    
public:
    int dayOfYear(string date) {
    
        vector<int> days = {
    0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        for(int i = 1; i <= 12; ++i) days[i] += days[i-1];
        int year = atoi(date.substr(0, 5).c_str()); 
        int month = atoi(date.substr(5, 3).c_str());
        int day = atoi(date.substr(8, 2).c_str());
        cout << year << " " <<  month << " " << day << endl;
        return day + 
               ((((year % 400 == 0 && year % 100 == 0) || (year % 100 != 0 && year % 4 == 0)) && month > 2) ? 
               days[month-1] + 1 : days[month-1]);
    }
};