线段树(Segment Tree)是一种二叉搜索树,与区间树相似,他将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶子节点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为 O(logN)。而未优化的空间复杂度为 2N ,实际应用时一般还要开 4N 的数组以免越界,因此有时需要离散化让空间压缩。 —— 百度百科* 线段树可以使用一个堆来表示,存储在长度为 2N… 阅读全文
标签: LeetCode
树状数组 —— 一种支持单点修改和区间查找的数据结构
树状数组(英语:Binary Indexed Tree)又称为二元索引树,由 Fenwick 于 1994年发明,故又称为 Fenwick 树,其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和、区间和。它支持在 O(logn) 的时间复杂度内得到任意前缀和和区间和,同时支持在 O(logn) 的时间复杂度内动态修改单点的值,空间复… 阅读全文
[LeetCode每日一题]264. Ugly Number II
题目如下: Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 1… 阅读全文
[LeetCode每日一题]263. Ugly Number
题目如下: Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example 1: Input: 6 Output: true Explanation: 6 = 2… 阅读全文
[LeetCode每日一题]213. House Robber II
题目如下: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first hou… 阅读全文
[LeetCode每日一题]198. House Robber
题目如下: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent… 阅读全文
[LeetCode每日一题]140. Word Break II
题目如下: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such pos… 阅读全文
[LeetCode每日一题]139. Word Break
题目如下: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Exampl… 阅读全文
[LeetCode每日一题]95. Unique Binary Search Trees II
题目如下: Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 … n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3… 阅读全文
[LeetCode每日一题]96. Unique Binary Search Trees
题目如下: Given n, how many structurally unique BST's (binary search trees) that store values 1 … n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 … 阅读全文