枚举所有可能的排列：通过递归选择未使用的元素加入当前路径，完成选择后回溯 class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> ans; vector<int> path; vector<bool> used(nums.size(), false); backtrack(nums, ans, path, used); return ans; } void backtrac...

定义最优排序规则若a+b > b+a，则a应排在b前面 class Solution { public: string largestNumber(vector<int>& nums) { // 将所有数字转为字符串 vector<string> strNums; for (int num : nums) { strNums.push_back(to_string(num)); } // 自定义排序规则 sort(strNums.begin(), strNums.end(), [](const string& a, const string&amp...

二分枚举所有的半边长，然后进行验证来找到合法正方形能包含的最多点数 class Solution { public: int check(long long i, vector<vector<int>>& points, string s) { unordered_set<char> labels; int cnt = 0; for (int idx = 0; idx < points.size(); idx++) { long long x = points[idx][0]; long long y = points[idx][1]; // ...

用二分查找锁定最大可能的最小差值，验证该差值是否能满足每个区间的选择限制 class Solution { public: bool check(long long lim,vector<int>& start,int d) { long long now = start[0]; for (int i = 1; i < start.size(); i++) { now = max(now + lim, 1LL * start[i]); if (now > start[i] + d) return false; } return true; }; int maxP...

用排序 + 二分查找快速统计每个咒语对应的成功药水数量：先将药水数组排序，再对每个咒语计算所需的最小药水强度，通过二分查找定位该强度的位置，从而得到符合条件的药水数量。 class Solution { public: vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) { sort(potions.begin(), potions.end()); //排序 vector<int> ans; for (i...

用哈希表统计当前窗口内每种物品的保留次数； 遍历每天的物品： 先尝试保留当前物品，若保留后该物品次数超过m，则丢弃 当遍历天数超过w时，滑动窗口左边界，移除i-w+1天的物品，减少其计数。 class Solution { public: int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) { int ans = 0; unordered_map<int, int> cnt; // 统计当前窗口内每种物品的保留次数 for (int i = 0; i < arrivals.size()...

滑动窗口 ，直接统计合法子串用滑动窗口维护[left, right]区间，保证区间内包含所有字符，当窗口满足条件时，所有以right为结尾、以[0, left-1]为起点的子串都合法，数量为left； 移动左指针缩小窗口，继续统计。 class Solution { public: int numberOfSubstrings(string s) { int ans = 0, left = 0; unordered_map<int, int> cnt; // 统计a、b、c的出现次数 for (char c : s) { cnt[c - 'a']++; // 右指针右移，统计当前字...

为了满足题目中每个编码都不能是另一个前缀，因此用哈夫曼树可以实现，k进制就是k叉的哈夫曼树，哈夫曼树的带权路径和就是编码长度，树高就是字符串长度。 用最小优先队列实现最优合并，核心思路是先补 0 使节点数满足 k 叉哈夫曼树的结构要求，再循环取出权值最小的 k 个节点合并，累加求权值和，记录合并后节点的高度，重复这个操作直到队列里面只有一个元素，最终输出总长度和树高。 #define ll long long using namespace std; // 节点结构：w为权值，h为高度 struct node { ll w,h; node(){w=0,h=0;} node(ll w,ll h)...

利用栈实现中序遍历，先遍历到左子树最深处并将路径节点入栈，弹出栈顶节点（根）记录值，再遍历其右子树，重复该过程直至所有节点处理完毕。 class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> stk; // 存储遍历路径的节点 vector<int> ans; // 存储中序遍历结果 // 栈非空或当前节点非空，继续遍历 while(!stk.empty() || root != nullptr){ // 遍历到左子树最深处，沿途节点入栈 ...

对二叉搜索树进行中序遍历，用数组保存结点，用另一个数组保存结点的值，然后找到值错误的两个结点，然后直接交换值就行  class Solution { public: void recoverTree(TreeNode* root) { vector<int> vals; vector<TreeNode*> nodes; stack<TreeNode*> stk; TreeNode* curr = root; // 非递归中序遍历 while (curr != nullptr || !stk.empty()) { while (curr != nullptr)...

对每个结点的左子树和右子树进行递归验证是否为二叉搜索树，如果左右子树都是二叉搜索树且与根节点比较没问题，然后返回true class Solution { public: bool isValidBST(TreeNode* root) { return dfs(root, LLONG_MIN, LLONG_MAX); } bool dfs(TreeNode* root, long long lower, long long upper) { if (root == nullptr) return true; if (root->val <= lower || root->va...

用分治递归生成所有合法的二叉搜索树： 在区间[left, right]，我们依次选每个值i作为根节点，递归生成左子树区间和右子树区间的所有可能结构，再将左、右子树的所有组合与根节点拼接，得到当前区间的所有二叉搜索树。 class Solution { public: vector<TreeNode*> generateTrees(int n) { return dfs(1, n); // 从区间[1,n]开始递归 } // 生成区间[left, right]对应的所有二叉搜索树 vector<TreeNode*> dfs(int left, int right) { i...

用栈记录括号的下标，通过栈顶元素定位有效括号的起始位置，计算最长长度。若遇到左括号，将其下标入栈；若遇到右括号，先弹出栈顶元素，若弹出后栈为空，说明当前右括号是新的无效起始点，将其下标入栈；若栈非空，用当前下标减去栈顶元素，得到以当前右括号为结尾的有效括号长度，更新最大长度，以下是代码解析：  class Solution {public: int longestValidParentheses(string s) { stack<int> st; st.push(-1); // 初始参考点，简化长度计算 int maxLen = 0; for (int i = 0; i <...

核心是用单调递增栈快速定位每个柱子的左右边界，计算以该柱子为高的最大矩形面积，然后取所有最大矩形最大值 以下是代码解析：  class Solution { public:     int largestRectangleArea(vector<int>& heights) {         if (heights.empty()) return 0;         // 首尾加0，简化边界处理 vector<int> res(heights.size() +...