您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

代码随想录:数组/ 链表/ 哈希表/ 字符串/ 双指针 刷题笔记(四月记录)

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:中右左->左右中;

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

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


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进