143.重排链表 发表于 2020-10-20 | 分类于 算法 字数统计: 175 | 阅读时长 ≈ 1 题目描述 题解快慢指针 + 反转链表先通过快慢指针的方法找出链表的中间节点, 以此为边界把后半段链表反转, 然后交错插入前半段链表中 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 ... 阅读全文 »
977.有序数组的平方 发表于 2020-10-16 | 分类于 算法 字数统计: 164 | 阅读时长 ≈ 1 题目描述 题解系统自带排序法先将数组中每个元素平方, 然后通过Arrays.sort() 方法排序 12345678public int[] sortedSquares(int[] A) { for (int i = 0; i < A.length; i++) { ... 阅读全文 »
1002.查找常用字符 发表于 2020-10-14 | 分类于 算法 字数统计: 312 | 阅读时长 ≈ 1 题目描述 题解哈希表(数组代替)题目的意思就是字符串数组中每个字符串都出现过的字符取交集添加到列表中返回 例如所有字符串中都出现两个a, 那么结果列表中也要添加两个a 如果有一个字符串出现了一个a, 但是其他的字符串那种都是两个a, 那么列表中只能添加一个a 做法就是以第一个字符串为基础, 第一个 ... 阅读全文 »
85.最大矩形 发表于 2020-10-09 | 分类于 算法 字数统计: 373 | 阅读时长 ≈ 1 题目描述 题解单调栈这道题可以完美使用上一道题的方法. 上一道题的场景是柱状图的最大矩形, 这道题编程了二维数组. 如何将二维数组转化为柱状图的形式成了本题的关键. 遍历每一行的数组, 那么正在遍历的这一行与上面的所有行就可以当做是柱状图. 如果某位置字符是1, 往上有多少连续的1 就是该位置的高 ... 阅读全文 »
82.删除排序链表中的重复元素Ⅱ 发表于 2020-10-08 | 分类于 算法 字数统计: 160 | 阅读时长 ≈ 1 题目描述 题解双指针使用双指针, 左指针指向最左边的重复节点, 右指针指向最右边的重复节点, 然后将其整段删除, 这里要用到哨兵节点和前驱节点. 12345678910111213141516171819202122232425262728293031public ListNode deleteD ... 阅读全文 »
80.删除排序数组中的重复项Ⅱ 发表于 2020-10-07 | 分类于 算法 字数统计: 161 | 阅读时长 ≈ 1 题目描述 题解双指针一个指针负责向右遍历, 一个指针指向需要被修改的位置. 123456789101112131415public int removeDuplicates(int[] nums) { int len = nums.length; if (len<=2) ... 阅读全文 »
71.简化路径 发表于 2020-10-07 | 分类于 算法 字数统计: 114 | 阅读时长 ≈ 1 题目描述 题解栈使用栈来记录字符串中出现的有效目录, 如果遇到.., 就将栈顶的目录弹出 123456789101112131415161718192021222324public String simplifyPath(String path) { String[] strs = ... 阅读全文 »
834.树中距离之和 发表于 2020-10-07 | 分类于 算法 字数统计: 477 | 阅读时长 ≈ 2 题目描述 题解树形DP先考虑本题的一个简化情况, 求出一棵树中每个节点到其所有子节点的距离之和. 对于以u为根的子树, 它到树中所有节点的距离之和用dp[u]表示. 状态转移方程为:$$dp[u] = \sum_{v\in son[u]} dp[v] + sz[v]$$ 其中$son[u]$表示 ... 阅读全文 »
86.分隔链表 发表于 2020-09-30 | 分类于 算法 字数统计: 182 | 阅读时长 ≈ 1 题目描述 题解双指针因为题目要求要保留两个分区中每个节点的初始相对位置, 所以就不能采用类似快排的方式在遍历过程中将小于目标值的节点插入到前面. 我们定义两个链表, 一个保存小于目标值的节点, 一个保存大于等于目标值的节点. 然后将两个链表进行拼接 123456789101112131415 ... 阅读全文 »
701.二叉搜索树中的插入操作 发表于 2020-09-30 | 分类于 算法 字数统计: 158 | 阅读时长 ≈ 1 题目描述 题解DFS大致思路为将当前根节点的值与要插入的值比较, 如果要插入的值比根节点的值大, 那么要将值传递给右子树的根节点. 如果右子树为null, 那么直接new一个新的节点作为右儿子. 反之亦然 1234567891011121314151617181920212223class Solu ... 阅读全文 »