2024-09-30

  1. 297. 二叉树的序列化与反序列化 - 力扣（LeetCode）
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        rserialize(root);
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string str;
        for (char ch : data) {
            if (ch == ',') {
                dataArray.push_back(str);
                str = "";
            }
            else
                str += ch;
        }
        return rdeserialize();
    }

private:
    string ans;
    list<string> dataArray;

    void rserialize(TreeNode* root) {
        if (root == nullptr) {
            ans += "null,";
            return;
        }
        ans += to_string(root->val) + ",";
        rserialize(root->left);
        rserialize(root->right);
    }

    TreeNode* rdeserialize() {
        if (dataArray.front() == "null") {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = rdeserialize();
        root->right = rdeserialize();
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
  1. 433. 最小基因变化 - 力扣（LeetCode）
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> hashBank;
        for (string& seq : bank) hashBank.insert(seq);
        if (hashBank.find(endGene) == hashBank.end()) return -1;
        const char gene[4] = {'A', 'C', 'G', 'T'};
        unordered_map<string, int> depth;
        depth[startGene] = 0;
        queue<string> q;
        q.push(startGene);
        while (!q.empty()) {
            string s = q.front();
            q.pop();
            for (int i = 0; i < 8; i++)
                for (int j = 0; j < 4; j++)
                    if (s[i] != gene[j]) {
                        string ns = s;
                        ns[i] = gene[j];
                        if (hashBank.find(ns) == hashBank.end()) continue;
                        if (depth.find(ns) != depth.end()) continue;
                        depth[ns] = depth[s] + 1;
                        q.push(ns);
                        if (ns == endGene) return depth[ns];
                    }
        }
        return -1;
    }
};
  1. 329. 矩阵中的最长递增路径 - 力扣（LeetCode）
    法一：拓扑序+BFS
class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        to = vector<vector<int>>(m * n);
        degree = vector<int>(m * n);
        depth = vector<int>(m * n);
        const int dx[4] = {-1, 0, 0, 1};
        const int dy[4] = {0, -1, 1, 0};
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) 
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (valid(ni, nj) && matrix[ni][nj] > matrix[i][j])
                        addEdge(num(i, j), num(ni, nj));
                }
        queue<int> q;
        for (int i = 0; i < m * n; i++)
            if (degree[i] == 0) {
                q.push(i);
                depth[i] = 1;
            }
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int y : to[x]) {
                degree[y]--;
                depth[y] = max(depth[y], depth[x] + 1);
                if (degree[y] == 0) q.push(y);
            }
        }
        int ans = 0;
        for (int i = 0; i < m * n; i++) ans = max(ans, depth[i]);
        return ans;
    }

private:
    vector<vector<int>> to;
    vector<int> degree;
    vector<int> depth;
    int m, n;

    void addEdge(int x, int y) {
        to[x].push_back(y);
        degree[y]++;
    }

    bool valid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
    int num(int i, int j) {
        return i * n + j;
    }
};

法二：DFS+记忆化

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        this->matrix = matrix;
        dist = vector<vector<int>>(m, vector<int>(n));
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                ans = max(ans, dfs(i, j));
        return ans;
    }

private:
    const int dx[4] = {-1, 0, 0, 1};
    const int dy[4] = {0, -1, 1, 0};
    vector<vector<int>> dist;
    vector<vector<int>> matrix;
    int m, n;

    bool valid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }

    int dfs(int sx, int sy) {
        if (dist[sx][sy] != 0) return dist[sx][sy];
        dist[sx][sy] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = sx + dx[i];
            int ny = sy + dy[i];
            if (valid(nx, ny) && matrix[nx][ny] > matrix[sx][sy])
                dist[sx][sy] = max(dist[sx][sy], dfs(nx, ny) + 1);
        }
        return dist[sx][sy];
    }
};
  1. 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) {
        for (ListNode* node : lists) {
            if (node == nullptr) continue;
            q.push({node->val, node});
        }
        ListNode head;
        ListNode* tail = &head;
        while (!q.empty()) {
            Node node = q.top();
            q.pop();
            tail->next = node.listNode;
            tail = tail->next;
            ListNode* next = node.listNode->next;
            if (next != nullptr)
                q.push({next->val, next});
        }
        return head.next;
    }

private:
    struct Node {
        int key;
        ListNode* listNode;
        bool operator <(const Node& r) const {
            return key > r.key;
        }
    };

    priority_queue<Node> q;
};

法二：二叉堆

/**
 * 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) {}
 * };
 */

struct Node {
    int key;
    ListNode* listNode;
};

class BinaryHeap {
public:
    BinaryHeap() {
        heap.push_back({0, nullptr});
    }

    bool empty() {
        return heap.size() == 1;
    }

    Node getMin() {
        return heap[1];
    }

    void insert(Node node) {
        heap.push_back(node);
        heapifyUp(heap.size() - 1);
    }

    void removeMin() {
        heap[1] = heap[heap.size() - 1];
        heap.pop_back();
        heapifyDown(1);
    }

private:
    vector<Node> heap;

    void heapifyUp(int p) {
        while (p > 1) {
            int fa = p / 2;
            if (heap[fa].key > heap[p].key) {
                swap(heap[fa], heap[p]);
                p = fa;
            }
            else break;
        }
    }

