2022四月算法学习日志

4.6

静态链表查找首个共有节点

判断全等少了个=运行出错

节点定义中没有节点地址（被记录为结点数组的下标）

输出有序静态链表

用return同时判断结果相同的几种情况；

输出时注意分情况讨论：1.最后一个节点next-1；2.结点数为0；

输出加换行符；

algorithm中的sort函数，false则交换；

reversing linked list

将地址、数据、指针分开用数组表示

reverse可用取补的运算

4.7

pop stack

判断可行的出栈顺序：将入栈的栈顶元素与被判断序列一一比对，相同弹出，不同则压进栈；

vector v(n+1);

4.11

移除元素

给函数调用出的结果一个简洁的名称

int size=nums.size();

注意边界控制 & 新一轮循环覆盖i的起始位置：

j=i+1;j<size;j++;
nums[j-1]=nums[j];

用快慢指针法求解

4.12

长度最小子数组

若c小于count，则更新count为c

普通写法：if (c < count) count = c;

“高级”写法:count = c < count ? c : count;

在循环中要注意累加结果来由于 自然结束or符合判断条件结束 ，防止后一种假结果

用滑动窗口求解

	while(sum>=target){
			int dis=j-i+1;
			count=dis<count?dis:count;
			sum-=nums[i++];
		}

4.13

螺旋矩阵

考虑到奇偶两种不同情况

移除链表元素

需要考虑头结点 && 用while而非用if（头结点不保证只有一个相同）

若想统一处理，则使用虚拟头结点

控制边界：

p!=NULL && p->next!=NULL;

free和mall匹配：释放malloc出来动态内存;
delete和new匹配：释放new出来的动态内存空间。

4.14

设计链表

构造函数就是用来初始化结构体的一种函数，它直接定义在结构体中。

构造函数的一个特点是它不需要写返回类型，且函数名与结构体名相同。

一般来说，对一个普通定义的结构体，其内部会生成一个默认的构造函数（但不可见）。正是由于这个构造函数的存在，才可以直接定义 StudentInfo 类型的变量而不进行初始化（因为它没有让用户提供任何初始化参数）

如果自己重新定义了构造函数，则不能不经初始化就定义结构体变量.

只要参数个数和类型不完全相同，就可以定义任意多个构造函数，以适应不同的初始化场合。

边界条件：插入/删除/查找时，注意Index position索引是否有效（>0&&<size-1）

语法：c++里是 delete cur; 而非 delete(cur);

注意_size即链表长度记录的更新；

private放置在public之前报错 类方法访问成员变量？？

反转链表

双指针法:

pre开始要指到NULL，即为反转链表的链尾；

要有tmp暂存cur的位置；

C++是强类型语言，void*不能隐式转换成其他类型的指针；在C++中，NULL实际上是0；C++11加入了nullptr，可以保证在任何情况下都代表空指针；

4.15

两两交换链表中的节点

新建节点和新建指针不是一回事：

新建节点 _dummyHead=new ListNode(0);
新建指针 ListNode* cur;

注意循环起始位的位置；

删除链表倒数第N个元素

快慢指针；

fast首先走n + 1步 ，这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）；

链表相交

c++中整数绝对值函数为abs()；

考虑没有交点的特殊情况，不用额外判断：

while(cur!=NULL){if... return...}
return NULL

4.17

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

当我们要使用集合来解决哈希问题的时候：

优先使用unordered_set，因为它的查询和增删效率是最优的；

如果需要集合是有序的，那么就用set；

如果要求不仅有序还要有重复数据的话，那么就用multiset。

反转字符串

可以使用c++库函数swap交换元素。

有效的字母异位词

c++中获得字符数组数组str的长度：

str.length();
str.size();

遍历检查哈希数组的时候，使用数组的长度，而非任意被比较字符串的长度

两个数组的交集

使用数组来做哈希的题目，如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

建议全文背诵标准答案：unorder_set构造，for(num:nums2)遍历，record_set.insert(num);

4.18

反转字符串

替换空格

搞替换啥了的，首先要扩充数组

s.resize(s.size()+count*2);

[c++输入字符串的几种方式]((10条消息) C++中输入字符串的几种方法_lixiaoyu20106587的博客-CSDN博客_c++输入字符串)

快乐数

无限循环->元素重复出现->判断用哈希

获得数位循环的时候：

