面试算法:有序链表转换为高度平衡的二叉搜索树
题目
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
0
/ \
...
2020-06-08 07:13:08 |
Algorithm
面试算法力扣96-二叉搜索树一共有多少种?
题目
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 ...
2020-06-08 07:13:08 |
Algorithm
leecode 126 127-Word Ladder II-backtracking 回溯算法 + 剪枝 BFS DFS
题目 127
word-ladder
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:
Ev...
2020-06-08 07:13:08 |
Algorithm
leecode 39 Combination Sum backtracking 回溯算法 + 剪枝
缘起
一个不会解的问题
https://leetcode.com/problems/combination-sum/
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集...
2020-06-08 07:13:08 |
Algorithm
leecode 详解 03-Manacher Algorithm 马拉车算法
Manacher’s Algorithm 马拉车算法。
马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性。
解决奇偶的问题
首先我们解决下奇数和偶数的问题,在每个字符间插入”#”,并且为了使得扩展的过程中,到边界后自动结束,在两端分别插入 ...
2020-06-08 07:13:08 |
Algorithm
【leetcode】力扣刷题技巧之结构化练习
⚙️ 一、基础理论与分析技巧
复杂度分析优先
实现算法前先分析时间/空间复杂度,避免无效优化。掌握常见复杂度类型(如 O(1)、O(logN)、O(NlogN))及其适用场景,例如二分法必须依赖有序性(O(logN)),而哈希表适合快速查找(O(1))。
优化时对比暴力解法(如冒泡排序 O(n²))与高效解法(快速排序 O(NlogN)),理解优化本质...
2020-06-08 07:13:08 |
Algorithm
【leetcode】力扣刷题技巧之对数器,如果没有OJ(在线判题系统)怎么办?如何保障本地代码的正确性
什么是对数器?
对数器,本质上是一种用于验证算法正确性的测试工具和调试方法。
它的核心思想是:
有一个你想测试的目标算法 A:这个算法通常是你新设计的、优化的、或者相对复杂、你对其正确性没有十足把握的算法(比如一个高效的排序算法、一个巧妙的动态规划解法)。
有一个绝对正确(但可能低效、简单、暴力)的算法 B:这个算法是作为“标杆”或“正确答案生成器”存在的。它的正确性很容易被...
2020-06-08 07:13:08 |
Algorithm
【leetcode】力扣刷题之时间复杂度介绍 Time Complexity
1. 核心概念:什么是时间复杂度?
定义: 时间复杂度衡量的是一个算法执行所需的时间如何随输入数据规模(通常用 n 表示)的增长而增长。它不是计算算法运行的具体秒数(这取决于硬件、编程语言、编译器优化等),而是描述运行时间随输入规模 n 变化的趋势。
目的:
比较算法优劣: 在解决同一问题时,不同算法可能有不同的时间效率。时间复杂度提供了一个理论框架来比较它...
2020-06-08 07:13:08 |
Algorithm