头像

Panson




离线:8小时前


最近来访(64)
用户头像
正在加载中...
用户头像
资源777
用户头像
七海千秋
用户头像
天元之弈
用户头像
落雨
用户头像
不学会数据结构不改名
用户头像
zzhhhh
用户头像
LonelyLove
用户头像
锦木千束
用户头像
我是雷电将军的狗
用户头像
蓝路
用户头像
kesmeey
用户头像
AntonyTang
用户头像
蓬蒿人
用户头像
如故
用户头像
gtt
用户头像
wuli_ni
用户头像
BigJingle
用户头像
今天AC了吗
用户头像
kccc

活动打卡代码 LeetCode 143. 重排链表

Panson
8小时前
class Solution {
public:
    void reorderList(ListNode* head) {
        int n = 0;
        for (auto p = head; p; p = p->next) n++;

        auto mid = head;
        for (int i = 0; i < (n + 1) / 2 - 1; i++) mid = mid->next;

        auto a = mid->next, b = mid;

        for (int i = 0; i < n / 2; i++)
        {
            auto c = a->next;
            a->next = b;
            b = a;
            a = c;
        }

        auto p = head, q = b;

        for (int i = 0; i < n / 2; i++)
        {
            auto o = q->next;
            q->next = p->next;
            p->next = q;
            if (n % 2 == 0 && i == n / 2 - 1) q->next = NULL;
            p = q->next, q = o;
        }
        if (n % 2) p->next = NULL;


    }
};


活动打卡代码 LeetCode 142. 环形链表 II

Panson
9小时前
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return 0;        
        auto f = head->next, s = head; // f and s are not start from the same point

        while (f)
        {
            f = f->next;
            s = s->next;
            if (!f) return 0;
            f = f->next;

            if (f == s)
            {
                s = head, f = f->next;  // as not same starting, so f = f->next
                while (s != f) f = f->next, s = s->next;   
                return s;
            }
        }

        return 0;
    }
};


活动打卡代码 LeetCode 141. 环形链表

Panson
9小时前
class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto f = head, s = head;


        while (f && f->next)
        {
            f = f->next->next;
            s = s->next;
            if (f == s) return true;
        }
        return false;
    }
};


活动打卡代码 LeetCode 838. 推多米诺

Panson
10小时前
class Solution {
public:
    string pushDominoes(string s) {
        s = 'L' + s + 'R';
        int n = s.size();
        vector<int> l(n), r(n);

        for (int i = 0, j = 0; i < n; i++)
        {
            if (s[i] != '.') j = i;
            l[i] = j;
        }

        for (int i = n - 1, j = 0; i >= 0; i--)
        {
            if (s[i] != '.') j = i;
            r[i] = j;
        }

        for (int i = 0; i < n; i++)
        {
            char L = s[l[i]], R = s[r[i]];

            if (L == 'L' && R == 'R') s[i] = '.';
            else if (L == 'L' && R == 'L') s[i] = 'L';
            else if (L == 'R' && R == 'R') s[i] = 'R';
            else 
            {
                if (i - l[i] < r[i] - i) s[i] = 'R';
                else if (i - l[i] > r[i] - i) s[i] = 'L';
                else s[i] = '.';
            }

        }
        return s.substr(1, n - 2);
    }
};


活动打卡代码 LeetCode 140. 单词拆分 II

Panson
1天前
class Solution {
public:
    unordered_set<string> hash;
    vector<string> res;
    int n;
    vector<bool> f;

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        f.resize(n + 1);

        for (auto& word: wordDict) hash.insert(word);

        f[n] = true;
        for (int i = n - 1; i > 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (hash.count(s.substr(i, j - i + 1)) && f[j + 1])
                    f[i] = true;
            }
        }

        dfs(s, 0, "");
        return res;
    }

    void dfs(string& s, int u, string path)
    {
        if (u == n)
        {
            path.pop_back();
            res.push_back(path);
        } else
        {
            for (int i = u; i < n; i++)
            {
                if (hash.count(s.substr(u, i - u + 1)) && f[i + 1])
                {
                    dfs(s, i + 1, path + s.substr(u, i - u + 1) + ' ');
                }
            }
        }
    }
};


活动打卡代码 LeetCode 139. 单词拆分

Panson
1天前
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        const int P = 131;
        unordered_set<ULL> hash;

        for (auto& word: wordDict)
        {
            ULL h = 0;
            for (auto &c: word) h = h * P + c;
            hash.insert(h);
        }

        int n = s.size();
        vector<bool> f(n + 1);
        f[0] = true;

        s = ' ' + s;

        for (int i = 0; i < n; i++)
        {
            if (f[i])
            {
                ULL h = 0;
                for (int j = i + 1; j <= n; j++)
                {
                    h = h * P + s[j];
                    if (hash.count(h)) f[j] = true;
                }

            }
        }

        return f[n];
    }
};



Panson
1天前

Approach 1:

class Solution {
public: 
    unordered_map<Node*, Node*> hash;

    Node* copyRandomList(Node* head) {
        if (!head) return 0;
        dfs(head);

        for (auto [s, d]: hash)
        {
            if (hash[s])
            {
                d->next = hash[s->next]; 
                d->random = hash[s->random];
            }
        }
        return hash[head];

    }

    void dfs(Node* u)
    {
        hash[u] = new Node(u->val);
        if (u->next) dfs(u->next);
    }
};

Approach 2:

class Solution {
public:
    Node* copyRandomList(Node* head) {
        auto dummy = new Node(-1), cur = dummy;
        for (auto p = head; p; p = p->next->next)
        {
            Node* q = new Node(p->val);
            q->next = p->next;
            p->next = q;
        }

        for (auto p = head; p; p = p->next->next)
        {
            if (p->random)
                p->next->random = p->random->next;
        }


        for (auto p = head; p; p = p->next)
        {
            auto q = p->next;
            cur = cur->next = q;
            p->next = q->next;
        }

        return dummy->next;
    }
};



Panson
2天前
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;

        for (auto &s: nums)
        {
            one = (one ^ s) & ~two;
            two = (two ^ s) & ~one;
        }
        return one;
    }
};



Panson
2天前
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto& x:nums) res ^= x;
        return res;
    }
};


活动打卡代码 LeetCode 135. 分发糖果

Panson
2天前
class Solution {
public:
    vector<int> f, w;
    int n, res;

    int candy(vector<int>& ratings) {
        n = ratings.size();
        w = ratings;
        f.resize(n, -1);


        for (int i = 0; i < n; i++)
            res += dp(i);
        return res;
    }

    int dp(int x)        // memorization
    {
        if (f[x] != -1) return f[x];

        f[x] = 1;
        if (x && w[x-1] < w[x]) f[x] = max(f[x], dp(x - 1) + 1); 
        if (x + 1 < n && w[x + 1] < w[x]) f[x] = max(f[x], dp(x + 1) + 1);

        return f[x];
    }
};