2022.0815算法第27题按之字形顺序打印二叉树 这道题目使用广度优先遍历BFS，只是对遍历出来的结果进行处理 并没有修改遍历的顺序。 res.push_back(temp); flag++; if(flag%2==0){     reverse(res[flag-1].begin(),res[flag-1].end()); } 采用flag做标志位，对遍历结果进行反转。 if (level % 2 == 0) {     //&n...

2022.0815算法第26题最长公共子串 这个和最长公共子序列采用的方法是一样的，需要构造状态矩阵，记录当前的子串状态。 主要在于获取最长子串的位置，用于分割子串。 可以记录最长子串的长度和最长子串出现的最后的索引位置。 这点需要使用两个变量 int maxLength=0,end=0; 然后获取状态矩阵 for(int i=1;i<=str1.size();i++){     for(int j=1;j<=str2.size();j++){    ...

2022.0815算法第25题最小花费爬楼梯 这个方法也是要找到递推关系式， res[i]=min(res[i-1]+cost[i-1],res[i-2]+cost[i-2]); 感觉这个和高中求数列是十分相似的，有初始值，有递推公式，这样也可以求出来通项 计算机则直接可以通过循环进行求解。 1、初始值 2、递推公式

2022.0815算法第24题跳台阶 这个解决方法和斐波那契数列一样，知识初始值不同。 但是最主要的是想到使用这个方法进行求解。 感觉这类问题都是需要找到状态转移方程，也就是状态数列的n和状态n-1等的关系。 递推公式就是这样， int a = 1, b = 1, sum; for(int i = 0; i < n; i++){     sum = (a&nbsp...

2022.0815算法第23题斐波那契数列 动态规划dynamic programing的入门级题目。 可以从后往前，也可以从前往后 从后往前需要递归，从后往前需要循环。 从后往前的代码： vector<int> res(n+1); res[1]=1; res[2]=1; for(int i=3;i<n+1;i++){     res[i]=res[i-1]+res[i-2]; } return res[n]; //迭代的代码 if(n==0)   &nbs...

2022.0815算法第22题链表相加(二) 对链表表示的两个整数进行相加，返回一个结果链表 首先要知道倒序相加算法，将低位相加，确保进位正确，把短的链表后面的数据视为零 最后一位需要进位时单独进行判断。 首先创建头指针和尾指针，以及进位标志。 ListNode* head=nullptr,*tail=nullptr; int carry=0; 确保当一个链表为空时仍然能够向后继续刷新，后面的视为0 对同位数字进行相加 int n1=head1?head1->val:0; int n2=head2?head2-...

2022.0814算法第21题最长公共子序列(二) 动态规划问题，但是做的比较少还没有理解动态规划的主要套路。 这个需要先求解一个二维矩阵，求解出最长子序列的长度，然后根据指示方向取出最长子序列。 第一步需要求解最长子序列长度，并记录当前字符的方向，也就是最长子序列的取值位置方向。 B站最长公共子序列 - 动态规划 Longest Common Subsequence - Dynamic Programming_哔哩哔哩_bilibili介绍的很清楚建议观看视频 if(s1[i-1]==s2.at(j-1)){     res[i][j]=res...

2022.0814算法第20题没有重复项数字的全排列 全排列采用递归回溯的思想， 递归是一种算法结构，回溯是一种算法思想 一个递归就是在函数中调用函数本身来解决问题。 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”。 回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用）， 回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。 递归回溯的思路还是挺好理解的，就是...

2022.0808算法第19题缺失的第一个正整数 哈希表也能解决这个问题，思路也很简单。 缺失的第一个正整数肯定是1-n+1之间的数，n为数组内元素的个数 因此只需要将数组内的元素存入哈希表，然后判断1-n+1之间的最小的不在hash中的数。 不采用hash存储时，也可以通过数组本身存储元素的特征，数组本身具有下标和值两个属性。 首先将非正数赋值为n+1， for(int i=0;i<nums.size();i++){     if(nums[i]<=0)    &nb...

2022.0808算法第18题数组中只出现一次的两个数字 这个问题可以使用哈希表进行求解，排序法也可以，异或运算是最正确的解法 异或运算牵扯到位运算，还没理解透。 采用哈希表的方法进行求解， 使用哈希表存储元素值和出现的次数，选择出现次数为1的元素进行输出 最后结果及逆行排序。 for(const int val : array){     hash[val]++;      } for(const int val&nbs...

2022.0808算法第17题数组中出现次数超过一半的数字 这道题有多种解法，哈希表法、排序法、BM投票法等 哈希表法记录每个元素出现的次数，最后找出次数大于size/2的元素 排序法直接选择排序后中间位置的数字即可 BM投票法是将相邻两个元素判断是否相等，如果相等则计数+1，否则计数-1； 当计数==0时，更新候选元素， 这样在最后剩下的候选元素就是次数超过一半的数字； 首先定义候选元素，并计数 int cand=numbers[0]; int count=1; 然后遍历数组，更新计数和候选元素 for(int ...

2022.0807算法第16题包含min函数的栈 算法要求min的复杂度为常数，刚开始想到了用一个变量存储min，存储时更新min没有问题，但是在pop删除操作时就比较麻烦了。 如果栈顶元素为最小值，删除之后的最小值就不知道了。 因此需要其他的结构存储最小值，可以使用一个辅助栈进行存储。 辅助栈里存储着当前栈元素的最小值，push操作一样，pop时只需要同样取出辅助栈的元素即可。 也就是以空间换时间的做法。 实现push函数： 当栈为空或者当前元素小于最小值时，更新辅助栈的值 否则直接将辅助栈的栈顶元素重复加入。 void push...

2022.0807算法第15题两数之和 利用哈希表进行求解，也可暴力求解。 哈希表中查询元素时间复杂度为常数，这点是使用哈希表的关键。 遍历数组，计算当前值与目标值的差值，并在哈希表中查找差值， 哈希表中没有则将当前元素存入哈希表，找到直接返回即可。 对哈希表了解较少，需要补充。

2022.0806算法第14题用两个栈实现队列 使用两个栈实现队列，需要将一个栈作为进，一个栈作为出。 push操作只需要存入stack1即可， pop操作需要对反转顺序的stack2进行操作。 首先需要判断stack2的数据是否需要更新，也就是stack2中是否还有元素 如果stack2中已经没有元素，需要将stack1中的元素进行传递 if(stack2.empty()) {     while(!stack1.empty())     {   &n...