2024-09-28

53. 最大子数组和 - 力扣（LeetCode）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> preSum(n + 1);
        preSum[0] = 0;
        for (int i = 1; i <= n; i++)
            preSum[i] = preSum[i - 1] + nums[i - 1];
        vector<int> preMin(n + 1);
        preMin[0] = preSum[0];
        for (int i = 1; i <= n; i++)
            preMin[i] = min(preMin[i - 1], preSum[i]);
        int ans = -1e9;
        for (int i = 1; i <= n; i++)
            ans = max(ans, preSum[i] - preMin[i - 1]);
        return ans;
    }
};

304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        preSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        row1++; col1++; row2++; col2++;
        return preSum[row2][col2] - preSum[row1 - 1][col2] - preSum[row2][col1 - 1] + preSum[row1 - 1][col1 - 1];
    }

private:
    vector<vector<int>> preSum;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

1109. 航班预订统计 - 力扣（LeetCode）

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> delta(n + 2);
        for (vector<int>& booking : bookings) {
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            delta[first] += seats;
            delta[last + 1] -= seats;
        }
        vector<int> preSum(n + 1);
        preSum[0] = delta[0];
        vector<int> ans;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + delta[i];
            ans.push_back(preSum[i]);
        }
        return ans;
    }
};

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            if (numbers[left] + numbers[right] > target) right--;
            else if (numbers[left] + numbers[right] < target) left++;
            else return {left + 1, right + 1};
        }
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int right = n - 1;
        for (int left = 0; left < n; left++) {
            while (left < right && numbers[left] + numbers[right] > target) right--;
            if (left < right && numbers[left] + numbers[right] == target) 
                return {left + 1, right + 1};
        }
        return {};
    }
};

15. 三数之和 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            vector<vector<int>> jks = twoSum(nums, i + 1, -nums[i]);
            for (vector<int> jk : jks) 
                ans.push_back({nums[i], jk[0], jk[1]});
        }
        return ans;
    }

private:
    vector<vector<int>> twoSum(vector<int>& nums, int start, int target) {
        vector<vector<int>> ans;
        int n = nums.size();
        int j = n - 1;
        for (int i = start; i < n; i++) {
            if (i > start && nums[i] == nums[i - 1])
                continue;
            while (i < j && nums[i] + nums[j] > target)
                j--;
            if (i < j && nums[i] + nums[j] == target)
                ans.push_back({nums[i], nums[j]});
        }
        return ans;
    }
};

11. 盛最多水的容器 - 力扣（LeetCode）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            ans = max(ans, min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) l++; else r--;
        }
        return ans;
    }
};

78. 子集 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        this->nums = nums;
        n = nums.size();
        recur(0);
        return ans;
    }

private:
    vector<vector<int>> ans;
    vector<int> chosen;
    vector<int> nums;
    int n;
    void recur(int i) {
        if (i == n) {
            ans.push_back(chosen);
            return;
        }
        recur(i + 1);
        chosen.push_back(nums[i]);
        recur(i + 1);
        chosen.pop_back();
    }
};

77. 组合 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        this->n = n;
        this->k = k;
        recur(1);
        return ans;
    }

private:
    void recur(int i) {
        if (chosen.size() > k || chosen.size() + (n - i + 1) < k)
            return;
        if (i == n + 1)
            ans.push_back(chosen);
        recur(i + 1);
        chosen.push_back(i);
        recur(i + 1);
        chosen.pop_back();
    }

    int n, k;
    vector<int> chosen;
    vector<vector<int>> ans;
};

46. 全排列 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        used = vector<bool>(n, false);
        this->nums = nums;
        recur(0);
        return ans;
    }

private:
    int n;
    vector<bool> used;
    vector<int> chosen;
    vector<vector<int>> ans;
    vector<int> nums;

    void recur(int pos) {
        if (pos == n) {
            ans.push_back(chosen);
            return;
        }
        for (int i = 0; i < n; i++) 
            if (!used[i]) {
                chosen.push_back(nums[i]);
                used[i] = true;
                recur(pos + 1);
                used[i] = false;
                chosen.pop_back();
            }
    }
};

