算法题笔记
2020-04-01 本文已影响0人
我是电饭煲
算法面试通关40讲教程
《链表》
Reverse Linked List翻转链表
image.png
Swap Nodes in Pairs链表交换相邻元素
https://www.cxyxiaowu.com/2289.html
TIM图片20200111220341.jpg
image.png
Linked List Cycle链表是否有环
image.png
image.png
栈、队列
Valid Parentheses判断括号字符串是否有效
image.png
image.png
image.png
Implement Queue using Stacks用栈实现队列
image.png
Implement Stack using Queues用队列实现栈
优先队列
image.png
Kth Largest Element in a Stream在流式数据中查找第k大的数（优先队列）
// 有k个元素的最小优先队列，第一个元素相当于k个元素里的第k大的数
// 1.保证优先队列个数为k
// 2.新数据 < 第一个数据，不如队列，反之，入队，并通过优先队列的原理，第k大的数会成为第一个元素。
image.png
image.png
Maximum Length of a Concatenated String with Unique Characters 返回滑动窗口中的最大值（优先队列）
- 解法
1.最大堆 NlogN
2.双端队列 N*1
映射（map）及集合（set）
- 实现方式
1.hashtab（HashMap）
2.二叉树（TreeMap）
Valid Anagram（异位词）
- 解法
1.快排（NlogN）
2.HashMap（2N）
3.26数组。s1对于下标+1，s2对于下标-1。num的值都为0，true，有一个不为0，false。（2N）
https://m.aliyun.com/yunqi/articles/26070
Two Sum
- 解决
1.冒泡（N2）
2.hashMap，加一次遍历。（N）注意元素可重复。
3Sum
-
解法
image.png
树、二叉树、二叉搜索树、图
image.png
Validate Binary Search Tree（验证二叉搜索树）
- 性质：节点的左子树只包含键小于节点键的节点。
节点的右子树只包含键大于节点键的节点。
左子树和右子树也必须是二进制搜索树。 - 解决
1.中序遍历
2.递归
Lowest Common Ancestor of a Binary Search Tree（二叉搜索树找公共祖先节点）
- 解法
递归
Lowest Common Ancestor of a Binary Tree（二叉树找公共祖先节点）
- 解法
递归
二叉树遍历
-
先根遍历、中根遍历、后跟遍历
image.png
递归、分治
pow(x, n)（数值的整数次方）
- 解法
1.暴力破解（N）
2.递归二分法（logN）
