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
481 Magical String
481.
Magical String
1. Question
A magical string
S
consists of only '1' and '2' and obeys the following rules:
The string
S
is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string
S
itself.
The first few elements of string
S
is the following:
S
= "1221121221221121122……"
If we group the consecutive '1's and '2's in
S
, it will be:
1 22 11 2 1 22 1 22 11 2 11 22 ......
and the occurrences of '1's or '2's in each group are:
1 2 2 1 1 2 1 2 2 1 2 2 ......
You can see that the occurrence sequence above is the
S
itself.
Given an integer N as input, return the number of '1's in the first N number in the magical string
S
.
Note:
N will not exceed 100,000.
Example 1:
1
Input: 6
2
3
Output: 3
4
5
Explanation:
6
The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.
Copied!
2. Implementation
(1) Two Pointers
思路: 这道题的关键在于找到形成magical string的规律,这里的规律是从"122"中的第3位开始,,该位置上是数字2,先形成2个1,然后到第四位,该位置上是数字1,形成1个2,然后第5位,该位置上是1, 形成1个1,以此类推
1
class
Solution
{
2
public
int
magicalString
(
int
n
)
{
3
if
(
n
<=
0
)
{
4
return
0
;
5
}
6
7
if
(
n
<=
3
)
{
8
return
1
;
9
}
10
11
int
[]
sequence
=
new
int
[
n
+
1
];
12
sequence
[
0
]
=
1
;
13
sequence
[
1
]
=
2
;
14
sequence
[
2
]
=
2
;
15
int
head
=
2
,
tail
=
3
;
16
int
res
=
1
;
17
int
num
=
1
;
18
19
while
(
tail
<
n
)
{
20
for
(
int
i
=
0
;
i
<
sequence
[
head
];
i
++
)
{
21
sequence
[
tail
]
=
num
;
22
if
(
num
==
1
&&
tail
<
n
)
{
23
++
res
;
24
}
25
++
tail
;
26
}
27
num
^=
3
;
28
++
head
;
29
}
30
return
res
;
31
}
32
}
Copied!
3. Time & Space Complexity
Two Pointers:
时间复杂度O(n), 空间复杂度O(n)
Previous
391 Perfect Rectangle
Next
380 Insert Delete GetRandom O(1)
Last modified
2yr ago
Copy link
Contents
481. Magical String
1. Question
2. Implementation
3. Time & Space Complexity