Leet Code Weekly Contest 295

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        unordered_map<char, int> cnt, tgt;
        for (auto &c : s) {
            cnt[c]++;
        }
        for (auto &c : target) {
            tgt[c]++;
        }
        int ans = INT_MAX;
        for (auto &p : tgt) {
            ans = min(ans, cnt[p.first] / p.second);
        }
        return ans;
    }
};

typedef long long ll;

class Solution {
private:
    bool isDigit(char c) {
        return c >= '0' && c <= '9';
    }

public:
    string discountPrices(string sentence, int discount) {
        string ans;
        for (int i = 0, j; i < sentence.size(); i = j + 1) {
            for (j = i; j + 1 < sentence.size() && (sentence[i] != ' ') == (sentence[j + 1] != ' '); ) j++;
            if (sentence[i] == '$' && i < j) {
                bool valid = true;
                ll x = 0;
                for (int k = i + 1; k <= j; k++) {
                    if (!isDigit(sentence[k])) {
                        valid = false;
                        break;
                    } else {
                        x = x * 10 + (sentence[k] - '0');
                    }
                }
                if (valid) {
                    ans.push_back('$');
                    x = x * (100 - discount);
                    ans += to_string(x / 100) + ".";
                    x %= 100;
                    if (x < 10) {
                        ans.push_back('0');
                    }
                    ans += to_string(x);
                    continue;
                }
            }
            ans += sentence.substr(i, j - i + 1);
        }
        return ans;
    }
};

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        stack<int> s;
        vector<int> f(nums.size(), 0);
        int ans = 0, prevMax = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            prevMax = max(prevMax, nums[i]);
            if (prevMax <= nums[i]) {
                s = stack<int>();
                
                continue;
            }
            f[i] = 1;
            while (!s.empty() && nums[s.top()] <= nums[i]) {
                f[i] = max(f[i], 1 + f[s.top()]);
                s.pop();
            }
            s.push(i);
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

const vector<pair<int, int>> kDir = {
    { -1,  0 },
    { +1,  0 },
    {  0, -1 },
    {  0, +1 }
};

const int maxn = 100000;

struct edge {
  int v, w;
};

struct node {
  int dis, u;
  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(vis, 0, sizeof(vis));
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  q = priority_queue<node, vector<node>, greater<node>>();
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

class Solution {
private:
    int n_, m_;
    
    int idxOf(int x, int y) {
        return x * m_ + y;
    }
    
    
public:
    
    void addEdge(int s, int t, int w) {
        edge x;
        x.v = t;
        x.w = w;
        e[s].push_back(x);
    }

    int minimumObstacles(vector<vector<int>>& grid) {
        n_ = grid.size();
        m_ = grid.front().size();
        for (int i = 0; i < (n_ * m_); i++) {
            e[i].clear();
        }
        for (int x = 0; x < n_; x++) {
            for (int y = 0; y < m_; y++) {
                for (auto &d : kDir) {
                    int nx = x + d.first, ny = y + d.second;
                    if (nx >= 0 && nx < n_ && ny >= 0 && ny < m_) {
                        addEdge(idxOf(x, y), idxOf(nx, ny), grid[nx][ny]);
                    }
                }
            }
        }
        dijkstra(n_ * m_, 0);
        return dis[n_ * m_ - 1];
    }
};