2024-10-03

  1. 1122. 數(shù)組的相對排序 - 力扣(LeetCode)
    法一:計數(shù)排序 O(n)
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> temp(1001, 0);
        for (int num : arr1) temp[num]++;
        vector<int> ans;
        for (int num : arr2)
            while (temp[num]-- > 0) ans.push_back(num);
        for (int i = 0; i <= 1000; i++)
            while (temp[i]-- > 0) ans.push_back(i);
        return ans;
    }
};

法二:內(nèi)置函數(shù)sort O(nlogn)

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        // <val, idx>
        unordered_map<int, int> arr2Order;
        for (int i = 0; i < arr2.size(); i++)
            arr2Order[arr2[i]] = i;
        sort(arr1.begin(), arr1.end(), [&](int x, int y) {
            int xPos = arr2Order.find(x) != arr2Order.end() 
                      ? arr2Order[x] : arr2Order.size();
            int yPos = arr2Order.find(y) != arr2Order.end() 
                      ? arr2Order[y] : arr2Order.size();
            return xPos < yPos || (xPos == yPos && x < y);
        });
        return arr1;
    }
};
  1. 56. 合并區(qū)間 - 力扣(LeetCode)
    法一:
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), 
            [](const vector<int>& a, const vector<int>& b) {
                return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
            });
        int start = -1, farthest = -1;
        vector<vector<int>> ans;
        for (const vector<int>& interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            if (left <= farthest)
                farthest = max(farthest, right);
            else {
                if (farthest != -1) 
                    ans.push_back({start, farthest});
                start = left;
                farthest = right;
            }
        }
        ans.push_back({start, farthest});
        return ans;
    }
};

法二:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<pair<int, int>> events;
        for (const vector<int>& interval : intervals) {
            events.push_back({interval[0], 1});
            events.push_back({interval[1] + 1, -1});
        }
        sort(events.begin(), events.end());
        int covering = 0;
        int start = 0;
        vector<vector<int>> ans;
        for (auto event : events) {
            if (covering == 0) start = event.first;
            covering += event.second;
            if (covering == 0) ans.push_back({start, event.first - 1});
        }
        return ans;
    }
};
  1. 215. 數(shù)組中的第K個最大元素 - 力扣(LeetCode)
    法一:內(nèi)置sort快排==O(NlogN)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

法二:利用快排partition思想==O(N)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSort(nums, 0, nums.size() - 1, nums.size() - k);
    }

private:
    int quickSort(vector<int>& nums, int l, int r, int idx) {
        if (l >= r) return nums[l];
        int pivot = partition(nums, l, r);
        if (idx <= pivot) return quickSort(nums, l, pivot, idx);
        else return quickSort(nums, pivot + 1, r, idx);
    }

    int partition(vector<int>& nums, int l, int r) {
        int pivotVal = nums[l + rand() % (r - l + 1)];
        while (l <= r) {
            while (nums[l] < pivotVal) l++;
            while (nums[r] > pivotVal) r--;
            if (l < r) {
                swap(nums[l], nums[r]);
                l++; r--;
            }
            else break;
        }
        return r;
    }
};
  1. 104. 貨倉選址 - AcWing題庫
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int pos = a[n / 2];
    long long ans = 0;
    for (int i = 0; i < n; i++) ans += abs(pos - a[i]);
    cout << ans << endl;
    return 0;
}
  1. 493. 翻轉(zhuǎn)對 - 力扣(LeetCode)
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        ans = 0;
        mergeSort(nums, 0, nums.size() - 1);
        return ans;
    }

private:
    int ans;

    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        calc(nums, l, mid, r);
        merge(nums, l, mid, r);
    }

    void merge(vector<int>& nums, int l, int mid, int r) {
        int size = r - l + 1;
        vector<int> temp(size);
        // nums[l, mid][mid+1, r]
        int i = l, j = mid + 1, k;
        for (k = 0; k < size; k++) 
            if (j > r || (i <= mid && nums[i] <= nums[j]))
                temp[k] = nums[i++];
            else
                temp[k] = nums[j++];
        for (k = 0; k < size; k++)
            nums[l + k] = temp[k];
    }

    void calc(vector<int>& nums, int l, int mid, int r) {
        // nums[l, mid][mid+1, r]
        int j = mid + 1;
        for (int i = l; i <= mid; i++) {
            while (j <= r && nums[i] > 2ll * nums[j]) j++;
            ans += (j - mid - 1);
        }
    }
};
  1. 327. 區(qū)間和的個數(shù) - 力扣(LeetCode)
    前綴和+歸并排序
class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        this->lower = lower;
        this->upper = upper;
        long s = 0;
        vector<long> sum{0};
        for (auto &num : nums) {
            s += num;
            sum.push_back(s);
        }
        res = 0;
        countRangeSumRecu(sum, 0, sum.size() - 1);
        return res;
    }

