刷题总结

ゝ一世哀愁。 2023-02-18 08:00 1阅读 0赞

数组、链表、跳表：

一般暴力可解决，优化思想一般有双指针、升维

1、数组

283 移动零

11 盛最多水的容器

70 爬楼梯

15 三数之和

2、链表

206 反转链表

24 两两交换链表中的节点

141 环形链表

142 环形链表II

25 K个一组翻转链表

3、其他

26 删除排序数组中的重复项

27 旋转数组

28 合并两个有序链表

30 两数之和

31 加一

栈：

具有最近相关性的问题，使用栈

队列：

具有先来后到特点的问题，使用队列

滑动窗口都使用队列

20 有效的括号

155 最小栈

84 柱状图中最大的矩形

239 滑动窗口最大值

641 设计循环双端队列

42 接雨水

哈希表、映射、集合

242 有效的字母异位词

49 字母异位词分组

1 两数之和

树、二叉树、二叉搜索树

树问题的解法都是递归

树的题目解法比较固定，要么深搜要么广搜

94 二叉树的中序遍历

144 二叉树的前序遍历

590 N叉树的后序遍历

589 N叉树的前序遍历

429 N叉树的层序遍历

递归

递归的基本思想为：1、找最近重复子问题；2、数学归纳法

递归的步骤为：1、递归终止条件；2、处理当层逻辑；3、跳到下一层；4、清理当前层

递归的代码模板：

public void recur(int level, int param) {
        //1、递归出口
        if (level > MAX_LEVEL) {
            //处理结果
            return;
        }
    
        //2、处理当前逻辑（参数发生变化）
        param = process(level, param);
    
        //3、进入下一层（缩小问题规模：子问题）
        recur(level+1, param);
    
        //4、逆处理（将参数回退到之前的状态）
        param = inverseProcess(level, param);
    }

相关题目：

70 爬楼梯

22 括号生成

226 翻转二叉树

98 验证二叉搜索树

104 二叉树的最大深度

其他：

111 二叉树的最小深度

297 二叉树的序列化与反序列化

236 二叉树的最近公共祖先

105 从前序与中序遍历序列构造二叉树

77 组合

46 全排列

47 全排列II

分治、回溯

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同

求出子问题的解，即可得到原问题的解。

简单问题可用二分法解决

50 Pow(x, n)

78 子集

169 多数元素

17 电话号码的字母组合

51 N皇后

深搜、广搜

1、深搜

1）递归写法

def dfs(node, visited):
        #终止
        if node in visited:
            return
    
        visited.add(node)
        ...
        for next_node in node.children():
            if not next_node in visited:
                dfs(next_node, visited)

2）可以用栈

2、广搜

BFS代码结构

def BFS(graph, start, end):
        queue = []
        queue.append([start])
        visited.add(start)
    
        while queue:
            node = queue.pop()
            visited.add(node)
    
            process(node)
            nodes = generate_related_nodes(node)
            queue.push(nodes)

102 二叉树的层序遍历

433 最小基因变化

22 括号生成

515 在每个树行中找最大值

其他：

127 单词接龙

126 单词接龙II

200 岛屿数量

529 扫雷游戏

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，不能回退

动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能

322 零钱兑换

860 柠檬水找零

122 买卖股票的最佳时机

455 分发饼干

874 模拟行走机器人

55 跳跃游戏

45 跳跃游戏II

二分查找

1、二分查找的前提

1）目标函数单调性

2）存在上下界

3）能够通过索引访问

2、代码模板

left, right = 0, len(array)-1
    while left <= right:
        mid = (left + right) / 2
        if array[mid] == target:
            # find the target
            break or return result
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

3、相关题目

69 x的平方根

367 有效的完全平方数

33 搜索旋转排序数组

74 搜索二维矩阵

153 妱旋转排序数组中的最小值

动态规划

1、关键点

动态规划和递归或者分治没有根本上的区别（关键看有无最优子结构）

共性：找到重复子问题

差异性：最优子结构、中途可以淘汰次优解

2、解题思路

1）最优子结构 opt\[n\] = best\_of(opt\[n-1\], opt\[n-2\], ...);

2）存储中间状态opt\[i\]

3）递推公式（状态转移方程或DP方程）

Fib：opt\[n-1\] + opt\[n-2\]

4）二维路径：opt\[i, j\] = opt\[i+1, j\] + opt\[i\]\[j+1\]（判断opt\[i, j\]是否空地）

3、相关题目

62 不同路径

63 不同路径II

1143 最长公共子序列

70 爬楼梯

120 三角形最小路径和

53 最大子序和

152 乘积最大子数组

63 不同路径II

322 零钱兑换

排序算法

其余不常见的

字典树、并查集、高级搜索、红黑树、AVL树、位运算、布隆过滤器、LRU缓存

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 sql刷题错误总结

![8ef9e95b826642a1b207ccc18791f7bb.png][] select from employees

太过爱你忘了你带给我的痛/ 2024年03月26日 15:06/ 0 赞/ 36 阅读

相关 PAT甲级刷题总结

树 LCA：1151 。[ ][Link 1] 转载于:https://www.cnblogs.com/yy-1046741080/p/11562339.ht

谁借莪１个温暖的怀抱￠/ 2023年08月17日 16:55/ 0 赞/ 37 阅读

相关刷题总结

数组、链表、跳表：一般暴力可解决，优化思想一般有双指针、升维 1、数组 283 移动零 11 盛最多水的容器 70 爬楼梯 15 三数之和 2、链表 2

ゝ一世哀愁。/ 2023年02月18日 08:00/ 0 赞/ 2 阅读

相关动态规划刷题总结

题目1：输出描述: 对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。输入例子: 2 7 89 256 7

逃离我推掉我的手/ 2022年09月24日 15:28/ 0 赞/ 199 阅读

相关 C++刷题知识点总结2

1.什么是异质链表？异质链表是指可以链表指针所指向的数据类型并不一致，比如一个链表中可以既存储整形数据，又可以存储浮点性的数据。在面向对象的语言中甚至就是可以指向不同的对

骑猪看日落/ 2022年04月23日 16:52/ 0 赞/ 207 阅读

相关 C++刷题知识点总结1

1.表达式1/4+2.75的值是3。请问这个说法是正确的吗？没有说明类型，假如是整型，则答案为2.若是浮点型，答案为3 2.strlen()计算字符数组的字符数，以"\

川长思鸟来/ 2022年02月24日 19:18/ 0 赞/ 313 阅读

相关 C++刷题知识点总结3

1. int p\[10\] p是一个数组含10个int元素 int (\p)\[10\] p是一个指针指向一个有10个int的数组 2.C++ Prime

淩亂°似流年/ 2022年02月23日 10:01/ 0 赞/ 223 阅读

相关 JavaScriptScript版《剑指Offer》刷题资源整理和JavaScript刷题总结

注意：资料来自网上，我会附上来源链接，我只是尝试总结下适合自己，方便自己查看 1.JavaScript版《剑指Offer》刷题资源牛客/博客园（非常推荐）： [htt

桃扇骨/ 2022年01月22日 23:45/ 0 赞/ 213 阅读

相关 9.17~9.18刷题总结

找到中序遍历二叉树下一个节点分析二叉树的下一个节点，一共有以下情况： 1.二叉树为空，则返回空； 2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着

绝地灬酷狼/ 2021年10月01日 12:26/ 0 赞/ 246 阅读

相关 9.19~9.20刷题总结

使二叉树变为其镜像类似先序遍历的方法 public void mirror(TreeNode node){ if(node==null)

小灰灰/ 2021年09月10日 07:58/ 0 赞/ 259 阅读