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
158 Read N Characters Given Read4 II - Call multiple times
158.
Read N Characters Given Read4 II - Call multiple times
1. Question
The API:
int read4(char *buf)
reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the
read4
API, implement the function
int read(char *buf, int n)
that readsncharacters from the file.
Note:
The
read
function may be called multiple times.
2. Implementation
思路:
(1) 这题和157不同的是read4()可能被call很多次,这意味着之前call read4()会有一些数据保留在buffer里未读到。举个例子,比如输入数据是 s = "abcde", 第一次我们call read(s, 1), 我们只要读a,但里面read4()实际上读"abcd", bcd还在buffer未被读取。如果我们下一次call read4(s, 4), 我们要读取"bcde",要先把buffer之前保留的数据读取。
(2) 解决方法是用一个全局数组buffer[] 保留每次read4()返回的数据,同时bufferIndex记录buffer上次读到的位置, 只有当bufferIndex等于readBytes时,之前的buffer的数据才读完。
1
/* The read4 API is defined in the parent class Reader4.
2
int read4(char[] buf); */
3
4
public class Solution extends Reader4 {
5
/**
6
* @param buf Destination buffer
7
* @param n Maximum number of characters to read
8
* @return The number of characters read
9
*/
10
11
int bufferIndex = 0;
12
int readBytes = 0;
13
char[] buffer = new char[4];
14
15
public int read(char[] buf, int n) {
16
int index = 0;
17
18
while (index < n) {
19
if (bufferIndex < readBytes) {
20
buf[index++] = buffer[bufferIndex++];
21
}
22
else {
23
readBytes = read4(buffer);
24
bufferIndex = 0;
25
if (readBytes == 0) {
26
break;
27
}
28
}
29
}
30
return index;
31
}
32
}
Copied!
3. Time & Space Complexity
时间复杂度O(n), 空间复杂度O(1)
Previous
157 Read N Characters Given Read4
Next
681 Next Closest Time
Last modified
2yr ago
Copy link
Contents
158. Read N Characters Given Read4 II - Call multiple times
1. Question
2. Implementation
3. Time & Space Complexity