Part I: 192题
- Sort a string with a given priority.
- Find the average of the most recent N numbers. (O(1) time complexity)
- copy list with random pointer
Given a word and a dictionary, delete one letter from the word to form a new word, until there is only one letter. Check whether there exists such sequence in the dictionary.
For example:office->ofice->ofce->ofc->oc->c
.Design a "BigInteger". (using string for multiply, sum...)
What will happen after typing url.???
Given a string, find whether there exists a substring str that
stoi(str)%36 == 1
. Consider a very long string.Design a data structure representing a matrix that can be scale up without limitation.
Given a room, and equipments. Find the point that has the smallest distance to all the equipments.
leetcode 249: Group Shifted Strings
Solution
string toA(string s) {
int n = s.size();
string letter = "abcdefghijklmnopqrstuvwxyz";
string res = "";
if ( n == 0 ) return res;
int shift = s[0]-'a';
for ( int i = 0; i < n; i++ ) {
res += letter[(s[i]-'a'-shift+26)%26];
}
return res;
}
vector<vector<string> > GroupShiftedStrings(vector<string> strs) {
unordered_map<string, vector<string> > map;
int n = strs.size();
for ( int i = 0; i < n; i++ ) {
string key = toA(strs[i]);
map[key].push_back(strs[i]);
}
vector<vector<string> > res;
for ( auto it = map.begin(); it != map.end(); it++ ) res.push_back(it->second);
return res;
}
- Given a sorted array, containing number 1-N. Each number appears 3 times, now we delete a number. Use O(logN) time to return the deleted number.
Solution binary search
int deleteNumber(vector<int> nums) {
int n = nums.size();
int l = 0, r = n-1;
while ( nums[l] != nums[r] ) {
int nn = (r-l+2)/3;
int i = l + (nn/2)*3 -1;
int n1 = nums[l] + (nn/2) - 1;
if ( nums[i] == n1 ) l = i + 1;
else r = i - 1;
}
return nums[l];
}
- 关于meeting room的两个问题
def meetingRoomI(meetings):
meetings.sort()
last_end = -1
for i in meetings:
if ( i[0] < last_end ): return False
last_end = i[1]
return True
def meetingRoomII(meetings):
meetings.sort()
ending = []
nroom = 0
for i in meetings:
while ( len(ending) != 0 ):
tmp = heapq.heappop(ending)
if ( tmp > i[0] ):
heapq.heappush(ending, tmp)
break
heapq.heappush(ending, i[1])
nroom = max(nroom, len(ending))
return nroom
首先将meeting按照开始时间排序,然后逐个扫描。同时用一个heap管理结束时间,如果堆顶元素小于当前开始时间就pop,直至heap为空或者堆顶元素大于当前开始时间。然后将当前的meeting压入堆。此时堆的size就是当前需要的会议室的个数。