头像

ZhCoding




离线:5天前



ZhCoding
13天前
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.empty()) return {};
        vector<int> res;
        int n = s.size(), w = words[0].size(), m = words.size();
        unordered_map<string, int> tot; // 统计words中每个单词的数量
        for (auto word : words) tot[word]++;
        for (int i = 0; i < w; ++i) { // 所有单词的长度相同, 所以s有w种切分方式, 每种方式的起点不同
            unordered_map<string, int> wd; // 统计s切分后得到单词
            int cnt = 0;
            for (int j = i; j + w <= n; j += w) {
                if (j >= i + w * m) {
                    // 删除开头的单词
                    auto word = s.substr(j - w * m, w);
                    wd[word]--;
                    if (wd[word] < tot[word]) --cnt;
                }
                auto word = s.substr(j, w);
                wd[word]++;
                if (wd[word] <= tot[word]) ++cnt;
                if (cnt == m) res.push_back(j - w * (m - 1));
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 29. 两数相除

ZhCoding
16天前
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool isMinus = (dividend > 0) ^ (divisor > 0);
        int a = dividend, b = divisor;
        // 均转为负数防止溢出
        if (dividend > 0) a = -a;
        if (divisor > 0) b = -b;
        const int halfIntMin = -1073741824;
        vector<pair<int, int>> vec;
        for (int t1 = b, t2 = -1; t1 >= a; t1 += t1, t2 += t2) {
            vec.push_back({t1, t2});
            if (t1 < halfIntMin) break;
        }
        int res = 0;
        for (int i = vec.size() - 1; i >= 0; --i) {
            if (a <= vec[i].first) {
                a -= vec[i].first;
                res += vec[i].second;
            }
        }
        if (!isMinus && res == INT_MIN) return INT_MAX;
        if (!isMinus) return -res;
        return res; 
    }
};


活动打卡代码 LeetCode 28. 实现 strStr()

ZhCoding
17天前
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        int n = needle.size();
        int m = haystack.size();
        vector<int> nx(n);
        nx[0] = -1;
        // 首字母没有前缀, 故从1开始
        for (int i = 1, j = -1; i < n; ++i) {
            while (j > -1 && needle[i] != needle[j + 1]) j = nx[j];
            if (needle[i] == needle[j + 1]) ++j;
            nx[i] = j;
        }

        for (int i = 0, j = -1; i < m; ++i) {
            while (j > -1 && haystack[i] != needle[j + 1]) j = nx[j];
            if (haystack[i] == needle[j + 1]) ++j;
            if (j == n - 1) return i - n + 1;
        }
        return -1;
    }
};


活动打卡代码 LeetCode 27. 移除元素

ZhCoding
20天前
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};



ZhCoding
20天前
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            nums[k++] = nums[i];
        }
        return k;
    }
};



ZhCoding
21天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = dummy;
        while (cur->next) {
            ListNode *first = cur->next, *end = cur;
            for (int i = 0; end && i < k; ++i) {
                end = end->next;
            }
            if (!end) {
                break;
            }
            ListNode *pr = first, *p = first->next;
            while (pr != end) {
                ListNode* pn = p->next;
                p->next = pr;
                pr = p;
                p = pn;
            }
            first->next = p;
            cur->next = pr;
            cur = first;
        }
        return dummy->next;
    }
};



ZhCoding
23天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *p = dummy; 
        dummy->next = head;
        while (p->next && p->next->next) {
            ListNode *a = p->next, *b = p->next->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy->next;
    }
};



ZhCoding
24天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct cmp {
        bool operator() (const ListNode *a, ListNode *b) {
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for (auto l : lists) {
            if (l) pq.push(l);
        }
        ListNode *dummy = new ListNode(-1), *tail = dummy;
        while (!pq.empty()) {
            ListNode *t = pq.top();
            pq.pop();
            tail->next = t;
            tail = tail->next;
            if (t->next) pq.push(t->next);
        }
        return dummy->next;
    }
};


活动打卡代码 LeetCode 22. 括号生成

ZhCoding
25天前
class Solution {
public:
    void dfs(int u, int n, int countL, string path, vector<string> &res) {
        if (u == 2 * n) {
            res.push_back(path);
            return;
        }
        if (countL == n) {
            dfs(u + 1, n, countL, path + ")", res);
        } else if (countL > u - countL) {
            dfs(u + 1, n, countL + 1, path + "(", res);
            dfs(u + 1, n, countL, path + ")", res);
        } else {
            dfs(u + 1, n, countL + 1, path + "(", res);
        }

    }
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs(0, n, 0, "", res);
        return res;
    }
};



ZhCoding
1个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode* p = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if (l1) p->next = l1;
        if (l2) p->next = l2;
        return dummy->next;
    }
};