JasonGitHub

// Time: O(n) Space: O(1)
class Solution {
public:
  string intToRoman(int num) {
    assert(num >= 1 && num <= 3999);
    string ret;
    char roman[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
    int scale = 1000;
    for (int i = 6; i >= 0; i -= 2) {
      int digit = num / scale;

JasonGitHub

// Time: n * log(n) 
// Space: depend on sort() implementation (most recent sgi implementation use Introsort, which is Space: log(n))
bool IsAnagram(string s1, string s2) {
  sort(s1.begin(), s1.end());
  sort(s2.begin(), s2.end());
  return s1 == s2;
}

// Time: n
// Space: 256

JasonGitHub

//Time: n^2 Space: 0
void RemoveDuplicate(char* str) {
  char* tail = str;
  char* p1 = str;
  char* p2 = str;

  while (*p2 != '\0') {
    for (p1 = str; p1 < tail; ++p1) {
      if (*p2 == *p1) break;
    }

JasonGitHub

void ReverseString(char* str, int n) {
  char* end = str + n - 1;
  while (str < end) {
    swap(*str, *end);
    ++str;
    --end;
  }
}

JasonGitHub

// Time: n Space: n
bool HasUniqueChars(char* str, int n) {
  bitset<256> s;
  for (size_t i = 0; i < n; ++i) {
    int val = str[i];
    if (s[val]) return false;
    else s[val] = true;
  }
  return true;
}