思路维护当前构建的字符串 cur。用两个计数器：left（已使用的左括号数）、right（已使用的右括号数）。递归条件：当 left == n 且 right == n 时，当前字符串是一个有效组合，加入结果。如果 left < n，可以继续添加 '('（左括号随时可以加，只要不超过 n）。如果 right < left，可以继续添加 ')'（右括号只有在已使用的左括号更多时才能加，以保证匹配）。使用 push_back 和 pop_back 实现回溯，避免字符串拷贝。先尝试添加左括号，再尝试添加右括号 #include <functional> #include &l...

类似：题解 | 有重复项数字的全排列：递归+回溯+去重剪枝思路：将字符串拆分为单个字符，并对字符进行排序，便于后续去重然后可以按照有重复数字的全排列进行解题 #include <algorithm> #include <functional> #include <string> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 * @return string字符串vect...

思路：循环遍历数组，如果遇到一个1，则将岛屿数量++同时对上下左右四个方向进行深度优先遍历（dfs使周围为1的值改为0，以防止深度优先遍历过后，再访问到1重复增加岛屿数量）遍历所有格子后，count值就是岛屿数量步骤：首先判断二维数组是否为空初始化数组的行数m、列数n、岛屿数量为0双层for循环遍历数组：如果此时遍历到的grid[i][j]=='1'，则count++，进行dfsdfs：若访问值合法未越界且值为1，则将此时值改为0，再继续进行上下左右方向的深度优先遍历。循环完毕，返回岛屿数量。正确答案： class Solution { public: /** * 代码中的类名、方法名、参数名...

题解 | 没有重复项数字的全排列：递归＋回溯去重思路在同一层的for循环中判断，i>0 && num[i]==num[i-1] && used[i-1]==false前一个数字未被使用（!used[i-1]，说明它在本层还没被选过，是重复的起点）满足的话就跳过该数字 #include <algorithm> #include <functional> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型ve...

回溯：是“原路返回”这一步，去试其他的路思路：维护一个向量path，用于记录正在排列的数字维护一个和数组同样大的布尔数组used，用来标记该位置是否使用过若path长度和原数组长度一样，则可以加入res作为一个返回递归在num中选一个未使用过的，加入path，设置为已使用，递归处理其他位置回溯：弹出当前最后一个位置标记为未使用匿名函数lambda 表达式：function<void()>dfs = [&]() {};没有返回值和参数，作为一个表达式很多时候只需要一个很短小的函数，只用一次，或者作为参数传给别的函数。 #include <functional> /...

思路：固定数组中的一个值为a，那么就是找到数组中另外两个数相加=-a；首先对数组进行排序顺序遍历数组，让数组中的每个数可以为一个“基准”a同时锁定除a外的一个区间，在区间里寻找满足相加=-a的值加入二维数组res中步骤：使用sort函数进行排序for循环遍历数组。去重：如果此时i>0且num[i]=num[i-1]，则直接下一个元素while循环设置双指针找后两个元素，在区间 [i+1, n-1] 中设置 left = i+1，right = n-1。计算当前和 s = num[i] + num[left] + num[right]。如果 s == 0：找到一个合法三元组，加入结果。去重...

思路：遍历存储哈希表遍历判断 #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int minNumberDisappeared(vector<int>& nums) { // write code here unordered_map<int, int> mp; for (int i = 0; i < nums....

思路：遍历存入哈希若哈希表中存在数组中的值，则让对应的value值加一；若没有则插入 #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @return int整型 */ int MoreThanHalfNum_Solution(vector<int>& numbers) { // write code here unordered_map<int, in...

思路设置一个补数temp为目标值-当前值，查看是否已经存储在哈希表中，若已经存储，直接返回已经存储的下标和当前下标（已经有序），如果没有，则插入当前值（先查后存）步骤初始化哈希表顺序遍历数组 for (int i = 0; i < n; i++)初始化补数值 temp=target-numbers[i];如果能在哈希表查找到，则返回{mp[temp],i+1} // 数字下标从1开始如果在哈希表中找不到，则插入当前值到哈希表中 mp[numbers[i]]=i+1;遍历完整个数组没找到，返回空知识点哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味...

使用两个栈实现：nums：存储数字（使用 long long 防止中间计算溢出）ops：存储操作符思路遍历字符串：遇到数字：解析完整数字（可能多位），压入 nums。遇到 (：直接压入 ops。遇到 )：反复弹出操作符并计算，直到遇到 (，再弹出 (。遇到操作符 +、-、*：只要 ops 不为空、栈顶不是 (，且栈顶操作符优先级 ≥ 当前操作符优先级，就弹出栈顶操作符和两个数字进行计算，结果压回 nums。然后将当前操作符压入 ops。遍历结束：将 ops 中剩余操作符全部弹出计算。最终 nums 栈顶即为结果。优先级：+ 和 -：优先级 1*：优先级 2同优先级左结合，因此 >= 时弹...

思路：维护两个堆，一个最大堆，一个最小堆优先加入最大堆，若为奇数，中位数应该在最大堆中步骤插入函数Insert判断最大堆是否为空或者num值小于最大堆，若是加入最大堆，否则加入最小堆判断两个堆的大小关系查询中位数函数GetMedian如果最大堆大小 > 最小堆，则直接返回最大堆顶，否则返回两个堆顶的平均数 #include <vector> class Solution { public: priority_queue<int> maxheap; priority_queue<int, vector<int>, greater<>&g...

思路：快速选择算法每次选择一个pivot进行partition操作，将大于等于pivot的元素放在左侧，小于的放在右侧。partition结束后pivot位于最终位置上。初始化一个递归函数来确定第K大的值：根据partition后pivot的位置计算左侧较大元素的个数：leftcount=p-l+1;步骤：partition函数让最后一个元素为基准元素，然后设置i初始指向 low 的左边（相当于还没开始）。i标记“左边区域的右边界”。遍历l到r部分，临时指针j指向初始l，如果遍历过程中有a[j]>=pivot，就让i++扩大左边区域，交换a[i],a[j]把大的换到左边来。findKth...

使用堆维护最小的k个数堆的定义结构：堆是一棵完全二叉树（除了最后一层，其他层都满，最后一层从左到右填充）。用数组存储很方便：对于节点索引 i，左孩子：2*i + 1右孩子：2*i + 2父节点：(i-1)/2堆性质（Heap Property）：大顶堆（Max Heap）：每个父节点的值 ≥ 所有子节点的值。→ 根节点（堆顶）是最大值。小顶堆（Min Heap）：每个父节点的值 ≤ 所有子节点的值。→ 根节点（堆顶）是最小值。堆不是排序好的树（不像二叉搜索树），它只保证父子关系，不保证左右子树关系，所以中序遍历不是有序的。思路：创建一个大顶堆用来存放k个数，当有数来的时候和堆顶元素比较，比堆顶...

思路：初始化一个栈用来存放字符串中的每个字符如果来的字符是（、[、{中的一种，就入栈如果是)、]、}中的一种，就和栈顶元素比较，不匹配或者栈此时为空就返回false；步骤：若字符串为空，返回true初始化栈循环遍历字符串中的每个字符 for(char c:s){}如果来的字符是（、[、{中的一种，就push否则：栈空返回fales；栈非空，取出栈顶元素top（然后弹出pop），和c进行比较。不匹配返回false。如果匹配，则继续下一个字符判断，直到比较完所有字符，查看栈中是否为空循环完，栈非空，则false知识点：范围基于循环 for (声明 : 表达式) { // 循环体 } 声明：定义一个...