Trie (Prefix Tree)
0 CommentsRef: http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/
我自己在刷题过程中也实现了一个, 可以参考leetcode 211 or lintcode 473
Ref: http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/
我自己在刷题过程中也实现了一个, 可以参考leetcode 211 or lintcode 473
There are a total of n courses you have to take, labeled from 0
to n - 1
.
Given a string, find the length of the longest substring T that contains at most k distinct characters.
Given a binary tree, find the length of the longest consecutive sequence path.
Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9
, ?
, :
, T
and F
(T
and F
represent True and False respectively).
Given an 2D board, count how many different battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Given a 2D grid, each cell is either a wall ‘W’, an enemy ‘E’ or empty ‘0’ (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.
Given a sequence of words, check whether it forms a valid word square.
|
|
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).
Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Given an array of integers, every element appears three times except for one. Find that single one.
There are two sorted arrays nums1
and nums2
of size m and n respectively.
Given an integer, write a function to determine if it is a power of three.
Calculate the sum of two integers a and b, but you are not allowed to use the operator +
and -
.
Given a string source and a string target, find the minimum window in source which will contain all the characters in target.
For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this node’s interval.
For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max
to denote the maximum number in the interval of the array (index from start to end).
The structure of Segment Tree is a binary tree which each node has two attributes start
and end
denote an segment / interval.
可以用来快速查询O(logn)数组一定区间内的最大值,最小值,和。存储结构可以用Tree,也可以用数组。这里提供一个从geeksforgeeks上找到的用数组的代码(略有调整)
Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )
Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.
Numbers keep coming, return the median of numbers at every time a new number added
Given N buildings in a x-axis,each building is a rectangle and can be represented by a triple (start, end, height),where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away,find the outline of them。
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.
Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)
Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)
Design a data structure that supports the following two operations: addWord(word)
and search(word)
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Given two integer arrays sorted in ascending order and an integer k. Define sum = a + b, where a is an element from the first array and b is an element from the second one. Find the kth smallest sum out of all possible sums.
Compare two strings A and B, determine whether A contains all of the characters in B.
Implement regular expression matching with support for ‘.’ and ‘*’.
Given an unsorted array of integers, find the length of longest increasing subsequence.
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
A message containing letters from A-Z is being encoded to numbers using the following mapping:
|
|
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.