    void heapifyDown(int p) {
        int child = p * 2;
        while (child < heap.size()) {
            int other = p * 2 + 1;
            if (other < heap.size() && heap[other].key < heap[child].key)
                child = other;
            if (heap[p].key > heap[child].key) {
                swap(heap[p], heap[child]);
                p = child;
                child = p * 2;
            }
            else break;
        }
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        BinaryHeap q;
        for (ListNode* node : lists) {
            if (node == nullptr) continue;
            q.insert({node->val, node});
        }
        ListNode head;
        ListNode* tail = &head;
        while (!q.empty()) {
            Node node = q.getMin();
            q.removeMin();
            tail->next = node.listNode;
            tail = tail->next;
            ListNode* next = node.listNode->next;
            if (next != nullptr)
                q.insert({next->val, next});
        }
        return head.next;
    }
};
  1. 239. 滑动窗口最大值 - 力扣（LeetCode）
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // <val, idx>
        priority_queue<pair<int, int>> q;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            q.push({nums[i], i});
            if (i >= k - 1) {
                while (q.top().second <= i - k) q.pop();
                ans.push_back(q.top().first);
            }
        }
        return ans;
    }
};
  1. 701. 二叉搜索树中的插入操作 - 力扣（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* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr)
            return new TreeNode(val);
        if (val < root->val)
            root->left = insertIntoBST(root->left, val);
        else
            root->right = insertIntoBST(root->right, val);
        return root;
    }
};
  1. 面试题 04.06. 后继者 - 力扣（LeetCode）
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* ans = nullptr;
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (cur->val == p->val) {
                if (p->right != nullptr) {
                    ans = p->right;
                    while (ans->left != nullptr) ans = ans->left;
                }
                break; // 因为如果p没有右孩子，则其后继一定在走过的节点中，所以此时一定已经有结果了，直接退出循环
            }
            else if (cur->val > p->val) {
                // 此处为大于p的最小值
                if (ans == nullptr || ans->val > cur->val)
                    ans = cur;
                cur = cur->left;
            }
            else
                cur = cur->right;
        }
        return ans;
    }
};
  1. 450. 删除二叉搜索树中的节点 - 力扣（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* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return nullptr;
        if (root->val == key) {
            if (root->left == nullptr) return root->right;
            if (root->right == nullptr) return root->left;
            TreeNode* next = root->right;
            while (next->left != nullptr) next = next->left;
            root->val = next->val;
            root->right = deleteNode(root->right, next->val);
        }
        else if (root->val < key)
            root->right = deleteNode(root->right, key);
        else
            root->left = deleteNode(root->left, key);
        return root;
    }
};
  1. 704. 二分查找 - 力扣（LeetCode）
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) 
                return mid;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
};
  1. 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[right];
    }
};
  1. 154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right])
                right = mid;
            else if (nums[mid] > nums[right])
                left = mid + 1;
            else
                right--;
        }
        return nums[right];
    }
};
  1. 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        // 第一个>=target
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target)
                right = mid;
            else
                left = mid + 1;
        }
        ans.push_back(right);
        // 最后一个<=target
        left = -1, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        ans.push_back(right);
        if (ans[0] > ans[1]) return {-1, -1};
        return ans;
    }
};
  1. 69. x 的平方根 - 力扣（LeetCode）
class Solution {
public:
    int mySqrt(int x) {
        // 找最大target使得，target*target<=x
        int left = 0, right = x;
        while (left < right) {
            int mid = left + 1 + (right -left - 1) / 2; // 防止越界
            if (mid <= x / mid)
                left = mid;
            else
                right = mid - 1;
        }
        return right;
    }
};

// (2 * left - left + right - 1  + 2) / 2 = left + 1 + (right -left - 1) / 2
  1. 162. 寻找峰值 - 力扣（LeetCode）
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // 三分查找
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int lmid = (left + right) / 2;
            int rmid = lmid + 1;
            if (nums[lmid] >= nums[rmid])
                right = rmid - 1;
            else
                left = lmid + 1;
        }
        return right;
    }
};
  1. 410. 分割数组的最大值 - 力扣（LeetCode）
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        // 求解：最小化“m个子数组各自和的最大值”
        // 判定：给一个数值T，“m个子数组各自和的最大值<=T”是否合法
        // 换一种说法：能否将nums分成m个连续子数组，每组和<=T
        int left = 0, right = 0;
        for (int num : nums) {
            left = max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = (left + right) / 2;
            if (valid(nums, k, mid))
                right = mid;
            else
                left = mid + 1;
        }
        return right;
    }

private:
    bool valid(vector<int>& nums, int k, int size) {
        int box = 0;
        int cnt = 1;
        for (int num : nums) {
            if (box + num <= size)
                box += num;
            else {
                box = num;
                cnt++;
            }
        }
        return cnt <= k;
    }
};
  1. 1482. 制作 m 束花所需的最少天数 - 力扣（LeetCode）
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int latestDay = 0;
        for (int day : bloomDay)
            latestDay = max(latestDay, day);
        int left = 0, right = latestDay + 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (valid(bloomDay, m, k, mid)) 
                right = mid;
            else
                left = mid + 1;
        }
        if (right == latestDay + 1) return -1;
        return right;
    }

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

推荐阅读更多精彩内容