头像

Nevermore_7




离线:5小时前


最近来访(1)
用户头像
小郑同学


Nevermore_7
5小时前

使用字典树存储,每个节点有26个儿子节点代表不同的字母,并用标记is_end来标记自己是否是终点
插入时将串在已有的路径上插入,没有则创建新节点。
搜索时判断已有节点是否可以到达is_end为TRUE的节点,如果不存在则返回FALSE
搜索前缀同理,但是不需要到达is_end为false的节点,找到了就是TRUE

//这里填你的代码^^
class Trie {
public:
    struct Node{
        Node* son[26];
        bool is_end;

        Node(){
            for(int i = 0; i < 26; i++) son[i] = nullptr;
            is_end = false;
        }
    } *root;

    Trie() {
        root = new Node();
    }

    void insert(string word) {
        auto p = root;
        for(auto c : word){
            int u = c - 'a';
            if(!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }

    bool search(string word) {
        auto p = root;
        for(auto c : word)
        {
            int u = c - 'a';
            if(!p->son[u]) return false;
            p = p->son[u];
        }
        return p->is_end;
    }

    bool startsWith(string prefix) {
        auto p = root;
        for(auto c : prefix)
        {
            int u = c - 'a';
            if(!p->son[u]) return false;
            p = p->son[u];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 LeetCode 160. 相交链表

Nevermore_7
23小时前

分别走相交链表的三条边(a list, b list, union list)
p指针从 a开始到union,再从b往后走
q指针从 b开始到union,再从a往后走
如果二者相遇的话,必定在交点相遇

//这里填你的代码^^
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto a = headA, b = headB;
        int cnt = 0;
        while(1)
        {
            if(a == b) return a;
            a = a->next;
            b = b->next;
            if(!a){
                a = headB;
                if(cnt == 1) break;
                cnt++;
            } 
            if(!b) b = headA;
        }
        return nullptr;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



考虑序列,数组问题的时候,一般如果固定起点不好做,可以考虑固定终点(应用双指针,DP)来降低复杂度。
如果最后是求和,可以考虑对求和的公式进行变形,再通过遍历代公式的方式进行优化。




类似DP的递推,双指针
考虑以i结尾的满足题目条件的子数组数目
实际上为以i - 1结尾的子数组数目加上包含nums[i]的所有小于k的子数组所得到的值
因此在每次循环时,只用在结果上加上后者的数目即可,这就要我们找到一个位置j,其中j以后到i的nums
所有乘积都比k小,后者的值就是i - j + 1。
由于本题所有元素为正数,因此j永远不会回退,因此符合双指针的条件,向后找找到j,动态更新乘积即可。

//这里填你的代码^^
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n = nums.size(), p = nums[0];
        vector<int> f(n);
        f[0] = (nums[0] < k) ? 1 : 0;
        for(int i = 1, j = 0; i < n; i++)
        {
            p *= nums[i];
            while(j <= i && p >= k) p /= nums[j++];
            f[i] = f[i - 1] + i - j + 1;
        }

        return f[n - 1];
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



DP:
由前i - 1个数的最大值来递推出前i个数的最大值
但由于乘法存在符号的问题,因此我们在存储最大值时,最好也存储一个最小值
前i个数的最大值有三种情况。分别是: 1. nums[i] 2. f[i - 1] * nums[i] 3. g[i - 1] * nums[i]取最大值
最小值同理,取上述三个数中的最小值即可
由于该递推公式只与前一个数有关,因此我们只需要滚动更新结果即可。

//这里填你的代码^^
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = INT_MIN, n = nums.size();
        int f = nums[0], g = nums[0];
        res = nums[0];
        for(int i = 1; i < n; i++)
        {
            int a = nums[i], fa = f * a, ga = g * a;
            f = max(a, max(fa, ga));
            g = min(a, min(fa, ga));
            res = max(res, f);
        }

        return res;

    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 854. Floyd求最短路

//这里填你的代码^^
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 210;

int n, m, Q;
int g[N][N];

void Floyd()
{
    for(int k = 1; k <= n; k++)
        for(int j = 1; j <= n; j++)
            for(int i = 1; i <= n; i++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int main()
{
    cin >> n >> m >> Q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) g[i][j] = 0;
            else g[i][j] = 0x3f3f3f3f;

    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    Floyd();

    for(int i = 1; i <= Q; i++)
    {
        int a, b;
        cin >> a >> b;
        if(g[a][b] > 0x3f3f3f3f / 2) puts("impossible");
        else cout << g[a][b] << endl;
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



算法思路非常奇特:
如果用传统思路,统计所有子串,那么肯定TLE。
那么我们转换思路,统计所有字符能在哪些子串中被囊括(子串中的单个字符数之和与包含某单个字符所有的子串数其实相等)。
我们枚举可能的包含当前字符的左端点和右端点最远能到哪里(标准为左右端点内没有出现该字符,左端点初始化为-1,右端点为n)。
再扫描一遍字符串,直接排列组合计算任一单字符,包含单字符的子串数目即为左端点和右端点字符数目的乘积。

//这里填你的代码^^
class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.size(), res = 0;
        vector<int> l(n), r(n);
        vector<int> p(26, -1); //下标对应26个字母,值对应在数组中出现的最近位置,左端点是-1,右端点为n

        for(int i = 0; i < n; i++)
        {
            l[i] = p[s[i] - 'A'];
            p[s[i] - 'A'] = i;
        }
        vector<int> p2(26, n);
        for(int i = n - 1; i >= 0; i--)
        {
            r[i] = p2[s[i] - 'A'];
            p2[s[i] - 'A'] = i;
        }

        for(int i = 0; i < n; i++)
            res += (i - l[i]) * (r[i] - i);

        return res;

    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 852. spfa判断负环

//这里填你的代码^^
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N], cnt[N];
bool st[N];

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

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int j = 1; j <= m; j++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

   if(spfa()) puts("Yes");
   else puts("No");

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 851. spfa求最短路

//这里填你的代码^^
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int j = 1; j <= m; j++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int res = spfa();
    if(res == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", res);

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edges{
    int a, b, c;
}edges[M];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 1; i <= k; i++)
    {
        memcpy(backup, dist, sizeof dist);

        for(int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, c = edges[j].c;
            if(dist[b] > backup[a] + c)
                dist[b] = backup[a] + c;
        }
    }

}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    bellman_ford();
    if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~