最长上升子队列 将问题看作有向无环图寻找最长的路径。每两个具有上升顺序的数字作为一条有向边，边权重设置为-1。将整个问题分解为从每个节点寻找最短路径（边权重为负）。每个节点的最短路径中最小值即位最长上升队列。复杂度O（$N^3$）。 以上方法是存在冗余的，一些节点的最短路径问题是另一些节点的子问题。 改进：按顺序计算以每个节点为结尾的最长子序列，并…

渐进算法 编写有效率的程序主要分为两个方面，一方面是编程花费：程序开发时间，易读性，易修改性以及易维护性。另一方面是程序执行花费包括时间复杂度和空间复杂度。 要比较算法的时间复杂度：只考虑最坏的情况，选择程序中最具有代表性的语句的时间，去掉低阶项和常数。大Θ表示法R（N）∈Θ（f(N)）;并且有k​1​​⋅f(N)≤R(N)≤k​2​​⋅f(N)；…

斐波那契数相关 结合动态规划分治、避免重叠子问题的思想来进行求解 剑指 Offer 10- I，II 两个问题都与斐波那契数列相关，以I为例，斐波那契数列可以通过递归实现，但要避免大量重复的运算，因此可以使用数组暂存。（自己写的就是丑陋了些） public static int fib(int n) { int[] res = new int[n+…

java基础 类：类的成员（方法和变量）。 静态语言与动态语言的区别。 类的实例化（对象） 实例变量,构造器（决定如何实例化类） 静态方法与非静态方法及其区别（调用） private、this关键词 对于变量对应的是变量的值，对象和数组对应的是内存位置的指针。 Java中使用变量必须实现声明；变量的定义和声明可以用一条语句实现。对于对象和数组需要进…

剑指 Offer 50. 第一个只出现一次的字符 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 首先通过字典（散列）将所以字符出现的频率保存。再用一个循环输出只出现一次的第一个字符 class Solution: def firstUniqChar(self, s: str) -> str: dict = {} fo…

剑指 Offer 53 - II. 0～n-1 中缺失的数字 找出递增数组中确实的数字； 思路：二分查找，看索引与值是否相等，即可找到缺失的数字；相比遍历的方法速度肯定会提升。虽然可以运行，但却难以通过测试。 class Solution: def missingNumber(self, nums) -> int: head = 0 tail…

剑指 Offer 03. 数组中重复的数字 数组长度为n，但数的范围在0到n-1。所以必定有重复。但直接遍历真的太憨憨了:sweat_smile:(是我没错了)。 使用哈希表的set()【集合】方法 set对象的每一个元素要求可进行哈希运算，set 会对内部元素进行去重，每个元素在同一个set 中只会出现一次; 字典可以将一个可哈希值映射到一个任意…

剑指 Offer 05. 替换空格 在 Python 和 Java 等语言中，字符串都被设计成「不可变」的类型，即无法直接修改字符串的某一位字符，需要新建一个字符串实现。 方法一：遍历 class Solution: def replaceSpace(self, s: str) -> str: if not s : return '…

剑指 Offer 06. 从尾到头打印链表 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reversePrint(self, head: List…

剑指offer09.用两个栈实现队列 不难，但自己对于python面向对象的掌握还有欠缺。中间也没有考虑周全。思路虽然有了，但编写代码的时候错误还蛮多的。 另外，特别要考虑到如过队列加入，删除再进入再删除情况下的情况。 class CQueue: def __init__(self): self.stack_1 = [] self.stack_2 …