lily's blog

Thinking will not overcome fear but action will.

贪心题况详情

摆动数列求摆动子序列的最大长度问题：摆动子序列：如何衡量是否摆动最大长度：如何遍历一遍找到最大长度解决思路：记录上两个数之间的差值，规定等于 i -（i+1），大于零则为上坡，小于零则为下坡，若能保持上下坡交替关系期间的子序列为摆动子序列。由此可以看出必须使用两个变量a， b 一个记录上一段坡度是否与当前坡度【相反】 ...

Posted by lily on April 7, 2023

算法题合集（简单收录）

不是主流思想里的解题角度和思路的合集 422 数组中重复的数字：时间复杂度O(n)，空间复杂度O(1)，仅使用常量额外空间的算法解决此问题。（输入输出的空间不算额外的空间，以列表或者其他任何形式存储的输出空间）要点：【用我查别人】假如没有重复的数字，那么由题意，每个数字都会对应唯一的下标（用数字作下标）；而现在有重复的数字，用数字做...

Posted by lily on April 7, 2023

树

树相关概念：节点的度：一个节点含有的子树的个数称为该节点的度；树的度：一棵树中，最大的节点度称为树的度；叶节点或终端节点：度为零的节点；非终端节点或分支节点：度不为零的节点；父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟...

Posted by lily on April 7, 2023

数据结构以及相关算法

主流的数据结构与必须要掌握的算法思想数据结构与算法简介程序 = “数据结构”+“算法” 数据结构是程序实现的工具算法是动态的存在于程序运行的过程数据结构表达了多种数据间的关系基本数据结构逻辑结构：线性结构、树、图物理结构：数据结构在实际代码中的实现刷题顺序参...

Posted by lily on April 7, 2023

排序查找算法

刷题顺序参考：数组——>链表——>哈希表——>字符串——>栈与队列——>树——>回溯——>贪心——>动态规划——>图论——>高级数据结构学习思维导图时间复杂度和空间复杂度时间复杂度概念：用于评估代码运行所需要时长的衡量单位 O(1),一段代码运行一个单位数量级 O(n),...

Posted by lily on April 7, 2023

排序查找算法

线性表的查找线性查找——linear search 按顺序依次往后查找二分查找——binary search 时间复杂度：每次查找，循环减半,时间复杂度为O（logn） ```python class Solution(object): def search(self, nums, target): left = 0 right = ...

Posted by lily on April 7, 2023

快速傅里叶变换FFT

以两个同次高阶多项式乘法为例两个多项式系数相乘Pe=[p0,p1…],Po=[p0,p1…]，时间复杂度为O(n^2) 为了降低时间复杂度，用n+1个点来表示n阶的多项式，那么只用对应点处函数值相乘，就可以得到结果多项式对应的点，时间复杂度降为O(n) 任一n阶的函数都可以凭借n+1个点来确定如何取点，如果我们取n个点，每个点都要计算函数值，其实又相...

Posted by lily on April 7, 2023

回溯算法

回溯的本质是穷举把要穷举的问题抽象为树形结构横向遍历（遍历遍及一维数组内所有数据）纵向遍历（纵向深度由递归深度控制）穷举模板枚举剪枝数据的共享和重复使用 “树枝剪枝” “树层剪枝” 组合问题（有无重复数据）、分割问题（按顺序分割) 回溯函数模板 ...

Posted by lily on April 7, 2023

动态规划

动态规划是什么？定义数组定义在我的理解来看，动态规划的定义强调的是当下此时的状态是由前一时刻的状态推导而来的，它不是由搜索所有的前置状态而去匹配适合的上一个状态（那是深搜/广搜），而是强调这一刻与上一刻的逻辑依赖关系。前置状态选择这一刻动规数组表达的是什么，取决于我们对它的自定义。上一刻是什么，该如何选择，到底是由什么推导而得到的此刻的状态？我看很多题目基本上都会将dp[i-...

Posted by lily on April 7, 2023

IDEA篇

Idea快捷键 | 快捷键组合 | 实现效果 | | — | — | | psvm + Tab键 / main + Tab键 | public static void main(String[] args) | | . +sout (点sout方法) | System.out.println() | | sout + Tab键/Enter键 | System.out.println() |...

Posted by lily on April 7, 2023