thq_algo

golang算法

Leetcode真题

1. 两数之和
2. 链表相加
3. 无重复字符最长子串
4. 最长回文子串
5. 三数之和
6. 删除链表的倒数第 N 个结点
7. 有效的括号
8. 合并两个有序链表
9. 反转链表
10. 两两交换链表中的节点
11. 字母异位词分组
12. 最大子数组和
13. 螺旋矩阵
14. 跳跃游戏
15. 合并区间
16. 不同路径
17. 加一
18. 爬楼梯
19. 删除排序链表中的重复元素
20. 反转链表 II
21. 买卖股票的最佳时机
22. 买卖股票的最佳时机 II
23. 买卖股票的最佳时机 III
24. 加油站
25. 环形链表
26. 环形链表 II
27. 乘积最大子数组
28. 寻找旋转排序数组中的最小值
29. 相交链表
30. 按奇偶排序数组
31. 按奇偶排序数组 II
32. 奇偶链表
33. 水果成篮
34. 链表的中间结点
35. 比较含退格的字符串
36. 旋转字符串
37. 岛屿数量
38. 岛屿的最大面积
39. 甲板上的战舰
40. 验证回文字符串 Ⅱ
41. 链表两数相加 II
42. 移动零
43. 除自身以外数组的乘积

数据结构

二叉树

1. 前序遍历递归形式和非递归形式
2. 中序遍历递归形式和非递归形式
3. 后序遍历递归形式和非递归形式
4. DFS、BFS
5. 归并、快速排序

例题：

1. 给定一个二叉树，找出其最大深度。
2. 给定一个二叉树，判断它是否是高度平衡的二叉树。
3. 给定一个非空二叉树，返回其最大路径和。
4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
5. 给定一个二叉树，返回其节点值自底向上的层次遍历。
6. 给定一个二叉树，返回其节点值的锯齿形层次遍历。
7. 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
8. 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。
9. 二叉树的序列化与反序列化
10. 二叉树的序列化与反序列化
11. 填充每个节点的下一个右侧节点指针 I
12. 填充每个节点的下一个右侧节点指针 II
13. 从前序与中序遍历序列构造二叉树
14. 从中序与后序遍历序列构造二叉树

链表

例题：

1. 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次
2. 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
3. 反转一个单链表
4. 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
5. 将两个升序链表合并为一个新的升序链表并返回
6. 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前
7. 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
8. 给定一个单链表 L：L→L→…→L__n→L 将其重新排列后变为： L→L__n→L→L__n→L→L__n→…
9. 给定一个链表，判断链表中是否有环。
10. 给定一个链表，返回链表开始入环的第一个节点
11. 请判断一个链表是否为回文链表

算法思维

回溯法

1. 无重复数字数组所有子集
2. 有重复数字数组所有子集
3. 无重复数字数组全排列
4. 有重复数字数组全排列

递归

1. 反转字符串
2. 两两交换链表中的节点
3. 递归反转链表

二叉搜索树

1. 验证二叉搜索树
2. 二叉树插入
3. 二叉树删除
4. 判断是否是平衡二叉树

技巧细节注意

1. 切片[:]返回原切片,[:0]返回空切片
2. string遍历用for i:=0;i<len(str);i++ 遍历得到的是byte
3. 排序

   sort.Ints([]int{})
   // 字符串排序
   sort.Strings([]string{})
   // 自定义排序
   sort.Slice(s,func(i,j int)bool{return s[i]<s[j]})
   

4. 切片append扩容指针地址会变