private:
    int lower, upper, res;

    void countRangeSumRecu(vector<long> &sum, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        countRangeSumRecu(sum, left, mid);
        countRangeSumRecu(sum, mid + 1, right);
        calculate(sum, left, mid, right);
        merge(sum, left, mid, right);
    }

    void calculate(vector<long> &sum, int left, int mid, int right) { 
        // 此處左側(cè)[left, mid]的原下標一定小于右側(cè)[mid+1, right]的原下標说搅,
        // 且可以while去累加數(shù)量
        // 這里可以累加没卸,就是merge歸并排序來保證的1.合并的兩側(cè)在各自原下標不相交2.有序
        // 可能講的不清楚。近迁。。
        int l = mid + 1, r = mid + 1;
        for (int i = left; i <= mid; ++i) {
            while (l <= right && sum[l] - sum[i] < lower)
                l++;
            while (r <= right && sum[r] - sum[i] <= upper)
                r++;
            res += (r - l);
        }
    }

    void merge(vector<long> &sum, int left, int mid, int right) {
        int size = right - left + 1;
        vector<long> temp(size, 0);
        int i = left, j = mid + 1, k;
        for (k = 0; k < size; ++k)
            if (j > right || (i <= mid && sum[i] <= sum[j]))
                temp[k] = sum[i++];
            else
                temp[k] = sum[j++];
        for (k = 0; k < size; ++k)
            sum[k + left] = temp[k];
    }
};
  1. 860. 檸檬水找零 - 力扣(LeetCode)
    法一:金額有倍數(shù)關(guān)系即有決策包容性旅急,可以貪心
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        coins[5] = coins[10] = coins[20] = 0;
        for (int bill : bills) {
            coins[bill]++;
            if (!exchange(bill - 5)) return false;
        }
        return true;
    }

private:
    unordered_map<int, int> coins;

    bool exchange(int amount) {
        for (int x : {20, 10, 5})
            while (amount >= x && coins[x] > 0) {
                amount -= x;
                coins[x]--;
            }
        return amount == 0;
    }
};
  1. 455. 分發(fā)餅干 - 力扣(LeetCode)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 分配給孩子滿足胃口的最小餅干杠步,具有決策包容性鸟顺,可以貪心
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int ans = 0;
        int j = 0;
        for (int child : g) {
            while (j < s.size() && s[j] < child) j++;
            if (j < s.size()) {
                ans++; j++;
            }
        }
        return ans;
    }
};
  1. 122. 買賣股票的最佳時機 II - 力扣(LeetCode)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for (int i = 1; i < prices.size(); i++)
            ans += max(prices[i] - prices[i - 1], 0);
        return ans;
    }
};
  1. 45. 跳躍游戲 II - 力扣(LeetCode)
class Solution {
public:
    int jump(vector<int>& nums) {
        int now = 0;
        int ans = 0;
        while (now < nums.size() - 1) {
            int right = now + nums[now];
            if (right >= nums.size() - 1)
                return ans + 1;
            // [now+1, right]
            int nextRight = right;
            int next = now;
            for (int i = now + 1; i <= right; i++)
                // 用下下步最遠的下步來確定下一步走哪
                if (i + nums[i] > nextRight) {
                    nextRight = i + nums[i];
                    next = i;
                }
            // 如果循環(huán)后next還不變,說明從now出發(fā)怎么走都不到終點亥贸,直接退出
            if (next == now) return -1;
            now = next;
            ans++;
        }
        return ans;
    }
};
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末躬窜,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子炕置,更是在濱河造成了極大的恐慌荣挨,老刑警劉巖,帶你破解...
    沈念sama閱讀 219,589評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件朴摊,死亡現(xiàn)場離奇詭異默垄,居然都是意外死亡,警方通過查閱死者的電腦和手機甚纲,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,615評論 3 396
  • 文/潘曉璐 我一進店門口锭,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人介杆,你說我怎么就攤上這事讹弯。” “怎么了这溅?”我有些...
    開封第一講書人閱讀 165,933評論 0 356
  • 文/不壞的土叔 我叫張陵组民,是天一觀的道長。 經(jīng)常有香客問我悲靴,道長臭胜,這世上最難降的妖魔是什么莫其? 我笑而不...
    開封第一講書人閱讀 58,976評論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮耸三,結(jié)果婚禮上乱陡,老公的妹妹穿的比我還像新娘。我一直安慰自己仪壮,他們只是感情好憨颠,可當我...
    茶點故事閱讀 67,999評論 6 393
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著积锅,像睡著了一般爽彤。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上缚陷,一...
    開封第一講書人閱讀 51,775評論 1 307
  • 那天适篙,我揣著相機與錄音,去河邊找鬼箫爷。 笑死嚷节,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的虎锚。 我是一名探鬼主播硫痰,決...
    沈念sama閱讀 40,474評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼窜护!你這毒婦竟也來了效斑?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,359評論 0 276
  • 序言:老撾萬榮一對情侶失蹤柄慰,失蹤者是張志新(化名)和其女友劉穎鳍悠,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體坐搔,經(jīng)...
    沈念sama閱讀 45,854評論 1 317
  • 正文 獨居荒郊野嶺守林人離奇死亡藏研,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,007評論 3 338
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了概行。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蠢挡。...
    茶點故事閱讀 40,146評論 1 351
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖凳忙,靈堂內(nèi)的尸體忽然破棺而出业踏,到底是詐尸還是另有隱情,我是刑警寧澤涧卵,帶...
    沈念sama閱讀 35,826評論 5 346
  • 正文 年R本政府宣布勤家,位于F島的核電站,受9級特大地震影響柳恐,放射性物質(zhì)發(fā)生泄漏伐脖。R本人自食惡果不足惜热幔,卻給世界環(huán)境...
    茶點故事閱讀 41,484評論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望讼庇。 院中可真熱鬧绎巨,春花似錦、人聲如沸蠕啄。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,029評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽歼跟。三九已至和媳,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間嘹承,已是汗流浹背窗价。 一陣腳步聲響...
    開封第一講書人閱讀 33,153評論 1 272
  • 我被黑心中介騙來泰國打工如庭, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留叹卷,地道東北人。 一個月前我還...
    沈念sama閱讀 48,420評論 3 373
  • 正文 我出身青樓坪它,卻偏偏與公主長得像骤竹,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子往毡,可洞房花燭夜當晚...
    茶點故事閱讀 45,107評論 2 356

推薦閱讀更多精彩內(nèi)容