1.判断条件可以为 while(n)

2.不要忘记n/10!

unordered_set的find、insert用法

4.19

两数之和

set是一个集合，里面放的元素只能是一个key；

map是一种key value的存储结构，可以用key保存数值，用value保存数值所在的下标。

指向map的迭代器：

(*it).first会得到key，

(*it).second会得到value。

这等同于`it->first`和`it->second`

通过map的insert()可以把一个pair对象作为map 的参数

函数需要返回数组，但没有符合条件的数组的时候，return{ }即可；

反转字符串里的单词

四数之和

分组打包相加——重要的不是数字本身，是它们组合产生的结果

c++遍历 for(int a:A){}

4.20

左旋转字符串

反转字符串的特殊思路：先局部再整体/先整体再局部

简洁表达

int i=0,j=n-1;reverse(s[i],s[j]);
可表达为
reverse(s.begin(),s.begin()+n);

赎金信

在元素类型确定（数组长度确定）的情况下，直接使用数组比使用map合理，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。

4.22

三数之和

要用数组找什么东西的时候，可以先排个序：方便剔除掉不可能的情况，或者找到重复值

sort(nums.begin(),nums.end());

注意去重的处理

若使用哈希法，对j去重时，须考虑到[0,0,0]的情况，则j的循环条件为：

if((j>i+2) && (nums[j]==nums[j-1]) && (nums[j-1]==nums[j-2])) continue;

除了首个元素之外且要保证 i 不越界的判断条件

for(i>0 && nums[i]==nums[i-1]) continue;

4.24

四数之和

哈希去重困难，推荐双指针；

比起k++,continue能多一层对边界判断；

时刻控制边界条件 left<right；

给vector数组追加数组元素的姿势

result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});

vector<vector >的输出

for(int i=0;i<result.size();i++){
		for(int j=0;j<4;j++){
			cout<<result[i][j]<<" ";
		}
		cout<<endl;		
	}

KMP算法实现strStr()

KMP算法时间复杂度：O(m+n) 比较&生成next数组

双指针的优势

通过两个指针在一个for循环下完成两个for循环的工作

环形链表

4.25

经常用到的功能可以抽象成函数或工具类以复用提高效率

myQueue(){
	pop(){...}
	peek(){
		int res=this->pop;
		stOut.push(res);
		...
	}
}

用栈实现队列 & 用队列实现栈

与栈相关的方法为 pop()；与队列相关的方法为 front()、back()、pop()；

有效的括号

逆向思维：做到对的->避免错的

string初始化

string s="{[]}";

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中

删除字符串中的所有相邻重复项

将栈中元素放到result字符串汇总
string result=" ";
while(!st.empty()){
  result+=st.top();
  st.pop();
}

4.26

逆波兰表达式求值

将字符数组中元素转化为数值元素压入栈

st.push(stoi(token[i]));

c++中，双引号中间的数据视作字符串，单引号中间的数据视作字符。

细心！取数组长度的时候注意是取谁的·size();

滑动窗口最大值

单调队列，即单调递减或单调递增的队列

deque容器，pop函数有两种类型：pop_back()、pop_front();

前k个高频元素

依据map的值/结构体某元素进行比较：类似于cmp

return lhs.second>rhs.second;

4.28

二叉树基础知识

结构体中：
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	};
TreeNode(int x) : val(x), left(NULL), right(NULL) {} 意为初始化支持 TreeNode（int x）这种方式，即 把x赋给val，left和right赋值NULL。

前序中序后序遍历

调用函数注意引用加&号；

4.29

递归和迭代的区别

递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环;
迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)。
在循环的次数较大的时候，迭代的效率明显高于递归。
————————————————
版权声明：本文为CSDN博主「围巢111」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40817827/article/details/89950325

vector顺序访问除了i的另一种调用方法

for(vector<int>::iterator:it=res.begin;it!=res.end();it++){}

push和push_back

push_back：将一个新的元素加到vector的最后面；

push：

stack::push();//在栈顶增加元素
queue::push();//将x接到队列的末端。

迭代法前中后序遍历二叉树

前序变后序：

1、交换左右子节点压栈顺序：中左右->中右左；

2、reverse一下result：中右左->左右中；

用标记法统一二叉树的迭代

入栈时给中结点前加入空指针，以便使用判断语句把中结点区别开放入结果集；