226. 翻转二叉树 - 力扣（LeetCode）

/**
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

98. 验证二叉搜索树 - 力扣（LeetCode）

/**
 * 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) {}
 * };
 */
#define LL long long
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return check(root, -(1ll << 31), (1ll << 31) - 1);
    }

private:
    bool check(TreeNode* root, LL leftRange, LL rightRange) {
        if (root == nullptr) return true;
        if (root->val < leftRange || root->val > rightRange) return false;
        return check(root->left, leftRange, root->val - 1ll) 
            && check(root->right, root->val + 1ll, rightRange);
    }
};

104. 二叉树的最大深度 - 力扣（LeetCode）

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        depth = 1;
        ans = 0;
        recur(root);
        return ans;
    }

private:
    int ans, depth;
    void recur(TreeNode* root) {
        if (root == nullptr) return;
        ans = max(ans, depth);
        depth++;
        recur(root->left);
        recur(root->right);
        depth--;
    }
};

50. Pow(x, n) - 力扣（LeetCode）

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == -(1ll << 31)) return 1.0 / (myPow(x, -(n + 1)) * x);
        if (n < 0) return 1.0 / myPow(x, -n);
        double temp = myPow(x, n / 2);
        double ans = temp * temp;
        if (n % 2 == 1) ans *= x;
        return ans;
    }
};

22. 括号生成 - 力扣（LeetCode）

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) return {""};
        if (store.find(n) != store.end()) return store[n];
        vector<string> ans;
        for (int k = 1; k <= n; k++) {
            vector<string> A = generateParenthesis(k - 1);
            vector<string> B = generateParenthesis(n - k);
            for (const string& a : A)
                for (const string& b : B)
                    ans.push_back("(" + a + ")" + b);
        }
        store[n] = ans;
        return ans;
    }

private:
    // (A)B
    unordered_map<int, vector<string>> store;
};

23. 合并 K 个升序链表 - 力扣（LeetCode）

/**
 * 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* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

private:
    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        if (a == nullptr || b == nullptr) return a ? a : b;
        ListNode* head = new ListNode();
        ListNode* tail = head;
        ListNode* aPtr = a, * bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr;
                aPtr = aPtr->next;
            }
            else {
                tail->next = bPtr;
                bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        if (aPtr == nullptr) tail->next = bPtr;
        if (bPtr == nullptr) tail->next = aPtr;
        return head->next;
    }
};

94. 二叉树的中序遍历 - 力扣（LeetCode）

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }

private:
    vector<int> ans;

    void dfs(TreeNode* root) {
        if (root == nullptr) return;
        dfs(root->left);
        ans.push_back(root->val);
        dfs(root->right);
    }
};

589. N 叉树的前序遍历 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        dfs(root);
        return ans;
    }
private:
    vector<int> ans;
    void dfs(Node* root) {
        if (root == nullptr) return;
        ans.push_back(root->val);
        for (int i = 0; i < root->children.size(); i++) 
            dfs(root->children[i]);
    }
};

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<Node*> s;
        s.push(root);
        while (!s.empty()) {
            Node* node = s.top();
            s.pop();
            ans.push_back(node->val);
            for (int i = node->children.size() - 1; i >= 0; i--)
                s.push(node->children[i]);
        }
        return ans;
    }
};

429. N 叉树的层序遍历 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        queue<pair<Node*, int>> q;
        q.push({root, 0});
        while (!q.empty()) {
            auto kv = q.front();
            Node* node = kv.first;
            int depth = kv.second;
            q.pop();
            if (depth >= ans.size()) ans.push_back({});
            ans[depth].push_back(node->val);
            for (int i = 0; i < node->children.size(); i++)
                q.push({node->children[i], depth + 1});
        }
        return ans;
    }
};

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,142评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,298评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,068评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,081评论 1赞 291
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,099评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,071评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,990评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,832评论 0赞 273
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,274评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,488评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,649评论 1赞 347
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,378评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,979评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,625评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,796评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,643评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,545评论 2赞 352

2024-09-28

推荐阅读更多精彩内容