A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Google
665 Non-decreasing Array
400 Nth Digit
484 Find Permutation
353 Design Snake Game
348 Design Tic-Tac-Toe
657 Judge Route Circle
789 Escape The Ghosts
667 Beautiful Arrangement II
359 Logger Rate Limiter
463 Island Perimeter
66 Plus One
249 Group Shifted Strings
281 Zigzag Iterator
54 Spiral Matrix
56 Merge Intervals
57 Insert Interval
163 Missing Ranges
228 Summary Ranges
166 Fraction to Recurring Decimal
780 Reaching Points
326 Power of Three
318 Maximum Product of Word Lengths
314 Binary Tree Vertical Order Traversal
297 Serialize and Deserialize Binary Tree
447 Number of Boomerangs
362 Design Hit Counter
448 Find All Numbers Disappeared in an Array
409 Longest Palindrome
406 Queue Reconstruction by Height
370 Range Addition
415 Add Strings
498 Diagonal Traverse
482 License Key Formatting
560 Subarray Sum Equals K
356 Line Reflection
748 Shortest Completing Word
218 The Skyline Problem
391 Perfect Rectangle
481 Magical String
380 Insert Delete GetRandom O(1)
800 Similar RGB Color
246 Strobogrammatic Number
247 Strobogrammatic Number II
465 Optimal Account Balancing
687 Longest Univalue Path
543 Diameter of Binary Tree
777 Swap Adjacent in LR String
792 Number of Matching Subsequences
460 LFU Cache
779 K-th Symbol in Grammar
289 Game of Life
31 Next Permutation
756 Pyramid Transition Matrix
753 Cracking the Safe
330 Patching Array
327 Count of Range Sum
769 Max Chunks To Make Sorted
768 Max Chunks To Make Sorted II
309 Best Time to Buy and Sell Stock with Cooldown
393 UTF-8 Validation
388 Longest Absolute File Path
807 Max Increase to Keep City Skyline
802 Find Eventual Safe States
469 Convex Polygon
683 K Empty Slots
157 Read N Characters Given Read4
158 Read N Characters Given Read4 II - Call multiple times
681 Next Closest Time
317 Shortest Distance from All Buildings
587 Erect the Fence
307 Range Sum Query - Mutable
308 Range Sum Query 2D - Mutable
282 Expression Add Operators
616 Add Bold Tag in String
497 Random Point in Non-overlapping Rectangles
544 Output Contest Matches
386 Lexicographical Numbers
Powered By
GitBook
386 Lexicographical Numbers
386.
Lexicographical Numbers
1. Question
Given an integern, return 1 -nin lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
2. Implementation
(1) Recursion
思路: 可以将数字排列成一个如下树状的结构, 这题的本质就是对这个树做preorder traversal
1
1 2 3 ...
2
/\ /\ /\
3
10...19 20...29 30...39 ....
Copied!
1
class
Solution
{
2
public
List
<
Integer
>
lexicalOrder
(
int
n
)
{
3
List
<
Integer
>
res
=
new
ArrayList
();
4
5
for
(
int
i
=
1
;
i
<=
9
;
i
++
)
{
6
findLexicalOrder
(
i
,
n
,
res
);
7
}
8
return
res
;
9
}
10
11
public
void
findLexicalOrder
(
int
curNum
,
int
n
,
List
<
Integer
>
res
)
{
12
if
(
curNum
>
n
)
{
13
return
;
14
}
15
res
.
add
(
curNum
);
16
17
for
(
int
i
=
0
;
i
<=
9
;
i
++
)
{
18
findLexicalOrder
(
curNum
*
10
+
i
,
n
,
res
);
19
}
20
}
21
}
Copied!
(2) Iteration
思路: Iteration的方法同样是对树做preorder traversal,具体分成以下几个步骤:
往下 找到leftmost node
当我们找到leftmost node时,开始进行level order traversal, 比如10是树的leftmost node,则遍历10-19的数
当我们到达rightmost node的时候,我们需要返回上一层,然后对下一个树做preorder traversal
1
class
Solution
{
2
public
List
<
Integer
>
lexicalOrder
(
int
n
)
{
3
List
<
Integer
>
res
=
new
ArrayList
();
4
5
int
curNum
=
1
;
6
for
(
int
i
=
1
;
i
<=
n
;
i
++
)
{
7
res
.
add
(
curNum
);
8
// Case 1: Traverse down to find lestmost node
9
if
(
curNum
*
10
<=
n
)
{
10
curNum
*=
10
;
11
}
12
// Case 2: leftmost node found, do level traversal
13
else
if
(
curNum
%
10
!=
9
&&
curNum
+
1
<=
n
)
{
14
++
curNum
;
15
}
16
else
{
17
// Case 3.1: we are at the rightmost node,traverse up to upper level
18
while
((
curNum
/
10
)
%
10
==
9
)
{
19
curNum
/=
10
;
20
}
21
// Case 3.2: prepare to do traversal for the next tree
22
curNum
=
curNum
/
10
+
1
;
23
}
24
}
25
return
res
;
26
}
27
}
Copied!
3. Time & Space Complexity
(1) Recursion:
时间复杂度O(n), 空间复杂度O(n), 递归深度是最大数的digit个数,比如100的话,digit个数是3
(2) Iteration:
时间复杂度O(n), 空间复杂度O(n)
Previous
544 Output Contest Matches
Last modified
2yr ago
Copy link
Contents
386. Lexicographical Numbers
1. Question
2. Implementation
3. Time & Space Complexity