365天挑战LeetCode1000题——Day 038 公交站间的距离 + 基于时间的键值存储 + 转变数组后最接近目标值的数组和 + 有界数组中指定下标处的最大值

1184. 公交站间的距离

代码实现（自解）

class Solution {
    
public:
    int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
    
        int n = 0;
        int total = 0;
        for (int i = 0; i < distance.size(); i++) {
    
            if ((i + start) % distance.size() == destination) n = total;
            total += distance[(i + start) % distance.size()];
        }
        return min(total - n, n);
    }
};

---

981. 基于时间的键值存储

代码实现（自解）

class TimeMap {
    
public:
    map<string, vector<pair<int, string>>> _map;
    TimeMap() {
    

    }
    
    void set(string key, string value, int timestamp) {
    
        _map[key].push_back(make_pair(timestamp, value));
    }
    
    string get(string key, int timestamp) {
    
        if (!_map.count(key)) return "";
        vector<pair<int, string>>& v = _map[key];
        if (v[0].first > timestamp) return "";
        int l = 0, r = v.size() - 1;
        while (l < r) {
    
            int m = (l + r + 1) >> 1;
            if (v[m].first <= timestamp) l = m;
            else r = m - 1;
        }
        return v[l].second;
    }
};

/** * Your TimeMap object will be instantiated and called as such: * TimeMap* obj = new TimeMap(); * obj->set(key,value,timestamp); * string param_2 = obj->get(key,timestamp); */

---

1300. 转变数组后最接近目标值的数组和

代码实现（自解）

class Solution {
    
public:
    int findBestValue(vector<int>& arr, int target) {
    
        int n = arr.size();
        if (n >= 2 * target) return 0;
        int l = 0, r = *max_element(arr.begin(), arr.end());
        int bestDiff = INT_MAX;
        int bestVal = INT_MAX;
        while (l < r) {
    
            int m = (l + r + 1) >> 1;
            int sum = 0;
            for (int num : arr) {
    
                sum += min(num, m);
            }
            if (abs(sum - target) < bestDiff) {
    
                bestVal = m;
                bestDiff = abs(sum - target);
            }
            else if (abs(sum - target) == bestDiff) {
    
                bestVal = min(m, bestVal);
            }
            if (sum <= target) l = m;
            else r = m - 1;
        }
        return bestVal;
    }
};

---

1802. 有界数组中指定下标处的最大值

代码实现（自解）

class Solution {
    
public:
    int maxValue(int n, int index, int maxSum) {
    
        int l = 1, r = maxSum;
        while (l < r) {
    
            int m = (l + r + 1) >> 1;
            long long sum = 0;
            if (m - index > 0) {
    
                sum += (long long) (2 * m - index) * (index + 1) / 2;
            }
            else {
    
                sum += (long long) (m + 1) * m / 2 + index - m + 1;
            }
            if (m + index + 1 - n > 0) {
    
                sum += (long long) (2 * m + index - n) * (n - index - 1) / 2;
            }
            else {
    
                sum += (long long) m * (m - 1) / 2 + n - index - m;
            }
            if (sum <= maxSum) l = m;
            else r = m - 1;
        }
        return l;
    }
};

---