双指针法，前后指针，并引入了虚拟头结点。首先根据pre和cur判断是否有重复结点，然后据此调整链接关系。这种方法并没有删除结点，会造成内存泄漏。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { ListNode* dummy_head=new ListNode{10...

二叉搜索树的中序遍历是递增的。判断完全二叉树的方法：层次遍历，注意空结点可以入队列，当队列pop的过程中遇到第一个空结点时break，然后检查队列中的剩余元素，如果存在非空结点则不是完全二叉树。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 the root * @return bool布尔型vector */ void in_order(Tre...

因为两个排序数组的大小都是n，上中位数相当于两个数组合并排序之后的第n个数，分别给arr1和arr2设置指针，比较大小，就可以找到第n个数。 class Solution { public: /** * find median in two sorted array * @param arr1 int整型vector the array1 * @param arr2 int整型vector the array2 * @return int整型 */ int findMedianinTwoSortedAray(vector<int>& arr1, vector<int&...

动态规划可以求出最长公共子序列的长度，dp[i][j]表示以i-1结尾的s1和以j-1结尾的s2之间的最长公共子序列长度，由dp[i-1][j]、dp[i][j-1]以及dp[i-1][j-1]这三个上一状态推导出当前状态。 难点在于如何根据dp表的信息得到具体的子序列。从dp的右下角到左上角方向遍历dp数组，途中首次遇到的s1[i-1]==s2[j-1]时的字符s1[i-1]就是公共子串中的字符。 class Solution { public: /** * longest common subsequence * @param s1 string字符串 the string * @para...

首先根据每个区间的起始位置值进行排序，然后遍历排序好的所有区间，设置一个活跃区间cur，并与下一个区间的范围进行比较，当可以扩展cur时对cur进行扩展，否则将cur加入到结果中。注意遍历完之后还剩一个区间，也要加入到结果集中。 /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { ...

动态规划，dp[i][j]表示到位置(i,j)的最大路径数目，当前位置状态由上方和左方推出。 class Solution { public: /** * * @param m int整型 * @param n int整型 * @return int整型 */ int uniquePaths(int m, int n) { vector<vector<int>> dp(m,vector<int>(n,0)); dp[0][0]=1; for(int j=1;j<n;j++) dp[0][j]=1; for(int i=1;i<m;i++) dp[...

保存反转区间的首尾结点指针，用于反转；同时保存反转区间的前一个结点指针和后一个结点指针，用于反转之后的链接。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ void reverse_list(ListNode* left,ListNode* right){ ListNode* pre ...

dfs。前序遍历，当达到叶子节点并且和满足要求时，保存此路径，递归的过程中还要对路径进行回溯。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return int整型vector<vector<>> */ void pre_order(TreeNode* root,vector&...

求二叉树的所有路径，使用先根遍历，递归结束条件为到达叶子节点，同时还要分别递归左子树和右子树之后加入回溯。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ #include<numeric> class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ void dfs(TreeNode* root,vector<string>& resu...

动态规划，插入、删除和替换的代价是不同的。注意题意只能编辑str1。dp[i][j]表示以i-1结尾的str1，和以j-1结尾的str2之间的最小编辑距离。初始化dp的时候只能插入或删除str1，更新dp数组时选择插入、删除、替换的最小值。 class Solution { public: /** * min edit cost * @param str1 string字符串 the string * @param str2 string字符串 the string * @param ic int整型 insert cost * @param dc int整型 delete cost * @p...

使用一个栈将链表倒序的值保存进去，然后正序遍历链表并不断与栈顶元素作比较。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head * @return bool布尔型 */ bool isPail(ListNode* head) { stack<int> stk{}; ListNode* cur=head; while(cur!=nullptr){ stk.push(cur-&...

辗转取余。 class Solution { public: /** * 进制转换 * @param M int整型 给定整数 * @param N int整型 转换到的进制 * @return string字符串 */ string solve(int M, int N) { vector<char> letter{'A','B','C','D','E','F'}; string result{}; bool flag=false; while(M!=0){ if(M<0){ flag=true; M*=-1; } int temp=M % N; if(temp<10...

通过哈希表统计每个字符串出现的次数，pair<string,int>，自定义排序lambda对象，取前k个即可。 class Solution { public: /** * return topK string * @param strings string字符串vector strings * @param k int整型 the k * @return string字符串vector<vector<>> */ vector<vector<string> > topKstrings(vector<string>&amp...

动态规划。dp[i][j]表示走到(i,j)位置时的最小路径和，当前状态由上方和左方两个方向递推得到。注意初始化第一行和第一列。 class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int minPathSum(vector<vector<int> >& matrix) { int n=matrix.size(); int m=matrix[0].size(); vector<vector...