Question 1 1880. Check if a word is equal to the sum of two words

1880. Check if a word equals the sum of two words

  • Add up the words bit by bit
class Solution {
public:
    int count(string s) {
        int ans = 0;
        for(const auto& c: s) {
            ans = ans * 10 + c - 'a';
        }
        return ans;
    }
    
    bool isSumEqual(string firstWord, string secondWord, string targetWord) {
        return count(firstWord) + count(secondWord) == count(targetWord); }};Copy the code

Problem 2:1881. Maximum after insertion

1881. Maximum value after insertion

  • ifnIf it’s positive, you find the first ratio from left to rightxSmall number, let’sxInsert it to the left of this number
  • ifnIf it’s negative, you find the first ratio from left to rightxBig numbers, let’s goxInsert it to the right of this number
class Solution {
public:
    string maxValue(string n, int x) {
        if(n[0] != The '-') {
            int i = 0;
            while(i < n.size() && n[i] - '0' >= x) {
                ++i;
            }
            if(i == n.size()) {
                return n + to_string(x);
            } else {
                return n.substr(0, i) + to_string(x) + n.substr(i); }}else {
            int i = 1;
            while(i < n.size() && n[i] - '0' <= x) {
                ++i;
            }
            if(i == n.size()) {
                return n + to_string(x);
            } else {
                return n.substr(0, i) + to_string(x) + n.substr(i); }}}};Copy the code

Problem 3:1882. Using a server to process tasks

Title link: 1882. Using a server to process tasks

  • According to the rules of the title, we classify servers as “idle servers”idle serversAnd “Busy Server”busy servers
  • Each time a new task arrives, a server “best suited to the current task” is selected to run the task
  • When a new task arrives:
    • If there are idle servers, the server with the least weight is selected to run. If the weights are the same, the server with the smallest subscript is selected
    • If there are no idle servers, the server waits for the first busy server to run the task. If multiple servers become idle at the same time, the server is selected based on the sorting rule of the idle servers
  • With this in mind, it is easy to think of two priority queues for maintenanceIdle serverisandBusy serverbs, the two priority queues have different collation rules
  • Initially, all servers are idle servers
  • Because we need to keep track of the completion times of busy servers, the server architecture we built containstime,The weight,The subscriptThree data members
  • For each task, the “most suitable” server is selected from the “free servers” to run the task, and this server is then removed from theisPop up, join inbs
  • If there are no free servers for the current task, the task is run by waiting for a free server to appear among the busy servers
class Solution {
private:
    int n, m;
    vector<int> ans;
    
    struct server {
        int time, weight, index;
        server(int t, int w, inti) { time = t; weight = w; index = i; }};public:
    struct busyServer {                                    // Prioritization of the busy server priority queue
        bool operator(a) (server a, server b) {
            if(a.time ! = b.time) {return a.time > b.time;
            }
            if(a.weight ! = b.weight) {return a.weight > b.weight;
            }
            returna.index > b.index; }};struct idleServer {                                   // Collation of priority queues for idle servers
        bool operator(a) (server a, server b) {
            if(a.weight ! = b.weight) {return a.weight > b.weight;
            }
            returna.index > b.index; }};vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        n = servers.size(a); m = tasks.size(a); priority_queue<server, vector<server>, busyServer> bs; priority_queue<server, vector<server>, idleServer> is;for(int i = 0; i < n; ++i) {
            is.push(server(0, servers[i], i));
        }
        for(int i = 0; i < m; ++i) {
            while(! bs.empty() && bs.top().time <= i) {         // The priority queue of the busy server may have a server that has finished running and needs to eject the heap
                is.push(bs.top());
                bs.pop(a); }if(! is.empty()) {                      // If there are free servers, select the server to run in the IS heap and add the server to the BS
                auto t = is.top(a); is.pop(a); ans.push_back(t.index);
                bs.push(server(i + tasks[i], t.weight, t.index));
            } else {                  // If there are no free servers, wait for the busy server to run the first completed server, and select the server to run the task from the first completed server
                auto t = bs.top(a); bs.pop(a); ans.push_back(t.index);
                bs.push(server(t.time + tasks[i], t.weight, t.index)); }}returnans; }};Copy the code

Question 4 5775. Minimum skipped breaks for arriving at a meeting on time

5775. Minimum skipped breaks for arriving at meetings on time

  • dp[i][j]It means pastiSection of the road,ifrom1Start), skipjThe shortest time of times. For accuracy purposes, the array is two-dimensionaldoubleAn array of
  • Consider state transitions fordp[i][j]:
    • ifskipThe current roaddist[i - 1], there are:dp[i][j] = dp[i - 1][j - 1] + dist[i - 1] / speed
    • ifDon’t skipThe current roaddist[i - 1], there are:dp[i][j] = ceil(dp[i - 1][j] + dist[i - 1] / speed)
  • Boundary case:
    • whenj = 0, means that we do not jump any road, thendp[i][j]Cannot be obtained by any “road skipping” state transitions
    • whenj = i, means we have skipped all roads, thendp[i][j]Cannot be obtained by any “do not skip path” state transition
    • Skip the number of timesjIt should be less than the number of roadsi
  • Final answer:
    • For all less than or equal tohoursBeforethedp[n][i](This status indicates that all paths are passed and skippediWe find the smallest oneiIs returned as a result
    • If the0 ~ nIs not found to meet the conditioni, then return- 1
  • Other details:
    • In terms of accuracy,Round up ceil()It’s possible to get the wrong answer, and the common way to do that is to subtract an error valueepsAnd then I’m going to round up
  • Reference: Official problem solving
class Solution {
private:
    const double INF = 1e10;
    const double eps = 1e-8;
    int n;
    vector<vector<double>> dp;
    
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        n = dist.size(a); dp.resize(n + 1, vector<double>(n + 1, INF));
        dp[0] [0] = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j <= i; ++j) {
                dp[i][j] = min(dp[i][j], ceil(dp[i - 1][j] + (double)dist[i - 1] / speed - eps));
                if(0 < j) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (double)dist[i - 1] / speed); }}}for(int i = 0; i <= n; ++i) {
            if(dp[n][i] <= hoursBefore) {
                returni; }}return - 1; }};Copy the code