头像

晓玲

重庆邮电大学


访客:8068

在线 



晓玲
6小时前
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        if (!A.size()) return 0;
        int n = A.size(), ans = A[0];
        vector<int> sum(2*n+1, 0);

        for (int i = 1; i <= 2*n; i ++) {
            if (i <= n) sum[i] = A[i-1] + sum[i - 1];
            else sum[i] = A[i-n-1] + sum[i-1];
        }

        deque<int> q;
        q.push_back(0);
        for (int i = 1; i <= 2*n; i ++) {
            while (q.size() && i - q.front() > n) q.pop_front();
            ans = max(ans, sum[i] - sum[q.front()]);
            while (q.size() && sum[i] <= sum[q.back()]) q.pop_back();
            q.push_back(i);
        }
        return ans;

    }
};



晓玲
6小时前
class Solution {
public:
    stack<int> stk;
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(-1);
        int ans = 0;
        for (int i = 0; i < heights.size(); i ++) {
            while (stk.size() && heights[i] < heights[stk.top()]) {
                auto cur = stk.top();
                stk.pop();
                if (stk.empty()) ans = max(ans, heights[cur] * i);
                else {
                    ans =  max(ans, heights[cur] * (i - stk.top() - 1));
                }
            }
            stk.push(i);
        }
        return ans;
    }
};



晓玲
7小时前
class Solution {
public:
    int trap(vector<int>& height) {
        if (!height.size()) return 0;
        int n = height.size();
        int left[n], right[n];
        memset(left, 0, sizeof left);
        memset(right, 0, sizeof right);

        left[0] = height[0], right[height.size() - 1] = height.back();
        for (int i = 1; i < height.size(); i ++) left[i] = max(height[i], left[i - 1]);
        for (int i = height.size() - 2; i >= 0; i --) right[i] = max(height[i], right[i + 1]);

        int ans = 0;
        for (int i = 0; i < height.size(); i ++) {
            ans += min(left[i], right[i]) - height[i];
        }
        return ans;


    }
};



晓玲
1天前
class Solution {
public:
    vector<int> ans;
    deque<int> q;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); i ++) {
            if (q.size() && i - q.front() >= k) q.pop_front();
            while (q.size() && nums[q.back()] < nums[i]) q.pop_back();
            q.push_back(i);
            if (i - k + 1 >= 0) ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};



晓玲
5天前
class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        for i, s in enumerate(sentence.split()):
            if s.startswith(searchWord):
                return i + 1
        return -1



晓玲
5天前
class Solution {
public:
    const int MOD = 1e9 + 7;
    int maxArea(int h, int w, vector<int>& hor, vector<int>& ver) {
        hor.push_back(0), ver.push_back(0);
        hor.push_back(h), ver.push_back(w);
        sort(hor.begin(), hor.end());
        sort(ver.begin(), ver.end());
        int mh = 0, mw = 0;
        for (int i = 1; i < hor.size(); i ++) mh = max(mh, hor[i] - hor[i - 1]);
        for (int i = 1; i < ver.size(); i ++) mw = max(mw, ver[i] - ver[i - 1]);
        return (long long)mh * mw % MOD;
    }
};



晓玲
5天前
class Solution {
public:
    int ans = 0;
    int maxProduct(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++)
            for (int j = i + 1; j < nums.size(); j ++)
                ans = max(ans, (nums[i] - 1) * (nums[j] - 1));
        return ans;
    }
};



晓玲
12天前

算法

(Bellman-ford)$O(nm)$

通过$n$轮松弛操作,
第一轮松弛,源点经过最多$1$条边到的点的最短路
第二轮松弛,源点经过最多$2$条边到的点的最短路
所以$n$轮松弛,得到最多经过$n$条边的最短路
如何用bellman-ford判断负权回路,通过$n$轮松弛,最多$n+1$个点,由抽屉原理,可以知道$2$点重复,所以有负权回路
时间复杂度分析:对于$n$个点,对$m$条边进行松弛操作,所以时间复杂度为$O(nm)$.

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 5e2 + 10;
const int M = 1e4 + 10;
int n, m, k;
int dis[N], back[N];
struct Edge{
    int a, b, w;
}edge[M];

int bellman() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    for (int i = 0; i < k; i ++) {
        memcpy(back, dis, sizeof dis);
        for (int j = 0; j < m; j ++) {
            int a = edge[j].a, b = edge[j].b, w = edge[j].w;
            //cout << a << b << w << endl;
            dis[b] = min(dis[b], back[a] + w);
        }
    }
    if (dis[n] > 0x3f3f3f3f / 2) return -1;
    return dis[n];
}

int bellman_ford()
{
    memset(dis, 0x3f, sizeof dis);

    dis[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(back, dis, sizeof dis);
        for (int j = 0; j < m; j ++ )
        {
            auto e = edge[j];
            dis[e.b] = min(dis[e.b], back[e.a] + e.w);
        }
        //cout << dis[n] << endl;
    }
    if (dis[n] > 0x3f3f3f3f / 2) return -1;
    return dis[n];
}


int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i ++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edge[i] = {a, b, c};
        //printf("%d %d\n", edge[i].a, edge[i].b);
    }
    int t = bellman();
    if (t == -1) cout << "impossible" << endl;
    else cout << dis[n] << endl;
    return 0;
}



晓玲
12天前

拓扑排序
思路:
BFS,记录每个点的入度,把入度为0的点加入队列中,BFS每个点的时候,入度-1,把入度为0的点继续加入队列。
BFS结束时,如果所有点都可以出队,则说明存在拓扑排序。
可以手动模拟队列,那么出队的队列即使拓扑排序的序列,直接输出q[1-n]数组即可。
时间复杂度$O(n + m)$,和点数和边数成正比

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool topsort()
{
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);

        d[b] ++ ;
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
        puts("");
    }

    return 0;
}



晓玲
1个月前
// f[i][j] 表示s从i开始到结尾可以和p从j到结尾匹配
// 1.p[j]是普通字符,则f[i][j]: s[i] == p[j] && f[i+1][j+1]
// 2.p[j]是'.',则 f[i][j]: f[i+1][j+1]
// 3.p[j]是'*',则 f[i][j]: f[i][j + 2], f[i+1][j]

class Solution {
public:
    int n, m;
    vector<vector<int>> f;
    bool isMatch(string s, string p) {
        n = s.size(), m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0, s, p);
    }

    bool dp(int x, int y, string& s, string& p) {
        if (f[x][y] != -1) return f[x][y];
        if (y == m) 
            return f[x][y] = x == n;
        bool first_match = x < n && (p[y] == '.' || s[x] == p[y]);
        bool ans;
        if (y + 1 < m && p[y + 1] == '*') {
            ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
        }
        else
            ans = first_match && dp(x + 1, y + 1, s, p);
        return f[x][y] = ans;
    }

};