vlambda博客
学习文章列表

马士兵LeetCode算法讲解

目录:

2021年4月2日14:07:01

Morris遍历——二叉树遍历

1、普通二叉树遍历有中序,先序和后序遍历,时间复杂度为O(n),空间复杂度为O(n)。

2、Morris遍历时间复杂度为O(n),空间复杂度为O(1)。

马士兵LeetCode算法讲解

马士兵LeetCode算法讲解

当有左孩子的节点会出现两次,没有左孩子的节点只出现一次:

马士兵LeetCode算法讲解


马士兵LeetCode算法讲解

1、2、3、分别代表先序,中序,后序,

马士兵LeetCode算法讲解

空间复杂度为O(1),打印时使用反转链表

马士兵LeetCode算法讲解



2021年4月6日09:54:50

N皇后问题

马士兵LeetCode算法讲解

共行不用判断,默认不共行

判断共列 或 共斜线

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);

动态规划来源于暴力递归

马士兵LeetCode算法讲解


2021年4月8日23:40:14

背包问题

马士兵LeetCode算法讲解

当发现大量重复问题时,暴力递归会消耗过多的资源,

可考虑用动态规划;


机器人问题

货币问题

每种面值可以使用任一张,给你一个钱数,有多少种组合方法可以排列出钱数,要知道有没有重复解,有重复行为就需要优化,

记忆化搜索


2021年4月10日23:01:22

dijkstra最短路径算法

马士兵LeetCode算法讲解


汉诺塔问题

马士兵LeetCode算法讲解



2021年4月11日17:27:56

设计一颗打印整棵树的打印函数---二叉树的中序遍历

打印顺序:右-》中-》左

后续节点:中序遍历的时候这个节点的下一个节点称为后续节点

前驱节点:中序遍历的时候一个节点的前一个节点

纸条折痕问题---打印二叉树(中序遍历)

马士兵LeetCode算法讲解

马士兵LeetCode算法讲解


代码:

递归调用:

马士兵LeetCode算法讲解


二叉树的递归套路

可以解决面试中绝大多数的二叉树问题尤其是树形dp问题

本质是利用遍历递归二叉树的便利性

马士兵LeetCode算法讲解


多叉树:

马士兵LeetCode算法讲解

马士兵LeetCode算法讲解



2021年4月16日16:45:41

二叉树的基本算法

二叉树的结构

马士兵LeetCode算法讲解

马士兵LeetCode算法讲解

先序遍历:

中序遍历:

后序遍历:

马士兵LeetCode算法讲解

先序;中序;后序  打印位置不同

马士兵LeetCode算法讲解

每个节点都有head,head.left, head.right

只不过叶子节点的左右子树为空null

遍历的时候每个节点都会到达三次

马士兵LeetCode算法讲解

遍历的时候每个节点都会到达三次,先序中序后序的区别是打印的时间不同,分别是第一次第二次第三次


非递归遍历打印二叉树

非递归先序遍历:

由于栈是先进后出,所以先压进右,再压左:

马士兵LeetCode算法讲解

代码:

马士兵LeetCode算法讲解

非递归中序遍历

马士兵LeetCode算法讲解

代码:

马士兵LeetCode算法讲解


非递归后序的逆序


非递归后序遍历:

使用了两个栈,第一个栈压进压出实现遍历的逆序,存储到第二个栈中再打印就变成了顺序,实现了后序遍历:

马士兵LeetCode算法讲解


用一个栈实现后序非递归遍历:

马士兵LeetCode算法讲解


二叉树的反序列化

马士兵LeetCode算法讲解

将子树的最后空节点补齐,可以反映树的结构



2021年4月17日15:20:27

经典面试题目一

搜索二叉树BST

每颗树的左树都比他小,右树都比他大

马士兵LeetCode算法讲解

马士兵LeetCode算法讲解

2021年4月18日13:47:30

字符串匹配

马士兵LeetCode算法讲解


2021年4月23日17:58:57

数组生成数值对

马士兵LeetCode算法讲解

主技巧的题和主业务的题


马士兵LeetCode算法讲解

刷LeetCode时候,一定要先做主技巧的题

上面的顶比踩多很多的题一般是主技巧的题!

马士兵LeetCode算法讲解

斗战胜佛

我要是天蒙不住我眼

我要是地埋不住我心

我要纵生都知晓我意

我要神佛都烟消云散


2021年5月13日19:18:44

马士兵LeetCode算法讲解

字符串给定某个位置的限制,交换左右两个子串位置

方法1:

马士兵LeetCode算法讲解

1、左边这部分逆序

2、右边这部分逆序

3、整体逆序


方法2:

循环右移

马士兵LeetCode算法讲解

时间复杂度能达到O(n²)

不合适!


第三种方法:

短的这部分与之交换,剩下的依次短的交换


马士兵LeetCode算法讲解

马士兵LeetCode算法讲解


马士兵LeetCode算法讲解


京东原题

马士兵LeetCode算法讲解


2021年5月20日16:17:02

异或操作