头像

上将邢道荣




离线:7小时前


最近来访(4)
用户头像
陈平安
用户头像
好きだよ
用户头像
yxc
用户头像
yxc的机器人a


class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> h;
        int m = nums.size();
        vector<int> s(m + 1);
        for (int i = 1; i <= m; i++) s[i] = s[i - 1] + nums[i - 1];
        h[0] = 1;
        int res = 0;
        for (int i = 1; i <= m; i++) {
            if (h.count(s[i] - k)) res += h[s[i] - k];
            h[s[i]]++;
        }
        return res;
    }
};



class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sum(n + 1);
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        unordered_set<int> s;
        for (int i = 2; i <= n; i++) {
            s.insert(sum[i - 2] % k);
            if (s.count(sum[i] % k)) return true;
        }
        return false;
    }
};


活动打卡代码 LeetCode 474. 一和零

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> f (m + 1, vector<int>(n + 1));
        //  f[i][j][k]  表示  前i个字符串中 0 不超过 j, 1 不超过 k的数目
        //  f[i][j][k] = f[i - 1][j - a][k - b] + 1// a 是0  的数目,b 是 1的数目。
        for (int i = 0; i < strs.size(); i++) {
            int a = 0, b = 0;
            for (auto ch : strs[i]) {
                if (ch == '0') a++;
                else b++;
            }
            for (int j = m; j >= a; j--) {
                for (int k = n; k >= b; k--) {
                    f[j][k] = max(f[j][k], f[j - a][k - b] + 1);
                }
            }
        }
        return f[m][n];
    }
};



class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int l = -1e9, r = 1e9;
        while (l < r) {
            int mid = l + r >> 1;
            int i = matrix[0].size() - 1;
            int cnt = 0;
            for (int j = 0; j < matrix.size(); j++) {
                while (i >= 0 && matrix[j][i] > mid) i--;
                cnt += i + 1;
            }
            if (cnt >= k) r = mid;
            else l = mid + 1;
        }
        return r; 
    }
};


活动打卡代码 LeetCode 205. 同构字符串

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        char hs[300] = "";
        char ht[300] = "";
        for (int i = 0; i < s.size(); i++) {
            if (hs[s[i]] && hs[s[i]] != t[i] || ht[t[i]] && ht[t[i]] != s[i]) return false;
            hs[s[i]] = t[i];
            ht[t[i]] = s[i];
        }
        return true;
    }
};


活动打卡代码 LeetCode 172. 阶乘后的零

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while (n) res += n / 5, n /= 5;
        return res;
    }
};


活动打卡代码 LeetCode 168. Excel表列名称

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string res;
        while (columnNumber > 0) {
            columnNumber--;
            res += (columnNumber % 26) + 'A';
            columnNumber /= 26;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};


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

class Solution {
public:
    int divide(int dividend, int divisor) {
        typedef long long ll;
        bool is_minus = false;
        if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0) is_minus = true;
        vector<ll> num;
        ll a = abs(dividend), b = abs(divisor);
        for (ll i = b; i <= a; i = i + i) num.push_back(i);
        ll res = 0;
        for (int i = num.size() - 1; i >= 0; i--) {
            if (a >= num[i]) {
                a -= num[i];
                res += (1ll << i);
            }
        }
        if (is_minus) res = -res;
        if (res < INT_MIN || res > INT_MAX) return INT_MAX;
        return res;
    }
};




/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //二叉树的前序遍历 moris写法。
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        while (root) {
            if (root->left) {
                auto p = root->left;
                while (p->right && p->right != root) p = p->right;
                if (!p->right) {
                    res.push_back(root->val);
                    p->right = root;
                    root = root->left;
                } else {
                    p->right = NULL;
                    root = root->right;
                }
            } else {
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

// 二叉树的中序遍历 moris写法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        auto cur = root;
        while (cur) {
            if (cur->left) {
                auto l = cur->left;
                while (l->right && l->right != cur) l = l->right;
                if (!l->right) {
                    l->right = cur;
                    cur = cur->left;
                } else {
                    res.push_back(cur->val);
                    l->right = NULL;
                    cur = cur->right;
                }
            } else {
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

// 二叉树的后续遍历 moris写法。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        while (root) {
            if (root->right) {
                auto p = root->right;
                while (p->left && p->left != root) p = p->left;
                if (!p->left) {
                    res.push_back(root->val);
                    p->left = root;
                    root = root->right;
                } else {
                    p->left = NULL;
                    root = root->left;
                }
            } else {
                res.push_back(root->val);
                root = root->left;
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};




class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        auto cur = root;
        while (cur) {
            auto head = new Node(-1);
            auto tail = head;
            for (auto p = cur; p; p = p->next) {
                if (p->left) tail = tail->next = p->left;
                if (p->right) tail = tail->next = p->right;
            }
            cur = head->next;
        }
        return root;
    }
};