马士兵LeetCode算法讲解
目录:
2021年4月2日14:07:01
Morris遍历——二叉树遍历
1、普通二叉树遍历有中序,先序和后序遍历,时间复杂度为O(n),空间复杂度为O(n)。
2、Morris遍历时间复杂度为O(n),空间复杂度为O(1)。
当有左孩子的节点会出现两次,没有左孩子的节点只出现一次:
1、2、3、分别代表先序,中序,后序,
空间复杂度为O(1),打印时使用反转链表
2021年4月6日09:54:50
N皇后问题
共行不用判断,默认不共行
判断共列 或 共斜线
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k))
当问题的基数过多时,运算时间需要很多~
可以通过 位运算 来优化
时间复杂度 N的n次方
怎么尝试一件事
动态递归
暴力递归
斐波那锲数列
if (n == 1){
return 1;
}
If (n == 2) {
return 1;
}
else
return f(n-1) + f(n-2);
动态规划来源于暴力递归
2021年4月8日23:40:14
背包问题
当发现大量重复问题时,暴力递归会消耗过多的资源,
可考虑用动态规划;
机器人问题
货币问题
每种面值可以使用任一张,给你一个钱数,有多少种组合方法可以排列出钱数,要知道有没有重复解,有重复行为就需要优化,
记忆化搜索
2021年4月10日23:01:22
dijkstra最短路径算法
汉诺塔问题
2021年4月11日17:27:56
设计一颗打印整棵树的打印函数---二叉树的中序遍历
打印顺序:右-》中-》左
后续节点:中序遍历的时候这个节点的下一个节点称为后续节点
前驱节点:中序遍历的时候一个节点的前一个节点
纸条折痕问题---打印二叉树(中序遍历)
代码:
递归调用:
二叉树的递归套路
可以解决面试中绝大多数的二叉树问题尤其是树形dp问题
本质是利用遍历递归二叉树的便利性
多叉树:
2021年4月16日16:45:41
二叉树的基本算法
二叉树的结构
先序遍历:
中序遍历:
后序遍历:
先序;中序;后序 打印位置不同
每个节点都有head,head.left, head.right
只不过叶子节点的左右子树为空null
遍历的时候每个节点都会到达三次
遍历的时候每个节点都会到达三次,先序中序后序的区别是打印的时间不同,分别是第一次第二次第三次
非递归遍历打印二叉树
非递归先序遍历:
由于栈是先进后出,所以先压进右,再压左:
代码:
非递归中序遍历
代码:
非递归后序的逆序
非递归后序遍历:
使用了两个栈,第一个栈压进压出实现遍历的逆序,存储到第二个栈中再打印就变成了顺序,实现了后序遍历:
用一个栈实现后序非递归遍历:
二叉树的反序列化
将子树的最后空节点补齐,可以反映树的结构
2021年4月17日15:20:27
经典面试题目一
搜索二叉树BST
每颗树的左树都比他小,右树都比他大
2021年4月18日13:47:30
字符串匹配
2021年4月23日17:58:57
数组生成数值对
主技巧的题和主业务的题
刷LeetCode时候,一定要先做主技巧的题
上面的顶比踩多很多的题一般是主技巧的题!
斗战胜佛
我要是天蒙不住我眼
我要是地埋不住我心
我要纵生都知晓我意
我要神佛都烟消云散
2021年5月13日19:18:44
字符串给定某个位置的限制,交换左右两个子串位置
方法1:
1、左边这部分逆序
2、右边这部分逆序
3、整体逆序
方法2:
循环右移
时间复杂度能达到O(n²)
不合适!
第三种方法:
短的这部分与之交换,剩下的依次短的交换
京东原题
2021年5月20日16:17:02
异或操作