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就是当前需要的会议室的个数。

results matching ""

    No results matching ""